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 even faster algorithms exist. 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 thereby proved that the general matrix multiplication algorithm wasn't 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 Let , be two square matrices over a ring , for example matrices whose entries are integers or the real numbers. The goal of matrix multiplication is to calculate the matrix product . The following exposition of the algorithm assumes that all of these matrices have sizes that are powers of two (i.e., ), but this is only conceptually necessary -- if the matrices , are not of type , 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. The Strassen algorithm partitions , and into equally sized block matrices with . The naive algorithm would be: This construction does not reduce the number of multiplications: 8 multiplications of matrix blocks are still needed to calculate the matrices, the same number of multiplications needed when using standard matrix multiplication. The Strassen algorithm defines instead new matrices: using only 7 multiplications (one for each ) instead of 8. We may now express the in terms of : We recursively iterate this division process until the submatrices degenerate into numbers (elements of the ring ). 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 and , and these will then be stripped at this point to obtain the (smaller) matrix we