TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Page Content

to Navigation

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

Some computational problems in linear algebra as hard as matrix multiplication
Citation key BKL-Some-Computational-Problems-In-Linear-Algebra-As-Hard-As-Matrix-Multiplication
Author Peter Bürgisser and Marek Karpinski and Thomas Lickteig
Pages 131-155
Year 1991
DOI 10.1007/BF01272518
Journal Comp. Compl.
Volume 1
Number 2
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 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 to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe