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

Дано две квадратных матрицы [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].

Сейчас будет показано, как немного уменьшить это время.

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

Для выполнения сжатия матриц выполним следующий предподсчёт : для всех возможных пар двоичных векторов длины [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]

Пример работы алгоритма

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

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

[math] k = log_2 n = log_2 4 = 2[/math], то предподсчитаем все скалярные произведения:

Для удобства каждому битовому вектору будет соответствовать десятичное число, т.е. [math] 00 = 0 [/math], [math] 01 = 1 [/math], [math] 10 = 2 [/math], [math] 11 = 3 [/math], тогда ниже приведена таблица, в которой записаны все искомые произведения:

[math] \begin{tabular}{|c|c|c|c|c|} \hline & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} \\ \hline \textbf{0} & 0 & 0 & 0 & 0 \\ \hline \textbf{1} & 0 & 1 & 0 & 1 \\ \hline \textbf{2} & 0 & 0 & 1 & 1 \\ \hline \textbf{3} & 0 & 1 & 1 & 0\\ \hline \end{tabular} [/math]

Согласно соглашению относительно битовых векторов и соответствующих им десятичным числам получим новые матрицы [math] A' [/math] и [math] B' [/math]:

[math] A' = [/math] [math] \left(\begin{array}{cccc} 1 & 3 \\ 1 & 0 \\ 3 & 1 \\ 2 & 1 \end{array}\right) [/math] , [math] B' = [/math] [math] \left(\begin{array}{cccc} 2 & 0 & 1 & 3 \\ 2 & 1 & 2 & 1 \end{array}\right) [/math]

Перемножим эти матрицы по модулю два с использованием нашего предпосчета:

[math] C = A' * B' = [/math] [math] \left(\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array}\right) [/math]

Матрица [math] C [/math] - искомая.

Код алгоритма

  // Чтение матриц
  for i := 0 to n - 1
     for j := 0 to n - 1 {
        read(cur);
        a[i][j] = cur;
     }   
  for i := 0 to n - 1
     for j := 0 to n - 1 {
        read(cur);
        b[i][j] = cur;
     }   
       
  // Предподсчёт скалярных произведений
  // Пусть preСalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j
  // "&" - битовый and; "**" - возведение в степень.
  int k = ceil(log2(n)); //округление вверх
  for i := 0 to (2 ** k) - 1
     for j := 0 to (2 ** k) - 1 {
        int scalMul = 0;
        for pos := 0 to k - 1
           if (((2 ** pos) & i) != 0 and ((2 ** pos) & j) != 0) {  
              scalMul = (scalMul + 1) mod 2;
           }
        preСalc[i][j] = scalMul;
     }
  
  // Создание сжатых матриц anew, bnew
  for i := 0 to n - 1 {
     while (start < n) {
        int curSumA = 0, curSumB = 0, curPos = start, deg = (2 ** (k - 1));
        while (curPos < start + k and curPos < n) {
           curSumA = curSumA + a[i][curPos] * deg;
           curSumB = curSumB + b[curPos][i] * deg;
           deg = deg div 2;
           curPos = curPos + 1;
        }
        anew[i][start div k] = curSumA;
        bnew[start div k][i] = curSumB;
        start = start + k;
     }
  }
  
  //Перемножение полученных матриц
  for i := 0 to n - 1
     for j := 0 to n - 1 {
        int curAns = 0;
        for pos := 0 to m - 1 {
           curAns = (curAns + preСalc[anew[i][pos]][bnew[pos][j]]) mod 2;
        }
        ans[i][j] = curAns;
  }

  // Вывод ответа
  for i := 0 to n - 1
     for j := 0 to n - 1 {
        write(ans[i][j]);
     }
     writeln();
  }

Литература

• Gregory V. Bard — Accelerating Cryptanalysis with the Method of Four Russians