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

---

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

В отличие от традиционного алгоритма умножения матриц (по формуле ${\displaystyle c_{ij}=\sum a_{ik}b_{kj}}$), работающего за время ${\displaystyle \Theta (n^{\log _{2}8})=\Theta (n^{3})}$, алгоритм Штрассена умножает матрицы за время ${\displaystyle \Theta (n^{\log _{2}7})=O(n^{2.81})}$, что даёт выигрыш на больших плотных матрицах.

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

Если добавить к матрицам ${\displaystyle A}$ и ${\displaystyle B}$ одинаковые нулевые строки и столбцы, их произведение станет равно матрице ${\displaystyle AB}$ с теми же добавленными строками и столбцами. Поэтому можно рассматривать только матрицы размера ${\displaystyle n=2^{k},\ k\in {\mathbb {N} }}$, а другие случаи сводить к этому добавлением нулей, отчего ${\displaystyle n}$ может увеличиться лишь вдвое.

---