29. Алгоритм Штрассена, сложность метода Штрассена.

Алгоритм Штрассена – рекурсивный алгоритм, предназначенный для быстрого умножения матриц, соответствует идее разделяй и властвуй (т.е. основан на разбиении задачи на более мелкие подзадачи, решение которых потом объединяется для получения решения исходной задачи).

В отличие от традиционного алгоритма умножения матриц (по формуле ), имеющего сложность , сложность алгоритма Штрассена: , что даёт выигрыш на больших плотных матрицах.

Если добавить к матрицам  и  одинаковые нулевые строки и столбцы, их произведение станет равно матрице  с теми же добавленными строками и столбцами. Поэтому можно рассматривать только матрицы размера , а другие случаи сводить к этому добавлением нулей, отчего  может увеличиться лишь вдвое.

Пусть A, B – матрицы размера . Их можно представить как блочные матрицы (матрицы из 4-х блоков) размера () из ()–матриц:

По принципу блочного умножения, матрица  выражается через их произведение:

где в правой части происходит восемь умножений матриц размера .

Для получения итоговой матрицы Штрассен предложил следующий вариант с 7 умножениями и 18 сложениями:

где:

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

  1. Разбиваем матрицы  и   размера  на 4 блока размера .
  2. Вычисляем произведения по указанным выше формулам рекурсивно.

Несмотря на то, что алгоритм Штрассена является асимптотически не самым быстрым из существующих алгоритмов быстрого умножения матриц, он проще программируется и эффективнее при умножении матриц относительно малого размера, поэтому именно он чаще используется на практике. Метод Штрассена становится быстрее наивного алгоритма, если .