Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication
| Title | Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication |
| Publication Type | Technical Report |
| Year of Publication | 1991 |
| Authors | Bürgisser, P., Karpinski M., & Lickteig T. Michael |
| Other Numbers | 635 |
| 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. |
| URL | http://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 |