The definition of matrix multiplication says that for matrices and , the product is given by . Every component of is an inside product of a row of and a column of , so if this components is used then the price of forming is additions and multiplications, that’s, operations. For over a century after the event of matrix algebra within the 1850s by Cayley, Sylvester and others, all strategies for matrix multiplication had been primarily based on this components and required operations.
In 1969 Volker Strassen confirmed that when the product may be computed from the formulation
The analysis requires multiplications and additions as an alternative of multiplications and additions for the standard formulation.
At first sight, Strassen’s formulation might seem merely to be a curiosity. Nevertheless, the formulation don’t depend on commutativity so are legitimate when the and are matrices, by which case for big dimensions the saving of 1 multiplication tremendously outweighs the additional additions. Assuming is an influence of , we are able to partition and into 4 blocks of dimension , apply Strassen’s formulation for the multiplication, after which apply the identical formulation recursively on the half-sized matrix merchandise.
Allow us to look at the variety of multiplications for the recursive Strassen algorithm. Denote by the variety of scalar multiplications required to multiply two matrices. We’ve got , so
However . The variety of additions may be proven to be of the identical order of magnitude, so the algorithm requires operations.
Strassen’s work sparked curiosity to find matrix multiplication algorithms of even decrease complexity. Since there are components of knowledge, which should every take part in at the very least one operation, the exponent of within the operation depend have to be at the very least .
The present document higher certain on the exponent is , proved by Alman and Vassilevska Williams (2021) which improved on the earlier document of , proved by Le Gall (2014) The next determine plots the very best higher certain for the exponent for matrix multiplication over time.
Within the strategies that obtain exponents decrease than 2.775, numerous intricate methods are used, primarily based on representing matrix multiplication by way of bilinear or trilinear varieties and their illustration as tensors having low rank. Laderman, Pan, and Sha (1993) clarify that for these strategies “very giant overhead constants are hidden within the `‘ notation”, and that the strategies “enhance on Strassen’s (and even the classical) algorithm just for immense numbers .”
Strassen’s methodology, when rigorously applied, may be sooner than standard matrix multiplication for cheap dimensions. In apply, one doesn’t recur all the way down to matrices, however moderately makes use of standard multiplication as soon as matrices are reached, the place the parameter is tuned for the very best efficiency.
Strassen’s methodology has the downside that it satisfies a weaker type of rounding error certain that standard multiplication. For standard multiplication of and we now have the componentwise certain
the place and is the unit roundoff. For Strassen’s methodology we now have solely a normwise error certain. The next outcome makes use of the norm , which isn’t a constant norm.
Theorem 1 (Brent). Let , the place . Suppose that is computed by Strassen’s methodology and that is the brink at which standard multiplication is used. The computed product satisfies
With full recursion () the fixed in (2) is , whereas with only one stage of recursion () it’s . These evaluate with for standard multiplication (obtained by taking norms in (1)). So the fixed for Strassen’s methodology grows at a sooner price than that for standard multiplication it doesn’t matter what the selection of .
The truth that Strassen’s methodology doesn’t fulfill a componentwise error certain is a big weak point of the strategy. Certainly Strassen’s methodology can not even precisely multiply by the identification matrix. The product
is evaluated precisely in floating-point arithmetic by standard multiplication, however Strassen’s methodology computes
As a result of includes subterms of order unity, the error will likely be of order . Thus the relative error ,
One other weak point of Strassen’s methodology is that whereas the scaling , the place is diagonal, leaves (1) unchanged, it may well alter (2) by an arbitrary quantity. Dumitrescu (1998) suggests computing , the place the diagonal matrices and are chosen to equilibrate the rows of and the columns of within the -norm; he reveals that this scaling can enhance the accuracy of the outcome. Additional investigations alongside these strains are made by Ballard et al. (2016).
Ought to one use Strassen’s methodology in apply, assuming that an implementation is obtainable that’s sooner than standard multiplication? Not if one wants a componentwise error certain, which ensures correct merchandise of matrices with nonnegative entries and ensures that the column scaling of and row scaling of has no impact on the error. But when a normwise error certain with a sooner rising fixed than for standard multiplication is suitable then the strategy is price contemplating.
For current work on high-performance implementation of Strassen’s methodology see Huang et al. (2016, 2020).
Theorem 1 is from an unpublished technical report of Brent (1970). A proof may be present in Higham (2002, §23.2.2).
For extra on quick matrix multiplication see Bini (2014) and Higham (2002, Chapter 23).
It is a minimal set of references, which comprise additional helpful references inside.
- Josh Alman and Virginia Vassilevska Williams. A refined laser methodology and sooner matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Utilized Arithmetic, January 2021, pages 522–539.
- Gray Ballard, Austin R. Benson, Alex Druinsky, Benjamin Lipshitz, and Oded Schwartz. Enhancing the numerical stability of quick matrix multiplication. SIAM J. Matrix Anal. Appl, 37(4):1382–1418, 2016.
- Benson, Alex Druinsky, Benjamin Lipshitz, and Oded Schwartz. Enhancing the numerical stability of quick matrix multiplication. SIAM J. Matrix Anal. Appl., 37(4):1382–1418, 2016.
- Dario A. Bini. Quick matrix multiplication. In Handbook of Linear Algebra, Leslie Hogben, editor, second version, Chapman and Corridor/CRC, Boca Raton, FL, USA, 2014, pages 61.1–61.17.
- Bogdan Dumitrescu. Enhancing and estimating the accuracy of Strassen’s algorithm. Numer. Math., 79:485–499, 1998.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second version, Society for Industrial and Utilized Arithmetic, Philadelphia, PA, USA, 2002.
- Jianyu Huang, Tyler M. Smith, Greg M. Henry, and Robert A. van de Geijn. Strassen’s algorithm reloaded. In SC16: Worldwide Convention for Excessive Efficiency Computing, Networking, Storage and Evaluation, IEEE, November 2016.
- Jianyu Huang, Chenhan D. Yu, and Robert A. van de Geijn. Strassen’s algorithm reloaded on GPUs, ACM Trans. Math. Software program, 46(1):1:1–1:22, 2020.
- Julian Laderman, Victor Pan, and Xuan-He Sha. On sensible algorithms for accelerated matrix multiplication. Linear Algebra Appl., 162–164:557–588, 1992.
- François Le Gall. Powers of tensors and quick matrix multiplication. In Proceedings of the thirty ninth Worldwide Symposium on Symbolic and Algebraic Computation, 2014, pages 296–303.
This text is a part of the “What Is” sequence, out there from https://nhigham.com/class/what-is and in PDF kind from the GitHub repository https://github.com/higham/what-is.