Матричное умножение: как устроены быстрые алгоритмы и где реальная производительность.

Часть 1 из 5

Информация актуальна на август 2026 года.

Матричное умножение кажется темой из учебника: строгая формула, три цикла, ответ в ячейке. Но именно на этой операции держится огромная часть вычислений в машинном обучении, графике, симуляциях, рекомендательных системах и научных расчетах. Когда модель обучается слишком медленно, когда инференс не укладывается в задержку, когда сервер потребляет энергию, но почти не продвигается по задаче, очень часто корень проблемы находится не в «плохом алгоритме», а в том, как именно выполняется матричное умножение.

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

Отдельная боль — память. Даже быстрая клиентская DDR5 в обычном компьютере по суммарной пропускной способности все равно сильно медленнее памяти современных видеокарт и ускорителей. Поэтому большие плотные матричные умножения часто эффективнее выполнять на GPU, а не на CPU. Но это не универсальное правило: для маленьких матриц, сложных ветвящихся задач, разреженных данных или жестких требований к задержке процессор может оказаться лучше. В этой статье разберем, как отличать такие ситуации и на что смотреть в реальной работе.

---

1. Что такое матричное умножение и почему это не просто «перемножить числа»

1.1. Определение и размерности

Матричное умножение — это операция, при которой каждый элемент результирующей матрицы формируется как скалярное произведение строки первой матрицы и столбца второй матрицы. Если матрица A имеет размерность m на n, а матрица B — размерность n на p, то результат, матрица C, будет иметь размерность m на p.

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

Для элемента результата получается выражение:

C[i, j] = сумма по k от 1 до n значений A[i, k] * B[k, j]

Здесь i — номер строки результата, j — номер столбца результата, k — общий индекс, по которому происходит суммирование.

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

1.2. Где матричное умножение встречается в реальных системах

Матричное умножение — одна из самых нагружаемых операций в вычислительной технике. Оно встречается не только в академических задачах, но и в продуктах, которыми пользуются ежедневно.

Типичные области применения:

1. Машинное обучение и нейросети. Прямое распространение, обратное распространение, преобразования признаков, слои внимания, полносвязные блоки, эмбеддинги, матричные разложения — почти везде внутри лежат операции вида C = A * B или их варианты.
2. Компьютерная графика. Повороты, масштабирование, проекции, переходы между системами координат, скелетная анимация, обработка вершин — все это часто выражается через матричные преобразования.
3. Научные расчеты. Метод конечных элементов, вычислительная гидродинамика, квантовая химия, оптимизация, решение систем линейных уравнений — во многих пакетах ядром являются плотные или разреженные матричные операции.
4. Рекомендательные системы. Пользовательские и товарные представления, матричные разложения, подсчет схожести, ранжирование — все это может быть сформулировано в терминах матричных произведений.
5. Обработка сигналов и данных. Фильтры, преобразования, спектральные методы, сжатие, восстановление — часто сводятся к набору матричных операций.
6. Базы данных и аналитика. Некоторые виды агрегаций, линейные модели, вычисление признаков, векторный поиск и приближенные методы также опираются на матричные вычисления.

Особенность этой операции в том, что она одновременно и простая, и массовая. Одна матричная операция может быть небольшой, но если она выполняется миллионы раз за обучение модели, итоговая цена становится огромной.

1.3. Почему эта операция часто становится узким местом

Причина не только в количестве арифметики. Матричное умножение нагружает сразу несколько подсистем компьютера:

• вычислительные блоки процессора или видеокарты;
• кэши разных уровней;
• оперативную память;
• шины передачи данных;
• систему синхронизации потоков;
• блоки преобразования и хранения чисел разных форматов.

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

Поэтому матричное умножение — хороший тест на зрелость вычислительного конвейера. Оно быстро показывает, где система спроектирована хорошо, а где все держится на случайных настройках.

1.4. Главная мысль: производительность определяется не только формулой

Формула матричного умножения не меняется десятилетиями, но скорость реализации на одном и том же железе может отличаться в десятки и сотни раз. Причины обычно такие:

• порядок обхода данных;
• блочность;
• использование векторных инструкций;
• настройка кэша;
• выбор формата чисел;
• выбор библиотеки;
• размещение данных в памяти;
• параллелизм;
• особенности компилятора;
• размер задачи.

Именно поэтому вопрос «какая сложность у матричного умножения?» и вопрос «сколько времени займет матричное умножение?» — разные. Первый относится к абстрактной модели вычислений. Второй — к конкретной архитектуре, памяти, компилятору и данным.

---

2. Формальная запись, размеры и цена вычислений

2.1. Классическая формула покомпонентного умножения

