Der 4-Russen-Algorithmus für Boolesche Matrixmultiplikation

Autoren:
V.L. Avlazarov, E.A. Dinic, M.A. Kronod, I.A. Faradzev : ``On economical construction of the transitive closure of a directed graph'', Soviet Math. Doklady 11 (1970), p. 1209-1210.

Gegeben zwei Boolesche $n \times n$ Matrizen A, B; gesucht: $C=A\cdot B$.
Sei $l:=\lfloor \log n \rfloor$, o.B.d.A. gelte l|n (l ist Teiler von n).

Teile A auf (setze $m := \frac{n}{l}$):

Sei $A=A'_1 \vee A'_2 \vee \cdots \vee A'_m ,C_i:=A_i \cdot B_i$ für $i=1,\ldots,m$. Dann gilt

$$\begin{split} C=&\bigvee_{i=1}^{m}C_i, \text{ da }\\ C=& A... ...q j \leq m$}}} A'_iB'_j = \bigvee_{i=1}^{m}A_iB_i, \end{split}$$

da A_iB_j=0 für $i \neq j$ (fasse A_i und B_j als $n \times n$Matrizen auf mit 0 außerhalb des jeweiligen Streifens). Gegeben die C_i's, benötigen wir Zeit $\mathcal{O}(mn^2)$.

Betrachte eine Zeile von C_i:

$$c_k^{(i)}=\bigvee_{j=1}^l a_k^{(i)} \cdot b_j^{(i)}$$

Der Algorithmus berechnet einfach zunächst alle Booleschen Linearkombinationen der Zeilen von B_i (Prozedur bcomb) und damit c_k⁽ⁱ⁾ für jedes mögliche a_k⁽ⁱ⁾.
Betrachte A, B und C als Matrizen von Zeilenvektoren:

$$A=\begin{pmatrix} a_1\\ \vdots\\ a_n\end{pmatrix}, \quad B=... ...rix}, \quad C=\begin{pmatrix} c_1\\ \vdots\\ c_n\end{pmatrix}$$

proc bcomb(int i) =

$\ulcorner$comb$[0]:=[0,\ldots,0]$;for j:=1 to $2^{\lfloor \log n \rfloor} -
 1$ do
		 $p:=\lfloor \log j \rfloor$;   co p Index der  vordersten 1 von j oc
		 comb[j]:=comb$[j-2^p] \vee b_{(i-1) \lfloor \log n \rfloor + p
 + 1}$od
$\llcorner$

Zeitbedarf:

(a)

sequentiell:

(b)

Vektoroperationen der Breite n:

algorithm four-russians(array a,b,c) =

$\ulcorner$co die Matrizen a,b,c sind als Vektor von n Zeilenvektoren organisiert oc
const $l = \lfloor \log n \rfloor$ co wir  nehmen l|n an oc;
array comb[0..2l-1] of boolean-vector;
 
for i:=1 to n do     $c[i]:=[0,\ldots,0]$ od
 
for i:=1 to $\frac{n}{l}$ do   co Berechne die Ci's oc
		 bcomb(i);
		 for j:=1 to n do
		 		 co Bitmuster in der j-ten Zeile von Ai in  Binärzahl wandeln oc
		 		 nc:=0;
		 		 for $k:=i\cdot l$ downto $(i-1) \cdot l + 1$ do
		 		 		 if a[j,k] then nc:=nc+nc+1 else nc:=nc+nc fi
		 		 od
		 		 $c[j]:=c[j] \vee$comb[nc];
		 od
od
$\llcorner$

Beispiel:

Zeitbedarf:

(a)

sequentiell:
$\mathcal{O}\left( \frac{n}{l} \cdot \left( n^2 + n(l+n)\right)\right)= \mathcal{O}\left(\frac{n^3}{l}\right)=$

(b)

Vektorrechner der Breite n (Interpretation eines Bitintervalls als Zahl in $\mathcal{O}(1)$ Zeit):
$\mathcal{O}\left(\frac{n}{l} \cdot (n + n(1+1)) \right) =$

Beweis: $\surd$ (s.o.) $\Diamond$