Efficient AI

Блок 1. Матричное умножение. Алгоритмические методы ускорения
Константин Кориков
Где мы?
  • 📍Вводная
  • 🫠
  • Блок 1
  • Блок 2
  • 🏝️1 мая
  • 🌹9 мая
  • Блок 3
  • 👨‍💻
  • 👨‍💻
  • ☠️Экзамен
Содержание
  • Наивное матричное умножение
  • Улучшенное матричное умножение
  • Можно ли улучшить ещё?
Матрица

Это матрица?

Матрица

Прямоугольная таблица чисел

Действия над матрицами
  • Сложение
  • Умножение на число
  • Матричное умножение
Матричное умножение

$$ C_{ij} = \sum_{k=1}^{n} A_{ik} \cdot B_{kj} $$

Наивный алгоритм

for i in range(n):
    for j in range(m):
        for k in range(p):
            C[i][j] += A[i][k] * B[k][j]
Умножение блоками

$$ \begin{pmatrix} \color{red}{c_{11}} & \color{red}{c_{12}} & \color{blue}{c_{13}} & \color{blue}{c_{14}} \\ \color{red}{c_{21}} & \color{red}{c_{22}} & \color{blue}{c_{23}} & \color{blue}{c_{24}} \\ \color{green}{c_{31}} & \color{green}{c_{32}} & \color{purple}{c_{33}} & \color{purple}{c_{34}} \\ \color{green}{c_{41}} & \color{green}{c_{42}} & \color{purple}{c_{43}} & \color{purple}{c_{44}} \end{pmatrix} = \begin{pmatrix} \color{red}{a_{11}} & \color{red}{a_{12}} & \color{blue}{a_{13}} & \color{blue}{a_{14}} \\ \color{red}{a_{21}} & \color{red}{a_{22}} & \color{blue}{a_{23}} & \color{blue}{a_{24}} \\ \color{green}{a_{31}} & \color{green}{a_{32}} & \color{purple}{a_{33}} & \color{purple}{a_{34}} \\ \color{green}{a_{41}} & \color{green}{a_{42}} & \color{purple}{a_{43}} & \color{purple}{a_{44}} \end{pmatrix} \begin{pmatrix} \color{red}{b_{11}} & \color{red}{b_{12}} & \color{blue}{b_{13}} & \color{blue}{b_{14}} \\ \color{red}{b_{21}} & \color{red}{b_{22}} & \color{blue}{b_{23}} & \color{blue}{b_{24}} \\ \color{green}{b_{31}} & \color{green}{b_{32}} & \color{purple}{b_{33}} & \color{purple}{b_{34}} \\ \color{green}{b_{41}} & \color{green}{b_{42}} & \color{purple}{b_{43}} & \color{purple}{b_{44}} \end{pmatrix} $$

Оценить сложность можно основной теоремой о рекуррентных соотношениях

Трюки
New Breakthrough Brings Matrix Multiplication Closer to Ideal. Merrill Sherman/Quanta Magazine
Что заметил Виноград?

Winograd, 1967

$$ a^T b = \sum_{i=1}^{n/2} (a_{2i-1} + b_{2i})(a_{2i} + b_{2i-1}) - \sum_{i=1}^{n/2} a_{2i-1}a_{2i} - \sum_{i=1}^{n/2} b_{2i-1}b_{2i} $$

Что заметил Штрассен?

Strassen, 1969

$$ \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix} = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix} $$

$$ P_1 = (A_{11} + A_{22})(B_{11} + B_{22}) $$ $$ P_2 = (A_{21} + A_{22})B_{11} $$ $$ P_3 = A_{11}(B_{12} - B_{22}) $$ $$ P_4 = A_{22}(B_{21} - B_{11}) $$ $$ P_5 = (A_{11} + A_{12})B_{22} $$ $$ P_6 = (A_{21} - A_{11})(B_{11} + B_{12}) $$ $$ P_7 = (A_{12} - A_{22})(B_{21} + B_{22}) $$

$$ C_{11} = P_1 + P_4 - P_5 + P_7 $$ $$ C_{12} = P_3 + P_5 $$ $$ C_{21} = P_2 + P_4 $$ $$ C_{22} = P_1 + P_3 - P_2 + P_6 $$

Что нашли в DeepMind?
Сравнение сложности ранее известных алгоритмов умножения матриц с алгоритмами, открытыми DeepMind
Что нашли в DeepMind?

$$ C_{ij} = \sum_k T_{ijk} A_{ik} B_{kj} $$


Перерыв
Вопрос

Как проверить правильность матричного умножения?

$$ C \overset{?}{=} AB $$

Алгоритм Фрейвальдса
  • Есть 3 матрицы $\mat{A}$, $\mat{B}$, $\mat{C}$
  • Выберем случайный вектор $x$ из 0 и 1
  • Сравним $\mat{A}(\mat{B}x)$ и $\mat{C}x$
  • Повторить $k$ раз
Вопрос

Как посчитать матричное умножение приближённо, но быстрее?

$$ C \approx AB $$

constantine.korikov@gmail.com