Metoda czterech Rosjan

W informatyce Metoda Czterech Rosjan jest techniką przyspieszania algorytmów wykorzystujących macierze boolowskie lub bardziej ogólnie algorytmów wykorzystujących macierze, w których każda komórka może przyjmować tylko ograniczoną liczbę możliwych wartości.

Pomysł

Główną ideą tej metody jest podzielenie macierzy na małe kwadratowe bloki o rozmiarze $t \times t$ dla pewnego parametru $t$ i użycie tabeli przeglądowej do szybkiego wykonania algorytmu w każdym bloku. Indeks w tabeli przeglądowej koduje wartości komórek macierzy w lewym górnym rogu granicy bloku przed wykonaniem jakiejś operacji algorytmu, a wynik tabeli przeglądowej koduje wartości komórek granicznych w prawym dolnym rogu bloku po operacji. W ten sposób cały algorytm można wykonać, działając tylko na $(n / t) 2$ bloki zamiast $n 2$ komórek macierzy, gdzie $n$ jest długością boku macierzy. Aby rozmiar tabel przeglądowych (i czas potrzebny do ich zainicjowania) był wystarczająco mały, $t$ jest zwykle wybierane jako $O (log n)$ .

Aplikacje

Algorytmy, do których można zastosować metodę czterech Rosjan, obejmują:

obliczenie domknięcia przechodniego grafu,
Mnożenie macierzy boolowskiej ,
obliczenia odległości ,
dopasowanie sekwencji ,
obliczanie indeksu dla binarnego pomieszanego dopasowywania wzorców.

W każdym z tych przypadków przyspiesza algorytm o jeden lub dwa czynniki logarytmiczne .

Algorytm odwracania macierzy Metoda Czterech Rosjan opublikowany przez Barda jest zaimplementowany w bibliotece M4RI dla szybkiej arytmetyki z gęstymi macierzami na F ₂ . M4RI jest używany przez SageMath i bibliotekę PolyBoRi.

Historia

Algorytm został wprowadzony przez VL Arlazarova , EA Dinica, MA Kronroda i IA Faradževa w 1970 roku. Pochodzenie nazwy jest nieznane; Aho, Hopcroft i Ullman (1974) wyjaśniają:

Druga metoda, często nazywana algorytmem „czterech Rosjan”, ze względu na liczność i narodowość jej wynalazców, jest nieco bardziej „praktyczna” niż algorytm z Twierdzenia 6.9.

Wszyscy czterej autorzy pracowali wówczas w Moskwie w Rosji .

Notatki

Arłazarow, W. ; Dinic, E.; Kronrod, M.; Faradžev, I. (1970), „O ekonomicznej konstrukcji przechodniego domknięcia grafu skierowanego”, Dokl. Akad. Nauk SSSR , 194 (11) . Tytuł oryginalny: "Об экономном построении транзитивного замыкания ориентированного графа", publikacja w Доклады Академии Наук СССР 134 (3), 1970.
Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), Projektowanie i analiza algorytmów komputerowych , Addison-Wesley
Bard, Gregory V. (2009), Kryptoanaliza algebraiczna , Springer, ISBN 978-0-387-88756-2