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

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

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

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

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

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

Див. також

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