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 algorithms are not useful in practice, as they are much slower for matrices of practical size. Strassen's algorithm works for any ring, such as plus/multiply, but not all semirings, such as min-plus or boolean algebra, where  the naive algorithm still works, and so called combinatorial matrix multiplication. History. Volker Strassen first published this algorithm in 1969 and proved that the formula_1 general matrix multiplication algorithm wasn't optimal. The Strassen algorithm is only slightly better than that, but its publication resulted in much more research about matrix multiplication that led to faster approaches, such as the Coppersmith–Winograd algorithm. Algorithm. Let formula_2, formula_3 be two square matrices over a ring formula_4, for example matrices whose entries are integers or the real numbers. We want to calculate the matrix product formula_5. In the following exposition of the  algorithm, we will assume that all of these matrices have sizes that are powers of two (i.e., formula_6), but this is only conceptually necessary -- if the matrices formula_2, formula_3 are not of type formula_9 we can think conceptually about filling the "missing" rows and columns with zeros to obtain matrices with sizes of powers of two -- though real implementations of the algorithm will of course not actually do this in practice. We then partition formula_2, formula_3 and formula_12 into equally sized block matrices with formula_14. The naive algorithm would be: With this construction we have not reduced the number of  multiplications. We still need 8 multiplications of matrix blocks to calculate the formula_16 matrices, the same number of multiplications we need when using standard matrix multiplication. The Strassen algorithm defines instead new matrices: only using 7 multiplications (one for each formula_18) instead of 8. We may now express the formula_16 in terms of formula_18: We recursively iterate this division process until the submatrices degenerate into numbers (elements of the ring formula_4). If, as mentioned above, the original matrix had a size that was not a power of 2, then the resulting product will have zero rows and columns just like  formula_2 and formula_3, and these will then be stripped at this point to obtain the (smaller) matrix formula_12 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%. Asymptotic complexity. The outline of the algorithm above showed that one can get away with just 7, instead of the traditional 8, matrix-matrix multiplications for the sub -blocks of the matrix. On the other hand, one has to do additions and subtractions of blocks, though this is of no concern for the overall complexity: Adding matrices of size formula_26 requires only formula_27 operations whereas multiplication is substantially more expensive (traditionally formula_28 addition or multiplication operations). The question then is how many operations exactly one needs for Strassen's algorithms, and how this compares with the standard matrix multiplication that takes approximately formula_29 (where formula_30) arithmetic operations, i.e. an asymptotic complexity formula_31. The number of additions and multiplications required in the Strassen algorithm can be calculated as follows : let formula_32 be the number of operations for a formula_9 matrix. Then by recursive application of the Strassen algorithm, we see that formula_34, for some constant formula_35 that depends on the number of additions performed at each application of the algorithm. Hence formula_36, i.e., the asymptotic complexity for multiplying matrices of size formula_30 using the Strassen algorithm is formula_38. 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. Strassen's algorithm needs to be compared to the "naive" way of doing the matrix multiplication that would require 8 instead of 7 multiplications of sub-blocks. This would then give rise to the complexity one expects from the standard approach: formula_39. The comparison of these two algorithms shows that "asymptotically", Strassen's algorithm is faster: There exists a size formula_40 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" even faster, the cross-over point formula_40 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 is an important concept in the asymptotic complexity of matrix multiplication. The rank of a bilinear map formula_42 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. The existence of Strassen's algorithm shows that the rank of formula_44 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.) It can be shown that  the total number of elementary multiplications formula_45 required for matrix multiplication is tightly asymptotically bound to the rank formula_46, i.e. formula_47, or more specifically, since the constants are known, formula_48. One useful property of the rank is that it is submultiplicative for tensor products, and this enables one to show that formula_49 matrix multiplication can be accomplished with no more than formula_50 elementary multiplications for any formula_51. (This formula_51-fold tensor product of the formula_53 matrix multiplication map with itself — an formula_51-th tensor power—is 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 cache misses during its execution, assuming an idealized cache of size formula_56 (i.e. with formula_57 lines of length formula_58). 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: Furthermore, there is no need for the matrices to be square. Non-square matrices can be split in half using the same methods, yielding smaller non-square matrices. If the matrices are sufficiently non-square it will be worthwhile reducing the initial operation to more square products, using simple methods which are essentially formula_59, for instance: 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. In practice, Strassen's algorithm can be implemented to attain better performance than conventional multiplication even for small matrices, for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for a high-performance conventional multiplication.