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

Алгоритм Штрассена предназначен для быстрого умножения матриц. Он был разработан Фолькером Штрассеном в 1969 году и является обобщениемметода умножения Карацубы на матрицы. В отличие от традиционного алгоритма умножения матриц (по формуле ), работающего за время , алгоритм Штрассена умножает матрицы за время , что даёт выигрыш на больших плотных матрицах. Несмотря на то, что алгоритм Штрассена является асимптотически не самым быстрым из существующих алгоритмов быстрого умножения матриц, он проще программируется и эффективнее при умножении матриц относительно малого размера, поэтому именно он чаще используется на практике.