Method of Four Russians


In computer science, the Method of Four Russians is a technique for speeding up algorithms involving Boolean matrices, or more generally algorithms involving matrices in which each cell may take on only a bounded number of possible values.

Idea

The main idea of the method is to partition the matrix into small square blocks of size for some parameter, and to use a lookup table to perform the algorithm quickly within each block. The index into the lookup table encodes the values of the matrix cells on the upper left of the block boundary prior to some operation of the algorithm, and the result of the lookup table encodes the values of the boundary cells on the lower right of the block after the operation. Thus, the overall algorithm may be performed by operating on only blocks instead of on matrix cells, where is the side length of the matrix. In order to keep the size of the lookup tables sufficiently small, is typically chosen to be.

Applications

Algorithms to which the Method of Four Russians may be applied include:
In each of these cases it speeds up the algorithm by one or two logarithmic factors.
The Method of Four Russians matrix inversion algorithm published by Bard is implemented in M4RI library for fast arithmetic with dense matrices over F2. M4RI is used by SageMath and the PolyBoRi library.

History

The algorithm was introduced by V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradžev in 1970. The origin of the name is unknown; explain:
All four authors worked in Moscow, Russia at the time.