Der Vier-Russen-Algorithmus

Algorithmus:
Der Vier-Russen-Algorithmus für die boolesche Matrixmultiplikation zerlegt die Matrix $A$ in $n/\log n$ Matrizen $A_i$ der Form $n \times \log n$ und $B$ umgekehrt in $\log n \times n$-Matrizen $B_i$. Für jede Zeile von $A_i$ wird zuerst eine Tabelle aller möglichen $2^{\log n} = n$ Bitkombinationen erstellt, dann wird das gesuchte Ergebnis der Multiplikation der Zeilen von $A_i$ mit den $n$ Spalten von $B_i$ aus der Tabelle abgelesen.
Der Trick:
Die Menge der $n$ möglichen Kombinationen lässt sich um $\log n$ schneller berechnen als die direkten $n$ Multiplikationen, genauer gesagt in $O(n^2)$.

Komplexität:
Der Vier-Russen-Algorithmus berechnet das boolesche Matrixprodukt in $O(n^3/\log n)$.