Matrizenmultiplikation à la Strassen

$$\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{p... ...22} \end{pmatrix} ; \quad c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j}$$

Bilde:

$$\begin{array} {ll} m_1 & := (a_{12}-a_{22})(b_{21}+b_{22})\\... ...{22}(b_{21}-b_{11})\\ m_7 & := (a_{21}+a_{22})b_{11}\end{array}$$

Dann gilt:

$$\begin{array} {ll} c_{11} & := m_1 + m_2 - m_4 - m_6\\ c_{12... ...} & := m_6 + m_7\\ c_{22} & := m_2 - m_3 + m_5 - m_7\end{array}$$

Sei n=2^k und $\text{M}(n)$ die Anzahl arithmetischer Operationen (Mult, Add, Sub), die Strassen's Algorithmus bei $n \times n$ Matrizen benötigt:

$$\begin{array} {ll} \text{M}(1) & = 1\\ \text{M}(n) & = 7 \te... ...left(\frac{n}{2}\right)+18\left(\frac{n}{2}\right)^2\end{array}$$

Expansion dieser Rekursionsgleichung $\rightarrow$

$$\text{M}(n)=7^{k+1}-6n^2=7 \cdot 2^{k \log_2 7} - 6n^2 = 7n^{\log_2 7} - 6n^2 < 7n^{2,81}-6n^2$$

procedure Matmult(A,B,n) =

kill 
$\ulcorner$ 
co A und B sind $n \times n$ Matrizen  oc
if n<16 then berechne $A \cdot B$ mit  klassischer Methode
else 		 if n gerade then
		 		 spalte A und B in je 4 $\frac{n}{2}\times\frac{n}{2}$  Matrizen auf und wende Strassen's Formeln
		 		 an. Führe die  Multiplikationen rekursiv mit Matmult aus.
		 else
		 		 spalte A und B in je eine $(n-1) \times (n-1)$ Matrix  (A11,B11) und
		 		 drei verbleibende Blöcke auf. Wende Matmult  rekursiv auf A11, B11 an
		 		 und berechne die anderen Produkte mit klassischer Methode.
		 fi
fi
$\llcorner$

Beweis:

1.

$\surd$

2.

Sei n gerade und seien A, B zwei $n \times n$Matrizen. Wir wenden Strassen's Formeln an, führen aber die 7 Multiplikationen der $\frac{n}{2}\times\frac{n}{2}$ Matrizen mit klassischer Methode aus.
Gesamtzahl arithmetischer Operationen:

$$7\left(2\left(\frac{n}{2}\right)^3-\left(\frac{n}{2}\right)^... ... +18\left(\frac{n}{2}\right)^2=\frac{7}{4}n^3+\frac{11}{4}n^2$$

Dies ist besser als die klassische Methode, falls:

$$\frac{7}{4}n^3+\frac{11}{4}n^2<2n^3-n^2 \Leftrightarrow \f... ...c{1}{4}n^3 \Leftrightarrow 15 < n \Leftrightarrow n \geq 16$$

Sei n ungerade. Multiplizieren wir $A \cdot B$ mit klassischer Methode, so auch $A_{11} \cdot B_{11}$. Also brauchen wir durch Anwendung von Strassen's Formeln auf die $(n-1) \times (n-1)$ Matrizen (n-1 gerade) weniger Operationen, wenn $n-1 \geq 16$ ist.
Durch Induktion über die Anzahl der rekursiven Anwendungen von Strassen's Formeln folgt die Behauptung.

3.

Sei $\text{M}'(n)$ die Anzahl arithmetischer Operationen. Dann ist:

$$\text{M}'(n) = \left\{ \begin{array} {ll} 2n^3-n^2 & \text... ...\text{falls } n \geq 16 \text{ ungerade} \end{array} \right.$$

Wir definieren für $x \in \mathbbm{R}^+$:

$$\overline{\text{M}}(x) = \left\{ \begin{array} {ll} 2x^3-x... ...rac{42}{4}x^2 & \text{falls } x \geq 32 \end{array} \right.$$

Dann gilt:

$$\overline{\text{M}}(n) \geq \text{M}'(n) \text{ f\uml {u}r alle } n \in \mathbbm{N}$$

Weiterhin ist

$$\begin{array} {l} \overline{\text{M}}'(x) = \sum\limits^{k-... ...\left\{l\left\vert\frac{x}{2^l}<32\right.\right\} \end{array}$$

Mit $k=\left\lfloor\log_2x\right\rfloor - 4 = \log_2x-t$ für $t \in [4,5]$ erhalten wir:

$$\overline{\text{M}}(x) \leq 7^{\log_2x}\left(13\left(\frac{... ... 4,8 \cdot 7^{\log_2x} \text{ f\uml {u}r } x \geq 32\text{.}$$

Für x<32 direkt nachrechnen.

$\Diamond$