Есть ли способ умножения матриц, имеющих O (n) сложность?

Question

Я хочу умножить две матрицы, но тройной цикл имеет сложность O (n ³ ). Есть ли алгоритм в динамическом программировании для умножения двух матриц со сложностью O (n)?

хорошо, хорошо, мы не можем получить лучше, чем O (n ^2.81 )

edit: но есть ли решение, которое может даже приблизить результат к некоторому конкретному нет. столбцов и строк матрицы

Я имею в виду, что мы получаем лучшее из O (n ^2.81 ) со сложным решением, но с прекрасными результатами, но если есть какое-либо решение даже для приближения умножения матриц, поскольку у нас есть формулы для факторного приближения и т. Д .

если есть кто-то, кого вы знаете, это поможет мне

привет.

Answer 1

Алгоритм умножения матриц лучший , известный до сих пор, - это "алгоритм Копперсмит-Винограда" с O (n ^2,38 ) сложность, но она не используется для практических целей.

Однако вы всегда можете использовать «Алгоритм Штрассена» , который имеет O (n ^2.81 ) сложность, но таких известных нет алгоритм умножения матриц со сложностью O (n).

Answer 2

Существует теоретическая нижняя граница для умножения матриц при O (n ^ 2), так как вы должны коснуться такого количества областей памяти, чтобы выполнить умножение. Как уже говорили другие, есть алгоритмы, которые опускают нас ниже O (n ^ 3), но обычно нецелесообразны в реальном использовании.

Если вам нужно ускорить его, вы, возможно, захотите взглянуть на алгоритмы кеширования, такие как этот (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650)), которые ускоряют производительность, выполняя операции связным способом в кэше, гарантируя, что данные находятся в кеш при необходимости.

Answer 3

Краткий ответ: Нет

Длинный ответ: Есть способы, если у вас есть особые виды матриц (например, диагональная матрица). Лучшие алгоритмы умножения матриц могут свести вас к чему-то вроде O (n ^2.4 ) (http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm).). Главный из них, с которым я немного знаком, использует алгоритм «разделяй и властвуй» для разделения рабочая нагрузка (не та, с которой я связан).

Надеюсь, это поможет!

Answer 4

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

Answer 5

Если известно, что матрицы диагональны, вы можете умножить их на O(N) операций. Но в общем, вы не можете.

Answer 6

Если

• ваши матрицы большие
• у них много нулей
• вы готовы хранить их в странных форматах

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

Answer 7

Если у вас есть n² процессоры и архитектура с разделяемой памятью, вы можете умножить две матрицы за O(n) время ... но пока это только теория.

Answer 8

Нет! Я так не думаю.

Нет способа, пока вы не используете параллельный процессор. Это тоже имеет свои зависимости и ограничения.

До сих пор это еще не достигнуто.