Strassen algorithm

The Strassen algorithm ( invented by German mathematician Volker Strassen ) is an algorithm in linear algebra and is used for matrix multiplication. The Strassen algorithm implements the matrix multiplication asymptotically more efficient than the standard method and is faster in practice for large matrices ( those with a rank greater than 1000).

The algorithm

For simplicity, we assume that two square matrices A, B over a ring R from. Furthermore, the A and B columns and row dimension n = 2 k, and C is the product of A and B.

Now one can consider A, B, C as block matrices:

Now, the following applies:

If we calculate with these formulas, so you need 8 (expensive) matrix multiplications. To reduce the number of multiplications, we can calculate the following Hilfsmatrizen:

To calculate the required one only 7 multiplications and now you can see the only additions ( and subtractions ) to calculate:

This idea is now used for the for the calculation of multiplications and iterating the whole until it multiplied only scalars.

In the practical implementation iterating usually only until the matrix dimension is so small that the standard algorithm for matrix multiplication is more efficient, and then uses this ( cut-off ).

Expenditure

The standard algorithm for matrix multiplication requires

Multiplications of the elements of the ring R. We ignore the required additions because, depending on R, in computer implementations can be much faster than multiplication. With the Strassen algorithm, we can increase the number of multiplications on

Reduce. Reducing the number of multiplications to be paid, however, by a reduction of the numerical stability.