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

Я ищу информацию о вычислительной сложности матричного умножения прямоугольных матриц. Википедия утверждает, что сложность умножения на составляет (умножение в школьных учебниках). $A \in \mathbb{R}^{m \times n}$ $B \in \mathbb{R}^{n \times p}$ $O(mnp)$

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

Есть идеи?

Благодарю.

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

cc.complexity-theory time-complexity linear-algebra matrix-product опросник
источник

Сложность (последовательного) алгоритма не может быть меньше размера его вывода. Для вашей проблемы вы можете представить ввод и вывод, используя пространство, которое является сублинейным по p?

Колин Маккуиллан

элементы в основном ненулевые или часто нулевые? то есть разреженный? это, безусловно, приводит к различным оптимизациям. также кажется, что SVD [разложение по сингулярным значениям] может быть актуальным на основе текущего отклика, относящегося к аппроксимациям.

vzn

Ответы:

Классическая работа Копперсмит показывает , что при некотором , можно умножать в матрицу с матрицы в арифметических операций. Это важнейший компонент недавнего знаменитого результата Райана Уильямса. $\alpha > 0$ $n \times n^\alpha$ $n^\alpha \times n$ $\tilde{O}(n^2)$

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

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

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

Юваль Фильмус
источник

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

Райан Уильямс