Street algorithm

from Wikipedia, the free encyclopedia

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

The algorithm

To simplify matters, the special case of square matrices with rows or columns is considered.

So be matrices over a ring and also be their product . These can also be used as block matrices

consider where are.

The following applies to the multiplication of block matrices:

The direct calculation of the requires (complex) matrix multiplications. To reduce this number, Strassen's algorithm calculates the following auxiliary matrices:

Only multiplications are necessary to calculate the , which can now be determined by additions (and subtractions):

For the multiplications in the calculation of the above procedure is carried out recursively until the problem is reduced to the multiplication of scalars.

In practice, normal multiplication can be faster for small matrices. Therefore, a change to the usual multiplication instead of a recursive call makes sense as soon as the matrix dimensions are small enough (cut-off).

The left column represents a matrix multiplication . Every other column represents one of the multiplications of the Strassen algorithm.

effort

The standard algorithm for matrix multiplication is required

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

to reduce. The reduction in the number of multiplications, however, is paid for with a reduction in numerical stability .

literature

Web links

Individual evidence

  1. ^ Webb Miller: Computational complexity and numerical stability . (PDF) In: SIAM News . 4, 1975, pp. 97-107.