Метод чотирьох українців для множення матриць

Якщо ми вважатимемо твір матриць [math]C = A \cdot B[/math] за визначенням [math]\left(c_ = \sum\limits_^n a_b_\right)[/math] , то складність роботи алгоритму складе [ math]O(n^3)[/math] — кожен із [math]n^2[/math] елементів результуючої матриці [math]C[/math] обчислюється за час, пропорційне [math]n[/math] .

Наразі буде показано, як трохи зменшити цей час.

Для виконання стиснення матриць виконаємо наступний передрахунок: для всіх можливих пар двійкових векторів довжини [math]k[/math] підрахуємо та запам'ятаємо їх скалярний твір за модулем [math]2[/math].

Візьмемо першу матрицю. розділимо кожен її рядок на шматки розміру [math]k[/math]. Для кожного шматка визначимо номер двійкового вектора, який відповідає числам, що знаходяться на цьому шматку. Якщо шматок вийшов нерівним по довжині [math]k[/math] (останній шматок рядка), то вважатимемо, що в кінці в ньому йдуть нулі, що не впливають на множення. Отримаємо матрицю [math]A'_ \rceil>[/math] .

Аналогічно зробимо з матрицею [math]B[/math] замість рядків ділячи стовпці. Отримаємо матрицю [math]B'_[/math].

Тепер, якщо замість добутку матриць [math]A[/math] і [math]B[/math] вважати добуток нових матриць [math]A'[/math] і [math]B'[/math] , скориставшись порахованими скалярними творами, то кожен елемент матриці [math]C[/math] буде виходити вже за час, пропорційне [math]\lceil \dfrac \rceil[/math] замість [math]n[/math] , і час твору матриць скоротиться з [math]O(n^3)[/math] до [math]O(n^2 \cdot\dfrac nk) = O(\dfrac) [/math] .

метод

Оцінимо асимптотику даного алгоритму.

  • Передрахунок скалярних творів працює за [math]O(2^k)[/math] .
  • Створення матриць [math]A'[/math] та [math]B'[/math] -[math]O(n^2)[/math] .
  • Перемноження отриманих матриць - [math]O(\dfrac)[/math].

Усього: [math]O(2^k) + O(\dfrac)[/math] . Вибравши [math]k = \log n [/math], отримуємо необхідну асимптотику [math]O(n^2 \log n) + O(\dfrac) = O(\dfrac)[/math]

Розглянемо роботу алгоритму з прикладу перемноження двох матриць [math] A [/math] і [math] B [/math] , де

[math] A = [/math] [math] \left(\begin 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 &0&0&1\end\right) [/math] , [math] B = [/math] \\ 0 &0 &1 &1 \\1 &0 &1 &0 \\ 0 &1 &

[math] k = \log_2 n = \log_2 4 = 2[/math] , то передрахуємо всі скалярні твори:

Для зручності кожному битовому вектору буде відповідати двійкове число з провідними нулями, тобто. у цьому випадку маємо числа [math] 00 [/math] , [math] 01 [/math] , [math] 10 [/math] , [math] 11 [/math] . Нижче наведено таблицю, в якій записані всі шукані твори:

[math] \begin \hline & \textbf & \textbf & \textbf & \textbf \\ \hline \textbf & 0 & 0 & 0 & 0 \\ \hline \textbf & 0 & 1 & 0 & 1 \\ \hline \textbf & 0 & 0 & 1 & 1 \\ \hline \textbf & 0 & 1 & 1 & 0\\hline\end[/math]

Відповідно до угоди щодо бітових векторів та двійкових чисел отримаємо нові матриці [math] A' [/math] і [math] B' [/math] :

[math] A' = [/math] [math] \left(\begin 01 & 11 \\ 01 & 00 \\ 11 & 01 \\ 10 & 01 \end\right) [/math] , [math] B' = [/math] [math] \left(\begin 10 & 00 & 01 & 11 \\ 10 & 01 & 10 & 01 \end\right)[/math]

Перемножимо ці матриці за модулем два з використанням нашого передрахунку:

[math] C = A' \times B' = [/math] [math] \left(\begin 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 &1 &1 \\ 1 &1 &0 &0 \end\right) [/math]