Существует ли какой-либо метод для умножения матриц, имеющих сложность O (n)?
Я хочу умножить две матрицы, но тройной цикл имеет сложность O (n 3). Есть ли какой-либо алгоритм в динамическом программировании для умножения двух матриц с сложностью O (n)?
ok fine, мы не можем получить лучшее, чем O (n 2.81)
edit:, но есть ли какое-либо решение, которое может даже приблизить результат до некоторого определенного значения. столбцов и строк матрицы
i означает, что мы получаем наилучшее из O (n 2,81) с комплексным решением, но отличные результаты, но если существует какое-либо решение даже для аппроксимации умножения матриц, так как мы имеем формулы для факториальной аппроксимации и др.
если есть кто-то, кого вы знаете, это поможет мне
С уважением.
Ответы
Ответ 1
Известный до сих пор лучший алгоритм умножения матриц - Coppersmith-Winograd algorithm strong > с O (n 2.38), но он не используется для практических целей.
Однако вы всегда можете использовать "алгоритм Strassen" , который имеет O (n 2.81), но нет такого известного алгоритма для матричного умножения с сложностью O (n).
Ответ 2
Существует теоретическая нижняя граница для матричного умножения в O (n ^ 2), так как вам нужно прикоснуться к таким местам памяти, чтобы выполнить умножение. Как говорили другие, существуют алгоритмы, которые опускают нас ниже O (n ^ 3), но обычно непрактичны в реальном использовании.
Если вам нужно ускорить его, вы можете посмотреть на Cache Oblivious Algorithms, например, этот (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650) которые ускоряют производительность путем выполнения операций в кеш-связном режиме, гарантируя, что данные находятся в кеше при необходимости.
Ответ 3
Короткий ответ: Нет
Длинный ответ: Существуют способы, если у вас есть специальные типы матриц (например, диагональная матрица). Лучшие алгоритмы умножения матрицы могут привести вас к чему-то вроде O (n 2.4) (http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm). В основном я знаком с алгоритмом разделения и завоевания, чтобы разделить рабочую нагрузку (а не ту, к которой я привязался).
Надеюсь, это поможет!
Ответ 4
Если матрицы, как известно, диагональны, их можно умножить на операции O(N)
. Но в целом вы не можете.
Ответ 5
Матрицы имеют O (n 2) элементы, и каждый элемент должен быть рассмотрен хотя бы один раз для результата, поэтому нет возможности, чтобы алгоритм матричного умножения выполнялся меньше, чем O ( n 2).
Ответ 6
Нет! Я так не думаю.
Нет способа, пока и пока вы не будете использовать машину параллельной обработки. Это тоже имеет свои собственные зависимости и ограничения.
До сих пор его еще не достигнуто.
Ответ 7
Если у вас есть процессоры n²
и архитектура общедоступной памяти, вы можете умножить две матрицы в O(n)
время... но пока это только теория.
Ответ 8
Если
- ваши матрицы большие
- у них много нулей
- вы готовы хранить их в странных форматах.
вы можете разработать алгоритмы, сложности которых зависят только от количества ненулевых элементов. Это может быть обязательным для некоторых проблем (например, методов конечных элементов).