Алгоритм Штрассена – рекурсивный алгоритм, предназначенный для быстрого умножения матриц, соответствует идее разделяй и властвуй (т.е. основан на разбиении задачи на более мелкие подзадачи, решение которых потом объединяется для получения решения исходной задачи).
В отличие от традиционного алгоритма умножения матриц (по формуле ), имеющего сложность
, сложность алгоритма Штрассена:
, что даёт выигрыш на больших плотных матрицах.
Если добавить к матрицам и
одинаковые нулевые строки и столбцы, их произведение станет равно матрице
с теми же добавленными строками и столбцами. Поэтому можно рассматривать только матрицы размера
, а другие случаи сводить к этому добавлением нулей, отчего
может увеличиться лишь вдвое.
Пусть A, B – матрицы размера . Их можно представить как блочные матрицы (матрицы из 4-х блоков) размера (
) из (
)–матриц:
По принципу блочного умножения, матрица выражается через их произведение:
где в правой части происходит восемь умножений матриц размера .
Для получения итоговой матрицы Штрассен предложил следующий вариант с 7 умножениями и 18 сложениями:
где:
Алгоритм Штрассена:
Несмотря на то, что алгоритм Штрассена является асимптотически не самым быстрым из существующих алгоритмов быстрого умножения матриц, он проще программируется и эффективнее при умножении матриц относительно малого размера, поэтому именно он чаще используется на практике. Метод Штрассена становится быстрее наивного алгоритма, если .