WikiSort.ru - Не сортированное

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

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

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

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

См. также

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

Примечания

Литература

• 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", SIAM News Т. 38 (9), <http://www.siam.org/pdf/news/174.pdf>. Проверено 20 февраля 2009. .

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.