Partial and Total Matrix Multiplication
Arnold Schönhage · SIAM Journal on Computing · 1981
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$.
Cited by 259 works. doi:10.1137/0210032
Authors
References
- Gaussian elimination is not optimal
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
- Strassen's algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations
- On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
- O(n2.7799) complexity for n × n approximate matrix multiplication
- A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
- New Fast Algorithms for Matrix Operations
- On varieties of optimal algorithms for the computation of bilinear mappings II. optimal algorithms for 2 × 2-matrix multiplication