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

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

Використовуючи цей алгоритм можна помножити дві матриці ${\displaystyle n\times n}$ за ${\displaystyle O(n^{2.375477})}$ одиниць часу. Такий результат є кращим за наївний алгоритм (${\displaystyle O(n^{3})}$) та алгоритм Штрассена (${\displaystyle O(n^{2.807355})}$). Алгоритми зі швидшим асимптотичним часом роботи, ніж алгоритм Штрассена рідко використовується на практиці, оскільки їхні великі сталі числа, у швидкості їх обрахунків, роблять їх непрактичними. Показник можна ще покращити, однак, показник не може бути меншим за 2 (бо ${\displaystyle n\times n}$ матриця має ${\displaystyle n^{2}}$ значення і кожне з них повинне бути прочитане принаймні раз для обчислення точного результату).

У 2010 Ендрю Стосерс запропонував покращення алгоритму з асимптотичним часом ${\displaystyle O(n^{2.374})}$. У 2011 Вірджинія Вільямс скомбінувала виверт зі Стосерсової статті зі своїми ідеями і автоматизованою комп'ютерною оптимізацією пропонуючи асимптотично швидший алгоритм (${\displaystyle O(n^{2.3728642})}$). У 2014 році Франсуа Ле Ґалл спростив метод Вільямс і отримав краще асимптотичне наближення ${\displaystyle O(n^{2.3728639}).}$.

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

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

Див. також

• Алгоритм Штрассена
• Метод Гауса

Джерела

1. Coppersmith, Don; Winograd, Shmuel (1990), (PDF), Journal of Symbolic Computation, 9 (3): 251, doi:10.1016/S0747-7171(08)80013-2, архів оригіналу (PDF) за 23 вересня 2015, процитовано 2 листопада 2015 (англ.)
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), (PDF), архів оригіналу (PDF) за 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), (PDF), архів оригіналу (PDF) за 26 жовтня 2014, процитовано 2 листопада 2015 (англ.)
6. Le Gall, François (2014), Powers of tensors and fast matrix multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation ( 2014), arXiv:1401.7714 (англ.)
7. Robinson, Sara (2005), (PDF), SIAM News, 38 (9), архів оригіналу (PDF) за 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. doi:10.1109/SFCS.2005.39. ISBN . (англ.)