Teile und Herrsche 2 SS10

Aus ProgrammingWiki

< AuK

Wechseln zu: Navigation, Suche

Diese Seite setzt das in Teile und Herrsche 1 begonnene Thema inhaltlich fort.

Autoren:

Felix Deutschmann (sifedeut@stud.hs-zigr.de)

Marek Brzozowski (simabrzo@stud.hs-zigr.de)

Inhaltsverzeichnis

1 Einführung
2 Binäre Suche
3 Multiplikation großer ganzer Zahlen
4 Schnelle Matrixmultiplikation
5 Übungsaufgaben
6 Quellen
7 Weblinks

Einführung

Diese Seite beschäftigt sich mit den Algorithmen Binäre Suche, Multiplikation großer, ganzer Zahlen nach KARATSUBA und OFMAN, sowie Schnelle Matrixmultiplikation, welche hier vorgestellt und demonstriert werden.

Weiterhin findet man hier auch die Vorlesungsunterlagen, sowie die Übungsaufgaben zu diesem Thema.

Binäre Suche

Wer schon einmal etwas gesucht hat, sei es ein Schlüssel an einem Schlüsselbund oder einen Namen im guten alten Telefonbuch oder auch nur eine Seite in einem dicken Buch, der hat sich dabei vielleicht schon eine wichtige Frage gestellt: "Wie finde ich das jetzt am besten?".

Beim Schlüsselbund sieht man sich jeden einzelnen Schlüssel an und prüft, ob es der Schlüssel ist, den man gesucht hat. Man kann diese Vorgehensweise mit dem Suchen in einer unsortierten Liste vergleichen. Bei dieser Art zu suchen prüft man, ob das zu suchende Element x in der Liste L vorkommt - Elementweise. Im ungünstigsten Fall findet man das Element an der letzten Stelle der Liste L. Diese Suche mit $\mathcal{O}(n)$ hat einen linearen Aufwand und ist für lange Liste nicht zu empfehlen. Eine Implementierung dieser Suche in Scheme ist folgende:

(define usortSeqSuch (lambda (x ls) (cond ((null? ls) "Nicht gefunden!") ((= x (car ls)) 'Gefunden!) (else (usortSeqSuch x (cdr ls))))))

(usortSeqSuch 5 '(99 43 65 44 29 83 10 4 5 8 6))

Dieser Suchalgorithmus hat zwei große sofort erkennbare Schwächen.

der Aufwand steigt linear mit wachsender Elementeanzahl
die Liste wird komplett durchsucht, wenn das Element fehlt

Das zweite Problem können wir mit einem kleinen Trick sofort beheben. Wir nehmen eine aufsteigend sortierte Liste und durchsuchen diese mit dem folgenden leicht modifizierten Algorithmus. Damit können wir dann in einigen Fällen die Suche vorzeitig abbrechen, wenn das Element nicht in der Liste ist.

(define sortSeqSuch (lambda (x ls) (cond ((null? ls) "Nicht gefunden!") ((< x (car ls)) "Nicht gefunden!") ((= x (car ls)) 'Gefunden!) (else (sortSeqSuch x (cdr ls))))))

(sortSeqSuch 38 '(1 4 7 9 12 17 24 29 31 33 38 41 53 74 86 93 104 137 143 163))

Da aber auch hier der Aufwand linear bleibt, erfüllt die sequentielle Suche nicht unseren Wunsch nach einem geringeren Aufwand.

Wenden wir uns also der Suche nach einem Namen im Telefonbuch zu. Wie würde man dabei vorgehen? Bei den meisten Menschen kann man folgendes erkennen:

Zuerst wird das Buch in der Mitte aufgeschlagen. Dann prüfen sie, ob der Anfangsbuchstabe vom gesuchten Namen mit dem aktuellen Index im Telefonbuch übereinstimmt. Wenn das so ist, dann ist die Suche vermutlich noch auf der selben Seite vorbei. Haben sie den Anfangsbuchstaben noch nicht gefunden, so überlegen sie, ob der gesuchte Anfangsbuchstabe vor oder nach dem aktuellen Index auftritt. Daraufhin wird entweder vor oder nach der Mitte des Buches weitergesucht. Aber nicht irgendwie, sondern wieder mit dem selben Verfahren. Auf diese Weise wird der Suchraum kontinuierlich halbiert und man kommt mit dieser Methode deutlich schneller zum Ziel als mit der sequentiellen Suche.

Jetzt wo der Name dieser Suche geklärt ist, befassen wir uns ein wenig näher mit der binären Suche. Dafür reduzieren wir das Suchproblem auf eine Liste mit $n$ Elementen aus dem Zahlenbereich der ganzen Zahlen $\mathbb{Z}$ :

$L=\{e_{1}, e_{2}, \dots ,e_{n}\}$ mit $e\in\mathbb{Z}$ und $n\in\mathbb{N}$

Unsere Liste L muss nun möglichst in der Mitte geteilt werden. Da das aber bei einer ungeraden Anzahl von Elementen ganzzahlig nicht möglich ist, teilen wir die Anzahl der Listenelemente durch 2 und runden das Ergebnis abschließend auf die nächst kleinere Zahl ab. Mathematisch schreibt man: $k=\lfloor\frac{n}{2}\rfloor$ ( $k$ ist der Index des Elementes in der Mitte der Liste $L$ )

Nach der Teilung haben wir nun zwei Teillisten, eine linke und eine rechte:

$L_{l}=\{e_{1}, e_{2}, \dots , e_{k}\}$ und

$L_{r}=\{e_{k+1}, e_{k+2}, \dots , e_{n}\}$

Wenn nun $x$ unser gesuchtes Element ist, dann wird $x$ mit dem ersten Element der rechten Teilliste verglichen $x < e_{k+1}$ . Abhängig vom Ergebnis dieser Prüfung wird nun mit der rechten oder linken Teillisten fortgefahren. Die verwendete Teilliste wird dann wieder in zwei Teillisten aufgeteilt und die Prüfung beginnt von vorn. Dieser Vorgang wird solange wiederholt, bis entweder $x$ gefunden wurde oder bis alle Teillisten untersucht worden sind. Im besten Fall ist das erste Element $e_{k+1}$ unserer Teilliste $L_{r}$ schon das gesuchte $x$ .

Zur übersichtlichen Darstellung der binären Suche zeigen wir hier die rekursive Bildungsvorschrift:

$BiSu = \{ \begin{array}{ll} BiSu(L_{\text{l}}) &\textrm{wenn }x<e_{k+1},\\ BiSu(L_{\text{r}}) &\textrm{wenn }x>e_{k},\\ print(e_{k}) &\textrm{wenn }x = e_{k}, \\ \textrm{"nicht Enthalten"} &\textrm{wenn }k < 0 \textrm{ oder } k > n\\ \textrm{"nicht Enthalten"} &\textrm{sonst } \end{array}$

Mit der binären Suche ist es möglich, in einem Telefonbuch mit 250.000 Einträgen und 700 Seiten
mit höchstens  Namensvergleichen jeden Namen zu finden.

Implementierung in Scheme

Aufgrund der oben stehenden interessanten Information schauen wir uns jetzt einmal den Algorithmus in seiner Scheme-Implementierung an.

Bevor wir aber zum eigentlichen Algorithmus kommen, benötigen wir noch die Prozedur teillisten2, welche im Kapitel Teile und Herrsche 1 im Zusammenhang mit Mergesort behandelt wurde.

(define teillisten2 (lambda (ls) (let ((k (floor (/ (length ls) 2)))) (letrec ((helfer (lambda (ls i) (if (= i 0) (values '() ls) (call-with-values (lambda () (helfer (cdr ls) (- i 1))) (lambda (links rechts) (values (cons (car ls) links) rechts))))))) (helfer ls k)))))

Scheme-Implementierung der binären Suche:

(define binaersuche (lambda (x ls) (call-with-values (lambda () (teillisten2 ls)) (lambda (lls rls) (cond ((null? rls) "Key not found!") ((= x (car rls)) "Key found :)") ((< x (car rls)) (binaersuche x lls)) (else (if (null? (cdr rls)) "Key not found!" (binaersuche x rls))))))))

Um zu sehen, dass der Algorithmus arbeitet, haben wir zur Vereinfachung eine Liste explizit angegeben. Bei der späteren selbständigen Arbeit mit der binären Suchen können auch die Prozeduren zzls (Erstellt eine Liste mit Zufallszahlen) und mergesort (sortiert eine Liste) verwendet werden. Beide Prozeduren werden für die Übungen bekannt gegeben.

(define suchliste '(4 8 15 16 23 42 55 63 78 84 92 103))

Wir suchen nach dem Element 42:

(binaersuche 42 suchliste)

Nachdem wir die binäre Suche nun ausprobieren konnten, stellen wir fest, dass das Ergebnis etwas dürftig ist. Denn die Aussage, dass etwas gefunden wurde ist nicht sinnvoll, wenn man nicht auch noch gesagt bekommt, an welcher Stelle das Element gefunden wurde. Aus diesem Grund fügen wir diese Funktion noch in unsere Prozedur ein. Weiterhin wird noch ein Aufrufzähler eingebaut, welcher die Rekursionsschritte zählt. Diesen können wir dann für die empirische Aufwandsanalyse benutzen.

Zuerst definieren wir einen Zähler und einen Index:

(define calls 0) (define index 0)

Dann implementieren wir die eben definierten Variablen in der Binären Suche

(define binhelfer (lambda (x ls) (call-with-values (lambda () (teillisten2 ls)) (lambda (lls rls) (cond ((null? rls) "Nicht gefunden!") ((= x (car rls)) (and (and (set! index (+ index (length lls))) (and (string-append "Gefunden - [Stelle: " (number->string index) "] - [rekursive Aufrufe: " (number->string calls) "]"))))) ((< x (car rls)) (if (null? lls) "Nicht gefunden" (and (set! calls (+ calls 1)) (binhelfer x lls)))) (else (if (null? (cdr rls)) (string-append "Nicht gefunden. [Rekursionen: " (number->string calls) "]") (and (set! calls (+ calls 1)) (and (set! index (+ index (length lls))) (binhelfer x rls))))))))))

Und abschließend benötigen wir noch eine Prozedur zum Aufruf der binären Suche:

(define binaersuche2 (lambda (x ls) (set! calls 0) (set! index 0) (binhelfer x ls)))

Ein Aufruf unserer neuen binären Suche ergibt dann das gewünschte Ergebnis.

;so haben wir die suchliste definiert: ;verändern könnt ihr sie mit set! ;(define suchliste '(4 8 15 16 23 42 55 63 78 84 92 103)) (binaersuche2 42 suchliste)

Vergleich Sequentielle Suche - Binäre Suche

Da wir nun im vorangegangenen Teilabschnitt die Grundlage für eine empirische Analyse der binären Suche geschaffen haben, möchten wir das an dieser Stelle auch für die sequentielle Suche tun. Somit ist es dann in der Übung möglich die Aufwände der beiden Suchen zu vergleichen.

Dafür müssen wir lediglich die Variable für die Aufrufe implementieren, da diese dann auch für den Index verwendet werden kann:

(define helper_sortSeqSuch (lambda (x ls) (cond ((null? ls) "Nicht gefunden") ((< x (car ls)) "Nicht gefunden") ((= x (car ls)) (string-append "Gefunden an Stelle: " (number->string calls) ". Anzahl der Aufrufe: " (number->string calls))) (else (set! calls (+ calls 1)) (helper_sortSeqSuch x (cdr ls))))))

Weiterhin schaffen wir uns noch eine Prozedur, welche die Variable "calls" zurücksetzt:

(define sortSeqSuch2 (lambda (x ls) (set! calls 0) (helper_sortSeqSuch x ls)))

Somit können wir mit den folgenden Aufruf machen:

(sortSeqSuch2 42 suchliste)

Effizienzanalysen

Best Case

Beide Suchalgorithmen können im ersten Schritt zum Ergebnis kommen. Bei der sequentiellen Suche ist das das erste Listenelement und bei der binären Suche ist es das erste Element der rechten Teilliste. Beide Suchen erreichen somit einen konstanten Aufwand $T(n)=\mathcal{O}(c)$ , der unabhängig von n ist.

Average- und Worst-Case

Betrachten wir zunächst die sequentielle Suche. Im schlechtesten Fall benötigt sie $n$ Durchläufe, d.h. $T(n)=\mathcal{O}(c)$ . Im mittleren Fall gilt das genauso. Geht man jetzt davon aus, das alle Listenelemente mit $x$ mit gleicher Wahrscheinlichkeit übereinstimmen, ist der Aufwand der sequentiellen Suche $T(n)=\frac{1}{n}\sum_{i=1}^{n}i=\frac{n}{2n}(n+1)=\mathcal{O}(n)$

Betrachten wir nun den Aufwand der binären Suche. Aufgrund der Arbeitsweise des Algorithmus kann man sofort erkennen, dass sich die Längen der Teillisten in jedem Schritt halbieren. Das gilt besonders dann, wenn die Anzahl der Listenelemente gerade ist. Ist dies der Fall, dann stimmt die Anzahl der rekursiven Aufrufe mit der Anzahl der Halbierungen überein. Das sind genau $\log_2 n$ Stück. Für die Vergleichoperationen (also die in den Zwischenschritten) setzen wir einen konstanten Aufwand $\mathcal{O}(c)$ an. Somit ergibt sich für die binäre Suche im mittleren, sowie schlechtesten Fall ein Gesamtaufwand von $T(n)=\mathcal{O}(\log_2 n)$

Fazit

Da man in der Praxis den Best Case vernachlässigen kann, muss man seine Aufmerksamkeit nur auf den mittleren und den schlechtesten Fall lenken. Der Aufwand der sequentiellen Suche ist linear. Der Aufwand der binären Suche ist logarithmisch. Aufgrund dessen sollte man die binäre Suche der sequentiellen vorziehen.

Um das ganze noch einmal deutlich zu gestalten stellen wir die Aufwände für verschieden große $n$ in einer Tabelle gegenüber:

$\begin{array}{|c|l r|r|r|r|r|} \hline f(n) & n= & 2 & 16 & 256 & 1024 & 1048576\\ \hline\\\hline\\ log_2 n & & 1 & 4 & 8 & 10 & 20\\ \hline\\ n & & 2 & 16 & 256 & 1024 & 1048576\\ \hline \end{array}$ Spätestens jetzt sollte einem der Unterschied klar geworden sein.

Multiplikation großer ganzer Zahlen

Ein weiterer Teile-und-Herrsche Algorithmus ist die schnelle Multiplikation nach KARATSUBA und OFMAN zum Multiplizieren zweier ganzen Zahlen $x$ und $y$ . Jetzt fragt man sich vielleicht, warum man sich noch eine Multiplikationsmethode ausgedacht hat und wieso man als angehender Informatiker davon gehört haben sollte. Wir kennen doch schon mindestens zwei - zum Einen die schriftliche Multiplikation aus der Schule und dann noch die Multiplikation á la Russe. Betrachten wir die Verfahren einmal etwas genauer.

Aufwand der schriftlichen Multiplikation

Zu Beginn wollen wir uns den Aufwand der schriftlichen Multiplikation aus unserer frühen Schulzeit ansehen. Für die Multiplikation zweier $n$ -stelliger Zahlen benötigt diese Methode $n^{2}$ Multiplikationen und einige Additionen. Der Aufwand ist mit $\mathcal{O}(n^{2})$ quadratisch.

Aufwand der Multiplikation á la Russe

Die Multiplikation á la Russe wurde schon in der Einführung in das Thema Algorithmen und Komplexität vorgestellt und soll hier nicht weiter erklärt werden. Wir wollen hier nur den Aufwand dieser Methode aufgreifen, um später in diesem Kapitel darauf zurück greifen zu können: $\mathcal{O}(n^{2})$ .

Mit diesen beiden Aufwänden im Hinterkopf betrachten wir nun die schnelle Multiplikation nach KARATSUBA und OFMAN.

Der Algorithmus von KARATSUBA und OFMAN

Gleich zu Beginn müssen wir eine Vereinbarung treffen. Die zu multiplizierenden Zahlen $a$ und $b$ müssen die gleiche Stelligkeit $n$ haben und $n$ muss gerade sein.

Die beiden Faktoren $a$ und $b$ lassen sich nun in je zwei Teile aufteilen.

$a=\underbrace{a_{1}z^{\frac{n}{2}}}_{Teil 1}+\underbrace{a_{0}}_{Teil 2}$ und $b=\underbrace{b_{1}z^{\frac{n}{2}}}_{Teil 1}+\underbrace{b_{0}}_{Teil 2}$ , wobei $z$ die Basis des Zahlensystems ist (z.B. $z=10$ ). Da wir eine gerade und gleiche Stelligkeit vorraussetzen, sind die beiden Teile der Faktoren gleich lang. Das Produkt ergibt sich nun aus folgender Rechnung:

$a \cdot b=(a_{1}z^{\frac{n}{2}}+a_{0})\cdot(b_{1}z^{\frac{n}{2}}+b_{0})\\ a \cdot b=(a_{1} \cdot b_{1})z^{n}+(a_{0}\cdot b_{1}+b_{0}\cdot a_{1})z^{\frac{n}{2}}+a_{0}\cdot b_{0}$

Ist man nach dieser einfachen Umstellung der Gleichung nun schon am Ziel und hat den Aufwand reduziert? Die Antwort ist "Nein". Man hat hier nur die Multiplikation der beiden $n$ -stelligen Zahlen $a$ und $b$ auf 4 gleichartige Multiplikationen zweier $\frac{n}{2}$ -stelliger Zahlen zugüglich dreier Additionen von je zwei Zahlen, die nicht mehr als $n$ -stellig sind, zurückgeführt. Die Addition hat eine Aufwand von $\Theta(n)$ . Somit erhält man für den Gesamtaufwand

$T(n)=4\cdot T(\frac{n}{2})+\Theta(n)$ .

Darauf können wir die Meistermethode anwenden. Das Matching führt in diesem Fall zu $x=4$ und $y=2$ . Damit ergibt sich nach $f(n)=n^{log_y x}$ folgendes: $f(n)=n^{log_2 4} = n^{\frac{\log 4}{\log 2}} = n^{2}$ Damit ergibt sich $T(n)=\mathcal{O}(n^{2})$ .

Bis zu dieser Stelle haben wir den selben quadratischen Aufwand wie unsere Schulbuch-Methode. Um nun eine Aufwandsminderung zu erreichen, wird die Gleichung von oben noch ein wenig umgeformt.

$a\cdot b=(a_{1}\cdot b_{1})z^{n}+$(a_{1}\cdot b_{1})+(a_{0}\cdot b_{0})-(a_{0}-a_{1})\cdot(b_{0}-b_{1})$z^{\frac{n}{2}}+a_{0}\cdot b_{0}$

Nach dieser Umformung ergibt sich eine kompliziert aussehende Gleichung mit nur noch 3 verschiedene Multiplikationen, die allerdings mehrfach auftreten. Deswegen werden die Multiplikationen substituiert und man erhält eine einfachere Gleichung.

$r=a_{1}\cdot b_{1}\\ s=(a_{0}-a_{1})\cdot(b_{0}-b_{1})\\ t=a_{0}\cdot b_{0}\\ \\ \underline{\underline{a\cdot b = r\cdot z^{n}+(r+t-s)z^{\frac{n}{2}}+t}}$

Jetzt kann man sehr gut erkennen, dass Multiplikationen, die mehrfach vorkommen, nur einmal berechnet werden müssen und dass eine aufwändige Multiplikation durch einfachere Addition und Subtraktion ersetzt worden ist. Diese Tatsachen geben diesem Algorithmus den Aufwandsvorteil, was wir im Folgenden noch zeigen werden.

Wir verzichten an dieser Stelle auf ein ausgiebiges Beispiel, da dieses für die Übung vorgesehen ist.

Der Aufwand der Multiplikation nach KARATSUBA und OFMAN

Aufwände für Karatsuba-Multiplikation und Schulbuch-Multiplikation

Nachdem wir uns nun mit der Funktionsweise des Algorithmus beschäftigt haben, wollen wir nun noch den Aufwand betrachten. Wir haben gerade festgestellt, dass die beiden Multiplikationen $r$ und $t$ je zweimal vorkommen, aber nur einmal mit einem einem Aufwand von jeweils $T(\frac{n}{2})$ berechnet und danach eingesetzt werden. Dazu kommt nun der Aufwand der noch verbleibenden Multiplikation in $s$ , so wie Additionen ( $\Theta(n)$ ).

Daraus ergibt sich ein Gesamtaufwand von $T(n)=3\cdot T(\frac{n}{2})+\Theta(n)$ .

Die Lösung dieser Gleichung ergibt $T(n)=\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$ .

Hier noch einmal alle drei Aufwände untereinander:

Schulbuch Multiplikationsmethode: $\mathcal{O}(n^2)$
Multiplikation á la Russe: $\mathcal{O}(n^2)$
Multiplikation nach Karatsuba und Ofman: $\Theta(n^{1.585})$

Die nebenstehende Grafik lässt diesen Unterschied noch deutlicher werden.

Schnelle Matrixmultiplikation

Dr. Volker Strassen (deutscher Mathematiker)

Die Multiplikation von zwei Matrizen mit $n$ Zeilen und $n$ Spalten ist ja schon aus der Schule bekannt.

$A=\begin{pmatrix} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}\\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}\end{pmatrix}$ , $B=\begin{pmatrix} b_{1,1} & b_{1,2} & b_{1,3} & b_{1,4}\\ b_{2,1} & b_{2,2} & b_{2,3} & b_{2,4}\\ b_{3,1} & b_{3,2} & b_{3,3} & b_{3,4}\\b_{4,1} & b_{4,2} & b_{4,3} & b_{4,4}\end{pmatrix}$

Um die Ergebnismatrix $C=A\cdot B$ zu erhalten, folgt man im Allgemeinen folgender Regel:

$C= \begin{pmatrix} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}\\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}\end{pmatrix}\bullet\begin{pmatrix} b_{1,1} & b_{1,2} & b_{1,3} & b_{1,4}\\ b_{2,1} & b_{2,2} & b_{2,3} & b_{2,4}\\ b_{3,1} & b_{3,2} & b_{3,3} & b_{3,4}\\b_{4,1} & b_{4,2} & b_{4,3} & b_{4,4}\end{pmatrix}\\ \\C= \begin{pmatrix} (a_{1,1}\cdot b_{1,1} + a_{1,2}\cdot b_{2,1} + a_{1,3}\cdot b_{3,1} + a_{1,4}\cdot b_{4,1}) & \cdots & \cdots & (a_{1,1}\cdot b_{1,4} + a_{1,2}\cdot b_{2,4} + a_{1,3}\cdot b_{3,4} + a_{1,4}\cdot b_{4,4})\\ \vdots & \ddots & & \vdots\\ \vdots & & \ddots & \vdots\\ (a_{4,1}\cdot b_{1,1} + a_{4,2}\cdot b_{2,1} + a_{4,3}\cdot b_{3,1} + a_{4,4}\cdot b_{4,1}) & \cdots & \cdots & (a_{4,1}\cdot b_{1,4} + a_{4,2}\cdot b_{2,4} + a_{4,3}\cdot b_{3,4} + a_{4,4}\cdot b_{4,4}) \end{pmatrix}$

Ausgehend von $n$ (Zeilen oder Spalten der beiden Matrizen $A$ und $B$ ), erkennt man schon an der allgemeinen Form, dass daraus $n^3$ Multiplikationen entstehen und dieses Verfahren somit einen Aufwand von $\mathcal{O}(n^3)$ benötigt.

Ende der 60er-Jahre hatte Dr. Volker Strassen eine Idee, welche die typische Teile-und-Herrsche Strategie verfolgte. Matrizen teilte er in Teilmatrizen auf und multiplizierte diese untereinander und ermittelte das Produkt, mithilfe aufwandsmäßig günstigen Operationen, mit einem geringeren Gesamtaufwand.

Das Verfahren von STRASSEN lässt sich am besten mithilfe eines Beispieles erklären. Hierzu nehmen wir zwei beliebige Matrizen vom Typ $\bigg(\frac{n}{2}$ , $\frac{n}{2} \bigg)$ $A$ und $B$ mit $A=\begin{pmatrix} 8 & 9 & 2 & 4\\ 5 & 7 & 2 & 6\\ 1 & 7 & 9 & 3\\ 5 & 8 & 2 & 7 \end{pmatrix}$ und $B=\begin{pmatrix} 3 & 5 & 8 & 6\\ 4 & 7 & 2 & 4\\ 1 & 1 & 6 & 2\\ 6 & 8 & 7 & 1 \end{pmatrix}$ .

Diese Zerlegen wir dann nach folgendem Muster in Teilmatrizen.

$C=A\cdot B= \begin{pmatrix} A_{1,1} & A_{1,2}\\ A_{2,1} & A_{2,2} \end{pmatrix}\cdot \begin{pmatrix} B_{1,1} & B_{1,2}\\ B_{2,1} & B_{2,2} \end{pmatrix} =\begin{pmatrix} C_{1,1} & C_{1,2}\\ C_{2,1} & C_{2,2} \end{pmatrix}$

Und erhalten: $A_{1,1}=\begin{bmatrix}8 & 9\\5 & 7\end{bmatrix}\text{, } A_{1,2}=\begin{bmatrix}2 & 4\\2 & 6\end{bmatrix}\text{, } A_{2,1}=\begin{bmatrix}1 & 7\\5 & 8\end{bmatrix}\text{, } A_{2,2}=\begin{bmatrix}9 & 3\\2 & 7\end{bmatrix}\\ B_{1,1}=\begin{bmatrix}3 & 5\\4 & 7\end{bmatrix}\text{, } B_{1,2}=\begin{bmatrix}8 & 6\\2 & 4\end{bmatrix}\text{, } B_{2,1}=\begin{bmatrix}1 & 1\\6 & 8\end{bmatrix}\text{, } B_{2,2}=\begin{bmatrix}6 & 2\\7 & 1\end{bmatrix}\\$

Die Teilmatrizen von $C$ erhält man durch

$C_{1,1}=A_{1,1}\cdot B_{1,1}+A_{1,2}\cdot B_{2,1}\\ C_{1,2}=A_{1,1}\cdot B_{1,2}+A_{1,2}\cdot B_{2,2}\\ C_{2,1}=A_{2,1}\cdot B_{1,1}+A_{2,2}\cdot B_{2,1}\\ C_{2,2}=A_{2,1}\cdot B_{1,2}+A_{2,2}\cdot B_{2,2}$

Das sind 8 Matrizenmultiplikationen ( $8\cdot T(\frac{n}{2})$ ) und 4 Matrizenadditionen, deren Aufwand in $\mathcal{O}(n^2)$ liegt. Daraus ergibt sich die Gleichung $T(n)=8\cdot T(\frac{n}{2})+\mathcal{O}(n^2)$ . Nach Auflösung dieser erhält man $T(n)=\mathcal{O}(n^3)$ . Offensichtlich ist hier noch keine Aufwandseinsparung entstanden.

Um das gewünschte Ergebnis zu erhalten berechnet man zunächst 7 Matrizen, mit denen man später Multiplikationen ersetzen kann.

$M_{1}=(A_{1,1}+A_{2,2})\cdot(B_{1,1}+B_{2,2})\\ M_{2}=(A_{2,1}+A_{2,2})\cdot B_{1,1}\\ M_{3}=A_{1,1}\cdot(B_{1,2}-B_{2,2})\\ M_{4}=A_{2,2})\cdot (B_{2,1}-B_{1,1})\\ M_{5}=(A_{1,1}+A_{1,2})\cdot B_{2,2}\\ M_{6}=(A_{2,1}-A_{1,1})\cdot(B_{1,1}+B_{1,2})\\ M_{7}=(A_{1,2}-A_{2,2})\cdot(B_{2,1}+B_{2,2})$

Danach kann man die 4 Teilmatrizen von $C$ durch Addition bzw. Subtraktion berechnen.

$C_{1,1}=M_1 + M_4 - M_5 + M_7\\ C_{1,2}=M_3 + M_5\\ C_{2,1}=M_2 + M_4\\ C_{2,2}=M_1 - M_2 + M_3 + M_6$

Der Gesamtaufwand setzt sich aus 7 Multiplikationen und 18 Additionen zusammen. Daraus ergibt sich $T(n)=7\cdot T(\frac{n}{2})+\mathcal{O}(n^2)$ . Die Lösung dieser Gleichung ergibt $T(n)=\mathcal{O}(n^{log_2 7})\approx\mathcal{O}(n^{2.81})$ . Wie wir sehen ist der Aufwand geringer als bei der normalen Matrixmultiplikation. Theoretisch verwendet man diesen Algorithmus, bis man nur noch Skalare multipliziert. In der Praxis wechselt man zwischen der Schulbuch-Methode und dem Strassen-Algorithmus. Der Strassen-Algorithmus wird nämlich erst ab einer Matrizengrößen von $1024\times1024$ besser. Für den Wechsel gibt es Verfahren, auf die hier nicht weiter eingegangen werden soll. An dieser Stelle wollen wir euch auch nicht vorenthalten, dass der Algorithmus auch für Matrizen vom Typ $(n,n)$ funktioniert, wenn das $n$ ungerade ist. Dafür spaltet man die letzte Zeile und Spalte ab und verfährt dann analog zum eigentlichen Strassen-Algorithmus. Da wir darauf nicht näher eingehen, kann man sich hier ein wenig belesen.

Übungsaufgaben

Die Übungsaufgaben zu den vorgestellten Algorithmen sind hier zu finden.

Quellen

[1] Wagenknecht, Christian: Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003. - ISBN 3-446-22314-2
[2] Cormen, Th. H.; Leiserson, Ch. E.; Rivest, R.; Stein, C.: Algorithmen - Eine Einführung, 2. Auflage.- Oldenburg Wissensch. Vlg., 2007 - ISBN 978-3-486-58262-8