Алгоритм Копперсмита — Винограда

Алгоритм Копперсмита—Винограда — алгоритм умножения квадратных матриц, предложенный в 1987 году Д. Копперсмитом и Ш. Виноградом^[англ.]. В исходной версии асимптотическая сложность алгоритма составляла ${\displaystyle O(n^{2.3755})}$, где ${\displaystyle n}$ — размер стороны матрицы. Алгоритм Копперсмита—Винограда, с учетом серии улучшений и доработок в последующие годы, обладает лучшей асимптотикой среди известных алгоритмов умножения матриц.

На практике алгоритм Копперсмита—Винограда не используется, так как он имеет очень большую константу пропорциональности и начинает выигрывать в быстродействии у других известных алгоритмов только для матриц, размер которых превышает память современных компьютеров.

Улучшения алгоритма

История улучшения оценок показателя степени ω для вычислительной сложности матричного умножения ${\displaystyle O(n^{\omega })}$.

• В 2010 Эндрю Стотерс усовершенствовал алгоритм до ${\displaystyle O(n^{2.374}).}$^[1]
• В 2011 году Вирджиния Вильямс^[англ.] усовершенствовала алгоритм до ${\displaystyle O(n^{2.3728642}).}$^[2]
• В 2014 году Франсуа Ле Галль упростил метод Вильямс и получил новую оценку ${\displaystyle O(n^{2.3728639}).}$^[3]
• В 2020 году Джош Алман и Вирджиния Вильямс улучшили метод снова, достигнув оценки ${\displaystyle O(n^{2.3728596}).}$^[4]

См. также

• Алгоритм Штрассена
• Гипотеза Штрассена
• Открытые математические проблемы — определить точную нижнюю границу сложности алгоритма умножения матриц.