Herzlich willkommen zur Fortsetzung der Vorlesung Effiziente
Algorithmen.
Ich vertrete heute Prof. Schmeck, der so einer wichtigen Sitzung nicht
fernbleiben kann.
Die findet jetzt gerade statt, in der wir hier in der Vorlesung sind.
Deshalb vertrete ich ihn heute und nächste Woche wird er auch leider
nicht da sein können, weil er auf einer Konferenz ist.
Da werde ich ihn ebenfalls vertreten.
Okay.
Also letzte Vorlesung.
Also wir haben jetzt mittlerweile mit dem algebraischen Problem
angefangen.
Letzte Vorlesung haben wir uns mit Matrixmultiplikation beschäftigt.
Insbesondere haben wir angefangen, uns nochmal die Schulmethode
anzufangen.
Also der naive Ansatz zur Matrixmultiplikation.
Und uns dann geschaut, wie das ein gewisser Herr Strassen vor
mittlerweile fast 50 Jahren gelöst hat.
Und zwar, sein Ansatz sieht folgendermaßen aus.
Er berechnet nicht naiv nach Schulmethode, Zeile mal Spalte, sondern
er teilt dieses große Problem der Matrixmultiplikation in verschiedene
kleine Teilprobleme ab.
Das ist ein sogenannter Divide-and-Conquer-Ansatz.
Und was ganz interessant ist, man könnte auch die Schulmethode naiv
ausführen per Divide-and-Conquer-Ansatz.
Es würde insgesamt, wenn man die Matrizen jeweils in 2x2-Matrizen
partitioniert, erhält man da insgesamt 8 Multiplikationen.
Strassen konnte zeigen, dass es tatsächlich sogar mit 7
Multiplikationen geht.
Und dadurch kann der asymptotische Aufwand, der für die
Matrixmultiplikation aufgewendet werden muss, von n hoch 3 auf n hoch
Logarithmus zur Basis 2 von 7 reduziert werden.
Allerdings lohnt sich dieser Ansatz erst, wenn n groß genug ist.
Also für kleinere Matrizen ist es nach wie vor sinnvoll, die
Schulmethode zu verwenden, weil sich durch Strassenansatz, also das,
was wir an Multiplikationen einsparen, dafür müssen wir mehr
Additionen und Subtraktionen durchführen.
Wir haben uns außerdem auch angeschaut, wie man
Matrizenmultiplikationen auf zweidimensionalen Prozessorfeldern
durchführen kann.
Insbesondere hier den Ansatz vom Kramerumfang.
Das heißt, wir haben hier zwei Matrizen A und B, die wir miteinander
multiplizieren wollen.
Die laufen hier, also die Matrix A läuft von oben nach unten durchs
Prozessorfeld und die Matrix B von unten nach oben.
Entsprechend werden dann in diesen einzelnen Prozessorfeldern die
Berechnungen durchgeführt und die Ergebnisse, die werden so rechts
rausgeschoben.
Das ist die Ergebnismatrix.
Indem wir die beiden Matrizen in das Feld reingehen, die Berechnungen
durchgeführt werden und die Zwischenergebnisse weiter geschoben
werden, halten wir am Ende hier rechts die Produktmatrix C.
Dann stehen geblieben waren wir bei dieser Folie, Folie 32,
systematischer Entwurf von Parallelteilungen.
Also die Matrixmultiplikation war erstmal dem zweidimensionalen
Prozessorfeld ein Beispiel.
Wir schauen uns jetzt an, wie man sowas systematisch machen kann.
Und das Ganze auch wieder...
Also wir schauen uns an, wie wir das systematisch machen können, aber
am Beispiel der Matrixmultiplikation.
Also wir starten mit unserer Problemdefinition.
Was wollen wir eigentlich berechnen?
Wir bauen darauf ein System von Rekurrenzgleichungen auf.
Das können wir auch aus einem iterativen Algorithmus ableiten.
Und daraus erzeugen wir einen Datenabhängigkeitsgraf.
Und anhand dieses Datenabhängigkeitsgrafes können wir dann ein
Verfahren entwickeln.
Das Ganze bezeichnen wir mit dem sogenannten Mapping-Ansatz.
Wie ja schon geschrieben, im Folgenden beleuchten wir das anhand der
Multiplikation von Matrizen.
Okay, also nochmal die Grundlage.
Was ist denn eigentlich die Matrizenmultiplikation?
Was führen wir hier aus?
Die Berechnung eines einzelnen Elementes der Ergebnismatrix folgt
dieser Gleichung hier.
Wenn das Ganze iterativ ausgeführt wird, also für ein einzelnes Matrix
-Element, können wir das Ganze hier nach der Schulmethode machen.
Die Schulmethode ist relativ simpel.
Wir iterieren hier über die einzelnen Elemente durch.
Wir initialisieren das Ergebnis-Element mit 0.
Und in jeder einzelnen Iteration addieren wir zum bisherigen
Zwischenergebnis dieses Produkt hier.
Das ist alles wie gehabt.
Das ist nichts Neues.
Okay, wenn wir das Ganze nochmal ein bisschen genauer anschauen,
dann stellen wir fest, das ist eine sogenannte Single Assignment Form.
Das heißt, dieses Zwischenergebnis, das wir hier einmal berechnen in
der Schleife, das wird danach nicht mehr verwendet.
Beziehungsweise die Zwischenergebnisse bauen aufeinander aus.
Aber das Zwischenergebnis aus irgendeiner vorherigen Iteration, das
benötige ich später nicht mehr.
Und deshalb können wir diese Abhängigkeit, die hier steht, auch
folgendermaßen schreiben.
Wir führen hier einfach einen weiteren Index k ein, der den aktuellen
Schleifendurchlauf beschreibt.
Das heißt, wir haben im Endeffekt ein System an Rekurrenzgleichungen.
Das heißt nämlich, um das c der aktuellen Iteration k zu berechnen,
brauchen wir hier den Wert aus der vorherigen Iteration.
Wenn wir das Ganze jetzt ein bisschen weiter aufschlüsseln, dann sehen
wir, wir haben hier insgesamt drei Indizes, i, j, k.
Das heißt, dieser Indexraum, den wir hier betrachten, das sind die
Werte von 1 bis n.
Die Schreibweise, die haben wir ja bereits schon mal gesehen in der
Vorlesung.
Vielleicht meint ihr nicht ganz geläufig, das bedeutet einfach nur, n
in eckigen Klammern heißt einfach so viel wie die Elemente von 1 bis
n.
Und auch 3 bedeutet einfach nur, dass wir nicht nur das Intervall
betrachten, sondern den Würfel.
Das heißt, wenn wir das Ganze ein bisschen anders schreiben, ein
bisschen umschreiben, dann haben wir hier insgesamt Element c, das von
drei Indizes abhängt.
Also das hier ist nochmal genau das gleiche, nur ein bisschen anders
dargeschrieben.
Okay.
Das heißt, wir wissen jetzt, wie wir c erzeugen.
Wie sieht es mit a aus?
Also diese Zuweisung hier bedeutet einfach nur, dass sich das Element
a nicht über den Index j verändert.
Also i und k werden ja festgelegt durch den aktuellen Zeitpunkt, wo
wir uns in der Iteration befinden.
Allerdings, also das Element a ist unabhängig von dem Index j bei der
Berechnung hier.
Das gleiche gilt natürlich auch für b.
Also b ist natürlich nicht unabhängig von j, sondern unabhängig von i.
Wir sehen es ja hier.
Für Element b, k, j, da taucht kein Index i auf.
Das heißt, dieses Element ist jetzt für die Berechnung von c, i und k,
b, ik, j, bleibt immer gleich.
Dann brauchen wir noch was für die Initialisierung.
Und zwar legen wir hier einfach fest, also wenn wir den Index 0
erreichen für j, ja, das ist einfach das Element a, i, k.
Das wird einfach so durchgereicht bei der Berechnung.
Und hier das Element c, also das wir berechnen, das ist quasi das
erste Element dieser Iteration, das wird mit 0 initialisiert.
Das ist im Endeffekt genau das, was hier steht.
Okay.
Wenn Sie es jetzt mal genauer anschauen, dann sehen wir, dass jedes
einzelne Element hier, also c, a und b, drei Indizes besitzt.
Ja, okay.
Das können wir doch als Graph abbilden, ja, also als dreidimensionalen
Graph.
Das heißt dann, dieser erste Index i, der beschreibt die Bewegung der
Elemente in x-Richtung.
Der zweite Index k beschreibt die Bewegung der Elemente in y-Richtung.
Und der Index j, ja, der beschreibt die räumliche Richtung, die dritte
Dimension.
Das können wir hier sehen, also so anhand, so wie die Indizes
definiert sind, bewegt sich b eben von links nach rechts.
c bewegt sich von oben nach unten.
Und a bewegt sich ja in den Raum hinein.
Und das Entscheidende ist, also dieses Berechnungsschema, das ist
gleich für alle c, i, j, die ich berechne.
Also es hängt nicht davon ab, welches Element ich gerade berechne, der
Ergebnismatrix.
Dieses System lässt sich auf alle einzelnen Elemente der
Ergebnismatrix anwenden.
Dann ist das hier Ganze nochmal ein bisschen genauer erklärt.
Also wir sehen zum Beispiel hier, dass das Element c, ja, das bewegt
sich eben nur in der Vertikalen.
b bewegt sich nur in der Horizontalen.
Und a bewegt sich nur räumlich.
Wir können das Ganze auch mal aufzeichnen.
Also das war jetzt gewissermaßen dieses Schaubel, das wir gesehen
haben.
Ein Knoten, also eine einzelne Berechnungseinheit.
Falls wir das Ganze jetzt für eine komplette Matrixmultiplikation
aufzeichnen wollen, also diesen kompletten Graphen, dann erhalten wir
im Endeffekt so einen Würfel.
Das Ganze ist hier mal beispielhaft dargestellt für die Größe n gleich
3.
Also im Endeffekt, wenn wir das Element c, 1, 1 berechnen wollen, dann
würden wir zum Beispiel hier starten.
Das Element wird initialisiert mit 0.
Hier kommt das Element b, 1, 1 rein.
Und aus der räumlichen Dimension hier das Element a.
Das heißt, nachdem diese erste Berechnung von c, 1, 1, 1, also des
ersten Schleifendurchlaufs berechnet wurde, dann wird es hier nach
unten weitergereicht.
Da wird dann also a, 1, 2 mal b, 2, 1 multipliziert und auf c, 1, 1
hinzuaddiert.
Also damit wir dann... ich schreibe es mal hin oder ich versuche es
hinzuschreiben.
Leider keine tolle Touchpad-Eingabe, wie es schmeckt.
Deshalb sieht es auf den Folien vielleicht nicht so schön aus.
Ja, vielleicht lasse ich es auch lieber.
Aber ich denke, es ist verständlich, was ich gesagt habe.
Also hier oben haben wir das Element c, 1, 1.
Es wird berechnet, dann wird es nach unten gereicht.
Hier werden noch die Elemente a, a, 1, 2 und b, 2, 1 miteinander
multipliziert und auf c, 1, 1 hinzuaddiert.
Und dadurch erhalten wir das Element c, 1, 1, 2.
Das Ganze wird hier auch noch im nächsten Schritt hier unten
wiederholt.
Und hier steht dann unser Ergebnis.
Die Sache ist, jetzt können wir das Ganze zwar dreidimensional schön
darstellen, aber für eine praktische Anwendung hilft es ja nicht
weiter.
Dreidimensionale Prozessorfelder, das ist zumindest für mich immer
noch Zukunftsmusik.
Stattdessen möchte man dieses Berechnungsschema, das hier abgebildet
ist, auf ein zweidimensionales Prozessorfeld abbilden.
Dazu führen wir eine lineare Transformation durch.
Wir haben hier eine Transformationsmatrix, die beschreibt, wie die
einzelnen Matrizen durch diesen Datenabhängigkeitsgraf wandern.
Dafür haben wir eine Zeit, die wird hier durch die erste Zeile
ausgedrückt.
Das ist t.
Dann haben wir einen Ort, der wird durch die unteren beiden Zeilen
ausgedrückt.
Die zweite Zeile gibt die Bewegung der Matrizen in x-Richtung an.
Und die dritte Zeile gibt die Bewegung der Matrizen in y-Richtung an.
Schlussendlich gibt die erste Spalte die Bewegung der Matrix B an.
Die zweite Spalte die Bewegung der Matrix C.
Und die dritte Spalte die Bewegung der Matrix A.
Das ist die Form dieser Matrix, die ergibt sich im Endeffekt aus der
Anordnung der Indizes.
Wir haben jetzt hier die Anordnung IKJ gewählt, die könnte man auch
theoretisch umdrehen.
Man könnte auch KJI schreiben oder JIK.
Eine beliebige Permutation ist möglich.
Was sich natürlich ändert, ist dann die Transformationsmatrix und auch
der Datenabhängigkeitsgrad.
Wie wir gesehen haben, C ist ja die zweite Spalte, weil das der zweite
Index ist.
Dementsprechend lassen sich auch die Bewegungen von Matrix A und B
nachbeleiten.
Jetzt haben wir diese Transformationsmatrix.
Jetzt wollen wir wissen, die Transformationsmatrix gibt die Bewegungen
der Matrizen in diesem Datenabhängigkeitsgrad an.
Jetzt wollen wir diese Transformationsmatrix verwenden, um daraus die
Berechnung auf einem zweidimensionalen Prozessorfeld abzuleisten.
Also diese Matrix hier, die bezieht sich jetzt auf dieses
zweidimensionale Prozessorfeld.
Nicht auf die Matrix auf diesen Datenabhängigkeitsgraden hier oben.
Um zu erfahren, welche Berechnung wo und wann durchgeführt wird in
diesem zweidimensionalen Prozessorfeld, führen wir hier eine Matrix
-Vektor -Multiplikation durch.
Also wir multiplizieren T mit dem Vektor i, k, j.
Also i, k, j ist natürlich ein Spaltenvektor.
Wenn wir wissen wollen, wo und wann das Element z.B.
c11 multipliziert wird, berechnet wird, dann multiplizieren wir diese
Matrix T mit dem Vektor 111.
Das führt dann zu dem Ergebnisvektor, also nochmal als Beispiel hier,
111, führt zu dem Ergebnisvektor 310.
Das bedeutet, dass das Element c11 im dritten Takt in der ersten
Spalte an dieser Position berechnet wird.
Was hier im Endeffekt gezeigt wird, ist die Matrix-Multiplikation nach
Kramer -Löwen.
Das heißt, das a ist der Element aus der Matrix c, das berechnet wird.
In der mittleren Prozessorlinie wird das berechnet.
Okay.
Jetzt haben wir uns angeschaut, wie man diesen Datenabhängigkeits
-Programm projizieren kann auf ein zweidimensionales Prozessorfeld.
Da müssen wir uns auch überlegen, welche Anforderungen muss dann
eigentlich diese Transformation erfüllen, damit die überhaupt zulässig
ist.
Okay, also erstmal darf pro Takt und pro Prozessor nur eine Berechnung
durchgeführt werden.
Das wäre ja unsinnig, wenn ein Prozessor mehrere Berechnungen
gleichzeitig durchführen könnte in einem Takt.
Ein Prozessor kann in einem Takt immer nur eine Berechnung
durchführen.
Und das bedeutet im Endeffekt, dass t auf dem gesamten Indexbereich
eine injektive Abbildung sein muss.
Das heißt im Endeffekt, dass t nicht singulär sein muss.
Weil wenn t singulär wäre, dann könnte es dazu führen, dass ein
Element an zwei verschiedene Prozessoren weitergereicht wird.
Dadurch könnte es sein, dass mehrere Elemente gleichzeitig an einem
Prozessor ankommen, und dass dadurch das Berechnungsschema nicht mehr
funktioniert.
Okay, das war der sogenannte Mapping-Ansatz.
Jetzt kann man sich natürlich überlegen, welche Vor- und Nachteile
dieser Ansatz insgesamt besitzt.
Also Vorteile, ein großer Vorteil ist einmal, dass man dadurch
automatisiert Algorithmen erzeugen kann, mit einer
korrektheitserhaltenden Transformation.
Das heißt, alleine durch diese Transformation kann sichergestellt
werden, dass der resultierende Algorithmus auch funktioniert.
Wenn man sich jetzt einen komplett neuen Algorithmus ausdenken würde,
um ein Problem zu lösen, müsste man ja immer erstmal zeigen, dass der
auch funktioniert, dass er irgendwie beweisen kann.
In diesem Fall ist es nicht notwendig, weil die Transformation ja
inhärent korrektheitserhaltend ist.
Dieser Ansatz, der kann auch auf verschiedene Probleme angewendet
werden, sofern sich das Ganze als iterativer Algorithmus darstellen
lässt, beziehungsweise wenn sich aus dem iterativen Algorithmus ein
reines Rekurrenzsystem darstellen lässt.
Ja, eine Frage?
Kannst du vielleicht nochmal an das Polygraphen sprechen?
Mhm.
Und vielleicht das Polygraphen-Thema zum Durchgangspunkt.
Das hier?
Genau.
Ja, das ist X.
Also das ist hier.
Das ist X.
Aber es kam auch auf X, weil die Bildkarte da ist.
Ja, also diese Transformationsmatrix T, die gibt die Bewegung der
Matrizen im Datenabhängigkeitsgraphen an.
Also wenn man... es kommt gleich noch ein Appler dazu, da wird es
vielleicht ein bisschen klarer.
Also weil... T beschreibt nicht die Bewegung der... oder beschreibt
nicht dieses Prozessorverhältnis im Endeffekt.
Also ich werde gleich noch...
Das Problem ist aber, dass ich es geschafft habe, dass das Graphen den
Datenabhängigkeitsgraphen vorzustellen.
Ja.
Das ist von T.
Also nochmal, T ist eine Transformationsmatrix, also wir haben ja
diesen Datenabhängigkeitsgraph, der leitet sich daraus ab, wie die
Matrizen, ja, in welche Richtung die wandern.
Ok, die Frage verstehe ich nicht ganz.
Klein T ist ja die Zeit.
Ja, die Zeit, die gibt im Endeffekt den Takt vor.
Das heißt, dadurch, dass hier Einsen stehen, das bedeutet nur, dass in
jedem Takt eine Berechnung durchgeführt wird.
Würde hier zum Beispiel eine Zwei stehen, oder würde hier in der
kompletten ersten Reihe eine Zwei stehen, da würde die Berechnung nur
jeden zweiten Takt durchgeführt werden.
Es wird eine Berechnung durchgeführt, dann wird ein Takt gewartet, und
dann wird die nächste Berechnung durchgeführt.
Ok.
Aber die Frage war doch, diese Matrix muss eben zu der linearen
Transformation...
Mhm.
...in Richtung diesen Teilchen, sobald er aufgeräumt wird.
Ja.
Und dabei ist die Frage auch, ob man die, ob man in dem Bild rechts,
was da drin ist, zwei niedrige Programmprozesse darstellt, was war
jetzt die X und was die Y?
Das war doch die Frage.
Oder kann man das da raus holen?
Achso, ok.
Also in diesem Vektor hier, also das ist die, genau, das ist T.
Das war die, das war X und das war Y.
Ne, die Frage war eigentlich, wie hat man das komponiert?
Rechts haben wir ja diese Prozessoren...
Mhm.
...komponiert.
Da in diesem Prozessorenarray eine X-Richtung, weil wir ja auch eine
Linienrichtung zeigen, also die X-Koordinate macht die X-Koordinate.
Ach, ok, ok, jetzt verstehe ich.
Also die X-Koordinate, die verläuft in die Richtung, also nach rechts,
und die Y-Koordinate nach unten.
Man muss aber allerdings bei dieser Indizierung noch darauf achten,
dass teilweise hier die, ja, also dass hier teilweise relative
Positionen verwendet werden.
Also bei dem Kramer-Löwen-Ansatz, wie ich ja vorhin gesagt habe, wird
das mittlere Element zuerst berechnet.
Also das C11 wird in der Mitte berechnet.
Aber ich zeige gleich nochmal das Applet, da wird es hoffentlich ein
bisschen klarer.
Ok, wir waren hier bei den Vorteilen.
Genau, also so ein Algorithmus, also man kann dadurch systematisch
verschiedene Algorithmen erzeugen.
Man kann das nicht nur auf algebraische Probleme wie
Matrixmultiplikation anwenden.
Zum Beispiel auch Graf-Algorithmen.
Also wenn jemand z.B.
mal den Borscher-Algorithmus von Ihnen was gehört hat, der wird auch
noch später in der Vorlesung vorgestellt.
Der Algorithmus, der also berechnet, ob ein Graf zusammenhängend ist,
also welche Knoten man erreichen kann von welchen anderen Knoten.
Und dazu kann auch so ein Mapping-Ansatz verwendet werden.
Der Nachteil dieses Ansatzes ist, dass halt die Grundlage dafür ist
ein linearisiertes Berechnungsschema.
Also wir haben ja gesehen, um ein c, k, i, j zu berechnen, brauchen
wir immer das Element, also k-1, das vorhergehende, das verwendet
wurde.
Das davor berechnet wurde.
Das Problem ist dadurch, dass das ja die Berechnung so ein bisschen
inhärenzsequenziell macht.
D.h.
die Möglichkeit zur Parallelverarbeitung ist bei diesem Ansatz ja
nicht eingeschränkt.
Was man allerdings machen kann, ist z.B.
wenn man jetzt zwei sehr große Matrizen miteinander multiplizieren
möchte, man könnte die, man hat ein zweidimensionales Prozessorfeld,
man könnte diese Matrizen so lange aufteilen und dann eben ein
zweidimensionales Prozessorfeld verwenden, um dann quasi eine
Teilmatrix zu berechnen.
Und das Ganze dann parallel machen.
D.h.
wenn man mehrere Prozessorfelder zur Verfügung hat, arbeitet man zwar
lokal sequenziell, also die Berechnung im Prozessorfeld wird
sequenziell durchgeführt, aber man kann trotzdem mehrere
Matrizenmultiplikationen gleichzeitig durchführen.
Und ein weiterer Nachteil ist eben, es handelt sich hier um homogene
Berechnungen.
D.h.
die gleiche Operation wird immer wieder durchgeführt.
D.h.
wenn man irgendeinen Algorithmus hat, wo die Schritte verschieden
sind, wo verschiedene Schritte in einer Iteration durchgeführt werden,
oder wo sich die Schritte verändern über die Iteration hinweg, dann
funktioniert dieses Schema auch nicht mehr.
Genau.
Was ich euch jetzt hier gezeigt habe, ist nur ein kleiner Ausschnitt
davon, was mit diesem Mapping-Ansatz möglich ist.
Da gibt es eine relativ ausführliche Literatur dazu, z.B.
dieses Buch von Zehn, der sich einem kompletten Buch nur den
systolischen Arrays gewidmet.
Um das Ganze nochmal ein bisschen anschaulicher zu gestalten,
gibt es hier ein Applet.
Das hat ein Kompletoner von Ihnen vor vielen, vielen Jahren
entwickelt.
Dazu noch ganz kurz eine Kleinigkeit.
Dieses Applet hat schon ein paar Jahre auf dem Buckel, wie man sagen
würde.
D.h.
es läuft auf einer alten Java-Version.
Es ist so, dass seit Java 7 Update 51, wo der neue
Sicherheitsmechanismus eingeführt wird, durch den automatisch Java
-Anwendungen geblockt werden, die auf einer veralteten Java-Version
laufen.
D.h.
wenn ihr dieses Applet aktivieren möchtet bei euch lokal, dann müsst
ihr im Endeffekt diese Seite auf eine Whitelist stellen, sodass sie
nicht mehr blockiert wird.
Wie genau das gemacht wird, das habe ich hier zusammengefasst.
Also in dem Vorlesungsmaterial, in dem kleinen Dokument Verwendung von
Applets unter Java 7 Update 51 im Bereich Zusatzmaterial.
Also in diesem Applet, da sind auch noch zwei andere Anwendungen
erklärt.
Also einmal Sortieren, das lässt sich auch mit Hilfe von einem
systolischen Array bewerkstelligen.
Und Matrix-Vektor-Multiplikation.
So sieht das Ganze so aus.
Wir brauchen jetzt nochmal die Matrix-Multiplikation.
Um nochmal zu deutlichen, wie das eigentlich funktioniert.
Also wir haben den Zeitvektor.
Da reiche ich normalerweise eigentlich immer 1, 1, 1 ein, weil ich
möchte eigentlich in jedem Takt eine Berechnung durchführen.
Und ich nehme hier einfach mal irgendwelche Werte ein.
Und erhalten folgendes Ergebnis.
Okay, also wir hören uns nochmal dran, wie die Zuordnung ist.
Die zweite Zeile gibt die Bewegung in X-Richtung an.
Die dritte Zeile in Y-Richtung.
Die erste Spalte zeigt die Bewegung von Matrix-B.
Die erste von Matrix-B.
Die zweite von Matrix-C.
Und die dritte von Matrix-A.
Okay, jetzt können wir sehen.
Also die Matrix-A, die ist rot eingezeichnet.
Also die bewegt sich hier von unten nach oben.
Und ja, das ist genau hier der Fall.
Also man sieht, Bewegung X, 0, bewegt sich nicht irgendwie horizontal,
sondern nur vertikal.
Also ein positiver Wert bedeutet hier eben, dass die Matrix von oben
nach unten geht, und ein negativer von unten nach oben.
Dieses Koordinatensystem ist im Endeffekt, ja, es zeigt nach unten.
Dann die Matrix-B.
Wir haben hier 1,1, das heißt sie bewegt sich von links oben nach
rechts unten.
Kann man hier auch sehr schön erkennen.
Die Zwischensumme schließlich, die wird von links nach rechts
durchgereicht.
Was man hier sieht.
Wenn man in eine unzulässige Matrix eingeht, dann passiert folgendes.
Dann ist die Transformationsmatrix singulär, das heißt die
determinante ist gleich 0.
Dadurch kann sich kein gültiger Signalfluss ergeben.
Allerdings wird dann trotzdem aufgezeigt, was hier passieren würde.
Also man sieht, dass die...
wird zwar der Graph dargestellt, aber man kann erkennen, dass sich
hier raus kein gültiges Berechnungsschema ergibt.
Also dieser Graph, der ist, muss man sich dreidimensional vorstellen.
Okay.
Dann kommen wir zurück zur Präsentation.
Okay.
Damit schließen wir jetzt vorerst mal das Kapitel der
Matrixmultiplikation.
Und machen weiter mit dem neuen Thema, und zwar der Auswertung von
Polynomen.
Okay, also was ist ein Polynom?
Ich denke, das ist jedem geläufig.
Wir haben die... ja, lassen Sie sich...
In den Koeffizienten-Darstellungen sehen die folgenden Maßnahmen aus.
Also nehmen wir eine Summe von i gleich 0 bis n.
Wir haben Koeffizienten, die mit einer Variable multipliziert werden.
Und diese Variable, die wird potenziert.
Also dieses n...
gibt den Grad des Polynoms an.
Also die höchste Potenz, die im Polynom berechnet wird.
Diese einzelnen Produkte hier, die werden aufsummiert.
Das heißt, ein Polynom lässt sich darstellen, immer durch die
Koeffizienten.
Und die Stelle, an der es ausgewertet wird.
Die Problemgröße, also für die Auswertung von einem Polynom, die ist
n.
Also der Grad des Polynoms gibt die Problemgröße an.
Die Datenstruktur, also wie kann ich denn so ein Polynom abspeichern?
Es ist einfach ein eindimensionales Feld.
In einem eindimensionalen Feld werden die Koeffizienten abgespeichert.
Und die Frage ist, wie viele arithmetische Operationen sind denn
notwendig, um so ein Polynom überhaupt auszuwerten.
In der Einleitung haben wir bereits das VORNACH-Schema kennengelernt.
Das benötigt insgesamt N-Multiplikationen und Additionen.
Es gibt allerdings, also das VORNACH-Schema ist für ganz allgemeine
Polynome.
Also da kann man keine besonderen Eigenschaften ausnutzen.
Wir können uns mal dieses spezielle Polynom allerdings anschauen, wo
alle ai gleich 0 sind.
Das heißt, gleich 1, ja.
Natürlich.
Gleich 1 halt.
Wenn diese ganzen Koeffizienten gleich 1 sind, lässt sich dieser Term
vereinfachen.
Dann haben wir im Endeffekt hier nur noch die Summe dieser Potenzen.
Und diese Potenzsumme, die lässt sich faktorisieren in diese beiden
Terme hier.
Das heißt, wenn wir uns anschauen, welche arithmetischen Operationen
werden hier eigentlich durchgeführt.
Also normalerweise, wenn wir das naiv auswerten würden, dann hätten
wir auch wieder hier unsere N-Additionen und da sehr viele
Multiplikationen.
Stattdessen, wenn wir das klug auswerten, haben wir einmal hier also
zwei Additionen bzw.
Subtraktionen.
Die sind hier.
Eine Potenzierung.
Dieses hier, x-hoch-n-plus-1.
Die kann man, wenn man die Intelligenz durchführt in logarithmischer
Laufzeit, berechnen.
Also man kann ja zum Beispiel, um die Potenz von x-hoch-4 zu
berechnen, kann man zuerst x-Quadrat berechnen und dann x-Quadrat
nochmal potenzieren.
Anstatt 4 mal x mit sich selbst zu multiplizieren.
Wenn man dieses Schema allgemein für n anwendet, kommt man da
insgesamt auf die logarithmische Laufzeit.
Und schlussendlich wird hier noch eine Division durchgeführt.
Okay, das war eine relativ allgemeine und anschauliche Definition.
Was wir, wie wir das Ganze jetzt betrachten, ist mal ein bisschen
abstrakter, also auf einer mathematischen Ebene.
Das heißt, wir wollen jetzt untere Schranken beschreiben, also wie
effizient kann man ein Polynom eigentlich auswerten.
Deshalb sagen wir nicht nur allgemein, dass wir ein Polynom auf einer
reellen Zahl auswerten zum Beispiel, sondern auf einem endlichen
Körper, also auf einer algebraischen Struktur.
Das heißt, wir sagen, wir werten ein Polynom auf f aus und f ist ein
algebraischer Körper.
Das heißt, für die meisten von euch sind vielleicht Körper noch aus
Grundlagen der Mathematik bekannt.
Das ist eigentlich auch gar nicht so entscheidend, jetzt die exakte
mathematische Definition für uns, sondern wichtig ist nur, also ein
Körper ist eine algebraische Struktur, bei dem alle vier
arithmetischen Operationen erlaubt sind.
Das heißt, wir haben Addition, Subtraktion, Multiplikation und
Division.
Okay, des Weiteren sind die Koeffizienten und die Stelle, an der wir
das Polynom auswerten wollen, transzendent über diesen Körper.
Das heißt lediglich, dass diese Stelle x im Zusammenhang mit den
Koeffizienten ist keine Nullstelle des Polynoms.
Weil dadurch würden sich noch ein paar andere mathematische
Ablänglichkeiten ergeben, die könnte man anderen Berechnungsschemata
ganz einfach anwenden.
Das heißt, wir haben auch keine zusätzlichen Informationen voneinander
und diese Werte sind alle völlig unabhängig voneinander.
Also wir wissen a priori, wir haben keine weitere Information, die wir
irgendwie nutzen könnten, um uns die Berechnung zu vereinfachen.
Okay.
Das ist ja die Definition von vorhin.
Das ist unser Polynom, das wir auswerten.
Das heißt also, das Polynom, hier dieser Ausdruck, der Auswertung über
den Körper f, ist im Endeffekt eine Körpererweiterung.
Das heißt, so eine Körpererweiterung ist im Endeffekt, also der Körper
wird erweitert unter Beibehaltung der bestehenden Operationen, die
auch auf dem Körper f, also die Körpererweiterung erhält die
Eigenschaften, die für diesen Ursprungskörper f gelten.
Und die bestimmten Eigenschaften erfüllen zum Beispiel, das war bei f,
dass die Additionen und Subtraktionen bleiben auf jeden Fall erhalten.
Das heißt, wenn wir dieses Polynom n in Grades über f auswerten
wollen, das ist die mathematische Definition dafür, das heißt, wir
konstruieren dieses Element hier auf f, ausgehend von der Menge b.
Und b können wir sagen, das ist so gewissermaßen eine
Anfangsinformation oder eine Eingabemenge, die wir haben.
Das heißt, je umfangreicher b ist, also je mehr Informationen wir zur
Verfügung haben, desto einfacher ist die Auswertung des Polynoms.
Also Beispiele für ähnliche Körper, das sind zum Beispiel die
rationalen Zahlen oder auch die reellen Zahlen.
Es gibt hier auch noch andere Körper, wie zum Beispiel Galoisfelder.
An der Stelle nur ganz kurz, ein Galoisfeld von 2 auf 8, das
beschreibt im Endeffekt den Definitionsbereich eines Bytes.
Also ein Byte, wenn man damit rechnet, das stellt auch das
algebraische Konstrukt eines algebraischen Körpers dar.
Okay.
Jetzt haben wir das alles nur...
Also wir wollen gar nicht zu sehr hier in diese mathematische
Terminologie einsteigen.
Interessanter ist für uns eigentlich die praktische Anwendbarkeit oder
die Schlüsse, die wir rausziehen können für die praktische Anwendung.
Okay.
Dann an der Stelle ein paar kleine Beispiele.
Also je nachdem abhängig, wie unsere Anfangsinformation oder unsere
Eingabemenge aussieht, haben wir bestimmte andere
Startvoraussetzungen.
Und dann ist die Auswertung leichter.
Das heißt, wenn B bereits dieser Körperweiterung entspricht, dann ist
es trivial.
Also diese Notation bedeutet im Endeffekt nur, dass wir das Ergebnis
bereits kennen.
Das heißt, dann haben wir auch keinerlei Auswand bei der Berechnung.
Okay.
In diesem Fall, das ist der allgemeine Fall.
Das heißt, dass X und A, also die Stelle, an der wir das Periodum
auswerten, und die Koeffizienten sind allgemein nicht bekannt.
Also wir wollen allgemeine Auswertung durchführen.
Da gibt es mehrere Methoden, wie man das machen kann.
Also die naive Variante ist, wenn wir einfach von links nach rechts
rechnen.
Das sind n²-arithmetische Operationen.
Wir summieren interne auf.
Also eine Potenz, also die x hoch n zum Beispiel, zu berechnen würde
hier im naiven Ansatz, wenn wir xn mal mit sich selbst multiplizieren
und dann auch mit dem Koeffizienten.
Dadurch enthalten wir insgesamt eine Laufzeit von n².
Okay, das Ganze lässt sich natürlich ein bisschen klüger auswerten.
Und zwar, wir können zuerst vorab die Potenzen berechnen.
Um x hoch n zu berechnen, kann ich bereits auf das vorherige Ergebnis
zurückgreifen, auf x hoch n-1.
Dann x hoch n ist ja nichts anderes als x hoch n mal x.
Das heißt, dadurch kann ich diese ganzen Potenzen mit insgesamt n-1
Multiplikationen berechnen.
Die Produkte aus den Potenzen mit den Koeffizienten, das ist pro
einzelnen Produkt, ist das eine Berechnung.
Insgesamt habe ich n Produkte, also ergeben sich daraus n
Multiplikationen.
Schlussendlich muss ich diese ganzen Produkte noch miteinander
addieren.
Das sind insgesamt dann auch n Additionen.
Wenn ich das Ganze zusammenfasse, halte ich dann 3n-1 arithmetische
Operationen.
Also schon mal wesentlich besser als dieses n².
Jetzt ist es so, also dieser Ausdruck hier bedeutet im Endeffekt
lediglich, dass wir die Stellen, also dass wir diese Potenzen bereits
kennen.
Das würde dem Fall entsprechen, wenn wir ein Polynom, also wir haben
eine Stelle, aber wir wollen verschiedene Polynome da auswerten.
Das heißt, wir hätten unterschiedliche Koeffizienten, aber die
Stellen, an denen wir die Polynome auswerten wollen, das würde gleich
bleiben.
Dadurch können wir uns diesen ersten Schritt sparen.
Das hier fällt weg, weil die Potenzen bereits bekannt sind.
Dadurch hätten wir dann 2n arithmetische Operationen.
Schließlich gibt es dann auch das Horner-Schema, das wir bereits in
der Einführung gesprochen haben.
Da haben wir bereits die Analyse durchgeführt.
Das Horner-Schema benötigt n Additionen, n Multiplikationen und
dadurch insgesamt 2n arithmetische Operationen.
Dann, jetzt sehen wir, dass wir die mathematischen Grundlagen geklärt
haben, können wir jetzt weiter machen mit den unteren Schranken.
Also wir wollen jetzt untere Schranken für die Polynomauswertung
bestimmen.
Dann gibt es einmal den Satz von Ostrofsky von 1954.
Der konnte zeigen tatsächlich, dass wir ein Polynom n gradus
tatsächlich mindestens n Additionen benötigen, um das zu berechnen,
also ganz allgemein.
Noch ein kleines Detail, ganz wichtig, und zwar, wir berechnen hier
nicht in immer n Körpern, sondern in Ringen.
Also in der mathematischen Struktur, der algebraischen Struktur von
Ringen sind keine Divisionen erlaubt.
Quasi ein schwächeres Konstrukt als ein Körper.
Also ein Körper ist gleichzeitig ein Ring, aber ein Ring ist kein
Körper.
Pan konnte dann 1966 zeigen, dass wir mindestens n Multiplikation
benötigen, um ein Polynom zu berechnen.
Und aus diesen beiden Erkenntnissen kann man dann schließlich
ableiten, dass das Vor-Nach-Schema optimal ist.
Für die Auswertung eines allgemeinen Polynoms.
Also wie gesagt, ein allgemeines Polynom, wir nutzen hier keinerlei
Eigenschaften aus, die sich jetzt aus der Struktur von einem Polynom
ergeben.
Also zum Beispiel, wenn jetzt die Koeffizienten irgendwelche
Umformungen erlauben, sodass man das Polynom schneller ausrechnen
könnte.
Genau, daraus erhalten wir dann das Korolla aus diesen beiden Sätzen,
dass eben das Vor-Nach-Schema optimal ist.
Also diese Beweise sind relativ umfangreich und komplex, deshalb
werden wir an dieser Stelle auch nur den Satz von Ostkowski beweisen.
Und das Ganze machen wir über Induktion.
Das ist eigentlich die Herausforderung, wenn man so einen Beweis
führen will, für die Anzahl der Additionen.
Also es ist ja so, wenn man diesen Beweis durchführt, muss man zeigen,
dass es unabhängig davon, welches Verfahren ich anwende, dass diese
untere Schranke für alle Algorithmen gilt.
Also alle Algorithmen, die man sich möglicherweise irgendwie ausdenken
kann, für die gilt diese untere Schranke.
Das heißt, wir müssen das Problem auch relativ allgemein handeln.
Wir werden hier sehr abstrakt argumentieren.
Den Beweis selbst, ja, werden wir über Induktion.
Also wir betrachten ganz allgemein einen beliebigen Algorithmus, der
dieses Polynom hier auswertet.
Jetzt vereinfachen wir zuerst dieses Problem.
Wir können ja x überall durch 1 ersetzen.
Das heißt, dieser komplette Tem hier, der fällt dann raus.
Diese Umformung ist zulässig, weil also die Aufsummierung der
einzelnen Koeffizienten ist ja mindestens genauso komplex wie die
Berechnung des kompletten Polynoms.
Also wenn wir auch noch zusätzlicherweise die Stellen berechnen
würden, also die noch potenzieren müssen und noch mit den
Koeffizienten multiplizieren.
Das heißt, wir erhalten einen neuen Algorithmus A'.
Das ist der gleiche, wie wenn wir A verwenden unter der Bedingung,
dass x gleich 1 ist.
Genau wie ich eben schon verbal gesagt habe, hier nochmal die
Zusammenfassung.
Also dieser Algorithmus A' macht im Endeffekt nichts anderes, als
einfach nur die Summe dieser Koeffizienten zu berechnen.
Selbstverständlich benötigt A' nicht mehr Additionen als A.
Wir haben ja keinen einzigen Summand aus der Summe entfernt.
Oder auch nichts hinzugefügt.
Okay.
Und die Behauptung, die wir jetzt aufstellen, ist, dass, also wenn wir
ein liebiges n haben, dass jeder Algorithmus mindestens n Additionen
benötigt, um diesen Term hier aufzunehmen.
Okay.
Um den genügend Platz zu haben, damit wir den Beweis komplett führen
können, hierzu eine neue Folie.
Also hier nochmal die Behauptung, um diesen Ausdruck auszuwerten,
benötigen wir mindestens n Additionen.
Ich habe vorhin schon gesagt, wir führen den Induktionsbeweis durch.
Das heißt, wir brauchen einen Induktionsanfang, der ist bei n gleich
0.
n gleich 0.
Das ist relativ trivial.
Diese Summe fällt zusammen zu lediglich einem einzelnen
Koeffizientenwert.
Da muss man nichts addieren.
Das heißt, wir kommen vollkommen ohne Addition aus.
Das heißt, der Induktionsanfang gegeben unserer Behauptung ist
erfüllt.
Okay.
Jetzt folgt der Induktionsschluss.
Also wir müssen zeigen, dass unsere Behauptung auch für n plus 1 gilt.
Aber wenn sie für n plus 1 gilt, haben sie bereits für den
Induktionsanfang gezeigt, können wir aus diesem Schritt hier für jede
beliebige n herleiten, dass unsere Behauptung stimmt.
Okay.
Dazu führen wir den Widerspruchsbeweis.
Okay.
Das heißt, wir gehen davon an, es gibt einen Algorithmus B, der diese
Summe von n plus 1, also der für n plus 1 diese Summe berechnet, mit k
Additionen, wobei k echt kleiner ist als n plus 1.
Okay.
Jetzt wird es ein bisschen abstrakter.
Okay.
Jetzt gehen wir ganz allgemein davon aus, dass die erste Addition, die
von diesem Algorithmus B durchgeführt wird, dieses Produkt 1 plus ein
zweites Produkt ist.
Also diese Produkte sind folgendermaßen definiert.
Also wir haben hier irgendein beliebiges Produkt.
Das heißt, ich potenziere die einzelnen Koeffizienten jeweils mit
einer natürlichen Zahl und multipliziere sie danach miteinander.
Also Ri, diese Potenz, kann ich für jeden einzelnen Koeffizienten
wählen.
Also völlig allgemein, völlig unabhängig.
Und diesen ganzen Term multipliziere ich dann noch mit einem Skalar
C1.
Das gleiche auch für Pi2.
Das heißt, also was die Idee dahinter ist, hier in dieser
Herangehensweise, also bevor ich meine erste Addition durchführe in
dem Algorithmus, darf ich zuvor beliebige andere Transformationen mit
den Koeffizienten durchführen.
Also ich darf in dem Fall zum Beispiel jetzt Multiplikationen.
Divisionen sind ja nicht erlaubt, aber Multiplikationen.
Dadurch, dass ich vorher irgendwelche Multiplikationen durchführe,
könnte ich ja meine Koeffizienten so verändern, irgendwie irgendwas
berechnen, wodurch ich weniger Additionen brauche.
Das heißt, ich würde im Endeffekt Additionen durch Multiplikationen
substituieren.
Okay.
Sagen wir völlig ohne Beschränkung der Allgemeinheit, dass mindestens
einer dieser Potenzen ungleich Null ist.
Damit wollen wir nur sicherstellen, also dass dieser Term, also dieser
Koeffizient auch tatsächlich in der ersten Summe vorkommt.
Könnten wir auch in beliebigen anderen Koeffizienten werden.
Ich weiß nicht, den ersten, zweiten, fünften etc.
Aber ohne Beschränkung der Allgemeinheit sage ich jetzt mal, der
letzte.
Das heißt, dass 1 plus 1 kommt auf jeden Fall vor.
Das heißt, es handelt sich auch tatsächlich um ein vollwertiges
Polynom von Grad N plus 1.
Okay.
Wenn wir jetzt 1 plus 1 aber durch Null ersetzen, dürfen wir machen,
da wir die Vision von vornherein ausgeschlossen haben.
Wir bewegen uns jetzt wieder auf einem Ring, nicht auf einem Körper.
Dann wird die erste Addition hier aus diesem Ausdruck eliminiert.
Weil wenn ich irgendwas mal Null nehme, kommt das schließlich bei Null
raus.
Das heißt, dieser Ausdruck hier, also der hier, da unten steht es
auch, ist dann gleich Null.
Das heißt, die erste Addition des Algorithmus findet gar nicht statt.
Okay.
Dann überlegen wir uns, okay, wir können ja, wenn jetzt diese erste
Addition gar nicht stattfindet, dann können wir daraus ja einen neuen
Algorithmus bestimmen.
Also ein Algorithmus B', der genau das gleiche macht wie B, aber unter
der Voraussetzung, dass An plus 1 gleich Null ist.
Dieser Algorithmus berechnet die Summe, diese Summe hier, also auch
diese Koeffizientensumme.
Und wenn jetzt allerdings der Koeffizient An plus 1 gleich Null ist,
das ist ja exakt das gleiche wie die Summe der Koeffizienten von Null
bis N.
Das würde bedeuten, dadurch, dass ich eine Addition eingespart habe,
brauche ich, also um das zu berechnen, nicht k Additionen, sondern k-1
Additionen.
Und k-1 ist kleiner als N.
Und das stellt Widerspruch dar zu unserer Behauptung.
Das heißt, dadurch habe ich gezeigt, dass diese Annahme nicht für N
plus 1 gilt, gilt sie folgendermaßen auch nicht für N.
Und das war schon der Beweis.
Also damit können wir zeigen, wenn wir ein allgemeines Polynom
auswerten, dass das Horner-Schema optimal ist, weil es die optimale
Anzahl an Additionen und Multiplikationen verwendet und sonst
keinerlei andere algorithmische Operationen.
Die Frage ist jetzt allerdings, was passiert denn eigentlich, wenn wir
das gleiche Polynom an verschiedenen Stellen auswerten wollen.
Also eine komplett andere Situation.
Beim Horner-Schema geht es darum, beliebiges Polynom, ich habe vorher
keinerlei Informationen.
Das heißt, im Unterschied zu vorher sind diese Koeffizienten bekannt.
Ich möchte irgendwie vielleicht m Berechnungen, m Auswertungen
durchführen und für diese m Ausberechnungen bleiben die Koeffizienten
immer gleich.
Dazu gibt es hier ein kleines Beispiel.
Und zwar folgendes Polynom 6.
Das ist relativ umfangreich.
Aber was man ja machen kann, ohne das mathematisch groß herzuleiten,
man kann dieses Polynom ja faktorisieren.
Das heißt, wenn ich von diesen riesigen Termen hier x²-4 ausklammere,
dann habe ich hier noch ein Polynom vierten Grades und einen Rest.
Dieses Polynom vierten Grades kann ich jedenfalls nochmal
faktorisieren.
Nochmal den Polynom zweiten Grades und in zwei Polynome zweiten Grades
aufteilen.
Weil interessanterweise die Struktur dieser Faktorisierung sieht so
aus, dass ich hier eben vorne immer x² stehen habe plus ein Skalar.
Schauen wir uns mal an, wenn ich dieses Polynom nicht wie hier nach
dem Horner-Schema ausrechne, sondern zunächst diese Teile, diese
Einzelteile berechne, wie auf wie viele arithmetische Operationen
komme ich denn dann?
Das heißt, was wir brauchen, sind die Potenzen.
Es tauchen ja keine höheren Potenzen als x² mehr auf, auch in diesem
Berechnungsschema.
Also wenn ich jeweils das hier alles ersetze.
Das heißt, wir berechnen x², dafür brauchen wir insgesamt eine
Multiplikation.
x mal x ist eine Multiplikation.
Dann berechnen wir p2, also p2 ist ja das hier.
Wir haben hier eine Multiplikation, 2 mal x², dann haben wir hier eine
Multiplikation, 8 mal x, und schließlich zwei Adjektionen.
Wenn wir p4 zusammenrechnen, also wir haben p2 bereits berechnet, das
heißt, hier steht nicht mehr dieser Ausdruck, sondern irgendein fester
Wert, den wir bereits vorher berechnet haben.
Dann kommen wir hier auf eine Multiplikation und schließlich zwei
Adjektionen, also einmal hier und hier.
x² haben wir jetzt auch bereits vorher berechnet.
Schließlich das gleiche Spiel nochmal.
Wenn wir p6 berechnen, p4 ist bereits bekannt, das ist im Endeffekt
nur noch ein Skalar, das mit diesem Ausdruck hier multipliziert wird.
Hier ist eine Subtraktion, beziehungsweise Addition.
Hier ist noch eine Multiplikation und schließlich diesen Rest, den wir
noch drauf addieren, führt zur zweiten Addition.
Wenn wir all das zusammenrechnen, haben wir sechs Additionen und fünf
Multiplikationen.
Und dann sehen wir, hoppla, das ist besser als das Horner Schema.
Bei dem Horner Schema hätten wir insgesamt sechs Multiplikationen
gebraucht.
Okay, was lernen wir daraus?
Das heißt, wenn die Koeffizienten bereits bekannt sind, dann können
wir so Preconditioning vornehmen, also eine Voreinstellung.
Wir können das Polynom vorher umformen, also durch irgendein Verfahren
und uns dadurch Berechnungen erleichtern.
Okay, ganz allgemein noch mal.
Wir haben hier dieses Polynom, bei dem die Koeffizienten bereits
bekannt sind.
Dieses Schema, das wir beispielhaft auf der vorherigen Folie
ausgeführt haben, ein bisschen zu verallgemeinern, können wir dieses
Polynom folgendermaßen faktorisieren.
Wir haben ein Polynom des Gerades n.
Und in diesem Polynom, da klammern wir gewissermaßen dieses x²-αn aus.
Also dieses αn, das muss irgendwie berechnet werden.
Das war jetzt in dem Beispiel davor, war das einmal diese 9 und hier
die –4.
Okay.
Das heißt, wenn wir diesen Term ausklammern, dann erhalten wir ein
Polynom vom Grad n-2 und noch irgendeinen Rest.
Dieses Schema, das können wir solange rekursiv anwenden, bis wir
irgendwann mal auf der untersten Ebene angekommen sind, wenn wir ein
Polynom vom Grad 4 haben.
Hier wird noch einmal dieses Verfahren angewendet.
Also wir klammern nochmal x² minus diesen Skalar hier aus.
Und multiplizieren das dann mit einem Polynom 2.
Plus dem Rest auf der Ebene.
Plus dem Rest hier für die Größe 4.
Und daraus können wir ein allgemeines Verfahren ableiten.
Das heißt, dieses Polynom wird rekursiv berechnet.
Wir berechnen zuerst P4, dann berechnen wir P6, P8, bis wir dann
schließlich bei Pn oben angelangt sind.
Das Problem ist allerdings bei diesem Verfahren, wir müssen ja erstmal
diese Stellen hier bestimmen.
Und das ist halt im Allgemeinen nicht so einfach.
Das heißt, wenn wir das allgemeine, also dieses Berechnungsschema für
die Größe n betrachten, wie viele Berechnungen werden da insgesamt
durchgeführt, wir berechnen einmal x², das ist eine Multiplikation,
dann diesen Ausdruck aufzuwerten, das haben wir ja schon auf der Folie
davor betrachtet, nehmen wir zwei Additionen, zwei Multiplikationen.
Wenn wir das alles rekursiv anwenden, kommen wir insgesamt dann auf n½
plus zwei Multiplikationen und n Additionen.
Das heißt, wir sind besser als das Horner-Schema.
Da gibt es auch einen Satz, der Borodin und Monroe bewiesen wurde.
Sagt einfach nur aus, wenn wir quasi ein Polynom n² berechnen wollen,
dass das auch mit n½ plus zwei Multiplikationen und n Additionen
möglich ist.
Bei diesem Satz wird halt ausgeklammert, dass wir in dem
Preconditioning -Step vorher diese Alphas berechnen müssen.
Das heißt also allgemein, das Horner-Schema gilt nach wie vor.
In dem Satz wird halt ausgeklammert, dass wir den Aufwand, den wir für
das Preconditioning betreiben müssen.
Allein diese Stellen hier zu berechnen, das ist schon relativ
aufwendig.
Das heißt, wenn wir das komplette Verfahren, wenn wir so ein Polynom
nur einmal auswerten würden, dann wäre der Aufwand wesentlich höher.
Weil um diese Stellen zu bestimmen, da brauchen wir dann auf jeden
Fall mehr als n½ Multiplikationen.
Das heißt, wir werden wieder schlechter als das Horner-Schema.
Und das Ganze motiviert dann noch ein Verfahren, das wir uns auch
gleich noch anschauen werden.
Und zwar kann auch ein Polynom-Enden-Gerades an den Enden
-Einheitswurzeln auswerten.
Und das Ganze, also ein allgemeines Polynom,
dessen Koeffizienten nur einmal ausgewertet werden, das Ganze geht in
der Laufzeit-Endlog an.
Aber das ist schon ein kleiner Vorgriff.
Okay.
Wir können uns ja noch überlegen, wenn wir die Polynom-Auswertung
parallelisieren wollen, welche Möglichkeiten haben wir denn da?
Also das Horner-Schema ist zwar optimal, wenn ich nur einen Prozessor
habe, aber das Problem ist, dass es inherentsequenziell ist.
Das heißt, um das nächste Ergebnis berechnen zu können, muss ich auf
jeden Fall das vorherige Ergebnis bereits zur Verfügung haben.
Also ich kann nicht irgendwelche Multiplikationen oder Additionen
vorgreifen.
Das heißt, wenn ich mehrere Prozessoren zur Verfügung habe, habe ich
keinen Zeitgewinn, wenn ich nur einen Polynom auswerten möchte.
Stattdessen kann ich allerdings auch hier einen Dividend-Conquer
-Ansatz verfolgen.
Ich kann ja zum Beispiel, wenn ich ein Polynom-Enden-Gerades habe,
kann ich das ja beispielsweise halbieren.
Das heißt, dann habe ich hier einmal ein Polynom vom n-Halben-Gerades.
Das sind im Endeffekt die Rodenpotenzen, also von n bis n-Halbe.
Da klammere ich x-n-Halbe aus, dann habe ich ein Polynom von n-Halben
-Gerades.
Und in dem Polynom q, das ist auch von grad-n-Halbe, fasse ich die
kleineren Potenzen zusammen.
Wenn ich das Ganze jetzt parallel auswerte, also wenn ich mehrere
Prozessoren zur Verfügung habe, dann kann ich ja diese beiden Polynome
parallel ausrechnen.
Die muss ich nicht nacheinander ausrechnen, sondern parallel.
Daraus ergibt sich dann folgende Rekurrenzgleichung.
Also der Aufwand, um ein Polynom des Gerades n zu lösen, ist dann
einmal der Aufwand, um ein Polynom von halben Grad zu lösen, plus 2.
Also das ist der Aufwand, der dadurch entsteht, durch diese
Multiplikation und die Addition.
Also nochmal 2 arithmetische Operationen.
Wenn ich diesen Ausdruck sequentiell, also mit nur einem Prozessor
ausrechnen würde, dann müsste hier noch eine 2 stehen.
Das eigentlich bedeutet, dass ich 2 Teilprobleme löse, der Größe n
-Halb wäre.
Aber dadurch, dass ich das Ganze parallel ausführe, kann ich diesen
Aufwand im Endeffekt als gleichzeitig verbuchen und dadurch entsteht
kein zusätzlicher Laufzeitverlust.
Okay.
Das heißt, wir haben uns die Polynomauswertung angeschaut.
Und dadurch kommen wir jetzt noch zum letzten Thema des Kapitels, und
zwar die schnelle Fourier-Transformation.
Die kann man auch zur Polynomauswertung verwenden.
Wir motivieren das Ganze aber aus anderer Perspektive.
Also was passiert jetzt, wenn wir 2 Polynome miteinander
multiplizieren wollen?
Das heißt, wir haben einmal ein Polynom px und einmal ein Polynom q.
Das Produkt dieser beiden Polynome, also ist da ein Polynom, wenn die
beide vom Grad n sind, ist das Produktpolynom natürlich vom Grad 2n.
Und wenn ich das Ganze naiv auswerte, benötige ich n
Quadratoperationen.
Ich kenne die Koeffizienten von dem ersten Polynom, ich kenne die
Koeffizienten vom zweiten Polynom.
Wenn ich jetzt den entsprechenden Koeffizienten an der Stelle k vom
Produktpolynom bestimmen möchte, muss ich im Endeffekt alle die
Koeffizienten, das Produkt aller Koeffizienten bilden, die zusammen
gerade die Potenz dieses Koeffizienten ergeben.
Und die muss ich noch alle miteinander auch multiplizieren.
Also wenn ich zwei Polynome achten Grades hätten, dann müsste ich zum
Beispiel a0 mal b8 nehmen.
Und ich müsste multiplizieren, dann müsste ich dazu noch addieren a1
mal b7 und so weiter.
Das heißt, wenn ich das naiv ausführe, muss ich im Endeffekt jeden
Koeffizienten a mit jedem Koeffizienten b mindestens einmal
multiplizieren.
Auch die entsprechend zusammenfügen, das ist insgesamt quadratischer
Aufwand.
Alternativ kann ich das Problem allerdings auch lösen.
Also ich multipliziere nicht die Koeffizienten direkt miteinander,
sondern ich führe eine Umformung durch.
Ich kann ja Polynome nicht nur durch Koeffizienten darstellen, sondern
auch durch Werte.
Wenn ich ein Polynom endengrades habe, kann ich das mit n plus 1
stellen, wenn ich das ausgewertet habe, exakt darstellen.
Ich weiß nicht, vielleicht erinnere ich mich noch an Aufgaben aus der
Oberstufe oder so, da hat man irgendwie drei Punkte gegeben und soll
dann daraus eine Parabel berechnen.
Anhand, wenn man diese drei Punkte kennt, kann man die Parabel exakt
bestellen.
Und wie gesagt, diese Wertedarstellung, die ist eindeutig
identifiziert für ein Polynom.
Das heißt, anstatt hier den Weg direkt zu gehen, die einzelnen
Koeffizienten miteinander zu multiplizieren, was einen quadratischen
Aufwand hat, kann ich zuerst die Polynome an zwei n verschiedenen
Stellen auswerten, also jeweils p und q.
Darauf komme ich dann auf die Wertedarstellung.
In Wertedarstellung lassen sich zwei Polynome sehr einfach miteinander
multiplizieren.
Da muss ich einfach entsprechend nur die Werte an der entsprechenden
Stelle miteinander multiplizieren.
Das heißt, um herauszufinden, welchen Wert r an der Stelle 0 hat, muss
ich einfach p an der Stelle x0 mal u an der Stelle x0 berechnen.
Das ist ganz simpel.
Die Wertedarstellung von r kann ich auch wieder rücktransformieren
durch ein Verfahren und erhalte dann schließlich das Polynom in den
Koeffizienten Darstellung.
Jetzt ist es so, also diese Multiplikation der einzelnen
Koeffizienten, das sind zwei n plus 1 Multiplikationen, wenn ich hier
alle Stellen auswerte.
Und diese Schritte, wo 1, also diese Auswertung, die ist ja
normalerweise, wenn ich irgendwelche beliebigen Werte verwende, wir
haben ja gelernt durch das Horner Schema, der Aufwand, der ist linear,
aber ich habe zwei n arithmetische Operationen.
Stattdessen kann ich hierfür auch die schnelle Fourier-Transformation
verwenden, um das Ganze zu beschleunigen.
Das heißt, anstatt hier den, ja, das Problem wäre nämlich, wenn ich
das Horner Schema anwende, dann hätte ich zwar einen Aufwand, einen
linearen Aufwand, um eine einzelne Auswertung durchzuführen, aber da
ich ja zwei n Werte brauche, um diese Produktpolynomen korrekt
darstellen zu können, hätte ich im Endeffekt durch das Horner Schema
auch einen quadratischen Aufwand.
Und stattdessen, dadurch, dass wir hier ja ein oder zwei Polynome
mehrmals auswerten, also die Koeffizienten bleiben gleich, aber die
Stellen ändern sich, können wir ja auch so ein Preconditioning
verwenden.
Und da gibt es halt dieses ganz spezielle Verfahren, wenn man das mit
der schnellen Fourier-Transformation macht, kann man diese
Auswertungen, also diese zwei n Werte, kann man in n log n berechnen.
Bevor wir uns damit beschäftigen, wie die schnelle Fourier
-Transformation funktioniert, schauen wir uns erstmal die diskrete
Fourier -Transformation an.
Ich weiß nicht, ob das mittlerweile noch in Mathe behandelt wird.
Wird es noch in Mathe 3 gemacht?
Schnelle Fourier-Transformation?
Ganz am Schluss.
Ja, das heißt, das Thema ist eher so ein bisschen neuer für euch, ja.
Also es ist auch relativ komplex und schwierig.
Allerdings, ja, wir stellen es hier ein bisschen verkürzter, weil
wichtig ist eigentlich nicht mehr unbedingt, wie dieses Verfahren
jetzt wirklich funktioniert, sondern eher der Informatikansatz, der
dahinter steckt.
Okay, das heißt, die diskrete Fourier-Transformation.
Die Frage ist natürlich, wenn man eine Wertedarstellung des Polynoms
wählt, wie man das sinnvollerweise machen kann.
Ich kann mir jetzt willkürlich irgendwelche Werte rauspicken, dann
habe ich allerdings einen relativ hohen Berechnungsaufwand.
Stattdessen kann ich das auch an den Endeneinheitswurzeln berechnen,
ja, also mit Hilfe von komplexen Zahlen.
Weil die, wenn ich das Ganze mit Endeneinheitswurzeln berechne, habe
ich den Vorteil, dass ich schon auf Zwischenergebnisse zurückgreifen
kann, wenn ich dieses Polynom dann an den verschiedenen Stellen
ausrechne.
Wie genau das funktioniert, dazu komme ich gleich.
Aber zuerst müssen wir uns ein paar Definitionen anschauen.
Und zwar, was ist denn eigentlich eine Endeneinheitswurzel überhaupt?
Also jede Nullstelle eines Polynoms, also im Endeffekt diese gleiche
Null, löst x hoch n minus 1, also x hoch n minus 1 gleich 0.
Für den Körper der komplexen Zahlen, also c steht für die komplexen
Zahlen.
Das ist eine Endeneinheitswurzel.
Das heißt, wenn ich irgendeine Endeneinheitswurzel hier einsetze für
x, dann kommt da der Wert gleich 0 raus.
Dann gibt es nochmal eine spezielle Definition, und zwar eine
Endeneinheitswurzel, die heißt primitiv, wenn gilt, wenn diese
Endeneinheitswurzel potenziert wird mit einer natürlichen Zahl j.
Das heißt, wenn diese Berechnung ungleich 1 ist.
Das heißt, für alle Zahlen, die kleiner als n minus 1 sind, die von 1
bis n minus 1 gehen, wenn ich damit diese Endeneinheitswurzel
potenziere, kommt nicht 1 raus.
Dann heißt die Einheitswurzel primitiv.
Okay, dann an der Stelle noch ein kleines Lemma.
Und zwar, wenn Omega eine primitive Endeneinheitswurzel ist, dann ist
diese Menge, also alle, das heißt alle, wenn ich diese
Endeneinheitswurzel hoch i nehme, also i steht hier nicht für das
komplexwertige i, sondern für ein Index, also wenn ich die
Endeneinheitswurzel hoch in eine natürliche Zahl nehme, zwischen 1 und
n, erhalte ich die Menge, also das beschreibt die Menge aller
Einheitswurzeln.
Das heißt,
jeder, das bedeutet im Endeffekt nur, also wenn ich die Omega hoch i
nehme, berechne, und das hier oben einsetze, dann kommt da 1 raus.
Diese Definition versteht man vielleicht ein bisschen besser, wenn man
sich nochmal diesen Beweis anschaut.
Das heißt, ich habe hier eine Endeneinheitswurzel, also die primitive
Endeneinheitswurzel Omega, ich potenziere die mit i,
dann, ja, um zu zeigen, dass es eine Endeneinheitswurzel ist, also um
zu zeigen, dass es diesen Ausdruck hier löst, potenziere ich sie
nochmal mit n, und das ist ja nichts anderes, also hier
Potenzrechengesetze, ich nehme Omega hoch i, dann potenziere ich es
nochmal mit n, unter Potenzrechengesetze kann ich ja beide Variablen
vertauschen, und dieser Ausdruck ist schließlich 1, also Omega hoch n,
das ist ja die Definition der Endeneinheitswurzel, und wenn ich 1 hoch
irgendeine beliebige natürliche Zahl nehme, dann kommt da schließlich
1 raus.
Um das Ganze nochmal ein bisschen anschaulicher zu erklären, dann sind
hier ein paar Beispiele für Einheitswurzeln.
Also die zweiten Einheitswurzeln, das sind im Endeffekt alle Zahlen,
die x²-1 gleich 0 lösen.
Ja, das ist einmal minus 1 und 1.
Minus 1 ist in dem Fall die primitive Endeneinheitswurzel, weil minus
1 hoch 1 ist ja 1, also ist es noch immer minus 1 und eben ungleich 1.
Dann die vierten Einheitswurzeln, die sehen folgendermaßen aus, da ist
i die primitive Einheitswurzel, und bei den achten Einheitswurzeln ist
es entsprechend die Wurzel von i.
Ja, wir haben nochmal hier die Definition der primitiven
Einheitswurzel ein bisschen zu verdeutlichen.
Also wenn ich i hoch 1 nehme, kommt immer noch i aus.
Wenn ich i² nehme, kommt minus 1 raus.
Wenn ich i hoch 3 berechne, kommt minus i raus.
Und i hoch 4 schließlich ist 1.
Ja, um nochmal die Definition zu verdeutlichen der primitiven
Endeneinheitswurzel, also nur i hoch 4 ist 1, wenn ich eine kleinere
Zahl als 4 nehme, kommt nicht 1 raus.
Allerdings ist es so, wenn ich quasi i hoch, also i, wenn ich i
potenziere mit irgendeiner natürlichen Zahl kleiner als 4, also 3, 2
oder 1, dann erhalte ich entsprechend hier diese Werte.
Und wenn ich allerdings die hier, also nochmal mit n potenziere, ja,
dann kommt er nur noch raus.
Deshalb sind das die Einheitswurzeln.
Also nochmal hier in Bezug auf dieses Lemma.
Okay, jetzt schauen wir uns noch ein paar Eigenschaften der
Einheitswurzeln an.
Wenn also Ω eine primitive Endeneinheitswurzel und zusätzlich n gerade
ist, dann gilt folgendes.
Also erstens gilt, wenn ich diese primitive Endeneinheitswurzel mit n
halber potenziere, kommt minus 1 raus.
Das kann man sich auch ganz simpel überlegen.
Wenn man diese Einheitswurzel hochnimmt, kommt 1 raus, die Wurzel
davon ist minus 1.
Des Weiteren gilt, also für alle i, also von 1 bis n halber, wenn ich
die Endeneinheitswurzel mit n halber plus i, also i ist ja auch wieder
ein Index, nicht die imaginäre Einheit i, dann erhalte ich folgenden
Ausdruck.
Ich meine, das ist ja ganz klar, weil n Ω hoch n halber ist ja
schließlich minus 1.
Das heißt, ich legiere im Endeffekt nur durch diese Berechnung diese
Einheitswurzel.
Abschließend habe ich hier oben ein Exponent bestellt.
Das heißt, eine weitere Eigenschaft der Endeneinheitswurzel ist noch,
wenn ich diese Endeneinheitswurzel quadriere, dann ist es eine
primitive n halber Einheitswurzel.
Das kann man sich auch ganz leicht vorstellen, und zwar wenn ich Ω²
mit n halber potenziere, dann kommt das schließlich auch wieder als
Ausdruck Ω hoch n raus und Ω hoch n ist 1.
Also diese Eigenschaft der Einheitswurzel ist dadurch wieder erfüllt.
Wenn ich jetzt dieses Polynom für alle Endeneinheitswurzeln berechnen
möchte, also ein Polynom n° hat natürlich n Einheitswurzeln, dann kann
ich das Ganze auch als Matrixvektormultiplikation schreiben.
Also man multipliziere hier die Zeile mit jeweils der Sparte.
Also das hier ist dann entsprechend die Endeneinheitswurzel hoch 0.
Das ist die Einheitswurzel hoch 1.
Das ist Ω².
Und das ist schließlich Ω von n minus 1.
Um das zu verdeutlichen.
Das heißt, in der ersten Zeile stehen die Potenzen für die Stützstelle
A0.
In der zweiten Stelle stehen die Potenzen für die Stützstelle A1.
Und hier in der dritten Zeile die Potenzen für die Stützstelle A2.
Das sieht man ja hier auch ganz einfach.
Wenn ich Ω, also die Endeneinheitswurzel hoch 0 nehme, für A0 kommt 1
raus.
Wenn ich die erste Einheitswurzel, also das entspricht ja dann
gewissermaßen der Multiplikation A1 mal x.
Wenn ich für x Ω, also die Endeneinheitswurzel reinsetze, kommt das
raus.
Hier würde entsprechend x² stehen.
So kann man sich das verdeutlichen.
Das ist im Endeffekt nur diese einzelnen Berechnungen dargestellt als
Vektormatrixmultiplikation.
Das ist einfach nur eine andere Darstellungsweise.
Und die Koeffizienten, die hier drin stehen, das sind entsprechend
die, wenn ich für die x-Werte in dem Polynom die Endeneinheitswurzel
einsetze und dann schon potenziere.
Okay, noch ganz wichtig an der Stelle.
Wir betrachten hier ein Polynom vom Grad n-1 und nicht mehr vom Grad
n.
Das hat einfach mit der Darstellung zu tun, weil ein Polynom vom Grad
n -1 hat insgesamt n Koeffizienten.
Für die schnelle Fourier-Transformation ist n bestenfalls eine
Zweierpotenz, damit die Rekursion am Ende schön aufgeht.
Okay, wenn ich das Ganze jetzt, also diese Auswertung hier, damit
erhalte ich die Wertedarstellung.
Ich kann aus der Wertedarstellung, also aus den Werten dieses
Ergebnisses Vektor y, daraus kann ich auch wieder die Koeffizienten
berechnen.
Das Ganze erfolgt, indem ich diesen Wertevektor mit der Inversen
dieser Fourier-Matrix multipliziere und gleichzeitig noch durch n
teile.
Also diese Matrix hier, diese Fourier-Matrix T, das ist mal so
zusammen, das ist die Fourier-Matrix F.
Das ist eine Vandermonde-Matrix und deshalb kann man die relativ
leicht invertieren und dadurch ergibt sich die Struktur hier.
Sie werden sich wundern, wie man von dieser Fourier-Matrix so einfach
auf diese Transformations-Matrix kommt.
Einfach daran, weil die einer bestimmten Struktur entspricht, also der
der Vandermonde-Matrix und die lässt sich relativ einfach invertieren.
Da gibt es vereinfachte Verfahren im Gegensatz dazu zur normalen
Matrix -Inversion.
Die Sache ist, wenn ich jetzt diskrete Fourier-Transformationen nach
diesem Schema ausführe, habe ich ja immer noch n² Operationen, weil im
Endeffekt berechne ich ja nur n Skalarprodukte.
Also die erste Zeile mit der ersten Spalte, erste Zeile mit der
zweiten Spalte etc.
Also um einen Eintrag dieses Wertevektors zu berechnen, benötige ich n
Operationen.
Wenn ich das Ganze n-mal mache, bin ich bei n².
Ja, ich sehe schon, wir sind schon am Ende der Zeit angekommen für
heute.
Dann machen wir nächste Woche genau an der Stelle weiter und da
erkläre ich dann, wie man aus der diskreten Fourier-Transformation die
schnelle Fourier-Transformation ableiten kann.