Каков самый быстрый способ умножения матрицы?

Question

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

• итерационного алгоритма
• Разделить и алгоритм властвуй
• Sub кубические алгоритмы
• Shared Memory параллелизм

Если кому-то нужен разъяснения по методам, перечисленным мной, или по вопросу в целом, не стесняйтесь спрашивать.

Answer 1

Алгоритм Strassen и наивный (O (n^3)) один из них наиболее используются на практике.

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

Как уже указывалось, вы можете использовать библиотеку, такую ​​как ATLAS, которая будет автоматически настраивать алгоритм в зависимости от характеристик платформы, на которой вы выполняете, например. Размер кеша L1/L2.

Answer 2

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