Strassen algorithm

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Strassen’s algorithm is a way to multiply two large square matrices faster than the usual method. Introduced by Volker Strassen in 1969, it shows that the classic n by n matrix multiplication can be done in about n^2.81 operations instead of n^3, so for large matrices it can be noticeably faster.

How it works in simple terms
- The algorithm splits each matrix into four equal blocks (quarters). Instead of performing eight standard block multiplications like the naive approach, Strassen uses a clever arrangement to do only seven multiplications.
- After computing these seven products, it combines them to get the final product. This saves work overall, which is why the method has a better asymptotic growth than the traditional method.

What this means in practice
- Strassen’s method is most effective for large matrices. For smaller matrices, the extra additions and the way data must be moved around often outweigh the savings from fewer multiplications.
- The algorithm works over many mathematical settings (rings), but not all, especially some nonstandard ones. For those cases the naive method may still be the simplest and fastest.

Practical considerations and trade-offs
- Size requirements: In theory, the matrices are treated as powers of two. If they aren’t, you conceptually pad with zeros to fit the pattern, or adapt the method to non-power-of-two sizes. In real code, implementations try to avoid wasted work from padding.
- Extra memory and stability: Strassen needs extra memory for the intermediate products and additions. It can also be less numerically stable than the standard method, which can matter for some applications.
- Crossover point: There is a threshold where Strassen becomes faster than the usual multiplication, and this point depends on the hardware and the software. Early studies suggested benefits for sizes from a few dozen to a few hundred in some cases, while later work has found benefits at larger sizes (hundreds to thousands of rows/columns) and sometimes only modest gains.

Improvements and variants
- A well-known variant by Winograd reduces the number of additions required per step, while keeping seven multiplications.
- Modern refinements (in 2017 and 2023) have further cut the amount of extra work in certain steps, making the method faster in practice for more cases. These changes tweak the way the seven products are formed and combined, but still keep the seven-multiplication core.
- Despite these improvements, the fundamental trade-off remains: fewer multiplications but more additions and more complex data movement.

Impact and takeaway
Strassen’s algorithm showed that the straightforward n^3 approach to matrix multiplication isn’t the end of the story. It sparked a wave of research into faster matrix multiplication and new ways to balance arithmetic, memory, and numerical accuracy. Today, Strassen is used in some high-performance libraries for large dense matrices, but it’s not a universal replacement for the standard method. The best choice depends on matrix size, hardware, and the need for numerical stability.