mathematics

Method of Four Russians

Method of Four Russians is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Method of Four Russians rather than just read about it. In short: In computer science, the Method of Four Russians or "The Four-Russians speedup," 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…

Key takeaways

Method of Four Russians belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Method of Four Russians to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Method of Four Russians from memory before moving on to harder problems.

Reference excerpt

In computer science, the Method of Four Russians or "The Four-Russians speedup," 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 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 (n/t)2 blocks instead of on n2 matrix 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). The creation of the lookup tables can be done in O(n × t2) time, and if t is set to log n, this results in O(n (log n)2) time complexity for creating the tables. That time is still dominated by the search time O(⁠n2/(log n)2⁠) time (assuming unit-cost RAM).

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, index calculation for binary jumbled pattern matching. 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; 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. All four authors worked in Moscow, Russia in the Soviet Union at the time, however, only Arlazarov was Russian; the name has thus been said to reflect the West's, "general level of ignorance about ethnicities in the then Soviet Union."

Notes

References Arlazarov, V.; Dinic, E.; Kronrod, M.; Faradžev, I. (1970), "On economical construction of the transitive closure of a directed graph", Dokl. Akad. Nauk SSSR, 194 (11). Original title: "Об экономном построении транзитивного замыкания ориентированного графа", published in Доклады Академии Наук СССР 134 (3), 1970. Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. ISBN 978-0-201-00029-0. OCLC 1147299. Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, ISBN 978-0-387-88756-2 Gusfield, Dan (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge: Cambridge University Press. pp. 302–307 (Sec. 12.7). ISBN 978-0-521-58519-4.

Worked examples

Example 1 — a first encounter with Method of Four Russians

Start with the simplest possible case. Write down what Method of Four Russians claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Method of Four Russians before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Method of Four Russians ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Method of Four Russians

In research: Method of Four Russians appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Method of Four Russians in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Method of Four Russians is common in secondary-school and first-year university syllabi. It links to neighbouring topics Applied mathematics stubs, Numerical linear algebra, so understanding it makes those chapters shorter.
In everyday life: Look for Method of Four Russians outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Method of Four Russians in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Method of Four Russians means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Method of Four Russians out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Method of Four Russians in simple terms?

Why does Method of Four Russians matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Method of Four Russians?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Method of Four Russians.