Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication

TitleSome Computational Problems in Linear Algebra as Hard as Matrix Multiplication
Publication TypeTechnical Report
Year of Publication1991
AuthorsBürgisser P, Karpinski M, Lickteig TMichael
Other Numbers635
Abstract

We define the complexity of a computational problem given by a relation using the model of a computation tree with Ostrowski complexity measure. To a sequence of problems we assign an exponent similar as for matrix multiplication. For the complexity of the following computational problems in linear algebra:KER: Compute a basis of the kernel for a given n x n - matrix.OGB: Find an invertible matrix that transforms a given symmetric n x n - matrix (quadratic form) to diagonal form.SPR: Find a sparse representation of a given n x n - matrix.We prove relative lower bounds of the form ((a)(M subscript n)) - b and absolute lower bounds where (M subscript 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 omega of matrix multiplication.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-91-005.pdf
Bibliographic Notes

ICSI Technical Report TR-91-005

Abbreviated Authors

P. Buergisser, M. Karpinski, and T. Lickteig

ICSI Publication Type

Technical Report