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 ) 2 bloques en lugar de en n 2 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:
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 2 . 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:
Los cuatro autores trabajaban en Moscú, Rusia, en ese momento. [4]