Пусть есть матрица A размером m на n и матрица B размером n на p. Тогда результат умножения, матрица C размером m на p, задается так:

C[i, j] = сумма по k от 1 до n значений A[i, k] * B[k, j]

Это означает, что для каждого элемента результата нужно выполнить n умножений и сложить полученные произведения. Если не учитывать оптимизации, именно так выглядит базовая цена операции.

2.2. Сколько операций нужно для квадратных матриц

Если матрицы квадратные и имеют размер n на n, то результат тоже будет размером n на n. Для каждого из n² элементов нужно n умножений и примерно n сложений. Поэтому часто говорят, что классическое матричное умножение требует порядка n³ операций.

Более аккуратно:

• умножений: n³;
• сложений: примерно n³ — n²;
• суммарно операций с плавающей точкой: около 2n³.

На практике в оценке производительности часто используют именно учет умножений и сложений как отдельных операций. Поэтому для квадратной матрицы размером 1000 на 1000 получается около двух миллиардов операций. Для размера 10000 на 10000 — уже около двух триллионов операций. Это очень много, даже для современного оборудования.

2.3. Сколько операций нужно для прямоугольных матриц

Для прямоугольных матриц размерностей m на n и n на p количество умножений равно m * n * p. Суммарное число арифметических действий обычно оценивают как примерно 2 * m * n * p.

Это важно для реальных задач, потому что матрицы редко бывают идеально квадратными. Например:

• эмбеддинги могут быть узкими и длинными;
• пакеты данных могут иметь большой размер по одной оси и маленький по другой;
• слои нейросетей часто имеют форму, далекую от квадрата.

Иногда можно выбрать порядок вычислений в цепочке матриц так, чтобы уменьшить общее число операций. Это классическая задача оптимального расставления скобок при умножении нескольких матриц.

2.4. Память против операций: минимальный объем чтения и записи

Для плотного матричного умножения нужно как минимум:

• прочитать матрицу A: m * n элементов;
• прочитать матрицу B: n * p элементов;
• записать матрицу C: m * p элементов.

Если каждый элемент занимает 4 байта в формате одинарной точности, то для квадратных матриц размером n на n минимальный трафик составляет примерно 12 * n² байт. Если элементов много, даже этот минимальный объем становится большим.

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

2.5. Арифметическая интенсивность и почему она важна

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

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

---

3. Как считать матрицы вручную и какая интуиция за этим стоит

3.1. Способ «строка на столбец»

Самый известный способ — взять строку первой матрицы и столбец второй матрицы, перемножить соответствующие элементы и сложить результаты. Так получают один элемент результата. Затем переходят к следующему элементу.

Этот способ удобен для объяснения, потому что он напрямую соответствует формуле. Он хорошо показывает, почему количество столбцов первой матрицы должно совпадать с количеством строк второй.

3.2. Способ «столбец на строку»

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

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

3.3. Линейные комбинации строк и столбцов

Третий полезный взгляд: столбцы результата можно получать как линейные комбинации столбцов первой матрицы с коэффициентами из второй. Аналогично можно рассуждать и о строках.

Эта точка зрения часто помогает в линейной алгебре: становится видно, как умножение матрицы на вектор или на другую матрицу преобразует пространство признаков или координат.

3.4. Пример умножения небольшой матрицы

Пусть матрица A имеет размер 2 на 3:

Строка 1: 1, 2, 3
Строка 2: 4, 5, 6

Матрица B имеет размер 3 на 2:

Столбец 1: 7, 8, 9
Столбец 2: 10, 11, 12

Тогда результат будет размером 2 на 2.

Элемент первой строки и первого столбца:

1 * 7 + 2 * 8 + 3 * 9 = 7 + 16 + 27 = 50

Элемент первой строки и второго столбца:

1 * 10 + 2 * 11 + 3 * 12 = 10 + 22 + 36 = 68

Элемент второй строки и первого столбца:

4 * 7 + 5 * 8 + 6 * 9 = 28 + 40 + 54 = 122

Элемент второй строки и второго столбца:

4 * 10 + 5 * 11 + 6 * 12 = 40 + 55 + 72 = 167

Итоговая матрица:

50, 68
122, 167

Пример маленький, но он показывает главное: результат зависит не от простого совпадения позиций, а от согласованного суммирования по общему индексу.

3.5. Почему разные взгляды на одну операцию полезны для оптимизации

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

В инженерной практике это важно: лучшая реализация почти никогда не повторяет учебный обход «в лоб». Она использует тот способ декомпозиции операции, который лучше ложится на память и вычислительные блоки конкретного устройства.

---

