Есть ли какой-либо метод для умножения матриц, имеющих O (n) сложность?
Я хочу умножить две матрицы, но тройной цикл имеет O (n3) сложность. Есть ли какой-либо алгоритм в динамическом программировании для умножения двух матриц с O (n) сложность?
хорошо прекрасный мы не можем стать лучшими, чем O (n2.81)
править: но есть ли любое решение, которое может даже приблизить результат некоторые конкретные нет. из столбцов и строк матрицы
я подразумеваю, что мы получаем лучший из O (n2.81) со сложным решением, но идеальными результатами, но если существует какое-либо решение даже для приближения умножения матриц, поскольку у нас есть формулы для факториального приближения и т.д.
если существует кто-либо, который Вы знаете, что это поможет мне
с уважением.
8 ответов
Лучшим алгоритмом умножения матриц, известным до сих пор, является "алгоритм Меднения-Винограда" со сложностью O(n2.38 ), но для практических целей используется , а не .
Однако Вы всегда можете использовать "алгоритм Штрассена" , который имеет O(n2.81 ) сложность, но такого известного алгоритма для умножения матриц со сложностью O(n) не существует.
.Существует теоретический нижний предел для умножения матриц при O(n^2), так как для этого необходимо коснуться такого количества ячеек памяти, чтобы выполнить умножение. Как говорили другие, существуют алгоритмы, которые опускают нас ниже O(n^3), но обычно непрактичны в реальном использовании.
Если Вам нужно ускорить это, то Вы, возможно, захотите взглянуть на Забвенные Алгоритмы Кэша, такие как этот (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650), которые ускоряют производительность, выполняя операции когерентным способом в кэше, гарантируя, что данные находятся в кэше, когда это необходимо.
.Короткий ответ: Нет
Длинный ответ: Есть способы, если у вас есть специальные виды матриц (например, диагональная матрица). Лучшие алгоритмы умножения матриц там могут свести Вас к чему-то вроде O(n2.4) (http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm). Главный из них, с которым я в некоторой степени знаком, использует алгоритм "разделяй и властвуй" для разделения рабочей нагрузки (а не тот, с которым я связался)
Надеюсь, это поможет!
.Нет! Я так не думаю.
Невозможно, пока и пока вы не используете параллельную машину обработки. Это тоже имеет свои собственные зависимости и ограничения.
До сих пор не достигнуто.
Матрицы имеют элементы O(n2), и каждый элемент должен быть рассмотрен хотя бы один раз для получения результата, поэтому невозможно, чтобы алгоритм умножения матриц выполнялся менее чем в операциях O(n2).
. Если известно, что матрицы диагональны, то их можно умножать с помощью операций O(N). Но в общем случае, это невозможно.
] Если у вас есть []n²[] процессоры и архитектура sharedd-read памяти, то вы могли бы умножить две матрицы во времени []O(n)[]... но пока это только теория. [
Если
- ваши матрицы большие
- в них много нулей
- , вы хотите хранить их в странных форматах
, вы можете разрабатывать алгоритмы, сложность которых зависит только от от количества ненулевых элементов. Это может быть обязательным для некоторых задач (например, методов конечных элементов).