Умножение матриц – одна из ключевых операций в линейной алгебре, машинном обучении и научных вычислениях. Для его эффективной реализации создано огромное количество методов.
1. Наивное умножение (стандартный алгоритм).
Пусть есть матрица размера
и матрица
размером
. Матрица
– результат произведения размера
:
Для умножения матриц требуется (при ):
умножений и
суммирований
Сложность наивного алгоритма:
.
2. Блочное умножение.
С целью повышения эффективности использования кэш-памяти CPU существует алгоритм блочного умножения матриц, в котором результирующая матрица формируется поблочно с использованием известной формулы , либо её более быстрых аналогов, а размер обрабатываемых данных на каждой итерации не превышает ёмкость кэш-памяти. Сложность:
.
Размер блока напрямую зависит от архитектуры вычислительной системы и определяет время выполнения умножения. Аналогичный подход применяется при умножении матриц с использованием GPU с оптимизацией использования разделяемой памяти ограниченного объёма.
(по сути то же наивное умножение, но блоками в целях оптимизации затрат памяти и времени)
3. Алгоритм Штрассена (см. вопрос 29).
4. Алгоритм Копперсмита–Винограда.
Алгоритм Копперсмита–Винограда – улучшенная версия Штрассена с вычислительной сложностью . Обладает лучшей асимптотикой среди известных алгоритмов умножения матриц.
На практике алгоритм Копперсмита–Винограда не используется, так как он имеет очень большую константу пропорциональности и начинает выигрывать в быстродействии у других известных алгоритмов только для матриц, размер которых превышает память современных компьютеров.
5. Реализация в numpy.
NumPy использует BLAS (Basic Linear Algebra Subprograms) – высокооптимизированные низкоуровневые библиотеки, предназначенные для выполнения основных операций линейной алгебры.
Сложность: .
Почему NumPy эффективен?