Каков наилучший алгоритм умножения матрицы? Что значит «лучшее для меня? Это самый быстрый и готовый к сегодняшним машинам.Каков наилучший алгоритм умножения матрицы?
Просьба указать ссылки на псевдокод, если сможете.
BLAS - лучшая готовая к использованию библиотека эффективного умножения матриц. Существует много разных вариантов реализации. Вот тест я сделал для некоторых реализаций на MacBook Pro с двухъядерным процессором Intel Core 2 Duo 2,66 ГГц:
Есть также другие коммерческие реализации, которые я не проверял здесь:
Существует алгоритм, который вызывает алгоритм умножения распределенной матрицы Cannon's algorithm. Подробнее here
Почему псевдокод? Зачем это реализовать? Если вам нужна скорость, есть очень оптимизированные алгоритмы, которые включают в себя оптимизацию для определенных наборов инструкций (например, SIMD), реализация которых сама по себе не дает никакой реальной выгоды (кроме обучения),
Посмотрите на разные BLAS реализации, как:
лучший алгоритм умножения матриц является один, что кто-то с детального архитектурного знания уже вручную настроены для вашей цели мн.ч. atform.
Существует множество хороших библиотек, которые предоставляют настроенные преобразования с матричным умножением. Используйте один из них.
Есть, вероятно, лучшие, но это те, которые я возглавляю (лучше, чем стандартный алгоритм кубической сложности).
Strassen's - O (N^2,8)
Coppersmith Winograd - O (N^2,376)
Там нет "лучший алгоритм" для всех матриц на всех современных процессорах.
Вам нужно будет провести исследование многих доступных методов, а затем найти наилучшее решение конкретных проблем, которые вы рассчитываете на конкретном оборудовании, с которым имеете дело.
Например, «самый быстрый» способ на аппаратной платформе может заключаться в использовании «медленного» алгоритма, но попросите ваш графический процессор применить его к 256 матрицам параллельно. Или использование «быстрого» алгоритма общего назначения (mxn) может давать гораздо более медленные результаты, чем использование умноженной матрицы 3x3. Если вы действительно хотите, чтобы это было быстро, вы можете подумать о том, чтобы перейти на голый металл, чтобы убедиться, что вы лучше всего используете определенные функции ЦП, такие как инструкции SIMD, предсказание ветвей и когерентность кэш-памяти, за счет переносимости.
Зависит от размера матрицы и является ли она разреженной или нет.
Для малых и средних плотных матриц, я считаю, что некоторые вариациями на «наивный» O (N^3) алгоритмом является победой, если обратить внимание на кэш-когерентность и использовать платформы векторные инструкции.
Важное значение имеет расположение данных - в тех случаях, когда стандартная матрица нечеткая (например, столбца-майор * строка-майор), вы должны попробовать двоичную разложение вашего умножения на матрицу - даже если вы этого не сделаете используйте алгоритмы Strassen или другие «быстрые» алгоритмы, этот порядок операций может дать «алгоритм без кэша», который автоматически использует каждый уровень кеша.Если у вас есть роскошь для изменения ваших матриц, вы можете попробовать объединить это с упорядочением элементов данных с чередованием (или «Z-order»).
Наконец, помните: преждевременная оптимизация - это корень всего зла. И когда это не преждевременная больше, всегда профиля & теста до, во время и после оптимизации ....
Вот алгоритмы курс MIT и умножение матриц лекция
матрицы умножение - O (N^3)
Штрассена алгоритм - О (п^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
Как бы вы умножаете матрица вручную? – 2010-12-15 22:35:12
Вы хотите один для общих матриц, или у вас есть какие-либо полезные ограничения на матрицы, такие как верхняя треугольная или диагональная? – 2010-12-15 22:36:27
Это для программы, или что-то еще, как школьная работа? Матричное умножение довольно просто; 1) убедитесь, что размеры согласуются (например, 3x3 * 3x1, а не 3x3 * 1x3), 2) умножьте соответствующие поля вместе и добавьте, чтобы они попали в конечное поле. http://en.wikipedia.org/wiki/Matrix_multiplication – Eaglebird 2010-12-15 22:38:23