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

Алгоритм Копперсміта — Вінограда (англ. Coppersmith–Winograd algorithm) — алгоритм для швидкого множення матриць. Алгоритм використовує ідеї, схожі з алгоритмом Штрассена. До 2010 року, алгоритм Копперсміта-Винограда був найбільш асимптотично швидким. Алгоритм названо на честь його розробників Дона Копперсміта і Шмуеля Вінограда.

Використовуючи цей алгоритм можна помножити дві матриці за одиниць часу[1]. Такий результат є кращим за наївний алгоритм () та алгоритм Штрассена (). Алгоритми зі швидшим асимптотичним часом роботи, ніж алгоритм Штрассена рідко використовується на практиці, оскільки їхні великі сталі числа, у швидкості їх обрахунків, роблять їх непрактичними[2]. Показник можна ще покращити, однак, показник не може бути меншим за 2 (бо матриця має значення і кожне з них повинне бути прочитане принаймні раз для обчислення точного результату).

У 2010 Ендрю Стосерс запропонував покращення алгоритму з асимптотичним часом [3][4]. У 2011 Вірджинія Вільямс скомбінувала виверт зі Стосерсової статті зі своїми ідеями і автоматизованою комп'ютерною оптимізацією пропонуючи асимптотично швидший алгоритм ()[5]. У 2014 році Франсуа Ле Ґалл спростив метод Вільямс і отримав краще асимптотичне наближення [6].

Алгоритм Копперсміта — Вінограда часто використовується як основа для інших алгоритмів, щоб довести теоретичні межі швидкості обрахунків. Проте, на відміну від алгоритму Штрассена, він не використовується на практиці, оскільки він забезпечує перевагу лише для матриць настільки великих, що вони не можуть бути оброблені сучасним обладнанням[7].

Генрі Кон, Роберт Клейнберг, Балаж Щеґеди і Кріс Уманс повторно вивели алгоритм Копперсміта — Вінограда, використовуючи теоретико-груповий підхід. Вони також показали, що кожен з двох підходів передбачає, що оптимальним показником для алгоритму множення матриць є 2, як давно підозрювали у наукових колах. Тим не менш, вони не змогли сформулювати конкретний розв'язок, що привів би до кращого часу обчислення, ніж алгоритм Копперсміта — Вінограда[8].

Див. такожРедагувати

ДжерелаРедагувати

  1. Coppersmith, Don; Winograd, Shmuel (1990). Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation 9 (3): 251. doi:10.1016/S0747-7171(08)80013-2.  (англ.)
  2. Le Gall, F. (2012). Faster algorithms for rectangular matrix multiplication. Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012). с. 514–523. arXiv:1204.1111. doi:10.1109/FOCS.2012.80.  (англ.)
  3. Stothers, Andrew (2010). On the Complexity of Matrix Multiplication. Архів оригіналу за 15 грудень 2011. Процитовано 2 листопад 2015.  (англ.)
  4. Davie, A.M.; Stothers, A.J. (2013). Improved bound for complexity of matrix multiplication. Proceedings of the Royal Society of Edinburgh 143A: 351–370. doi:10.1017/S0308210511001648.  (англ.)
  5. Williams, Virginia (2011). Breaking the Coppersmith-Winograd barrier.  (англ.)
  6. 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.  (англ.)
  7. Robinson, Sara (2005). Toward an Optimal Algorithm for Matrix Multiplication. SIAM News 38 (9). Архів оригіналу за 31 березень 2010. Процитовано 2 листопад 2015.  (англ.)
  8. Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C. (2005). Group-theoretic Algorithms for Matrix Multiplication. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). с. 379. ISBN 0-7695-2468-0. doi:10.1109/SFCS.2005.39.  (англ.)