Алгоритм Копперсмита — Винограда
Алгоритм
Копперсмита — Винограда, самый асимптотически быстрый из всех
известных алгоритмов умножения
квадратных матриц. Алгоритм
требует O(n2,376) операций, где n —
размер стороны матрицы. Предложен в
1987 году. Однако, на практике для быстрого
умножения матриц обычно пользуются алгоритмом
Штрассена с O(n2,807)операциями.
А.К.-В. в
реальных программах не используется,
так как он имеет гораздо большую константу
пропорциональности. Поэтому он будет
выгодным только для тех матриц, размер
которых превышает память современных
компьютеров.
Лит.: 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.