http://en.wikipedia.org/wiki/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 t × t for some parameter t, 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 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 (n/t)2 blocks instead of on n2matrix cells, where n 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, t is typically chosen to be O(log n).
Applications
Algorithms to which the Method of Four Russians may be applied include:
- computing the transitive closure of a graph,
- Boolean matrix multiplication,
- edit distance calculation,
- sequence alignment.
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 theSage mathematics software and the PolyBoRi library.[1]
History
The algorithm was introduced by V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev in 1970.[2] The origin of the name is unknown; Aho, Hopcroft & Ullman (1974)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.
[3]
It was later determined that not all of the four are Russian, but the name stuck.[4]
Notes
- ^ M4RI(e)- Linear Algebra over F2 (and F2e)
- ^ Arlazarov et al. 1970.
- ^ Aho, Hopcraft & Ullman 1974, p. 243.
- ^ Bard 2009, pp. 133–134.
References
- Arlazarov, V.; Dinic, E.; Kronrod, M.; Faradzev, I. (1970), “On economical construction of the transitive closure of a directed graph” (in Russian), Dokl. Akad. Nauk. 194(11), English Translation in Soviet Math Dokl.
- Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), The design and analysis of computer algorithms, Addison-Wesley
- Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, ISBN 978-0-387-88756-2
 |
This applied mathematics-related article is a stub. You can help Wikipedia by expanding it. |
转载于:https://www.cnblogs.com/xianghang123/archive/2012/04/06/2434318.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230411.html原文链接：https://javaforall.net
