Перегляд вихідного коду сторінки Алгоритм Копперсміта — Вінограда

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

Використовуючи цей алгоритм можна помножити дві матриці <math>n \times n</math> за <math>O(n^{2.375477})</math> одиниць часу<ref  name="coppersmith">{{Citation|doi=10.1016/S0747-7171(08)80013-2|title=Matrix multiplication via arithmetic progressions|url=http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf|year=1990|last1=Coppersmith|first1=Don|last2=Winograd|first2=Shmuel|journal=Journal of Symbolic Computation|volume=9|issue=3|pages=251|accessdate=2 листопада 2015|archive-date=23 вересня 2015|archive-url=https://web.archive.org/web/20150923213139/http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf}} {{ref-en}}</ref>. Такий результат є кращим за наївний алгоритм (<math>O(n^{3})</math>) та алгоритм Штрассена (<math>O(n^{2.807355})</math>). [[Алгоритм перемножування матриць|Алгоритми зі швидшим асимптотичним часом роботи]], ніж алгоритм Штрассена рідко використовується на практиці, оскільки їхні великі сталі числа, у швидкості їх обрахунків, роблять їх непрактичними<ref>{{citation|last = Le Gall | first = F.|arxiv = 1204.1111|contribution = Faster algorithms for rectangular matrix multiplication|doi = 10.1109/FOCS.2012.80|pages = 514–523|title = Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)|year = 2012}} {{ref-en}}</ref>. Показник можна ще покращити, однак, показник не може бути меншим за 2 (бо <math>n \times n</math> матриця має <math>n^2</math> значення і кожне з них повинне бути прочитане принаймні раз для обчислення точного результату).

У 2010 Ендрю Стосерс запропонував покращення алгоритму з асимптотичним часом <math>O(n^{2.374})</math><ref>{{Citation | last1=Stothers | first1=Andrew | title=On the Complexity of Matrix Multiplication | url=http://www.maths.ed.ac.uk/pg/thesis/stothers.pdf | year=2010 | accessdate=2 листопада 2015 | archiveurl=https://web.archive.org/web/20111215153010/http://www.maths.ed.ac.uk/pg/thesis/stothers.pdf | archivedate=15 грудня 2011 | deadurl=yes }} {{ref-en}}</ref><ref>{{Citation | last1=Davie | first1=A.M. | last2=Stothers | first2=A.J. | title=Improved bound for complexity of matrix multiplication|journal=Proceedings of the Royal Society of Edinburgh|volume=143A|pages=351–370|year=2013|doi=10.1017/S0308210511001648}} {{ref-en}}</ref>. У 2011 Вірджинія Вільямс скомбінувала виверт зі Стосерсової статті зі своїми ідеями і автоматизованою комп'ютерною оптимізацією пропонуючи асимптотично швидший алгоритм (<math>O(n^{2.3728642})</math>)<ref>{{Citation | last1=Williams | first1=Virginia | title=Breaking the Coppersmith-Winograd barrier | url=http://theory.stanford.edu/~virgi/matrixmult-f.pdf | year=2011 | accessdate=2 листопада 2015 | archive-date=26 жовтня 2014 | archive-url=https://web.archive.org/web/20141026144011/http://theory.stanford.edu/~virgi/matrixmult-f.pdf }} {{ref-en}}</ref>. У 2014 році Франсуа Ле Ґалл спростив метод Вільямс і отримав краще асимптотичне наближення <math>O(n^{2.3728639}).</math><ref>{{Citation | last1=Le Gall | first1=François | contribution=Powers of tensors and fast matrix multiplication | year = 2014 | arxiv=1401.7714 | title = Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation ([[ISSAC]] 2014)}} {{ref-en}}</ref>.

Алгоритм Копперсміта — Вінограда часто використовується як основа для інших алгоритмів, щоб довести теоретичні межі швидкості обрахунків. Проте, на відміну від алгоритму Штрассена, він не використовується на практиці, оскільки він забезпечує перевагу лише для матриць настільки великих, що вони не можуть бути оброблені сучасним обладнанням<ref>{{Citation | last1=Robinson | first1=Sara | title=Toward an Optimal Algorithm for Matrix Multiplication | url=http://www.siam.org/pdf/news/174.pdf | year=2005 | journal=SIAM News | volume=38 | issue=9 | accessdate=2 листопада 2015 | archiveurl=https://web.archive.org/web/20100331095603/http://www.siam.org/pdf/news/174.pdf | archivedate=31 березня 2010 | deadurl=yes }} {{ref-en}}</ref>.

Генрі Кон, Роберт Клейнберг, Балаж Щеґеди і Кріс Уманс повторно вивели алгоритм Копперсміта — Вінограда, використовуючи [[Теорія груп|теоретико-груповий]] підхід. Вони також показали, що кожен з двох підходів передбачає, що оптимальним показником для алгоритму множення матриць є 2, як давно підозрювали у наукових колах. Тим не менш, вони не змогли сформулювати конкретний розв'язок, що привів би до кращого часу обчислення, ніж алгоритм Копперсміта — Вінограда<ref>{{Cite book | last1 = Cohn | first1 = H. | last2 = Kleinberg | first2 = R. | last3 = Szegedy | first3 = B. | last4 = Umans | first4 = C. | chapter = Group-theoretic Algorithms for Matrix Multiplication | doi = 10.1109/SFCS.2005.39 | title = 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) | pages = 379 | year = 2005 | isbn = 0-7695-2468-0 | pmid =  | pmc = }} {{ref-en}}</ref>.

== Див. також ==
* [[Алгоритм Штрассена]]
* [[Метод Гауса]]

== Джерела ==
{{reflist|2}}

{{math-stub}}

[[Категорія:Числова лінійна алгебра]]
[[Категорія:Алгоритми]]
[[Категорія:Теорія матриць]]
[[Категорія:Алгоритми множення матриць]]
[[Категорія:1987 у науці]]