Алгоритм Копперсмита – Винограда - Coppersmith–Winograd algorithm

В линейная алгебра, то Алгоритм Копперсмита – Винограда, названный в честь Дон Копперсмит и Шмуэль Виноград, был асимптотически самым быстрым из известных алгоритм умножения матриц с 1990 по 2010 год. Может умножить два матрицы в время[1] (видеть Обозначение Big O ).

Это улучшение по сравнению с наивным временной алгоритм и время Алгоритм Штрассена. Алгоритмы с лучшим асимптотическим временем выполнения, чем алгоритм Штрассена, редко используются на практике, потому что большие постоянные множители во времени их выполнения делают их непрактичными.[2] Возможно дальнейшее улучшение показателя степени; однако показатель степени должен быть не менее 2 (потому что есть значения в результате, которые необходимо вычислить).

В 2010 году Эндрю Стотерс усовершенствовал алгоритм, [3][4] В 2011, Вирджиния Василевска Уильямс объединила математический сокращенный вариант из статьи Стотерс с ее собственными идеями и автоматизированной оптимизацией на компьютерах, улучшив привязку к [5] В 2014 году Франсуа Ле Галль упростил методы Вильямса и получил улучшенную оценку [6]

Алгоритм Копперсмита – Винограда часто используется в качестве строительного блока в других алгоритмах для доказательства теоретических временных рамок. Однако, в отличие от алгоритма Штрассена, он не используется на практике, потому что он дает преимущество только для матриц настолько больших, что они не могут быть обработаны современным оборудованием (что делает его галактический алгоритм ).[7]

Генри Кон, Роберт Клейнберг, Балаж Сегеди и Крис Уманс восстановили алгоритм Копперсмита – Винограда, используя теоретико-групповой строительство. Они также показали, что любая из двух различных гипотез будет означать, что оптимальный показатель умножения матриц равен 2, как давно подозревали. Однако они не смогли сформулировать конкретное решение, ведущее к лучшему времени работы, чем Coppersmith – Winograd.[8] Некоторые из их предположений с тех пор были опровергнуты Блазиаком, Коном, Черчем, Грохоу, Наслундом, Савином и Умансом с использованием метода ранжирования срезов.[9]

Смотрите также

Рекомендации

  1. ^ Медник, Дон; Виноград, Шмуэль (1990), «Умножение матриц с помощью арифметических прогрессий» (PDF), Журнал символических вычислений, 9 (3): 251, Дои:10.1016 / S0747-7171 (08) 80013-2
  2. ^ Ле Галл, Ф. (2012), "Более быстрые алгоритмы умножения прямоугольных матриц", Материалы 53-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS 2012), стр. 514–523, arXiv:1204.1111, Дои:10.1109 / FOCS.2012.80.
  3. ^ Стотерс, Эндрю (2010), О сложности умножения матриц (Докторская диссертация), Эдинбургский университет.
  4. ^ Дэви, A.M .; Стотерс, А.Дж. (Апрель 2013), «Улучшенная оценка сложности матричного умножения» (PDF), Труды Королевского общества Эдинбурга, 143A (2): 351–370, Дои:10.1017 / S0308210511001648
  5. ^ Уильямс, Вирджиния Василевская (2011), Преодоление барьера медников-виноград (PDF)
  6. ^ ""Ле Галл, Франсуа (2014), «Степени тензоров и быстрое матричное умножение», Труды 39-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC 2014), arXiv:1401.7714, Bibcode:2014arXiv1401.7714L
  7. ^ Робинсон, Сара (ноябрь 2005 г.), «К оптимальному алгоритму умножения матриц» (PDF), Новости SIAM, 38 (9), Даже если кому-то удастся доказать одну из гипотез - тем самым продемонстрировав, что ω = 2- подход сплетения вряд ли применим к задачам с большими матрицами, которые возникают на практике. [...] входные матрицы должны быть астрономически большими, чтобы разница во времени была очевидной.
  8. ^ Cohn, H .; Kleinberg, R .; Szegedy, B .; Уманс, К. (2005). "Теоретико-групповые алгоритмы умножения матриц". 46-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS'05). п. 379. Дои:10.1109 / SFCS.2005.39. ISBN  0-7695-2468-0.
  9. ^ Blasiak, J .; Cohn, H .; Церковь, Т .; Grochow, J .; Naslund, E .; Sawin, W .; Уманс, К. "О наборах крышек и теоретико-групповом подходе к умножению матриц". Дискретный анализ. Дои:10.19086 / da.1245.

дальнейшее чтение

  • Bürgisser, P .; Clausen, M .; Шокроллахи, М. А. (1997). Алгебраическая теория сложности. Grundlehren der Mathematischen Wissenschaften. 315. Springer Verlag. ISBN  3-540-60582-7.