Алгоритм четырёх русских

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

Разработанный комбинаторный алгоритм позволяет умножать матрицы за $O(n^3/\log n)$. С некоторыми изменениями можно получить время работы $O(n^3/{\log }^{2}n)$. В 2015 году был получен алгоритм, работающий за $\hat{O}(n^3/{\log }^{4}n)$.

Идея

Основная идея метода состоит в том, чтобы разделить матрицу на небольшие квадратные блоки размером $t\times t$ для некоторого параметра $t$ и использовать таблицу поиска для быстрого выполнения алгоритма в каждом блоке. Индекс в таблице поиска кодирует значения ячеек матрицы в верхнем левом углу границы блока до некоторой операции алгоритма, а значения в таблице поиска кодируют значения граничных ячеек в правом нижнем углу блока после операции. Таким образом, общий алгоритм может быть выполнен с использованием только $(n/t{)}^2$ блоков вместо $n^2$ ячеек матрицы, где $n$ — длина строки матрицы. Для того чтобы размер таблиц поиска (и время, необходимое для их инициализации) было достаточно малым, $t$ обычно выбирается равным $O(\log n)$.

Применение

Алгоритмы, к которым может быть применен метод четырех русских:

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

В каждом из этих случаев это ускоряет алгоритм в $\log n$ или ${\log }^{2}n$ раз.

Опубликованный Бардом алгоритм инверсии матрицы «Метод четырёх русских» реализован в библиотеке M4RI для быстрой арифметики с плотными матрицами над F2. M4RI используется SageMath и библиотекой PolyBoRi.[1]

Алгоритм умножения булевых матриц

Описание алгоритма

Алгоритм получает на вход две булевы матрицы $(n\times n)$ $A$ и $B$ и возвращает матрицу $C=AB$.

Пусть $m=\lfloor \log n\rfloor$.

Разобьём $A$ на матрицы $A_1,A_2,...,A_{\lceil n/m\rceil }$, где $A_i,1\le i<\lceil n/m\rceil$, состоит из столбцов матрицы $A$ с номерами от $m(i-1)+1$ до $mi$, а $A_{\lceil }n/m\rceil$ — из оставшихся столбцов, к которым добавлены столбцы нулей, если это нужно, чтобы в матрице было $m$ столбцов.

Разобьём $B$ на матрицы $B_1,B_2,...,B_{\lceil n/m\rceil }$, где $B_i,1\le i<\lceil n/m\rceil$, состоит из строк матрицы $B$ с номерами от $m(i-1)+1$ до $mi$, а $B_{\lceil }n/m\rceil$ — из оставшихся строк, к которым добавлены строки нулей, если это нужно, чтобы в матрице было $m$ строк.

Псевдокод

begin

  for $i\leftarrow 1$ to $\lceil n/m\rceil$ do

  begin

    comment Вычисляем суммы строк $b_1^{(i)},...,b_m^{(i)}$ матрицы $B_i$;

    СУММАСТРОК[$0$] $\leftarrow \underset{n}{\underbrace{[0,0,\cdots ,0]}}$

    for $j\leftarrow 1$ to $2^m-1$ do

    begin

      Пусть $k$ таково, что $2^k\le j<2^{k+1}$

      СУММАСТРОК[$j$]$\leftarrow$СУММАСТРОК[$j-2^k$]$+b_{k+1}^{(i)}$

    end

    Пусть $C_i$ — матрица,  i-я строка которой равна СУММАСТРОК[ЧИС($a_j$)],

    где $a_j$ — j-я строка матрицы $A_i$, $1\le j<n$,

  end;

  Пусть $C=\sum _{i=1}^{\lceil n/m\rceil }{C}_i$

end.

ЧИС(v) — целое число, представленное двоичным вектором v, записанным в двоичной системе счисления с обратным порядком разрядов. Например, ЧИС([0,1,1])=6.

Обоснование корректности

Простая индукция по $j$ показывает, что СУММАСТРОК[$j$] становится равной поразрядной булевой сумме таких строк $b_k$ матрицы $B_i$, что в двоичном представлении числа $j$ на $k$-том месте справа стоит 1. Отсюда вытекает, что $C_i=A_i{B}_i$ и $C=AB$.

Время работы

Рассмотрим цикл по $j$. Вычисление и присваивание значений СУММАСТРОК[$j$] происходит за $O(n)$. Вычисление $k$ занимает время $O(m)$. Итерация цикла выполняется за $O(n)$, всего $2^m-1$ итераций. $m<\log n$, $2^m-1<n$, следовательно весь цикл выполнится за $O((2^m-1)n)=O(n^2)$.

Вычисление ЧИС($a_j$) имеет сложность $O(m)$, а копирование вектора СУММАСТРОК[ЧИС($a_j$)] — сложность $O(n)$, так что инициализация $C_i$ выполняется за $O(n^2)$. Итого, цикл по $i$ выполняется за $O(n^2)$. Всего $\lceil n/m\rceil$ итераций. $\lceil n/m\rceil <2n/\log n$, следовательно сложность цикла — $O(n^3/\log n)$.

Сумма $C_i$ вычисляется за $O(n^2*\lceil n/m\rceil )=O(n^3/\log n)$.

Итоговая сложность алгоритма — $O(n^3/\log n)$.

История

Алгоритм был введён В. Л. Арлазаровым, Е. А. Диницем, М. А. Кронродом и И. А. Фараджевым в 1970 году. Происхождение названия неизвестно; Ахо, Хопкрофт и Ульман (1974) объясняют:

Второй метод, часто называемый алгоритмом «четырёх русских», в честь его изобретателей, в какой-то мере «практичнее» алгоритма в теореме 6.9.

Все четыре автора работали в Москве в то время.