Метод четырёх русских для умножения матриц

Постановка задачи

Рассмотрим следующую задачу: «Дано две квадратных матрицы [math]A_{[n \times n]}[/math] и [math]B_{[n \times n]}[/math], Состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю [math]2[/math].»

Простое решение

Если мы будем считать произведение матриц [math]C = A \cdot B[/math] по определению([math]c_{i, j} = \sum\limits_{k = 1}^n a_{i,k}b_{k,j}[/math]), то трудоёмкость алгоритма составит [math]O(n^3)[/math] — каждый из [math]n^2[/math] элементов результирующей матрицы [math]C[/math] вычисляется за время, пропорциональное [math]n[/math].

Хочется большего меньшего...

Предподсчёт

Воспользуемся следующим TODO: ну не уместно здесь это словосочетание финтом ушами. Возьмём некоторое целое число [math]k[/math]. Для всех пар двоичных векторов длины [math]k[/math] подсчитаем их скалярное произведение по модулю [math]2[/math].

Сжатие матриц

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

Возьмём первую матрицу. разделим каждую её строку на куски размера [math]k[/math]. В каждый кусок запишем номер двоичного вектора, который соответствует числам, которые находятся на этом куске. Если кусок получился неравным по длине [math]k[/math](последний кусок строки), то будем считать, что в нём в конце идут не влияющие на умножение нули. Получим матрицу [math]A'_{n \times \lceil\frac{n}{k} \rceil}[/math].

Аналогично поступим с матрицей [math]B[/math], вместо строк деля столбцы. Получим матрицу [math]B'_{\lceil\frac nk\rceil\times n}[/math].

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

Оценка трудоёмкости и выбор k

Оценим трудоёмкость данного алгоритма.

• Предподсчёт скалярных произведений работает за [math]O(2^{2k}k)[/math].
• Создание матриц [math]A'[/math] и [math]B'[/math] — [math]O(N^2)[/math]
• Перемножение полученных матриц — [math]O(\frac{n^3}{k})[/math]

Итого: [math]O(2^{2k}k) + O(\frac{n^3}{k})[/math].

Взяв [math]k = \log n[/math], получаем итоговую трудоёмкость [math]O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})[/math]