Some computational problems in linear algebra as hard as matrix multiplication |
| |
Authors: | Peter Bürgisser Marek Karpinski Thomas Lickteig |
| |
Affiliation: | 1. Institut für Informatik, Universit?t Bonn, D-5300, Bonn 1 2. International Computer Science Institute, 94704, Berkeley, CA 3. Fachbereich Mathematik, Universit?t Tübingen, D-7400, Tübingen
|
| |
Abstract: | We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are: KER n : Compute a basis of the kernel for a givenn×n-matrix, OGB n : Find an invertible matrix that transforms a given symmetricn×n-matrix (quadratic form) into diagonal form, SPR n : Find a sparse representation of a givenn×n-matrix. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|