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

Алгоритм Копперсмита—Винограда — алгоритм умножения квадратных матриц, предложенный в 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]

См. также

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

Примечания

1. Stothers, Andrew (2010), On the Complexity of Matrix Multiplication, Архивировано 29 августа 2017, Дата обращения: 28 мая 2017 Источник  (неопр.). Дата обращения: 28 мая 2017. Архивировано 29 августа 2017 года..
2. Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Архивная копия от 26 октября 2014 на Wayback Machine
3. «Even if someone manages to prove one of the conjectures—thereby demonstrating that ω = 2—the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. (…) the input matrices must be astronomically large for the difference in time to be apparent.»Le Gall, François (2014), "Powers of tensors and fast matrix multiplication", Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), arXiv:1401.7714
4. Quanta Magazine  (неопр.). Дата обращения: 21 августа 2022. Архивировано 17 августа 2022 года.

Литература

• 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.