93d:68030 68Q25 68Q40
Bürgisser, Peter(D-BONN-C); Karpi\'nski, Marek(D-BONN-C); Lickteig, Thomas(D-TBNG)
Some computational problems in linear algebra as hard as matrix multiplication. (English)
Comput. Complexity 1 (1991), no. 2, 131--155.

Lower bounds on the complexity of several problems in linear algebra are given in terms of the complexity of matrix multiplication. The Ostrowsky complexity measure and the computation tree model are used. Roughly speaking, the complexity $C(f)$ of a problem $f$ is the minimum number of multiplications and divisions sufficient to compute $f$ for any input data.

The following problems are considered over a field $F$ of characteristic zero or an ordered field. (1) Compression: given $n\times n$ matrices $A\sb 1,A\sb 2,A\sb 3$, compute matrices $B\sb 1,B\sb 2$ such that $A\sb 1A\sb 2A\sb 3=B\sb 1B\sb 2$. (2) Kernel: given an $n\times n$ matrix $A$ compute an $n\times m$ matrix $B$ such that $AB=O$ and $m=n-{\rm rank}(A)$. (3) Orthogonal basis: given a symmetric matrix $A$, compute a nonsingular matrix $S$ such that $SAS\sp {\ssf T}$ is diagonal. (4) Sparse representation: given an $n\times n$ matrix $A$, compute matrices $S,T,B$ such that $S$ and $T$ are nonsingular, $B=SAT$ and $B$ is a sparse matrix, i.e., $\vert {\rm supp}(B)\vert \leq cn$, where $c$ is a constant. (5) Sparse representation 1: given an $n\times n$ matrix $A$, compute the matrices $S,T$ defined in Problem 4. Problem 2 consists in computing a basis of the kernel of a square matrix, Problem 3 consists in reducing a quadratic form to diagonal form, and Problems 4 and 5 include classical matrix factorizations such as $LU$ and $QR$.

Let $M\sb n$ denote the complexity and $\omega={\rm inf}\{\tau\in\bold R\colon M\sb n=O(n\sp \tau)\}$ the exponent of $n\times n$ matrix multiplication. It is proved that relative lower bounds of the form $aM\sb n-b$ and an absolute lower bound $dn\sp 2$ hold for the complexities of Problems 1--4, where $a$, $b$ and $d$ are suitable constants. Moreover, similarly as for matrix multiplication, to each of Problems 1--5, an exponent $\omega\sb i$, $i=1,2,3,4,5$, is assigned. It is proved that $\omega\sb i=\omega$ for $i=1,2,3,4,5$.

The lower bounds are proved by using differential methods, in particular the derivation theorem of Baur-Strassen. The proof of the upper bounds is sketched.

Copyright American Mathematical Society 1993, 1997

Back