Method of Four Russians
Encyclopedia
In computer science
, the Method of Four Russians is a technique for speeding up algorithm
s involving Boolean matrices, or more generally algorithms involving matrices in which each cell may take on only a bounded number of possible values.
to perform the algorithm quickly within each block. The index into the lookup table encodes the values of the matrix cells on the block boundary prior to some operation of the algorithm, and the result of the lookup table encodes the values of the boundary cells 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 (and the time needed to initialize them) sufficiently small, is typically chosen to be .
In each of these cases it speeds up the algorithm by one or two logarithm
ic 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 the Sage mathematics software and the PolyBoRi library.
, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev in 1970. The origin of the name is unknown; explain:
It was later determined that not all of the four are Russian, but the name stuck.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the Method of Four Russians is a technique for speeding up algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s 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 tableLookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
to perform the algorithm quickly within each block. The index into the lookup table encodes the values of the matrix cells on the block boundary prior to some operation of the algorithm, and the result of the lookup table encodes the values of the boundary cells 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 (and the time needed to initialize them) sufficiently small, is typically chosen to be .
Applications
Algorithms to which the Method of Four Russians may be applied include:- computing the transitive closureTransitive closureIn mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
of a graph, - Boolean matrix multiplication,
- edit distanceEdit distanceIn information theory and computer science, the edit distance between two strings of characters generally refers to the Levenshtein distance. However, according to Nico Jacobs, “The term ‘edit distance’ is sometimes used to refer to the distance in which insertions and deletions have equal cost and...
calculation, - sequence alignmentSequence alignmentIn bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences. Aligned sequences of nucleotide or amino acid residues are...
.
In each of these cases it speeds up the algorithm by one or two logarithm
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
ic 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 the Sage mathematics software and the PolyBoRi library.
History
The algorithm was introduced by V. L. ArlazarovVladimir Arlazarov
- Research work :In 1965 at Alexander Kronrod’s laboratory at the Moscow Institute of Theoretical and Experimental Physics , Vladimir Arlazarov co-developed the ITEP Chess Program, together with Georgy Adelson-Velsky, Anatoly Uskov and Alexander Zhivotovsky, advised by Russian chess master...
, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev in 1970. The origin of the name is unknown; explain:
- The second method, often called the "Four Russians'" algorithm, after the cardinality and nationality of its inventors, is somewhat more "practical" than the algorithm in Theorem 6.9.
It was later determined that not all of the four are Russian, but the name stuck.