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.
Notes
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).
References
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.