Про умножение матриц или как курс по вычислительной линейной алгебре проигрывает жестокой реальности
Мы умеем умножать матрицы быстрее, чем за O(N^3)! По крайней мере, так рассказывают на курсе по алгоритмам. Потом теория сталкивается с "железом", и выясняется, что в DL этим почти никто не пользуется. Но почему?
Для начала вспомним базовые факты про умножение матриц:
- У нас есть матрицы A (b * d) и B (d * k);
- При их умножении нам нужно сделать одно сложение и одно умножение для каждого элемента в паре "строка–столбец";
- Получается b * d * k таких троек для каждой операции;
- Итого 2 * b * d * k троек;
Для квадратных матриц это упрощается до 2 * n^3, то есть O(n^3).
Умный дядька Штрассен когда-то предложил алгоритм, который уменьшает число умножений за счёт рекурсивного разбиения матриц. В сухом остатке теоретическая сложность падает примерно до O(N^2.7).
Сегодня я смотрел лекции "LLM from Scratch" и заметил, что они считают FLOPs что называется "в лоб" - будто в PyTorch используется наивное умножение матриц (скрин из лекции выше). Сначала подумал, что это просто упрощение, чтобы не уходить в численные методы линейной алгебры, но решил копнуть глубже.
Выяснилось, что в DL практически никто не использует алгоритм Штрассена (и его современные, ещё более эффективные аналоги)!
Во-первых, он менее численно устойчив из-за сложений и вычитаний промежуточных подматриц.
Во-вторых, он плохо стыкуется со специализированными тензорными ядрами, которые выполняют операции Matrix Multiply-Accumulate (MMA, `D = A * B + C`) на маленьких матрицах фиксированного размера.
В-третьих, из-за рекурсивной структуры он сильно менее эффективен с точки зрения работы с памятью и кэшем.
Реальность vs теория — 1:0
9
3
2November 28, 2025 1.8K 11 5
