Как BLAS включает оптимизацию умножения матричной цепочки

Question

BLAS (базовые подпрограммы линейной алгебры) предоставляют многие другие языки программирования, такие как Matlab, которые я использую, с быстрыми процедурами, чтобы делать такие вещи, как матричное умножение.

Однако при умножении нескольких матриц существует оптимальный порядок «скобки» матриц. Взятые из wikipedia article:

Например, предположим, что А представляет собой 10 × 30 матрица, В представляет собой 30 × 5 матрицы, а С представляет собой 5 × 60 матрица. Затем

(АВ) С = (10 × 30 × 5) + (10 × 5 × 60) = 1500 + 3000 = 4500 операций

А (ВС) = (30 × 5 × 60) + (10 × 30 × 60) = 9000 + 18000 = 27000 операций.

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

Answer 1

Каноническое определение BLAS можно найти here и не включает вызов с несколькими матрицами. Поэтому я не ожидаю, что какая-либо реализация, которая следует этому определению, обеспечивает оптимизацию цепочки, которую вы упомянули. Трудно дать окончательный ответ, потому что BLAS был до смерти за последние 30 лет, поэтому есть many implementations, и кто знает, может быть, какой-то скучный студент PhD решил сделать это в какой-то момент :)

Это, как говорится, есть реализации, которые являются similar but not compatible with BLAS, как Eigen, которые используют такие функции, как Выражение шаблонов (...) для разумного удаления временных рядов и обеспечения ленивой оценки, когда это уместно. Это что-то многообещающее, но применимо ли оно к цепочке матриц, о которой я действительно не знаю. Я не подозреваю, судя по тому, что его не включили в их benchmark.

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