Алгоритм Штрассена

Использование правил блочного произведения матриц позволяет уменьшить общее количество операций, а значит, и время выполнения работы программы. Допустим, требуется умножить квадратные матрицы A и B порядка . При перемножении матриц, по формулам, приведённым в определении произведения, потребуется умножений и сложений. Разобьём матрицы A и B на блоки порядка n. Вычисление произведения блочных матриц проведём по формулам Штрассена

1. потребуется умножений и сложений
2. потребуется умножений и сложений
3. потребуется умножений и сложений
4. потребуется умножений и сложений
5. потребуется умножений и сложений
6. потребуется умножений и сложений
7. потребуется умножений и сложений
8. потребуется сложений
9. потребуется сложений
10. потребуется сложений
11. потребуется сложений.

Всего, для вычисления произведения матриц по формулам Штрассена, потребуется операций сложения и умножения. При выполнении неравенства (n>7) формулы Штрассена приводят к меньшему объёму вычислений. Выигрыш в числе операций будет увеличиваться, если при вычислении произведения матриц (шаги1-7) использовать ту же схему.

Обозначим через число операций сложения и умножения, используемых при умножении матриц n -го порядка по формулам Штрассена. Справедлива рекуррентная формула . Положим . Тогда , далее, свернём сумму по формуле суммы членов геометрической прогрессии и заметим. В результате получим . Подставив вместо k его выражение через n () получим ().