4. Классический алгоритм: три цикла и скрытые проблемы

4.1. Базовый псевдокод

Самый простой вариант выглядит так:

для i от 1 до m:
для j от 1 до p:
сумма = 0
для k от 1 до n:
сумма = сумма + A[i, k] * B[k, j]
C[i, j] = сумма

Этот код верен, но почти всегда медленен. Причина не в логике, а в характере доступа к памяти.

4.2. Порядок циклов и его влияние на скорость

Три цикла можно переставлять. Например:

• внешний по i, средний по j, внутренний по k;
• внешний по i, средний по k, внутренний по j;
• внешний по j, средний по i, внутренний по k;
• и другие варианты.

Формально все они считают одно и то же, но доступ к памяти будет разным. Один порядок обеспечивает последовательное чтение данных, другой приводит к прыжкам по памяти, третьему не хватает переиспользования.

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

4.3. Размещение данных в памяти: строки и столбцы

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

Если данные лежат по строкам, то последовательное чтение строки эффективно. Если же алгоритм часто обращается к столбцам, он может постоянно попадать на разреженные обращения к памяти, потому что соседние элементы столбца в памяти далеко друг от друга.

Если данные лежат по столбцам, картина меняется. Поэтому одна и та же программа на разных библиотеках может работать по-разному.

4.4. Кэш-промахи и локальность данных

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

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

4.5. Почему «честные» три цикла почти никогда не бывают быстрыми

Наивный алгоритм легко написать и легко понять, но он не использует три важнейших ресурса:

• локальность данных;
• векторные инструкции;
• переиспользование значений в регистрах.

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

---

5. Память решает больше, чем кажется

5.1. Пропускная способность и задержка: разные виды узких мест

У памяти есть два важных параметра:

• пропускная способность — сколько байт можно передать за секунду;
• задержка — сколько времени занимает первое обращение.

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

5.2. Почему быстрая DDR5 не решает задачу сама по себе

Часто можно услышать: «Поставим быструю DDR5, и все ускорится». Это справедливо лишь частично.

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

Например, двухканальная система с быстрой DDR5 в настольном ПК может давать порядка десятков или чуть более ста гигабайт в секунду. Современные видеокарты и ускорители могут обеспечивать сотни гигабайт и даже терабайты в секунду. Разница не всегда одинакова, но для плотных матричных операций она часто решающая.

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

5.3. Сравнение памяти процессора и памяти видеокарт

Упрощенно картина выглядит так:

Система	Типичная сильная сторона	Ограничение
Центральный процессор с быстрой памятью	хорошая логика, гибкость, низкие задержки	умеренная суммарная пропускная способность памяти
Игровая или рабочая видеокарта	высокая пропускная способность, много параллельных блоков	эффективность зависит от регулярности задачи
Специализированный ускоритель	оптимизация под матричные операции и конкретные форматы чисел	меньше гибкости, выше требования к типу нагрузки

Важно не абсолютизировать. Для маленьких матриц накладные расходы на передачу данных и запуск вычислений на видеокарте могут съесть весь выигрыш. Для больших плотных матриц видеокарта чаще выигрывает. Для разреженных и нерегулярных задач результат может быть непредсказуемым без измерений.

5.4. Когда матричное умножение упирается в память

Признаки того, что узкое место — память:

• загрузка вычислительных блоков низкая, хотя задача большая;
• увеличение размера блока улучшает скорость;
• производительность сильно зависит от формата хранения;
• перестановка циклов заметно меняет результат;
• на небольших данных, которые помещаются в кэш, скорость намного выше.

В такой ситуации нужно улучшать локальность, уменьшать повторные чтения и правильно выбирать размеры блоков.

5.5. Когда матричное умножение упирается в вычисления

Иногда память справляется, а ограничение создают сами вычислительные блоки. Это бывает, когда:

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

Тогда дальнейшая оптимизация должна идти не в сторону памяти, а в сторону использования векторных инструкций, уменьшения служебных операций и выбора подходящего формата чисел.

---

6. Тайлинг, блокировка и переиспользование данных

6.1. Что такое блочное умножение матриц

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

Формула при этом не меняется. Меняется организация вычислений.

6.2. Как блоки уменьшают трафик памяти

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

Грубо говоря, вместо того чтобы читать данные и сразу их терять, система держит их поблизости и выполняет больше полезной работы на каждый байт.

6.3. Выбор размера блока под кэш

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

Универсального размера нет. Он зависит от:

• объема кэша;
• размера регистров;
• формата чисел;
• архитектуры;
• способа параллелизма;
• требований к задержке.

6.4. Микро-ядро и регистровая блокировка

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

