Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1991 Copyright 1991 University of Bonn, Department of Computer Science, Abt. V
8561

Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication
Peter Buergnisser, Marek Karpinski, Thomas Lickteig
[Download PostScript] [Download PDF]

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 \begin{itemize} \item $KER_n$: Compute a basis of the kernel for a given $n \times n$--matrix. \item $OGB_n$: Find an invertible matrix that transforms a given symmetric $n \times n$--matrix to diagonal form. \item $SPR_n$: Find a sparse representation of a given $n \times n$--matrix. \end{itemize} we prove relative lower bounds of the form $aM_n - b$ and absolute lower bounds $dn^2$, where $M_n$ denotes the complexity of matrix multiplication and $a,b,d$ are suitably chosen constants. We show that the exponent of the problem sequences $KER,\;OGB,\;SPR$ is the same as the exponent $\omega$ of matrix multiplication.

Last Change: 08/18/99 at 13:00:38
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V