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

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

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

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

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

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

См. также

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

Литература

• Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arXiv:math.GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379—388.
• Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.
• Robinson, Sara (2005), "Toward an Optimal Algorithm for Matrix Multiplication" (PDF), SIAM News, 38 (9), Дата обращения: 20 февраля 2009 Архивная копия от 31 марта 2010 на Wayback Machine.