Как быстро перемножать большие матрицы с помощью алгоритма Штрассена?

Алгоритм Штрассена позволяет быстро перемножать большие матрицы. 3 Он работает, сводя все матрицы к специальному, блочному виду. 3

Процесс перемножения: 4

1. Каждую из исходных матриц разбивают на четыре блока одинакового размера. 4
2. Вычисляют несколько вспомогательных матриц, для чего требуется только 7 умножений. 3
3. Из этих вспомогательных матриц с помощью сложений формируют итоговую матрицу. 3

Алгоритм Штрассена увеличивает скорость умножения матриц с n³ до n²⁸¹ мультипликативных шагов. 1 При достаточно больших значениях n (например, больше 500) этот алгоритм работает быстрее обычного алгоритма умножения. 5 Для разрежённых матриц он даёт больший эффект, чем для плотных. 5

Существуют модификации алгоритма Штрассена, например, алгоритм Винограда — Штрассена, для которого требуется 7 умножений и 15 сложений. 5