The usual number of scalar operations (i.e., the total number of additions and multiplications) required to
perform Matrix Multiplication is
(1) |
(2) |
(3) | |||
(4) |
(5) |
Two matrices can therefore be multiplied
(6) |
(7) |
(8) |
(9) | |||
(10) | |||
(11) | |||
(12) | |||
(13) | |||
(14) | |||
(15) |
(16) | |||
(17) | |||
(18) | |||
(19) |
Matrix inversion of a matrix
to yield
can also be done in fewer operations
than expected using the formulas
(20) | |||
(21) | |||
(22) | |||
(23) | |||
(24) | |||
(25) | |||
(26) | |||
(27) | |||
(28) | |||
(29) | |||
(30) |
See also Complex Multiplication, Karatsuba Multiplication
References
Coppersmith, D. and Winograd, S. ``Matrix Multiplication via Arithmetic Programming.'' J. Symb. Comput. 9, 251-280, 1990.
Pan, V. How to Multiply Matrices Faster. New York: Springer-Verlag, 1982.
Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Is Matrix Inversion an Process?''
§2.11 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed.
Cambridge, England: Cambridge University Press, pp. 95-98, 1989.
Strassen, V. ``Gaussian Elimination is Not Optimal.'' Numerische Mathematik 13, 354-356, 1969.
© 1996-9 Eric W. Weisstein