Каков наилучший алгоритм умножения матрицы?

Ответ 1

BLAS - лучшая готовая к использованию библиотека эффективного умножения матриц. Существует много разных вариантов реализации. Вот тест, который я сделал для некоторых реализаций на MacBook Pro с двухъядерным процессором Intel Core 2 Duo 2,66 ГГц:

• gotoBLAS2 (open-source): https://www.tacc.utexas.edu/research-development/tacc-software/gotoblas2
• ATLAS (open-source): http://math-atlas.sourceforge.net/
• Accelerate.framework(Apple): http://developer.apple.com/performance/accelerateframework.html
• не оптимизированная, но переносимая реализация, которую я назвал 'vanilla' (из GSL)

Существуют и другие коммерческие реализации, которые я не тестировал здесь:

• MKL (Intel): http://software.intel.com/en-us/articles/intel-mkl/
• ACML (AMD): http://developer.amd.com/cpu/Libraries/acml/Pages/default.aspx

Ответ 2

Лучший алгоритм умножения матрицы - это тот, который кто-то с подробными архитектурными знаниями уже настроен вручную для вашей целевой платформы.

Есть много хороших библиотек, которые предоставляют настроенные преобразования с матричным умножением. Используйте один из них.

Ответ 3

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

Strassen's - O (N ^ 2.8)

Coppersmith Winograd - O (N ^ 2.376)

Ответ 4

Почему псевдокод? Зачем это реализовать? Если вам нужна скорость, есть высоко оптимизированные алгоритмы, которые включают в себя оптимизацию для определенных наборов инструкций (например, SIMD), реализация этих программ сама по себе не дает реальной выгоды (кроме обучения),

Взгляните на различные реализации BLAS, например:

http://www.netlib.org/blas/

http://math-atlas.sourceforge.net/

Ответ 5

Вот алгоритм курса MIT и лекции матрицы умножения

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-19-shortest-paths-iii-all-pairs-shortest-paths-matrix-multiplication-floyd-warshall-johnson/

умножение матрицы - O (n ^ 3)

Алгоритм Strassens - O (n ^ 2.8) http://en.wikipedia.org/wiki/Strassen_algorithm

Coppersmith-Winograd - O (n ^ 2.376) http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm

Ответ 6

Зависит от размера матрицы и является ли она разреженной или нет.

Для плотных матриц малого и среднего размера, я считаю, что некоторые вариации "наивного" алгоритма O (N ^ 3) являются победой, если вы обратите внимание на согласованность кеша и используйте векторные инструкции платформы.

Важное значение имеет расположение данных - в тех случаях, когда ваш стандартный макет макета является недружественным по отношению к кешу (например, майор столбца), вы должны попробовать двоичную разложение вашего умножения на матрицу - даже если вы не используете Strassen или других "быстрых" алгоритмов, этот порядок операций может привести к "отказоустойчивому" алгоритму, который автоматически использует каждый уровень кеша. Если у вас есть возможность перестроить ваши матрицы, вы можете попробовать комбинировать это с упорядочением элементов данных с чередованием (или "Z-order" ).

Наконец, помните: преждевременная оптимизация - это корень всего зла. И когда это еще не преждевременно, всегда проверяйте профиль и контрольные показатели до, во время и после оптимизации....

Ответ 7

Существует алгоритм, который вызывает Cannon algorithm алгоритм умножения распределенной матрицы. Подробнее здесь

Ответ 8

Нет никакого "наилучшего алгоритма" для всех матриц на всех современных процессорах.

Вам нужно будет провести некоторое исследование доступных методов, а затем найти подходящее решение для конкретных проблем, которые вы рассчитываете на конкретном оборудовании, с которым имеете дело.

Например, "самый быстрый" способ на вашей аппаратной платформе может заключаться в использовании "медленного" алгоритма, но попросите ваш графический процессор применить его к 256 матрицам параллельно. Или использование "быстрого" алгоритма общего назначения (mxn) может давать гораздо более медленные результаты, чем использование умноженной матрицы 3x3. Если вы действительно хотите, чтобы это было быстро, вы можете подумать о том, чтобы перейти на голый металл, чтобы убедиться, что вы лучше всего используете определенные функции ЦП, такие как инструкции SIMD, предсказание ветвлений и когерентность кэш-памяти, за счет переносимости.