In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, the Method of Four Russians is a technique for speeding up
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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 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 (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 closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
of a graph,
* Boolean
matrix multiplication
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
,
*
edit distance
In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to ...
calculation,
*
sequence alignment,
* index calculation for
binary jumbled pattern matching.
In each of these cases it speeds up the algorithm by one or two
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
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 ''F''
2. M4RI is used by
SageMath
SageMath (previously Sage or SAGE, "System for Algebra and Geometry Experimentation") is a computer algebra system (CAS) with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, numbe ...
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:
: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.
All four authors worked in
Moscow, Russia at the time.
Author affiliations
on MathNet.ru.
Notes
References
*. Original title: "Об экономном построении транзитивного замыкания ориентированного графа", published in '' Доклады Академии Наук СССР'' 134 (3), 1970.
*
*
Numerical linear algebra
{{mathapplied-stub