Регистровая блокировка позволяет уменьшить обращения к памяти и кэшу. Это один из главных приемов, который отличает учебный код от промышленного.

6.5. Почему блочный подход стал основой промышленных библиотек

Почти все серьезные библиотеки матричных операций используют блочные схемы. Причина проста: они позволяют получить высокую производительность на разных архитектурах, не меняя саму математическую операцию.

Блочность — это мост между абстрактной формулой и реальным железом. Без нее даже очень быстрый процессор будет простаивать, ожидая данные.

---

7. Быстрые теоретические алгоритмы

7.1. Алгоритм Штрассена: меньше умножений, больше сложений

Алгоритм Штрассена, предложенный в 1969 году, показал, что матрицы можно умножать быстрее классического метода. Для квадратных матриц он уменьшает количество рекурсивных умножений за счет большего числа сложений.

Классический подход требует 8 умножений для блока 2 на 2. Алгоритм Штрассена обходится 7 умножениями, но добавляет больше сложений. В теории это снижает показатель степени со строгих 3 до примерно 2,807.

7.2. Практические пределы алгоритма Штрассена

Несмотря на красивую идею, алгоритм Штрассена не всегда полезен на практике. Причины:

• накладные расходы на сложения;
• повышенные требования к памяти;
• возможное ухудшение числовой устойчивости;
• эффективность только на достаточно больших размерах;
• сложность реализации и отладки.

В реальных библиотеках его используют ограниченно и не всегда по умолчанию. Для большинства рабочих задач тщательно оптимизированный классический блочный алгоритм оказывается быстрее и надежнее.

7.3. Алгоритмы Копперсмита — Винограда и дальнейшие улучшения

Существуют и более сложные теоретические алгоритмы, например алгоритм Копперсмита — Винограда и его последующие улучшения. Они еще сильнее снижают теоретическую оценку сложности.

К 2026 году лучшие известные теоретические оценки находятся вблизи показателя 2,37 для квадратных матриц. Это важный научный результат, но он не означает, что такие алгоритмы следует использовать в обычных программах.

7.4. Теоретическая сложность и практическая неприменимость

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

Кроме того, они могут быть неудобны для памяти, параллелизма и точности. Поэтому в инженерных системах побеждает не самый «быстрый на бумаге» алгоритм, а тот, который лучше использует конкретное железо.

7.5. Автоматизированный поиск алгоритмов и его реальный смысл

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

Это интересное направление, но его не стоит переоценивать. Для большинства практических задач по-прежнему важнее:

• хорошая библиотека;
• правильный формат данных;
• подходящий тип чисел;
• настройка под память и кэш;
• эффективный параллелизм.

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

---

8. Редкие матрицы и особые структуры

8.1. Разреженные матрицы и форматы хранения

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

Типичные варианты:

• список ненулевых элементов с индексами;
• построчное сжатие;
• по-столбцовое сжатие;
• координатный формат;
• блочные разреженные форматы.

Выбор формата влияет не только на объем памяти, но и на скорость доступа, параллелизм и совместимость с библиотеками.

8.2. Когда разреженность дает выигрыш

Разреженность помогает, если:

• нулей действительно много;
• структура данных регулярна;
• формат хорошо подходит для задачи;
• библиотека умеет эффективно работать с этим форматом;
• не возникает чрезмерных накладных расходов на индексы.

В таких случаях можно сильно сократить и объем вычислений, и объем памяти.

8.3. Когда разреженность мешает

Иногда разреженная матрица работает медленнее плотной, даже если ненулевых элементов немного. Причины:

• нерегулярные обращения к памяти;
• много служебных данных;
• ветвления и сложная логика обхода;
• плохая загрузка векторных блоков;
• неэффективный параллелизм.

Поэтому правило «если матрица разреженная, она всегда быстрее» ошибочно. Нужно измерять.

8.4. Симметричные, диагональные, блочно-диагональные матрицы

Если у матрицы есть структура, это можно использовать. Диагональную матрицу не нужно умножать как плотную. Симметричную можно хранить компактнее. Блочно-диагональная структура позволяет разбить задачу на независимые подзадачи.

Такие свойства часто важнее, чем попытка применить универсальный быстрый алгоритм ко всему подряд.

8.5. Матрицы низкого ранга и приблизительные методы

Если матрица хорошо приближается произведением более узких матриц, можно использовать низкоранговые разложения. Это не точное умножение исходных больших матриц, но во многих прикладных задачах допустимо.

Такие методы используют в сжатии, рекомендациях, графике и машинном обучении. Главное — понимать, где ошибка приближения допустима, а где она разрушает результат.

---

Часть 1 из 5