Publication Details
Title: Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication
Author: P. Buergisser, M. Karpinski, and T. Lickteig
Group: ICSI Technical Reports
Date: January 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-005.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-91-005
Bibliographic Reference:
P. Buergisser, M. Karpinski, and T. Lickteig. Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication. ICSI Technical Report TR-91-005, January 1991
Author: P. Buergisser, M. Karpinski, and T. Lickteig
Group: ICSI Technical Reports
Date: January 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-005.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-91-005
Bibliographic Reference:
P. Buergisser, M. Karpinski, and T. Lickteig. Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication. ICSI Technical Report TR-91-005, January 1991