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

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

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

См. также

• Алгоритм Штрассена
• Гипотеза Штрассена

Литература

• Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arΧiv: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> .