Какой алгоритм умножения матриц самый быстрый?
В теоретической информатике , то вычислительная сложность матричного умножения диктата , как быстро операция умножения матриц может быть выполнена. Алгоритмы матричного умножения являются центральной подпрограммой в теоретических и численных алгоритмах численной линейной алгебры и оптимизации , поэтому поиск правильного количества времени, которое потребуется для этого, имеет большое практическое значение.
Непосредственное применение математического определения умножения матриц дает алгоритм, который требует n 3 полевых операций для умножения двух матриц n × n над этим полем ( Θ ( n 3 ) в нотации большой O ). Удивительно, но существуют алгоритмы, обеспечивающие лучшее время работы, чем этот простой «школьный алгоритм». Первым был открыт алгоритм Штрассена , разработанный Фолькером Штрассеном в 1969 году и часто называемый «быстрым умножением матриц». [1] Оптимальное количество полевых операций, необходимых для умножения двух квадратных матриц размера n × n с точностью до постоянных множителей , все еще неизвестно. Это главный открытый вопрос теоретической информатики .
По состоянию на декабрь 2020 [Обновить]года алгоритм умножения матриц с наилучшей асимптотической сложностью выполняется за время O ( n 2,3728596 ) , указанное Джошем Алманом и Вирджинией Василевской Уильямс . [2] [3] Однако это и подобные усовершенствования Штрассена не используются на практике, потому что они являются галактическими алгоритмами : постоянный коэффициент, скрытый нотацией Big O, настолько велик, что они подходят только для матриц, которые слишком велики для работать на современных компьютерах. [4] [5]
Простые алгоритмы
Если A , B - это матрицы размера n × n над полем, то их произведение AB также является матрицей n × n над этим полем, определяемой по входам как
Алгоритм учебника
Самый простой подход к вычислению произведения двух матриц размера n × n A и B состоит в том, чтобы вычислить арифметические выражения, вытекающие из определения умножения матриц. В псевдокоде:
входные A и B , обе матрицы n на n инициализируют C как матрицу n на n всех нулей для i от 1 до n : для j от 1 до n : для k от 1 до n : C [ i ] [ j ] = C [ i ] [ j ] + A [ i ] [ k ] * B [ k ] [ j ] вывод C (как A * B)
Этот алгоритм требует, в худшем случае , умножения скаляров и дополнения для вычисления произведения двух квадратных матриц размера n × n . Следовательно, его вычислительная сложность составляетв модели вычислений, где операции с полями (сложение и умножение) занимают постоянное время (на практике это имеет место для чисел с плавающей запятой , но не обязательно для целых чисел).
Алгоритм Штрассена
Алгоритм Штрассена улучшает наивное умножение матриц за счет подхода « разделяй и властвуй» . Ключевое наблюдение состоит в том, что умножение двух матриц 2 × 2 может быть выполнено всего за 7 умножений вместо обычных 8 (за счет нескольких дополнительных операций сложения и вычитания). Это означает, что, рассматривая входные матрицы размера n × n как блочные матрицы 2 × 2 , задача умножения матриц n × n может быть уменьшена до 7 подзадач умножения матриц n / 2 × n / 2 . Применение этого рекурсивно дает алгоритм, требующий полевые операции.
В отличие от алгоритмов с более быстрой асимптотической сложностью, алгоритм Штрассена используется на практике. Численная устойчивость снижается по сравнению с наивным алгоритма, [6] , но это быстрее в тех случаях , когда п > 100 или около [7] , и появляется в нескольких библиотеках, таких как BLAS . [8] Это очень полезно для больших матриц в точных областях, таких как конечные поля , где числовая стабильность не является проблемой.
Показатель умножения матрицы
Год | Связанный с омегой | Авторы |
---|---|---|
1969 г. | 2,8074 | Штрассен [1] |
1978 г. | 2,796 | Сковорода [9] |
1979 г. | 2,780 | Бини, Каповани, романи [10] |
1981 г. | 2,522 | Шёнхаге [11] |
1981 г. | 2,517 | Цыгане [12] |
1981 г. | 2,496 | Медник , Виноград [13] |
1986 г. | 2,479 | Штрассен [14] |
1990 г. | 2,3755 | Медник , Виноград [15] |
2010 г. | 2,3737 | Стотерс [16] |
2013 | 2,3729 | Уильямс [17] [18] |
2014 г. | 2,3728639 | Ле Галль [19] |
2020 г. | 2,3728596 | Алман, Уильямс [2] |
Показатель матричного умножения , обычно обозначаемый ω , является наименьшим действительным числом, для которого любое матрицу над полем можно перемножить, используя полевые операции. Это обозначение обычно используется при исследовании алгоритмов , поэтому алгоритмы, использующие умножение матриц в качестве подпрограммы, имеют значимые границы времени выполнения независимо от истинного значения ω .
Используя наивную нижнюю оценку и умножение школьных матриц для верхней оценки, можно напрямую заключить, что 2 ≤ ω ≤ 3 . Является ли ω = 2 основным открытым вопросом в теоретической информатике , и существует направление исследований, направленных на разработку алгоритмов умножения матриц для получения улучшенных оценок ω .
На данный момент наилучшая оценка ω составляет ω <2.3728596 , сделанная Джошем Алманом и Вирджинией Василевской Уильямс . [2] Этот алгоритм, как и все другие недавние алгоритмы в этом направлении исследований, использует лазерный метод , обобщение алгоритма Копперсмита – Винограда, который был предложен Доном Копперсмитом и Шмуэлем Виноградом в 1990 году и до тех пор был лучшим алгоритмом умножения матриц. 2010. [20] Концептуальная идея этих алгоритмов аналогична алгоритму Штрассена: разработан способ умножения двух k × k -матриц с менее чем k 3 умножениями, и этот метод применяется рекурсивно. Лазерный метод имеет ограничения по мощности, и его нельзя использовать, чтобы показать, что ω <2.3725 . [21]
Теория групп переформулировки алгоритмов умножения матриц
Генри Кон , Роберт Клейнберг , Балаж Сегеди и Крис Уманс поместили такие методы, как алгоритмы Штрассена и Копперсмита – Винограда, в совершенно другой теоретико-групповой контекст, используя тройки подмножеств конечных групп, которые удовлетворяют свойству непересекаемости, называемому свойством тройного произведения ( ТЭС) . Они также выдвигают гипотезы, которые, если они верны, означают, что существуют алгоритмы умножения матриц с по существу квадратичной сложностью. Это означает, что оптимальный показатель умножения матриц равен 2, что, по мнению большинства исследователей, действительно так. [5] Одним из такой гипотезы состоит в том , что семейства сплетений из абелевых групп с симметричными группами понимают семейство подмножеств троек с одновременной версией ТЭС. [22] [23] Некоторые из их гипотез были с тех пор опровергнуты Блазиаком, Коном, Черчем, Грохоу, Наслундом, Савином и Умансом с использованием метода Slice Rank. [24] Кроме того, Алон, Шпилка и Крис Уманс недавно показали, что некоторые из этих гипотез, предполагающих быстрое матричное умножение, несовместимы с другой правдоподобной гипотезой - гипотезой о подсолнечнике . [25]
Оценки снизу для ω
Существует тривиальная нижняя оценка . Поскольку любой алгоритм умножения двух n × n -матриц должен обрабатывать все 2 n 2 элементов, существует тривиальная асимптотическая нижняя граница операций Ω ( n 2 ) для любого алгоритма умножения матриц. Таким образом. Неизвестно, были ли. Самая известная нижняя граница сложности умножения матриц - это Ω ( n 2 log ( n )) для арифметических схем с ограниченными коэффициентами над действительными или комплексными числами и принадлежит Рану Разу . [26]
Умножение прямоугольной матрицы
Подобные методы также применимы к умножению прямоугольной матрицы. Центральный объект исследования -, который является самым маленьким так что можно умножить матрицу размера с матрицей размеров с участием арифметические операции. Результатом алгебраической сложности является утверждение, что умножение матриц размера а также требует того же количества арифметических операций, что и умножение матриц размера а также и по размеру а также , так что это включает в себя сложность умножения прямоугольной матрицы. [27] Это обобщает показатель умножения квадратной матрицы, поскольку.
Интересно доказать, что для значений k от 0 до 1, что. Поскольку выходом задачи умножения матриц является размер, всегда, поэтому эти результаты показывают, что точно. Наибольшее k такое, чтоизвестен как показатель двойственной матрицы умножения , обычно обозначаемый α . α называется « двойственным », потому что показывает, что эквивалентно показать, что . Как и показатель умножения матриц, показатель двойственного матричного умножения иногда появляется в сложности алгоритмов численной линейной алгебры и оптимизации. [28]
Первая граница альфа является Копперсмитом в 1982 году, который показал , что. [29] Текущая наилучшая оценка α равна, предоставленный Ле Галлом и Уррутией. [30] Эта статья также содержит оценки на.
Связанные сложности
Задачи, которые имеют ту же асимптотическую сложность, что и умножение матриц, включают определитель , обращение матриц , исключение Гаусса (см. Следующий раздел). Проблемы со сложностью, которые можно выразить с помощьювключают в себя характеристический полином, собственные значения (но не собственные векторы), Эрмита нормальную форму , и Smith нормальную форму . [ необходима цитата ]
Обращение матрицы, определитель и исключение Гаусса
В своей статье 1969 года, где он доказал сложность для вычисления матриц Штрассен также доказал, что обращение матриц , определитель и исключение Гаусса имеют, с точностью до константы мультипликатора, ту же вычислительную сложность, что и умножение матриц. Доказательство не делает никаких предположений об используемом умножении матриц, за исключением того, что его сложность составляет для некоторых
Отправной точкой доказательства Штрассена является использование блочного умножения матриц . В частности, матрица четной размерности 2 n × 2 n может быть разделена на четыре блока n × n.
В этой форме его обратное
при условии, что A и обратимы.
Таким образом, обратная матрица 2 n × 2 n может быть вычислена с помощью двух инверсий, шести умножений и четырех сложений или аддитивных обращений матриц n × n . Отсюда следует, что, обозначая соответственно I ( n ) , M ( n ) и A ( n ) = n 2 количество операций, необходимых для инвертирования, умножения и сложения матриц размера n × n , мы получаем
Если можно применить эту формулу рекурсивно:
Если а также в конце концов получается
для некоторой постоянной d .
Для матриц, размерность которых не является степенью двойки, такая же сложность достигается увеличением размерности матрицы до степени двойки путем заполнения матрицы строками и столбцами, элементы которых равны 1 по диагонали и 0 в других местах.
Это доказывает заявленную сложность таких матриц, что все подматрицы, которые нужно инвертировать, действительно обратимы. Таким образом, эта сложность доказана почти для всех матриц, поскольку матрица со случайно выбранными элементами обратима с вероятностью единица.
Тот же аргумент применяется к разложению LU , так как, если матрица A обратима, равенство
определяет декомпозицию блочного LU, которая может рекурсивно применяться к а также для получения в конечном итоге истинного LU-разложения исходной матрицы.
Аргумент применим также к определителю, поскольку он является результатом разложения блочного LU, что
Смотрите также
- Вычислительная сложность математических операций
- Алгоритм CYK, алгоритм §Valiant
- Алгоритм Фрейвальдс , простой Монте - Карло алгоритм , который, с учетом матрицы , B и C , проверяет в Q ( п 2 ) время , если AB = C .
- Умножение матричной цепочки
- Умножение матриц для абстрактных определений
- Алгоритм умножения матриц , для деталей практической реализации
- Умножение разреженной матрицы на вектор
Рекомендации
- ^ a b Фолькер Штрассен (август 1969). «Исключение Гаусса не оптимально» . Numerische Mathematik . 13 (4): 354–356. DOI : 10.1007 / BF02165411 . S2CID 121656251 .
- ^ а б в Алман, Джош; Уильямс, Вирджиния Василевска (2020), «Усовершенствованный лазерный метод и более быстрое умножение матриц», 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021) , arXiv : 2010.05846
- ^ Хартнетт, Кевин. «Умножение матриц на дюймы ближе к мифической цели» . Журнал Quanta . Проверено 1 апреля 2021 .
- ^ Илиопулос, Костас С. (1989), "Границы сложности в наихудшем случае алгоритмов вычисления канонической структуры конечных абелевых групп и нормальных форм Эрмита и Смита целочисленной матрицы" (PDF) , SIAM Journal on Computing , 18 (4 ): 658-669, CiteSeerX 10.1.1.531.9309 , DOI : 10,1137 / 0218045 , MR 1004789 , архивируются с оригинала (PDF) на 2014-03-05 , извлекаться 2015-01-16 ,
алгоритм Медник-Винограда не практично из-за очень большой скрытой константы в верхней границе количества требуемых умножений.
- ^ а б Робинсон, Сара (ноябрь 2005 г.), «К оптимальному алгоритму умножения матриц» (PDF) , SIAM News , 38 (9),
Даже если кому-то удастся доказать одну из гипотез - тем самым продемонстрировав, что ω = 2 - сплетение подход вряд ли применим к задачам с большими матрицами, которые возникают на практике. [...] входные матрицы должны быть астрономически большими, чтобы разница во времени была очевидной.
- ^ Миллер, Уэбб (1975), "Вычислительная сложность и численное стабильность", SIAM Новости , 4 (2): 97-107, CiteSeerX 10.1.1.148.9947 , DOI : 10,1137 / 0204009
- ^ Скиена, Стивен (2008). «Сортировка и поиск». Руководство по разработке алгоритмов . Springer. стр. 45 -46, 401-403. DOI : 10.1007 / 978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.
- ^ Press, William H .; Флэннери, Брайан П .; Теукольский, Саул А .; Веттерлинг, Уильям Т. (2007). Числовые рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета . п. 108 . ISBN 978-0-521-88068-8.
- ^ Виктор Яковлевич Пан (октябрь 1978 г.). «Алгоритм Штрассена не оптимален: трилинейная техника агрегирования, объединения и отмены для построения быстрых алгоритмов для матричных операций». Proc. 19-й ВОКС . С. 166–176. DOI : 10,1109 / SFCS.1978.34 . S2CID 14348408 .
- ^ Дарио Андреа Бини; Мильвио Каповани; Франческо Романи; Грация Лотти (июнь 1979 г.). " О ( п 2,7799 ) {\ displaystyle O (п ^ {2.7799})} сложность для п × п {\ Displaystyle п \ раз п} приблизительное матричное умножение " . Письма об обработке информации . 8 (5): 234–235. doi : 10.1016 / 0020-0190 (79) 90113-3 .
- ^ А. Шёнхаге (1981). «Частичное и полное умножение матриц». SIAM Journal on Computing . 10 (3): 434–455. DOI : 10.1137 / 0210032 .
- ^ Франческо Романи (1982). «Некоторые свойства дизъюнктных сумм тензоров, связанные с умножением матриц». SIAM Journal on Computing . 11 (2): 263–267. DOI : 10.1137 / 0211020 .
- ^ Д. Медник; С. Виноград (1981). «Об асимптотической сложности умножения матриц». Proc. 22-й ежегодный симпозиум по основам информатики (FOCS) . С. 82–90. DOI : 10.1109 / SFCS.1981.27 . S2CID 206558664 .
- ^ Фолькер Штрассен (октябрь 1986 г.). «Асимптотический спектр тензоров и показатель умножения матриц». Proc. 27-я Ann. Symp. о Фонде компьютерных наук (FOCS) . С. 49–54. DOI : 10.1109 / SFCS.1986.52 . S2CID 15077423 .
- ^ Д. Медник; С. Виноград (март 1990 г.). «Умножение матриц с помощью арифметических прогрессий» . Журнал символических вычислений . 9 (3): 251–280. DOI : 10.1016 / S0747-7171 (08) 80013-2 .
- ^ Стотерс, Эндрю Джеймс (2010). О сложности умножения матриц (кандидатская диссертация). Эдинбургский университет.
- ^ Вирджиния Василевска Уильямс (2012). «Умножение матриц быстрее, чем Копперсмит-Виноград». У Говарда Дж. Карлоффа; Тониан Питасси (ред.). Proc. 44-й симпозиум по теории вычислений (STOC) . ACM. С. 887–898. DOI : 10.1145 / 2213977.2214056 .
- ^ Уильямс, Вирджиния Василевская . Умножение матриц в О ( п 2.373 ) {\ displaystyle O (п ^ {2.373})} время (PDF) (Технический отчет). Стэндфордский Университет.
- ^ Ле Галл, Франсуа (2014), «Силы тензоров и быстрое умножение матриц», в Katsusuke Nabeshima (ed.), Proceedings of the 39th International Symposium on Symbolic and Algebraic Computing (ISSAC) , pp. 296–303, arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L , ISBN 978-1-4503-2501-1
- ^ Медник, Дон; Винограда, Шмуэль (1990), "Умножение матриц с помощью арифметических прогрессий" (PDF) , журнал символьных вычислений , 9 (3): 251, DOI : 10.1016 / S0747-7171 (08) 80013-2
- ^ Амбаинис, Андрис; Фильмус, Юваль; Ле Галль, Франсуа (14 июня 2015 г.). "Быстрое умножение матриц: ограничения метода Копперсмита-Винограда" . Материалы сорок седьмого ежегодного симпозиума ACM по теории вычислений . СТОК '15. Портленд, Орегон, США: Ассоциация вычислительной техники: 585–593. DOI : 10.1145 / 2746539.2746554 . ISBN 978-1-4503-3536-2.
- ^ Cohn, H .; Kleinberg, R .; Szegedy, B .; Уманс, К. (2005). "Теоретико-групповые алгоритмы умножения матриц". 46-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS'05) . п. 379. DOI : 10.1109 / SFCS.2005.39 . ISBN 0-7695-2468-0. S2CID 41278294 .
- ^ Генри Кон, Крис Уманс. Теоретико-групповой подход к быстрому умножению матриц. arXiv : math.GR/0307321 . Материалы 44-го ежегодного симпозиума IEEE по основам компьютерных наук , 11–14 октября 2003 г., Кембридж, Массачусетс, Компьютерное общество IEEE, стр. 438–449.
- ^ Blasiak, J .; Cohn, H .; Церковь, Т .; Grochow, J .; Naslund, E .; Sawin, W .; Уманс, К. (2017). «О наборах крышек и теоретико-групповом подходе к умножению матриц». Дискретный анализ . DOI : 10,19086 / da.1245 . S2CID 9687868 .
- ^ Алон , Шпилка, Уманс, О подсолнухах и матричном умножении
- ^ Раз, Ран (2002). «О сложности матричного произведения». Труды тридцать четвертый ежегодный ACM симпозиум по теории вычислений : 144. DOI : 10,1145 / 509907.509932 . ISBN 1581134959. S2CID 9582328 .
- ^ Галл, Франсуа Ле; Уррутия, Флоран (2018-01-01), «Улучшенное умножение прямоугольной матрицы с использованием степеней тензора Копперсмит-Винограда» , Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2018 г. , Труды, Общество промышленной и прикладной математики , pp. 1029–1046, arXiv : 1708.05622 , doi : 10.1137 / 1.9781611975031.67 , получено 2021-05-23
- ^ Коэн, Майкл Б .; Ли, Инь Тат; Сун, Чжао (2021-01-05). «Решение линейных программ во время умножения текущей матрицы» . Журнал ACM . 68 (1): 3: 1–3: 39. arXiv : 1810.07896 . DOI : 10.1145 / 3424305 . ISSN 0004-5411 .
- ^ Копперсмит, Д. (1 августа 1982 г.). «Быстрое умножение прямоугольных матриц» . SIAM Journal on Computing . 11 (3): 467–471. DOI : 10.1137 / 0211037 . ISSN 0097-5397 .
- ^ Ле Галль, Франсуа; Уррутия, Флоран (2018-01-01), «Улучшенное умножение прямоугольной матрицы с использованием степеней тензора Копперсмит-Винограда» , Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2018 г. , Труды, Общество промышленной и прикладной математики , pp. 1029–1046, arXiv : 1708.05622 , doi : 10.1137 / 1.9781611975031.67 , получено 2021-05-23