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

Матеріал з Вікіпедії - вільної енциклопедії

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

На практиці алгоритм Копперсміта-Винограду не використовується, так як він має дуже велику константу пропорційності і починає вигравати у швидкодії у інших відомих алгоритмів тільки для матриць, розмір яких перевищує пам'ять сучасних комп'ютерів.

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