TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Inhalt des Dokuments

zur Navigation

Search for Publication

Suche nach Publikationen

All Publications

Some computational problems in linear algebra as hard as matrix multiplication
Zitatschlüssel BKL-Some-Computational-Problems-In-Linear-Algebra-As-Hard-As-Matrix-Multiplication
Autor Peter Bürgisser and Marek Karpinski and Thomas Lickteig
Seiten 131-155
Jahr 1991
DOI 10.1007/BF01272518
Journal Comp. Compl.
Jahrgang 1
Nummer 2
Zusammenfassung 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 given $n× n$ matrix, $OGB_n$: Find an invertible matrix that transforms a given symmetric $n× n$ matrix (quadratic form) into diagonal form, $SPR_n$: Find a sparse representation of a given $n× n$ matrix. To such a sequence of problems we assign an exponent similarly as for matrix multiplication. For the complexity of the above problems we prove relative lower bounds of the form $a M_n - b$ and absolute lower bounds $d n^2$, where $M_n$ denotes the complexity of matrix multiplication and $a$, $b$, $d$ are suitably chosen constants. We show that the exponents of the problem sequences KER, OGB, SPR are the same as the exponent of matrix multiplication.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe