28. Эффективная реализация алгоритмов вычисления произведения матриц.

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

1. Наивное умножение (стандартный алгоритм).

Пусть есть матрица  размера  и матрица  размером . Матрица  – результат произведения размера :

Для умножения матриц требуется (при ):  умножений и  суммирований  Сложность наивного алгоритма: .

2. Блочное умножение.

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

Размер блока напрямую зависит от архитектуры вычислительной системы и определяет время выполнения умножения. Аналогичный подход применяется при умножении матриц с использованием GPU с оптимизацией использования разделяемой памяти ограниченного объёма.

(по сути то же наивное умножение, но блоками в целях оптимизации затрат памяти и времени)

3. Алгоритм Штрассена (см. вопрос 29).

4. Алгоритм Копперсмита–Винограда.

Алгоритм Копперсмита–Винограда  улучшенная версия Штрассена с вычислительной сложностью . Обладает лучшей асимптотикой среди известных алгоритмов умножения матриц.

На практике алгоритм Копперсмита–Винограда не используется, так как он имеет очень большую константу пропорциональности и начинает выигрывать в быстродействии у других известных алгоритмов только для матриц, размер которых превышает память современных компьютеров.

5. Реализация в numpy.

NumPy использует BLAS (Basic Linear Algebra Subprograms) – высокооптимизированные низкоуровневые библиотеки, предназначенные для выполнения основных операций линейной алгебры.

Сложность: .

Почему NumPy эффективен?