Требование к памяти для быстрого умножения матриц

12

Предположим, мы хотим умножить матриц. Алгоритм медленного умножения матриц выполняется за время O ( n 3 ) и использует O ( n 2 ) памяти. Самое быстрое умножение матриц выполняется за время n ω + o ( 1 ) , где ω - постоянная линейной алгебры, но что известно о ее сложности памяти?n×nO(n3)O(n2)nω+o(1)ω

Кажется, что априори возможно, что быстрое матричное умножение потребляет памяти. Есть ли гарантия того, что это можно сделать в памяти O ( n 2 ) ? Это тот случай, когда известные алгоритмы умножения матриц используют O ( n 2 ) памяти?nωO(n2)O(n2)

(На самом деле меня интересует умножение прямоугольных матриц, но я предполагаю, что в этом случае ответ будет таким же, как и для квадратного случая, и квадратный случай лучше изучен.)

Дэвид Харрис
источник

Ответы:

16

Использование пространства не более для всех алгоритмов, подобных Штрассену (т.е. основанных на верхнем ограничении ранга матричного умножения алгебраически). См. Пространственная сложность алгоритма Копперсмита – ВиноградаO(n2)

Тем не менее, в своем предыдущем ответе я понял, что не объяснил, почему используется пространство ... так что тут что-то волнистое. Рассмотрим, что делает алгоритм, подобный Штрассену. Он начинается с фиксированного алгоритма умножения матрицы K × K, который использует умножения K c для некоторой константы c < 3 . В частности, этот алгоритм (каким бы он ни был) может быть написан на WLOG так, чтобы:O(n2)K×KKcc<3

  1. Он вычисляет различных матриц L 1 , , L K c, которые умножают записи первой матрицы A на различные скаляры и матрицы K c R 1 , , R K c из второй матрицы B аналогичной формы,KcL1,,LKcAKcR1,,RKcB

  2. Он умножает эти линейные комбинации , тогдаLiRi

  3. Умножает элементы матрицы различными скаляров, а затем добавляет все эти матрицы вверх entrywise получить A B .LiRiAB

(Это так называемый «билинейный» алгоритм, но оказывается, что каждый «алгебраический» алгоритм умножения матриц может быть записан таким образом.) Для каждого этот алгоритм должен хранить только текущий продукт л яR я и текущее значение A B (первоначально установлено на все нули) в памяти в любой заданной точке, таким образом , использование пространства O ( K 2 ) .i=1,,KcLiRiABO(K2)

С учетом этого конечного алгоритма, то затем продолжается до произвольного матриц, разбивая большие матрицы в K × K блоков размерами K л - 1 × K л - 1 , применяя конечное K × K алгоритм к блоку матрицы и рекурсивный вызов алгоритма всякий раз, когда необходимо умножить два блока. На каждом уровне рекурсии нам нужно хранить только O ( K 2 ) элементов поля в памяти (сохраняя O ( 1 )K×KK×KK1×K1K×KO(K2)O(1)отличается матрицы). Предполагая, что использование пространства для умножения матрицы K - 1 × K - 1 равно S ( - 1 ) , использование пространства этого рекурсивного алгоритма составляет S ( ) S ( - 1 ) + O ( K 2 ) который для S ( 1 ) = 2 K 2K×KK1×K1S(1)S()S(1)+O(K2)S(1)=2K2решает в .S()O(K2)

Райан Уильямс
источник
Для любого алгоритма в стиле Штрассена это мне кажется правильным. Но Копперсмит-Виноград также доказал, что для перехода к самом деле требуется бесконечная последовательность алгоритмов в стиле Штрассена, каждый из которых становится все ближе и ближе к истинному показателю. Действительно, как алгоритмы в стиле CW, так и алгоритмы в стиле CU предоставляют такие последовательности (хотя , насколько нам известно, не приближающиеся к ω ). С точки зрения рациональных значений, возможно, что константы, используемые в такой последовательности, будут расти очень быстро, так что алгоритм « n ω» может в конечном итоге использовать пространство ω ( n 2 ) . nωωnωω(n2)
Джошуа Грохов
1
... Но по вашему аргументу всегда можно получить алгоритм во времени и пространстве O ( n 2 ) для любого δ > 0 . O(nω+δ)O(n2)δ>0
Джошуа Грохов
f(i)n2i=0,...,knω+o(1)n2+o(1)
kfkf1fkkn2+o(1)
nkknf(k(n))=no(1)k(n)nnω+o(1)