Метод чотирьох росіян

В інформатиці, метод чотирьох росіян— це техніка пришвидшення алгоритму, що використовує булеві матриці або, загальніше, алгоритмів, що використовують матриці в яких кожна комірка може набувати обмеженої кількості можливих значень.

Розроблений комбінаторний алгоритм дозволяв множити булеві матриці за $O\left({\frac {n^{3}}{\log n}}\right)$. З маленькою зміною алгоритм може працювати за $O\left({\frac {n^{3}}{\log ^{2}n}}\right)$. Станом на 2015 було вже отримано алгоритм, що працює за $O\left({\frac {n^{3}}{\log ^{4}n}}\right)$.

Алгоритм

Нехай $A$ і $B$ будуть $n\times n$ булевими матрицями. Обираючи довільне $\epsilon$ можна розбити $A$ на блоки розміру $\epsilon \log n\times \epsilon \log n$. Позначимо кожен такий блок через $A_{ij}$, тоді $1\leq i,j\leq {\frac {n}{\epsilon \log n}}$.

Для кожної двійки $i,j$ створюємо таблицю пошуку $T_{ij}$ згідно з такою специфікацією:

для кожного бітового вектора $v$ завдовжки $\epsilon \log n$: $T_{ij}[v]=A_{ij}\cdot v$.

Маємо, що $|T_{ij}|=n^{\epsilon }\epsilon \log n$.

Час необхідний для обчислення всіх таблиць асимптотично становить:

$\left({\frac {n}{\log n}}\right)^{2}n^{\epsilon }\log ^{2}n=n^{2+\epsilon }$,

бо всього $\left({\frac {n}{\log n}}\right)^{2}$ двійок $i,j$, $n^{\epsilon }$ векторів $v$ і обчислення $A_{ij}v$ потребує $O(\log ^{2}n)$ для сталої $\epsilon$.

Щодо матриці $B$, то кожен її стовпчик можна розбити на ${\frac {n}{\epsilon \log n}}$ частин. Нехай $B_{j}^{k}$ буде $j-$й шматок $k-$го стовпчика. Кожен добуток $A_{ij}B_{j}^{k}$ можна обчислити за сталий час, бо ми вже маємо обчислені таблиці.

Щоб обчислити $Q=AB$, можна зробити наступне.

Для $j\in [1..{\frac {n}{\epsilon \log n}}]$ : $Q_{ij}=Q_{ik}\lor (A_{ij}\cdot B_{j}^{k})$ (за означенням булевого добутку матриць). Таким чином, час потрібний для виконання алгоритму становить

$O\left(n\cdot {\frac {n}{\log n}}^{2}\cdot \log n\right)=O\left({\frac {n^{3}}{\log n}}\right)$.

Передобчисливши всі можливі побітові $\lor$ у таблицю $S$ так, що $S(u,v)=u\lor v$, де $u,v\in \{0,1\}^{\epsilon \log n}$, можна зменшити час виконання до $O\left({\frac {n^{3}}{\log ^{2}n}}\right)$.

Історія

Алгоритм запропонували Арлазаров, Дініц, Кронрод і Фараджев в 1970. Походження назви невідоме; пояснюють:

Другий метод, часто згадуваний як алгоритм «чотирьох росіян», через кількість і громадянство його винахідників, що «практичніше» ніж алгоритм в теоремі 6.9.

Всі чотири автори працювали тоді в Москві.

Примітки

• Арлазаров; Дініц; Кронрод; Фараджев (1970), Про ощадну побудову транзитивного замикання орієнтованого графу, Доповіді академії наук СРСР, 194 (11). Оригінальна назва: "Об экономном построении транзитивного замыкания ориентированного графа".
• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), The design and analysis of computer algorithms, Addison-Wesley