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.
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.
In order to keep the size of the lookup tables (and the time needed to initialize them) sufficiently small, t is typically chosen to be O(log n).
The Method of Four Russians matrix inversion algorithm published by Bard is implemented in M4RI library for fast arithmetic with dense matrices over F2.
[2] The origin of the name is unknown; Aho, Hopcroft & Ullman (1974) explain: All four authors worked in Moscow, Russia in the Soviet Union at the time.