Вычислительная сложность умножения матриц

14

Я ищу информацию о вычислительной сложности матричного умножения прямоугольных матриц. Википедия утверждает, что сложность умножения на составляет (умножение в школьных учебниках).ARm×nBRn×pO(mnp)

У меня есть случай, когда и намного меньше , и я надеялся получить лучшую сложность, чем linear по , за счет того, что зависимость от и хуже линейной.mnppmn

Есть идеи?

Благодарю.

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

опросник
источник
8
Сложность (последовательного) алгоритма не может быть меньше размера его вывода. Для вашей проблемы вы можете представить ввод и вывод, используя пространство, которое является сублинейным по p?
Колин Маккуиллан
элементы в основном ненулевые или часто нулевые? то есть разреженный? это, безусловно, приводит к различным оптимизациям. также кажется, что SVD [разложение по сингулярным значениям] может быть актуальным на основе текущего отклика, относящегося к аппроксимациям.
vzn

Ответы:

13

Классическая работа Копперсмит показывает , что при некотором , можно умножать в п × п альфа матрицу с п альфа × п матрицы в ~ O ( п 2 ) арифметических операций. Это важнейший компонент недавнего знаменитого результата Райана Уильямса.α>0N×NαNα×NО~(N2)

Франсуа ле Галль недавно улучшил работу Копперсмита, и его статья была только что принята на FOCS 2012. Чтобы понять эту работу, вам понадобятся некоторые знания теории алгебраической сложности. Статья Вирджинии Уильямс содержит некоторые соответствующие указатели. В частности, работа Копперсмита полностью описана в книге « Алгебраическая теория сложности» .

Другая часть работы концентрируется на умножении матриц приблизительно . Вы можете проверить эту работу Маген и Зузиас. Это полезно для обработки действительно больших матриц, скажем, умножения матрицы матрицы N × n , где N n .N×NN×NN»N

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

Юваль Фильмус
источник
Просто примечание: известно (по состоянию на ноябрь 2010 года), что умножение прямоугольной матрицы не является необходимым для решения ACC SAT. (Что хорошо, потому что прямоугольная матрица мульт "галактическая" и сложная.)
Райан Уильямс