Partial and Total Matrix Multiplication
Author:
- A. SchönhageASA. Schönhage
- 1 August 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 10 (3) , 434-455
Abstract
In 1979 considerable progress was made in estimating the complexity of matrix multiplication. Here the new techniques and recent results are presented, based upon the notion of approximate rank and the observation that certain patterns of partial matrix multiplication (some of the entries of the matrices may be zero) can efficiently be utilized to perform multiplication of large total matrices. By combining Pan’s trilinear technique with a strong version of our compression theorem for the case of several disjoint matrix multiplications it is shown that multiplication of $N \times N$ matrices (over arbitrary fields) is possible in time $O(N^\beta )$, where $\beta $ is a bit smaller than $3\ln 52/\ln 110 \approx 2.522$.
Keywords
This publication has 8 references indexed in Scilit:
- New Fast Algorithms for Matrix OperationsSIAM Journal on Computing, 1980
- O(n2.7799) complexity for n × n approximate matrix multiplicationInformation Processing Letters, 1979
- Strassen's algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations1978
- On varieties of optimal algorithms for the computation of bilinear mappings II. optimal algorithms for 2 × 2-matrix multiplicationTheoretical Computer Science, 1978
- A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplicationsBulletin of the American Mathematical Society, 1976
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear FormsSIAM Journal on Computing, 1973
- On Minimizing the Number of Multiplications Necessary for Matrix MultiplicationSIAM Journal on Applied Mathematics, 1971
- Gaussian elimination is not optimalNumerische Mathematik, 1969