Сложность произвольных матричных умножений

Question

У меня есть простой вопрос относительно реализации умножения матриц. Я знаю, что существуют алгоритмы для матриц одинакового размера (n x n), которые имеют сложность O (n ^ 2.xxx). Но если у меня есть две матрицы A и B разных размеров (p x q, q x r), какова будет минимальная сложность реализации на сегодняшний день? Я бы предположил, что это O (pqr), так как я бы реализовал умножение с 3 вложенными циклами с p, q и r итерациями. В частности, кто-нибудь теперь понимает, как библиотека Eigen реализует умножение?

Answer 1

Обычный метод - заполнить матрицы размером (p * q, q * r), чтобы их размеры стали (n * n).Затем вы можете применить алгоритм Штрассена.

Answer 2

Как упоминал Ю-Хэд-Лю, вы можете дополнить их нулями, но если p, q и r не близки, сложность вырождается (время для заполнения).

Чтобы ответить на ваш другой вопрос о том, как Eigen это реализует:

В пакетах чисел реализовано умножение матриц, как правило, с использованием типичного алгоритма O (pqr), но в значительной степени оптимизировано "нематематическими" способами: блокировка для лучшей локализации кэша, с использованием специальных инструкций процессора (SIMD и т. *

В некоторых пакетах (MATLAB, Octave, ublas) используются две библиотеки, называемые BLAS и LAPACK, которые обеспечивают примитивы линейной алгебры (например, умножение матриц), сильно оптимизированные таким образом (иногда с использованием аппаратных оптимизаций).

AFAIK, Eigen просто использует инструкции блокировки и SIMD.

Несколько распространенных числовых библиотек (включая Eigen) используют Алгоритм Штрассена . Причина этого на самом деле очень интересная: хотя сложность лучше (O (n ^ (log2 7))), скрытые константы за большим Oh очень велики из-за всех выполненных дополнений - другими словами, алгоритм полезен только на практике для очень больших матриц.

Примечание: Существует еще более эффективный (с точки зрения асимптотической сложности) алгоритм, чем алгоритм Штрассена: алгоритм Coppersmith – Winograd с O (n ^ (2.3727)), но для которых константы настолько велики, что маловероятно, что они когда-либо будут использоваться на практике. Фактически считается, что существует алгоритм, который работает в O (n ^ 2) (что является тривиальной нижней границей, поскольку любой алгоритм должен по крайней мере прочитать n ^ 2 элементов матриц).

Answer 3

Вы правы, что это O (pqr) именно по тем причинам, которые вы указали.

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