El método de los cuatro rusos

En informática , el método de los cuatro rusos es una técnica para acelerar algoritmos que involucran matrices booleanas o, más generalmente, algoritmos que involucran matrices en las que cada celda puede tomar solo un número limitado de valores posibles.

La idea principal del método es dividir la matriz en pequeños bloques cuadrados de tamaño t × t para algún parámetro t , y utilizar una tabla de búsqueda para ejecutar el algoritmo rápidamente dentro de cada bloque. El índice en la tabla de búsqueda codifica los valores de las celdas de la matriz en la parte superior izquierda del límite del bloque antes de alguna operación del algoritmo, y el resultado de la tabla de búsqueda codifica los valores de las celdas del límite en la parte inferior derecha del bloque después de la operación. Por lo tanto, el algoritmo general se puede ejecutar operando solo en ( n / t ) ² bloques en lugar de en n ² celdas de la matriz, donde n es la longitud del lado de la matriz. Para mantener el tamaño de las tablas de búsqueda (y el tiempo necesario para inicializarlas) suficientemente pequeño, t se elige típicamente para que sea O (log n ) .

Los algoritmos a los que se puede aplicar el Método de los Cuatro Rusos incluyen:

• calcular el cierre transitivo de un gráfico,
• Multiplicación de matrices booleanas ,
• editar cálculo de distancia,
• alineación de secuencia ,
• Cálculo de índice para la coincidencia de patrones binarios desordenados.

En cada uno de estos casos, acelera el algoritmo en uno o dos factores logarítmicos .

El algoritmo de inversión de matrices del Método de los Cuatro Rusos publicado por Bard se implementa en la biblioteca M4RI para realizar operaciones aritméticas rápidas con matrices densas sobre F ₂ . M4RI es utilizado por SageMath y la biblioteca PolyBoRi. ^[1]

El algoritmo fue introducido por VL Arlazarov , EA Dinic, MA Kronrod y IA Faradžev en 1970. ^[2] Se desconoce el origen del nombre; Aho, Hopcroft y Ullman (1974) explican:

El segundo método, a menudo llamado algoritmo de los "Cuatro Rusos", en honor a la cardinalidad y nacionalidad de sus inventores, es algo más "práctico" que el algoritmo del Teorema 6.9. ^[3]

Los cuatro autores trabajaban en Moscú, Rusia, en ese momento. ^[4]

• Arlazarov, V .; Dinic, E.; Kronrod, M.; Faradžev, I. (1970), "Sobre la construcción económica del cierre transitivo de un grafo dirigido", Dokl. Akad. Nauk SSSR , 194 (11). Título original: "Об экономном построении транзитивного замыкания ориентированного графа", publicado en Доклады Академии Наук СССР 134 (3), 1970.
• Aho, Alfred V. ; Hopcroft, John E. ; Ullman, Jeffrey D. (1974). El diseño y análisis de algoritmos informáticos . Addison-Wesley. ISBN 978-0-201-00029-0.OCLC 1147299  .
• Bard, Gregory V. (2009), Criptoanálisis algebraico , Springer, ISBN 978-0-387-88756-2