↑ arvau

Wikipedia / Strassen algorithm

In linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication. It is faster than the standard matrix multiplication algorithm for large matrices, with a better asymptotic complexity), although the naive algorithm is often better for smaller matrices. The Strassen algorithm is slower than the fastest known algorithms for extremely large matrices, but such galactic algorithms are not useful in practice, as they are much slower for matrices of practical size. For small matrices, highly optimized implementations of the conventional algorithm are generally faster because Strassen's additional additions and recursion overhead outweigh its reduction in multiplications.

Strassen's algorithm works for any ring such as plus/multiply, but not all semirings, particularly combinatorial matrix multiplication such as min-plus or boolean algebra, where the naive algorithm still works.

History

Volker Strassen general matrix multiplication algorithm was not optimal. The Strassen algorithm's publication resulted in more research about matrix multiplication that led to both asymptotically lower bounds and improved computational upper bounds.

Algorithm

be two square matrices over a ring, the "missing" rows and columns can be filled with zeros to obtain matrices with sizes of powers of two — though real implementations of the algorithm do not do this in practice.

into equally sized block matrices

. The naive algorithm would be:

matrices, the same number of multiplications needed when using standard matrix multiplication.

The Strassen algorithm defines instead new values:

:

We recursively iterate this division process until the submatrices we really wanted.

Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations. However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less). A more recent study (2016) observed benefits for matrices as small as 512 and a benefit around 20%.

Improvements to Strassen algorithm

It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd in 1971:

.

This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.

The algorithm was further optimised in 2017 using an alternative basis, reducing the number of matrix additions per bilinear step to 12 while maintaining the number of matrix multiplications, and again in 2023:

Asymptotic complexity

addition or multiplication operations).

.

. The reduction in the number of arithmetic operations however comes at the price of a somewhat reduced numerical stability, and the algorithm also requires significantly more memory compared to the naive algorithm. Both initial matrices must have their dimensions expanded to the next power of 2, which results in storing up to four times as many elements, and the seven auxiliary matrices each contain a quarter of the elements in the expanded ones.

. The comparison of these two algorithms shows that asymptotically so that matrices that are larger are more efficiently multiplied with Strassen's algorithm than the "traditional" way. However, the asymptotic statement does not imply that Strassen's algorithm is always faster even for small matrices, and in practice this is in fact not the case: For small matrices, the cost of the additional additions of matrix blocks outweighs the savings in the number of multiplications. There are also other factors not captured by the analysis above, such as the difference in cost on today's hardware between loading data from memory onto processors vs. the cost of actually doing operations on this data. As a consequence of these sorts of considerations, Strassen's algorithm is typically only used on "large" matrices. This kind of effect is even more pronounced with alternative algorithms such as the one by Coppersmith and Winograd: While asymptotically is so large that the algorithm is not generally used on matrices one encounters in practice.

Rank or bilinear complexity

The bilinear complexity or rank of a bilinear map over a field F is defined as (somewhat of an abuse of notation)

In other words, the rank of a bilinear map is the length of its shortest bilinear computation. matrix multiplication is no more than seven. To see this, let us express this algorithm (alongside the standard algorithm) as such a bilinear computation. In the case of matrices, the dual spaces A* and B* consist of maps into the field F induced by a scalar double-dot product, (i.e. in this case the sum of all the entries of a Hadamard product.). One useful property of the rank is that it is submultiplicative for tensor products matrix multiplication map with itself -th tensor poweris realized by the recursive step in the algorithm shown.)

Cache behavior

Strassen's algorithm is cache oblivious. Analysis of its cache behavior algorithm has shown it to incur

).

Implementation considerations

The description above states that the matrices are square, and the size is a power of two, and that padding should be used if needed. This restriction allows the matrices to be split in half, recursively, until limit of scalar multiplication is reached. The restriction simplifies the explanation, and analysis of complexity, but is not actually necessary; and in fact, padding the matrix as described will increase the computation time and can easily eliminate the fairly narrow time savings obtained by using the method in the first place.

A good implementation will observe the following:

  • matrices and conventional multiplication can then be used at that level.

  • The method can indeed be applied to square matrices of any dimension..

, for instance:

  • operations, arranged to form the result;

  • operations, summed to form the result.

These techniques will make the implementation more complicated, compared to simply padding to a power-of-two square; however, it is a reasonable assumption that anyone undertaking an implementation of Strassen, rather than conventional multiplication, will place a higher priority on computational efficiency than on simplicity of the implementation.

, for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for a high-performance conventional multiplication.

See also

Karatsuba algorithm, for multiplying n time

  • A similar complex multiplication algorithm multiplies two complex numbers using 3 real multiplications instead of 4

  • Toom-Cook algorithm, a faster generalization of the Karatsuba algorithm that permits recursive divide-and-conquer decomposition into more than 2 blocks at a time

References