WEBVTT

00:00.000 --> 00:01.340
So, schönen guten Tag.

00:01.440 --> 00:04.860
Ich begrüße Sie zur Fortsetzung der Vorlesung Grundlagen...

00:04.860 --> 00:06.140
Nicht Grundlagen.

00:06.280 --> 00:06.680
Quatsch.

00:08.000 --> 00:09.020
Ist lange vorbei.

00:09.440 --> 00:10.360
Effiziente Algorithmen.

00:10.780 --> 00:11.460
Schönere Vorlesungen.

00:11.980 --> 00:12.740
Auch nicht schöner.

00:12.860 --> 00:13.240
Auch schön.

00:15.100 --> 00:16.660
Vorlesung Effiziente Algorithmen.

00:16.740 --> 00:20.740
Letztes Mal haben wir uns noch mit dem Rest der Berechnungsmodelle

00:20.740 --> 00:21.600
beschäftigt.

00:21.780 --> 00:23.180
Da waren vier mal längst vorbei.

00:23.740 --> 00:25.220
Turing meiste bei den ganzen Modellen.

00:25.960 --> 00:28.320
Gradlinige Programme, Entscheidungsbäume.

00:29.180 --> 00:30.560
Klassifikation von Algorithmen.

00:30.680 --> 00:31.940
Sequenzielle Algorithmen.

00:32.100 --> 00:33.380
Parallele Algorithmen.

00:34.020 --> 00:36.980
Wir hatten diese verschiedenen Berechnungsmodelle angeguckt.

00:37.180 --> 00:40.720
Mit den Shared Memory, Distributed Memory und so weiter.

00:40.980 --> 00:44.100
Wir haben uns angeschaut.

00:44.600 --> 00:49.420
Verbindungsstrukturen, die parallele Infrastrukturen kennzeichnen.

00:49.580 --> 00:51.540
Wir haben uns Hardware Algorithmen angeschaut.

00:53.500 --> 00:56.160
Die verschiedenen Dinge, die eine Rolle spielen.

00:56.500 --> 01:00.100
Wenn man eine Berechnungsstruktur in Hardware gießt.

01:00.200 --> 01:03.480
Dass dann die Leitungen und das Layout auch eine Rolle spielen.

01:04.060 --> 01:05.960
Wir haben den Ripple-Carry-Addierer angeschaut.

01:06.060 --> 01:07.460
Die Matrix-Multiplikation.

01:07.840 --> 01:10.200
Wir haben uns den Berechnungsaufwand genauer angeschaut.

01:10.340 --> 01:14.060
Insbesondere Zeitgewinn, Effizienz bei parallelen Algorithmen.

01:14.240 --> 01:15.340
Nochmal genauer betrachtet.

01:16.280 --> 01:18.940
Und ich habe Ihnen dann etwas erzählt.

01:19.080 --> 01:20.480
Kurz zu verteilten Algorithmen.

01:20.480 --> 01:22.900
Das war alles im Kapitel Berechnungsmodelle.

01:23.460 --> 01:26.160
Und dann kamen wir zum Kapitel Algebraische Probleme.

01:26.940 --> 01:30.060
Ich habe Ihnen da etwas erzählt.

01:31.760 --> 01:34.260
Zunächst mal zu Matrix-Multiplikation.

01:34.680 --> 01:36.100
Was wir eigentlich schon kennen.

01:36.220 --> 01:38.740
Wir haben uns die Darstellung von Matrizen angeguckt.

01:38.880 --> 01:40.420
Als zweidimensionales Feld.

01:40.780 --> 01:44.660
Oder als eindimensionales Feld.

01:44.720 --> 01:46.600
Wir haben uns den Aufwand angeschaut.

01:46.600 --> 01:48.320
Für den Zugriff.

01:48.500 --> 01:50.700
Beim zweidimensionalen Feld eine Multiplikation.

01:50.840 --> 01:51.900
Zwei Additionen.

01:52.100 --> 01:54.320
Beim eindimensionalen Feld weniger.

01:54.680 --> 01:58.200
Insbesondere kann man innerhalb eines Programms den Aufwand deutlich

01:58.200 --> 01:58.760
verringern.

02:00.280 --> 02:04.300
Weil man da eine Index-Operation explizit macht.

02:04.760 --> 02:06.830
Aber es ist ein nicht so elegantes Programmieren.

02:07.220 --> 02:09.880
Weil man nicht intuitiv nur von der Mathematik spricht.

02:10.160 --> 02:12.300
Sondern die Abbildung noch im Kopf haben muss.

02:12.360 --> 02:14.720
Kann aber effizientere Programme bewirken.

02:14.720 --> 02:17.580
Und mit den dünn besetzten Matrizen dürfen Sie sich jetzt in den

02:17.580 --> 02:18.820
Übungen ein bisschen beschäftigen.

02:20.320 --> 02:23.520
Dann haben wir das Matrix-Produkt nochmal genauer angeschaut.

02:24.600 --> 02:25.560
Wie man das machen kann.

02:26.120 --> 02:27.560
Standardansatz mit Endhof 3.

02:27.860 --> 02:32.750
Und dann waren nochmal die Kosten der Zugriffe bei dem Standardansatz.

02:33.520 --> 02:35.700
Wir hatten gesehen, dass der ziemlich hoch sein kann.

02:36.380 --> 02:38.400
Haben das dann aber eigentlich ab Akta gelegt.

02:38.480 --> 02:41.780
Und gesagt, jetzt gucken wir uns die Matrix-Modifikation genauer an.

02:41.860 --> 02:44.200
Ich habe Ihnen dieses Verfahren von Winograd vorgestellt.

02:44.200 --> 02:47.760
Wo man auf einmal die Anzahl der Modifikationen halbieren kann.

02:48.620 --> 02:50.230
Auf Kosten von zusätzlichen Additionen.

02:51.280 --> 02:54.360
Aber das interessante war eben, dass man hier sieht, wie man einfach

02:54.360 --> 02:56.660
so mit solchen Ausdrücken herumspielen kann.

02:56.800 --> 02:58.920
Und auf einmal Berechnungsmöglichkeiten sieht.

02:59.060 --> 03:00.660
Durch eine geschickte Realisierung.

03:00.760 --> 03:02.200
Das war diese geschickte Realisierung.

03:02.360 --> 03:06.980
Dass ich hier also die Abhängigkeiten von zwei Indizes ausgezogen

03:06.980 --> 03:07.360
habe.

03:07.480 --> 03:08.540
Beim Teil der Berechnung.

03:08.660 --> 03:12.680
Und dann nur auf ein Index mich konzentrieren musste.

03:12.680 --> 03:17.980
Also die Elemente von A und die Elemente von Matrix B.

03:18.700 --> 03:20.420
Und dadurch konnte man einiges verbessern.

03:21.000 --> 03:23.740
Konnte eben dann diese Anzahl der Modifikationen reduzieren.

03:24.200 --> 03:26.720
Und das ist eben einfach, um zu zeigen, dass man wirklich manchmal

03:26.720 --> 03:27.900
sehr rumspielen muss.

03:28.020 --> 03:29.960
Mit den Arten, wie man etwas berechnet.

03:30.680 --> 03:32.640
Und die Gesetze der Arithmetik ausnutzen muss.

03:32.740 --> 03:35.780
Um tatsächlich dann höhere Effizienz zu erreichen.

03:36.360 --> 03:38.720
Und dann kam der divide-and-conquer-Ansatz von Strassen.

03:38.720 --> 03:42.440
Wo wir eben sagen, wir haben ein Verfahren, mit dem wir Matrizen

03:42.440 --> 03:42.720
modifizieren.

03:44.660 --> 03:45.740
K -Kreuz-K-Matrizen.

03:45.860 --> 03:49.360
Und setzen das jetzt ein für eine beliebige Matrix-Modifikation von N

03:49.360 --> 03:50.180
-Kreuz -N-Matrizen.

03:50.600 --> 03:54.720
Müssen die dadurch auffassen als K-Kreuz-K-Matrix von Matrizen.

03:55.740 --> 04:00.220
Deswegen darf dieses Verfahren für die Kommunikation nicht ausnutzen.

04:00.920 --> 04:03.700
Und weil das eben Teilmatrizen sind, die modifiziert werden.

04:03.700 --> 04:07.100
Wir hatten gesehen, da muss natürlich rekursiv, wann immer wir eine

04:07.100 --> 04:10.160
Modifikation ausführen, wieder rekursiv das gleiche Verfahren

04:10.160 --> 04:11.520
eingesetzt werden.

04:12.080 --> 04:16.600
Und wir waren jetzt gerade dabei zu analysieren, wie viel Aufwand das

04:16.600 --> 04:17.380
eigentlich macht.

04:17.800 --> 04:21.820
Und das war hier unsere letzte Folie.

04:22.000 --> 04:23.600
Da will ich dann wieder einsteigen.

04:24.640 --> 04:26.920
Das war also hier unsere Analyse.

04:26.920 --> 04:33.920
Wir haben uns zunächst mal überlegt, das ist also eine naheliegende,

04:34.320 --> 04:38.940
einfache Überlegung, wie die Anzahl der Multiplikationen ist für

04:38.940 --> 04:43.400
Matrizen, deren Dimension eine Zweierpotenz ist.

04:43.620 --> 04:48.680
Also K hoch N gleich K hoch R.

04:50.020 --> 04:56.220
Und dann kann ich mir halt hier den Weide-Konker-Ansatz besonders gut

04:56.220 --> 04:56.900
einsetzen.

04:57.120 --> 05:00.200
Ich habe also dann bei den Modifikationen zu betrachten, die

05:00.200 --> 05:04.500
Modifikation, die ich brauche, innerhalb des Verfahrens, dieses K

05:04.500 --> 05:09.660
-Kreuz -K-Verfahren, also bei dieser Modifikation, die hier blau noch

05:09.660 --> 05:13.780
angegeben ist, das ist die Modifikation von K-Kreuz-K-Matrizen, deren

05:13.780 --> 05:17.740
Elemente N durch K-Kreuz, N durch K-Matrizen sind.

05:18.440 --> 05:22.400
Beziehungsweise K hoch R-1-Kreuz-K-R-1-Matrizen.

05:23.120 --> 05:27.000
Und ich habe also klein m von K viele Modifikationen solcher Matrizen

05:27.000 --> 05:27.460
zu machen.

05:27.900 --> 05:32.820
Jedes Mal habe ich also dann mein Rekursiv, das gleiche Verfahren

05:32.820 --> 05:33.420
einzusetzen.

05:33.580 --> 05:37.920
Deswegen Anzahl der Modifikationen bei der Modifikation von K hoch R-1

05:37.920 --> 05:39.420
-Kreuz -K-R-1-Matrizen.

05:40.180 --> 05:42.940
Und bei den Additionen ist es eben so, dass ich dann auch anschauen

05:42.940 --> 05:48.420
muss, die Additionen für N-Kreuz-N-Matrizen sind dann halt diese A-von

05:48.420 --> 05:52.660
-K -Additionen von N durch K-Kreuz-N-K-Matrizen.

05:52.960 --> 05:56.400
In diesen Matrizen habe ich das Relage drin, das sind genau dann N

05:56.400 --> 06:00.280
durch K zum Quadrat, beziehungsweise K hoch R-1 zum Quadrat, viele

06:00.280 --> 06:02.880
Elemente, so viele explizite Additionen.

06:03.420 --> 06:09.080
Und dann kommen natürlich hier bei der Multiplikation der N durch K

06:09.080 --> 06:12.920
-Kreuz -N-K-Matrizen, also bei diesem rekursiven Aufruf des

06:12.920 --> 06:19.400
Verfahrens, dann natürlich für jeden solche rekursiven Aufruf noch

06:19.400 --> 06:23.880
wieder die Additionen dazu, die ich für diese Multiplikation jeweils

06:23.880 --> 06:24.700
ansetzen muss.

06:25.300 --> 06:27.020
Deswegen also diese beiden Formeln.

06:27.620 --> 06:29.220
Und nun muss man sich anschauen, wie kann ich die ein bisschen

06:29.220 --> 06:29.560
vereinfachen.

06:29.560 --> 06:36.340
Man sieht sehr schnell, das ist also wirklich trivial, dass hier die

06:36.340 --> 06:41.100
Anzahl der Multiplikationen, weil das eben diese einfache Formel ist,

06:41.520 --> 06:49.400
für K hoch R-plus-1-Matrizen, gerade M-von-K mal der Aufwand für K

06:49.400 --> 06:51.980
-hoch -R-Matrizen ist, also M-von-K-hoch-R-plus-1.

06:52.080 --> 06:53.440
Das ist wirklich sehr einfach.

06:54.200 --> 06:58.080
Natürlich ist es so, dass für R-gleich-1, also wenn ich hier nur K

06:58.080 --> 07:01.040
-Kreuz -K-Matrizen habe, dann ist es genau dieses M-von-K,

07:01.220 --> 07:02.920
beziehungsweise genau dieses A-von-K.

07:03.380 --> 07:08.320
Nun muss ich mir anschauen, wie komme ich zu der Formel für die Anzahl

07:08.320 --> 07:09.180
der Additionen.

07:09.480 --> 07:10.780
Ein bisschen kompliziertere Formel.

07:11.660 --> 07:15.580
Und was ich hier sofort aufschreiben kann, ist eben entsprechend

07:15.580 --> 07:21.320
dieses Ausdrucks hier oben, ist das A-von-K-hoch-R-plus-1, halt gerade

07:21.320 --> 07:30.340
die Additionen für diese K-hoch-R-plus-1-minus-1, also K-hoch-R

07:30.340 --> 07:35.740
-Matrizen zum Quadrat, also A-von-K-mal-K-hoch-2-R, plus dieses M-von

07:35.740 --> 07:40.340
-K mal, weil ich hier von R-plus-1 ausgehe, A-von-K-hoch-R.

07:40.720 --> 07:43.600
Das A-von-K-hoch-R kann ich durch Induktion einsetzen.

07:43.600 --> 07:47.140
Dann ist das gerade dieser Ausdruck hier oben, den kann ich einsetzen

07:47.140 --> 07:51.600
an der Stelle, als Induktionsannahme, wegen der Induktionsannahme.

07:52.620 --> 07:55.040
Und dann habe ich also hier diesen Ausdruck.

07:55.120 --> 07:57.880
Und wenn ich mir den genauer anschaue, dann kann ich diesen vorderen

07:57.880 --> 08:01.340
Term auch damit reinziehen, muss den Index nur um 1 erhöhen.

08:02.260 --> 08:05.500
Das sieht man hier unten, also zwei Schritte.

08:05.760 --> 08:10.060
Und dann sieht man, dass ich hier einfach nur A-von-K rausziehen kann.

08:10.060 --> 08:16.500
Und in der Summe jetzt gehe ich bis R-plus-1 und dieses M-von-K-hoch-R

08:16.500 --> 08:21.940
-plus -1 minus R-plus-1, das ist ja gerade M-von-K-hoch-0, also dann

08:21.940 --> 08:23.060
1.

08:23.260 --> 08:28.920
Und dann bleibt für das R-plus-1 hier gerade K-hoch-2-R übrig.

08:29.080 --> 08:30.100
Genau das, was hier vorne stand.

08:30.200 --> 08:31.060
Also das ist ganz einfach.

08:31.260 --> 08:33.740
Einfaches Einsetzen sieht schlimmer aus, als es ist.

08:34.160 --> 08:35.520
Das ist ein ganz einfacher Beweis.

08:35.520 --> 08:39.520
Und jetzt kommt das Nächste, dass wir diesen Ausdruck, der nicht so

08:39.520 --> 08:43.640
schön offensichtlich ist, welche Größenordnung das eigentlich ist,

08:43.740 --> 08:46.020
dass man den sich ein bisschen genauer anguckt.

08:46.800 --> 08:53.340
Und wir stellen fest, dieses M-von-K-hoch-R-minus-I, Summe M-von-K

08:53.340 --> 09:01.380
-hoch -R-minus-I mal K-hoch-2 mal I-minus-1, das ist angeblich eine

09:01.380 --> 09:07.420
Funktion, die nicht stärker wächst als M-von-K-hoch-R, asymptotisch.

09:08.880 --> 09:11.760
Und das M-von-K war die Anzahl der Multiplikationen in dem K-kreuz-K

09:11.760 --> 09:12.240
-Verfahren.

09:12.900 --> 09:14.600
Das schauen wir uns jetzt genauer an.

09:15.940 --> 09:20.340
Also, das nehmen wir an, zunächst mal aus technischen Gründen, dass

09:20.340 --> 09:27.360
das M-von-K mindestens K-quadrat plus eine Operation braucht.

09:28.620 --> 09:31.520
Also, es braucht mindestens, also Multiplikationen.

09:31.580 --> 09:37.620
Für N-kreuz-N-Matrizen, für 4-kreuz-4-Matrizen, brauche ich mindestens

09:37.620 --> 09:39.800
17 Multiplikationen.

09:39.940 --> 09:42.360
16 plus irgendetwas, plus C.

09:43.540 --> 09:46.820
Man kann sich auch den Fall angucken, dass das M-von-K genau gleich K

09:46.820 --> 09:47.580
-quadrat ist.

09:47.580 --> 09:50.180
Können Sie sich gerne ausrechnen, was dann rauskommt.

09:50.500 --> 09:51.300
Das ist auch interessant.

09:52.680 --> 09:53.720
Betrachte ich hier aber nicht.

09:54.420 --> 09:56.000
Das ist eine einfache Überlegung.

09:57.920 --> 10:01.220
Und dann sieht man da auch ein interessantes Ergebnis.

10:04.700 --> 10:09.940
Für den Fall, dass also mindestens diese K-quadrat plus C-Operationen

10:09.940 --> 10:11.900
sind, rechne ich jetzt weiter.

10:13.120 --> 10:15.080
Und was kann ich jetzt hier hinschreiben?

10:15.080 --> 10:19.220
Also, diese Summe M-von-K, diese Summe, die wir hier darstellen

10:19.220 --> 10:22.240
wollen, die kann ich jetzt etwas anders darstellen.

10:22.360 --> 10:25.820
Aufgrund dieser Darstellung schreibe ich jetzt hier hin, M-von-K-auf-R

10:25.820 --> 10:29.420
-minus -I mal M-von-K-minus-C-auf-I-minus-1.

10:30.580 --> 10:33.240
Das K-quadrat ist ja gerade dieses M-von-K-minus-C.

10:34.280 --> 10:38.340
Und wenn ich mir das genauer anschaue, dann ist das folgendes.

10:38.380 --> 10:42.240
Ich kann das M-von-K-auf-R einfach rausziehen.

10:43.420 --> 10:48.920
Und dann bleibt hier übrig M-von-K-auf-R-minus-I mal M-von-K-minus-C

10:48.920 --> 10:49.940
-auf -I-minus-1.

10:53.120 --> 10:57.100
Jetzt erweitere ich einfach um M-von-K-minus-C, kommt also einmal in

10:57.100 --> 10:59.840
den Nenner, einmal in den Zähler rein.

11:00.380 --> 11:06.240
Dann habe ich hier eine Summe, wo ich M-von-K-minus-C durch M-von-K,

11:06.240 --> 11:11.440
also einen Bruch habe, der kleiner als 1 ist, hoch I, also eine

11:11.440 --> 11:12.340
geometrische Reihe.

11:13.340 --> 11:16.420
Und hier vorne steht als Faktor noch davor dieses M-von-K-auf-R durch

11:16.420 --> 11:17.480
M -von-K-minus-C.

11:19.220 --> 11:26.480
Und der Wert einer geometrischen Reihe ist ja ganz einfach, da haben

11:26.480 --> 11:27.920
wir die einfachen Formeln für.

11:27.920 --> 11:30.320
Das ist dann genau das Ergebnis.

11:30.900 --> 11:39.680
1-M-von-K, also dieser Term, der da immer hochiteriert wird, durch 1

11:39.680 --> 11:40.280
-...

11:40.280 --> 11:43.660
also das Ding hoch R-plus-1, das Ding hier, hier bis R, das ist genau

11:43.660 --> 11:47.020
der Term für den Grenzwert einer solchen Reihe.

11:47.060 --> 11:50.440
Oder für den Wert einer solchen Reihe, gleich 1 bis R, das Ganze minus

11:50.440 --> 11:50.860
1.

11:50.860 --> 11:55.060
Und wenn ich das jetzt, diesen Ausdruck hier ausrechne, kann ich

11:55.060 --> 11:56.180
umformen.

11:56.260 --> 12:00.800
Dann komme ich hier sukzessive, das sind einfache Umrechnungen, können

12:00.800 --> 12:03.560
Sie einfach nachvollziehen, wie ich hier gerechnet habe.

12:03.660 --> 12:06.060
Ich habe einfach das hier entsprechend erweitert, diesen Bruch, den

12:06.060 --> 12:10.120
auch erweitert, also das hier als einen Bruch jeweils hingeschrieben

12:10.120 --> 12:13.740
und komme dann auf die entsprechenden Ausdrücke.

12:15.020 --> 12:18.780
Also Bruch durch Bruch, also multiplicative Umkehrwerte des Bruchs.

12:19.240 --> 12:23.180
So kommen dann diese Ausdrücke hier drin zustande.

12:25.160 --> 12:29.240
Und da habe ich wieder das M-von-K-minus-C-durch-K-quadrat ersetzt,

12:29.580 --> 12:30.580
kürzere Schreibweise.

12:31.300 --> 12:37.660
Und ich komme dann auf diesen Term hier unten, M-von-K-auf-R-durch-K

12:37.660 --> 12:39.340
-quadrat, mal diesem Ausdruck.

12:39.340 --> 12:42.960
Und wenn ich mir das genauer angucke, dann habe ich hier einen Wert,

12:43.220 --> 12:50.260
das ist 1-durch-M-von-K-minus-K-quadrat, minus, das kommt hier raus,

12:51.360 --> 12:57.640
minus dieses K-auf-2-R und dieser Term da unten.

12:57.800 --> 13:00.800
Und wenn ich mir das genauer angucke, dann ist das hier folgender

13:00.800 --> 13:01.500
Ausdruck.

13:01.500 --> 13:10.880
Das ist gerade M-von-K-auf-R, mal 1-K-quadrat-durch-M-von-K-auf-R.

13:11.080 --> 13:17.780
Diese K-quadrat-durch-M-von-K ist etwas, das ist kleiner als 1.

13:17.960 --> 13:21.060
Also ist das, wenn ich das hoch-R nehme, das geht gegen 0.

13:21.500 --> 13:23.080
Das heißt, das ist ein kleiner Wert.

13:24.140 --> 13:28.380
Dieses hier, 1-durch-M-von-K-minus-K-quadrat, 1-durch-M-von-K-minus-K

13:28.380 --> 13:30.160
-quadrat ist gerade das C.

13:30.160 --> 13:36.600
Das heißt, das hier insgesamt, was hier steht, ist kleiner gleich

13:36.600 --> 13:42.780
irgendeine Konstante mal M-von-K-auf-R für genügend große Werte.

13:42.940 --> 13:46.480
Das heißt, ich habe genau herausgefunden, dass das nicht stärker

13:46.480 --> 13:48.560
wächst als M-von-K-auf-R.

13:48.900 --> 13:54.280
Ab einer gewissen Größe, ab einem gewissen R kann ich das durch die

13:54.280 --> 13:59.060
Konstante abschätzen und dann bin ich schon fertig mit dieser Aussage.

13:59.060 --> 14:02.020
Das heißt, was wir jetzt herausgefunden haben mit diesen einfachen

14:02.020 --> 14:04.780
arithmetischen Umrechnungen, die ein bisschen kompliziert aussehen,

14:04.940 --> 14:09.660
aber das muss man sich einfach einmal klar machen, wie hier die Terme

14:09.660 --> 14:13.220
umgewandelt werden, einfache Bruchrechnung, komme ich also darauf,

14:13.380 --> 14:18.360
dass dieser Ausdruck, der hier ein bisschen kompliziert aussieht,

14:18.980 --> 14:23.920
abgeschätzt werden kann durch C-mal M-von-K-hoch-R, also irgendeine

14:23.920 --> 14:25.580
Konstante mal M-von-K-hoch-R.

14:26.700 --> 14:28.620
Und jetzt nutze ich das aus.

14:28.740 --> 14:34.980
Die Folgerung ist, dass die Summe, also die Anzahl aller

14:34.980 --> 14:41.140
arithmetischen Operationen, ist also M-von-K-hoch-R, das war die

14:41.140 --> 14:47.160
Anzahl der Modifikationen insgesamt, und dieses O-von-M-von-K-hoch-R

14:47.160 --> 14:49.480
war die Anzahl der Additionen in der Matrix-Modifikation.

14:50.700 --> 14:55.120
Also ist das insgesamt N-O-von-M-von-K-hoch-R.

14:56.220 --> 15:02.200
Und jetzt ist das R, ist ja gerade Logarithmus zur Basis, Sie erinnern

15:02.200 --> 15:05.240
sich, N ist gleich K-hoch-R.

15:06.360 --> 15:09.740
Das R ist ja gerade der Logarithmus zur Basis K-von-N.

15:10.440 --> 15:12.780
So, und jetzt können Sie das einfach umwandeln.

15:13.560 --> 15:19.360
Dann ist das Ganze, diese M-von-K-hoch-Logarithmus zur Basis K-von-N,

15:20.300 --> 15:25.980
ist das gleiche wie N-hoch-Logarithmus zur Basis K-von-M-von-K.

15:26.980 --> 15:38.810
Können Sie sich einfach überlegen, das heißt, wenn man sich das hier

15:38.810 --> 15:47.330
anguckt, dann steht hier A-hoch-Log zur Basis B-C.

15:47.330 --> 16:03.290
Und das andere ist C-hoch-Log zur Basis K-A.

16:05.790 --> 16:11.690
Und das steht hier, genau, das ist richtig.

16:13.870 --> 16:17.050
Und dass das hier gleich ist, können Sie sich leicht überlegen.

16:17.610 --> 16:21.450
Ja, Entschuldigung, B.

16:22.730 --> 16:24.350
Ja, danke, B.

16:24.730 --> 16:25.990
Also ich habe nur einfach C und A vertauscht.

16:26.190 --> 16:28.810
Also C-hoch-Log zur Basis B-A.

16:29.410 --> 16:32.110
Das ist mal kurz richtig gemacht.

16:32.350 --> 16:33.750
Also hier ein B, danke für den Hinweis.

16:35.510 --> 16:38.450
Und das können Sie sich leicht überlegen, dass diese Gleichheit gilt.

16:38.450 --> 16:44.470
Das ist auch einfach das hingeschrieben.

16:47.570 --> 16:54.190
Und die Konstante, die hier rauskommt, von N-hoch-Log zur Basis K-von

16:54.190 --> 16:57.050
-M -von-K, beziehungsweise hier von diesem M-von-K-hoch-R,

16:57.210 --> 17:00.490
beziehungsweise was hier rauskommt, die Konstante aufgrund der sehr

17:00.490 --> 17:05.570
groben Abschätzung, die wir gemacht haben, das ist diese Abschätzung,

17:05.670 --> 17:09.110
die hier steht, A-von-K, also Anzahl der Additionen in dem K-quads-K

17:09.110 --> 17:14.510
-Verfahren durch dieses M-von-K-minus-K-quadrat, plus 1.

17:15.550 --> 17:19.350
Das ist eine relativ große Zahl im Vergleich, wenn man sich das genau

17:19.350 --> 17:23.630
ausrechnet, für bestimmte Werte, aber es ist eine sehr grobe

17:23.630 --> 17:25.070
Abschätzung, man kann das noch verbessern.

17:25.690 --> 17:28.210
Das zeigt eben nur, wir können das abschätzen durch diesen Ausdruck.

17:28.210 --> 17:32.190
Nun sieht der immer noch sehr kompliziert aus, und jetzt ist das Ganze

17:32.190 --> 17:38.150
interessant, in dem Augenblick, wo Logarithmus zur Basis K-von-M-von-K

17:38.150 --> 17:39.690
kleiner als 3 ist.

17:41.830 --> 17:46.230
Jetzt schauen wir uns das mal an, für den Fall, dass wir es zu tun

17:46.230 --> 17:49.470
haben mit 2-kreuz-2-Matrizen.

17:52.580 --> 17:58.520
Da haben wir 8 Multiplikationen, die wir machen müssen, beim

17:58.520 --> 17:59.620
Standardverfahren.

18:01.840 --> 18:06.880
Also Logarithmus zur Basis 2 von 8 wäre 3, das würde uns nichts

18:06.880 --> 18:07.380
helfen.

18:09.300 --> 18:14.560
Also sobald wir weniger als 8 Multiplikationen bräuchten, für die

18:14.560 --> 18:18.320
Multiplikation von 2-kreuz-2-Matrizen, hätten wir einen Vorteil.

18:20.040 --> 18:23.880
Beziehungsweise allgemeiner, dass dieser Satz, wenn es also einen

18:23.880 --> 18:28.440
Algorithmus gibt, der ein Produkt von K-kreuz-K-Matrizen mit M-von-K

18:28.440 --> 18:33.000
-größer -K-quadrat-Multiplikationen berechnet, ohne die Kommutativität

18:33.000 --> 18:37.180
der Multiplikation auszunutzen, dann können N-kreuz-N-Matrizen mit O

18:37.180 --> 18:43.340
-von -N-hoch-Log-zu-Basis-K-von-M-von-K-arithmetischen-Operationen Das

18:43.340 --> 18:45.140
ist der Satz, den wir uns jetzt gerade überlegt haben.

18:45.400 --> 18:47.200
Da muss die Frage, was kann ich jetzt damit machen.

18:48.040 --> 18:51.160
Da schaut man sich das natürlich an, für die 2-kreuz-2-Matrizen.

18:51.680 --> 18:56.720
Der Strassen hat halt geschaut, wie kann man das hinkriegen, und er

18:56.720 --> 19:04.440
hat insbesondere ein Verfahren sich überlegt, wie man genau die Cij

19:04.440 --> 19:12.460
bei einer Multiplikation von 2-kreuz-2-Matrizen berechnen kann, nur

19:12.460 --> 19:15.320
mit 7 Multiplikationen.

19:15.420 --> 19:21.000
Die P steht hier für Produkt, also jeweils ein Produkt, und Sie sehen

19:21.000 --> 19:22.340
hier die verschiedenen Terme.

19:23.220 --> 19:28.640
7 Multiplikationen, hier stehen jeweils unterschiedliche Ausdrücke

19:28.640 --> 19:36.000
drin, und diese Produkte, die ausgerechnet werden, werden anschließend

19:36.000 --> 19:38.180
noch entsprechend kombiniert.

19:38.180 --> 19:40.660
Hier ist mir die Formatierung verrutscht, das sollte eigentlich in

19:40.660 --> 19:42.260
einer Spalte stehen.

19:43.100 --> 19:47.460
Und dann sehen Sie, dass wir jetzt hier nur noch Additionen drin haben

19:47.460 --> 19:48.380
und Subtraktionen.

19:48.760 --> 19:52.460
Wenn Sie das durchzählen, dann kommen Sie auf 7 Multiplikationen,

19:52.540 --> 19:55.900
hatte ich schon gesagt, und 18 Additionen.

19:56.760 --> 20:01.200
Das sind deutlich mehr Additionen als bei der Schulmethode.

20:06.300 --> 20:09.620
Aber asymptotisch, das haben wir gerade festgestellt, wird das Ganze

20:09.620 --> 20:13.300
dominiert durch die Anzahl der Multiplikationen.

20:13.820 --> 20:16.900
Das ist der wesentliche Parameter, und den haben wir um 1 reduziert

20:16.900 --> 20:19.560
gegenüber der klassischen Methode.

20:20.100 --> 20:21.300
Nicht 8, sondern 7.

20:22.080 --> 20:27.380
Und was heißt das für die asymptotische Abschätzung?

20:28.260 --> 20:33.540
n hoch log zur Basis 2 von 7 ist 2.81.

20:34.680 --> 20:40.280
Das heißt, wir haben auf einmal eine Verbesserung bekommen von 3 auf 2

20:40.280 --> 20:41.960
.81 im Exponenten.

20:42.620 --> 20:45.200
Das ist also deutlich besser als das, was wir mit dem Winograd

20:45.200 --> 20:46.140
-Verfahren erreicht hatten.

20:46.140 --> 20:48.180
Das war eine konstante Verbesserung bei der Anzahl der

20:48.180 --> 20:50.880
Multiplikationen, die auch nicht schlecht ist.

20:51.340 --> 20:54.900
Aber hier haben wir eine asymptotische Verbesserung, die, je größer

20:54.900 --> 20:57.500
die Matrizen werden, desto stärker eine Rolle spielt.

20:58.880 --> 21:01.180
Jetzt kann man natürlich sagen, ok, ich schau mal, ob ich vielleicht

21:01.180 --> 21:02.960
das mit 6 Multiplikationen hinkriegen kann.

21:03.460 --> 21:05.960
Da haben sich viele Leute Gedanken gemacht, wie man das machen kann.

21:06.400 --> 21:08.540
Hat der Schubler auch in letzter Zeit mal intensiv sich Sachen

21:08.540 --> 21:09.080
angeguckt.

21:11.720 --> 21:13.360
Aber da haben viele Leute geguckt.

21:13.360 --> 21:20.140
Und es ist so, man kann dann gucken, zunächst mal suche ich mir

21:20.140 --> 21:23.460
irgendein Schema, das mit 7 Multiplikationen auskommt.

21:23.760 --> 21:26.500
Dann versuche ich die Anzahl der Additionen zu drücken.

21:27.740 --> 21:29.240
Und ich weiß nicht, ob es auf dieser Folie ist.

21:30.680 --> 21:31.400
Ne, steht hier nicht.

21:32.080 --> 21:35.740
Man kann das drücken, kommt auf einer der nächsten Folien, von 18 auf

21:35.740 --> 21:36.280
15.

21:36.620 --> 21:38.320
Das hat Winograd ziemlich schnell festgestellt.

21:38.920 --> 21:39.880
Hier haben wir uns viel kooperiert.

21:41.020 --> 21:43.440
Besser als 15 hat man bisher nicht gefunden.

21:43.500 --> 21:45.760
Man kann sogar zeigen, dass es nicht besser geht als mit 15.

21:46.540 --> 21:47.960
Wenn man 7 Multiplikationen hat.

21:50.100 --> 21:50.900
Interessante Erkenntnis.

21:51.400 --> 21:54.220
Ok, der 2x2 ist abgegrast.

21:54.660 --> 21:55.800
Gehen wir auf 3x3.

21:57.420 --> 22:00.660
Bei 3x3-Matrizen könnte man ja versuchen, die Anzahl der

22:00.660 --> 22:06.480
Multiplikationen, im Endeffekt 3 Multiplikationen, also 27

22:06.480 --> 22:10.760
Multiplikationen, die um 1 oder 2 oder vielleicht 3, da ist ja viel

22:10.760 --> 22:12.100
mehr Möglichkeit, etwas zu tun.

22:13.340 --> 22:19.940
Es hat leider bisher niemand mit diesem Ansatz es geschafft, unter das

22:19.940 --> 22:21.400
Ergebnis von Strassen zu kommen.

22:21.660 --> 22:28.200
Also auch für größeres K, wenn K größer als 2 ist, ist man nicht mit

22:28.200 --> 22:31.160
diesem Ansatz auf ein besseres Verfahren gekommen.

22:32.180 --> 22:33.380
Also ganz interessant.

22:34.540 --> 22:38.260
Das Einfachste, 2x2-Matrizen, eine Multiplikation eingespart.

22:39.120 --> 22:40.700
Und ich habe diesen asymptotischen Gewinn.

22:41.800 --> 22:44.800
Wenn ich mir das genau, wenn ich das jetzt sehr gut implementiere,

22:46.280 --> 22:51.540
dann, oder ich, zunächst mal Standard-Einsatz.

22:51.920 --> 22:54.300
Da bin ich erst auf R gleich 10 besser als die Schulmethode.

22:54.400 --> 23:00.300
Das heißt aber, dass ich dann 2 hoch 10 mal 2 hoch 10-Matrizen

23:00.300 --> 23:01.020
multipliziere.

23:04.740 --> 23:10.140
Das sind 1024x1024-Matrizen.

23:10.360 --> 23:11.180
Ziemlich große Dinge.

23:12.280 --> 23:13.820
Man kann es noch verbessern.

23:14.220 --> 23:15.700
Aber dann muss man ein bisschen anders vorgehen.

23:16.800 --> 23:20.860
Also erst mal Vinograd hat auf 15 Additionen das reduziert.

23:21.940 --> 23:23.620
Und dann kann ich folgendes machen.

23:23.700 --> 23:29.260
Ich habe ja nicht immer unbedingt gerade 2 hoch R-Matrizen, 2er

23:29.260 --> 23:30.320
-Potenzen drin.

23:30.320 --> 23:34.220
Dann kann es sein, dass ich einfach irgendeinen P mal 2 hoch R kann

23:34.220 --> 23:34.740
ich nehmen.

23:35.500 --> 23:41.380
Und dann mache ich einfach bis zur Rekursionstiefe R das Verfahren von

23:41.380 --> 23:41.760
Straßen.

23:43.000 --> 23:47.580
Und dann multipliziere ich die dann noch übrigbleibenden P-Kreuz-P

23:47.580 --> 23:50.000
-Matrizen mit der Schulmethode.

23:50.940 --> 23:55.560
Dann ist die Frage, also die Schulmethode ist ja besser als Straßen

23:55.560 --> 23:56.860
für kleines n.

23:57.620 --> 24:05.100
Mache ich also das P gerade so, dass ich schneller bin für die

24:05.100 --> 24:06.040
kleineren Matrizen.

24:06.700 --> 24:10.520
Und das ausnutze, dass Straßen besser ist für die großen Matrizen.

24:12.060 --> 24:17.020
Und auf die Art und Weise, wenn man das also macht, wie es hier steht

24:17.020 --> 24:21.080
und auch noch effizient implementiert, also auf Zugriffe achtet und

24:21.080 --> 24:25.780
all sowas, möglichst eindimensionale Darstellung der Matrizen usw.

24:25.960 --> 24:26.280
usw.

24:27.100 --> 24:34.740
Dann kommt man schon ab n gleich 40 oder 41 zu besserem Zeitverhalten

24:34.740 --> 24:36.780
als die Schulmethode.

24:37.560 --> 24:42.260
40 kreuz 40 Matrizen sind durchaus etwas, was nicht mehr so groß ist.

24:42.260 --> 24:48.680
Also das Straßenverfahren ist relevant für praktischen Einsatz.

24:49.240 --> 24:53.800
Ist inzwischen Standardverfahren, was genau auf diese Art und Weise

24:53.800 --> 24:57.560
auch eingesetzt wird, dass man umschaltet an einer sinnvollen Stelle

24:57.560 --> 25:00.160
auf die Schulmethode.

25:02.700 --> 25:06.640
Und das Entwurfsprinzip ist klar, die beiden Konker kennen sie alle.

25:07.500 --> 25:13.020
Und das Interessante ist, wenn man schnelle Verfahren zur Modifikation

25:13.020 --> 25:17.360
von Matrizen hat, dann bekommt man auf einmal auch schnelle Verfahren

25:17.360 --> 25:19.600
für eine ganze Reihe von anderen Problemen.

25:19.980 --> 25:22.880
Also für die Inversion von Matrizen zum Beispiel, für die Berechnung

25:22.880 --> 25:26.120
von Determinanten, für die Lösung linierer Gleichungssysteme.

25:26.640 --> 25:28.460
Da brauche ich nämlich genau diese Operation.

25:28.660 --> 25:30.100
Da muss ich Matrizen invertieren.

25:31.060 --> 25:33.700
Und für die Lösung linierer Gleichungssysteme.

25:33.700 --> 25:38.380
Wenn ich das genauso schnell kann wie Matrizmodifikation, dann habe

25:38.380 --> 25:41.000
ich auf einmal Lösungen linierer Gleichungssysteme auch schnell

25:41.000 --> 25:41.440
gemacht.

25:42.700 --> 25:49.640
Und es ist so, dass man durchaus, ich gehe darauf gleich noch ein auf

25:49.640 --> 25:52.240
der nächsten Folie, nur noch eine Bemerkung zu überhaupt der

25:52.240 --> 25:53.260
Matrizmodifikation.

25:53.920 --> 25:57.500
Man hat natürlich dann alle möglichen anderen Verfahren sich überlegt,

25:57.600 --> 25:59.880
wie könnte man die Matrizmodifikation beschleunigen.

25:59.880 --> 26:06.060
Das Dumme ist nämlich, die bestbekannte untere Schranke für die Anzahl

26:06.060 --> 26:09.400
der arithmetischen Operationen, für die Matrizmodifikation, also die

26:09.400 --> 26:11.300
Modifikation von NxN-Matrizen, ist N².

26:12.280 --> 26:21.120
Also mindestens eine Operation pro zu berechnendem Element der

26:21.120 --> 26:21.980
Produktmatrix.

26:22.660 --> 26:24.520
Das ist trivial, diese untere Schranke.

26:25.540 --> 26:28.960
Ja, also N² ist trivial, dass ich die brauche.

26:30.300 --> 26:31.460
Aber ich habe keine bessere.

26:32.140 --> 26:34.620
Es hat niemand bisher eine bessere Schranke gefunden.

26:35.640 --> 26:37.980
Und dann haben Leute versucht, das doch noch runterzudrücken und haben

26:37.980 --> 26:43.720
dann mit anderen Ansätzen, da sind also tiefer liegende Sätze der

26:43.720 --> 26:51.920
linearen Algebra mit drin, hat man das geschafft, auf N hoch 2.37 zu

26:51.920 --> 26:52.180
kommen.

26:52.180 --> 26:58.960
Da waren auch Barbinograd stark beteiligt, Coppersmith, auch ein

26:58.960 --> 26:59.620
Wissenschaftler.

27:00.020 --> 27:04.420
Die haben also, dass wir es auf 2 hoch, also 2.37 drücken können.

27:04.700 --> 27:09.080
Allerdings ist die Konstante hier so hoch, dass das nicht praktisch

27:09.080 --> 27:09.880
relevant ist.

27:10.760 --> 27:14.260
Also theoretisch interessant, asymptotisch komme ich runter auf N hoch

27:14.260 --> 27:18.820
2.37, aber die Konstante, die ich brauche da drin, die so ein bisschen

27:18.820 --> 27:24.880
was sagt, wie kompliziert dieser Ansatz eigentlich ist, die ist halt

27:24.880 --> 27:27.540
sehr groß, deswegen ist es praktisch nicht relevant.

27:27.720 --> 27:29.440
Praktisch relevant ist die Straßenbedürfnisse.

27:31.860 --> 27:34.260
Und, wie gesagt, untere Schranke, N², hatte ich schon gesagt.

27:34.340 --> 27:36.680
Jetzt schauen wir uns nochmal kurz an diese Beziehungen zwischen der

27:36.680 --> 27:38.520
Matrix -Modifikation und Matrix-Inversion.

27:39.000 --> 27:40.280
Was haben die miteinander zu tun?

27:41.140 --> 27:44.920
Und da kommen wir auf einen Ansatz, den man auch häufig wählt, dass

27:44.920 --> 27:47.220
man Probleme ineinander transformiert.

27:47.560 --> 27:54.520
Also zunächst mal, ich habe eine Matrix A und jetzt möchte ich die

27:54.520 --> 27:55.240
invertieren.

27:57.120 --> 27:58.800
Es gibt also eine Matrix C.

28:00.200 --> 28:05.420
Und jetzt hat auch Straßen sich überlegt, wie man das macht.

28:05.460 --> 28:08.720
Das ist jetzt hier also der gleiche Ansatz, ein ähnlicher Ansatz.

28:08.720 --> 28:14.540
Ich habe hier eine Matrix A und die teile ich auf, genau wie vorher

28:14.540 --> 28:20.560
bei dem Straßenansatz, in 2x2-Matrizen von Teilmatrizen.

28:22.260 --> 28:28.840
Und A auf –1, die Inverse, auch so aufgeteilt.

28:28.940 --> 28:32.240
Nun ist die Frage, wie bestimme ich jetzt diese vier Komponenten C11

28:32.240 --> 28:33.260
bis C22?

28:35.000 --> 28:39.580
Das Interessante ist, ich habe hier eine Reihe von Operationen.

28:39.700 --> 28:42.580
Da habe ich ein paar Produkte zu machen.

28:43.440 --> 28:47.380
Hier muss ich prekursiv das A11 invertieren.

28:48.460 --> 28:50.180
Ja, das mache ich wieder diesen Ansatz.

28:50.580 --> 28:53.120
Dann habe ich hier ein Produkt von Matrizen, da habe ich ein Produkt

28:53.120 --> 28:53.840
von Matrizen.

28:54.300 --> 28:56.560
Da habe ich eins, hier habe ich eine Differenz.

28:57.340 --> 29:00.160
Da habe ich nochmal eine Inversion zu machen, prekursiv.

29:00.160 --> 29:04.620
Produkt, Produkt, Differenz, Produkt.

29:05.360 --> 29:09.140
Und dann hier nochmal, das C22 ist gerade der negative Wert von dem

29:09.140 --> 29:09.640
T6.

29:12.320 --> 29:20.840
Und was man hier mit diesem Ansatz herausfinden kann ist, dass wenn

29:20.840 --> 29:25.280
ich eine Matrix-Multiplikation in der Zeit O von N hoch Alpha

29:25.280 --> 29:29.480
hinbekommen kann, und Alpha ist größer gleich 2, dann kann ich mit

29:29.480 --> 29:34.060
diesem Ansatz die Matrix-Inversion auch in der Zeit O von N hoch Alpha

29:34.060 --> 29:34.600
hinbekommen.

29:36.620 --> 29:38.160
Das heißt, gleiche Größenordnung.

29:38.840 --> 29:43.460
Das heißt, im Prinzip kann ich also jetzt aus dem N hoch 2.3.7

29:43.460 --> 29:50.360
-Verfahren auch eine solche Matrix-Inversion-Verfahren ableiten.

29:52.700 --> 29:58.240
Und das heißt, aus einem Verfahren für eine Matrix-Multiplikation kann

29:58.240 --> 30:01.240
ich ableiten, ein Verfahren, oder kann ich erzeugen ein Verfahren für

30:01.240 --> 30:02.480
die Matrix-Inversion.

30:03.920 --> 30:05.180
Wie sieht das andersrum aus?

30:05.980 --> 30:06.540
Umkehrung.

30:08.040 --> 30:11.300
Nehmen wir an, ich kenne ein Verfahren für eine Matrix-Inversion.

30:12.280 --> 30:15.540
Könnte ja sein, dass ich da auch irgendeinen ganz tollen Ansatz habe.

30:17.820 --> 30:26.820
Und jetzt bekomme ich das Produkt von zwei Matrixen auf eine ganz

30:26.820 --> 30:27.980
einfache Art und Weise.

30:28.920 --> 30:31.920
Ich möchte gerne Matrixen A und B multiplizieren.

30:32.660 --> 30:37.680
Und setze die einfach in eine größere Matrix ein, in eine 3N kreuz 3N

30:37.680 --> 30:40.780
Matrix, die diese Gestalt hat, wie sie hier steht.

30:41.260 --> 30:46.200
Und von einer solchen Matrix, obere 3N Matrix, mit dieser Form, wenn

30:46.200 --> 30:49.960
ich mir da die Inverse anschaue, stelle ich fest, die hat gerade diese

30:49.960 --> 30:51.060
Gestalt.

30:51.200 --> 30:55.400
Und hier oben, in der rechten oberen Ecke, steht dann bei der Inverse

30:55.400 --> 30:57.540
das Produkt der beiden Matrixen A und B.

30:58.420 --> 31:01.340
Das heißt, wenn ich ein Verfahren für die Inversion habe, welches auch

31:01.340 --> 31:05.780
immer, und ich möchte N kreuz N Matrixen multiplizieren, invertiere

31:05.780 --> 31:11.940
ich einfach diese 3N kreuz 3N Matrix und bekomme dann hier oben das

31:11.940 --> 31:14.180
Produkt der beiden Matrixen.

31:14.960 --> 31:19.160
Und hier sehen Sie die Beziehung zwischen Inversion und Modifikation.

31:20.940 --> 31:23.880
Manchmal kann man durch Transformation von Problemen in andere

31:23.880 --> 31:28.140
Probleme sehr interessante neue Verfahren entwickeln.

31:29.580 --> 31:33.240
Und das, was Strassen eben ursprünglich formuliert hat, oder nicht

31:33.240 --> 31:36.400
ursprünglich, sondern was er veröffentlicht hat, in seinem Artikel, in

31:36.400 --> 31:41.000
dem er sein Verfahren vorgestellt hat, war ein Artikel mit der

31:41.000 --> 31:43.660
Überschrift, Gauss'sche Elimination ist nicht optimal.

31:44.900 --> 31:47.060
Natürlich auf Englisch.

31:47.200 --> 31:54.660
Und das war eben etwas, was völlig gegen die Intuition war, weil bis

31:54.660 --> 31:59.880
dahin jeder davon ausgegangen ist, dass selbstverständlich besser als

31:59.880 --> 32:03.300
Gauss mit dem NO3-Verfahren geht das eigentlich gar nicht.

32:04.620 --> 32:08.240
Nur durch ein besseres Verfahren für die Matrixmultiplikation kann ich

32:08.240 --> 32:12.500
eben durch diese ganzen Implikationen hier für die Matrixinversion auf

32:12.500 --> 32:15.920
einmal die Gauss'sche Elimination auch in der gleichen Zeit machen.

32:17.080 --> 32:20.040
Das ist das Interessante, was dann zu vielen weiteren

32:20.040 --> 32:23.620
Forschungsarbeiten geführt hat.

32:24.700 --> 32:28.320
Ob man jetzt noch unter dieses 2.37 kommen kann, ist nach wie vor

32:28.320 --> 32:28.560
offen.

32:29.980 --> 32:32.280
Da ist man noch nicht wirklich weiter gekommen.

32:32.440 --> 32:35.260
Wenn von Ihnen einer eine Idee hat, wie er das mit 2.3 hinkriegt oder

32:35.260 --> 32:39.300
mit 2.35 oder 2.34, können Sie einen guten Artikel darüber schreiben.

32:40.800 --> 32:41.860
Kann interessant sein.

32:43.440 --> 32:45.880
So, jetzt reicht uns das aber nicht.

32:46.580 --> 32:49.280
Wir sagen, wir sind ja in der Lage, das ganz anders zu machen.

32:49.660 --> 32:52.320
Es kommt uns nur auf die Zeit an, also die Anzahl der Schritte.

32:52.800 --> 32:54.480
Und deswegen parallelisieren wir das Ganze.

32:56.660 --> 33:02.180
Und ich kann es auf einer PRAM machen, das haben wir schon getan.

33:02.360 --> 33:05.880
Das Verfahren kennen Sie, da hatten wir Log-In-Schritte gebraucht.

33:05.880 --> 33:10.260
Das war hier diese überall Summen.

33:10.320 --> 33:12.840
Hier ein Produkt, da viele Produkte.

33:13.100 --> 33:15.000
Und dann hatten wir die entsprechend addiert.

33:18.390 --> 33:19.050
Na, wie war das jetzt?

33:19.230 --> 33:19.510
Da und da.

33:20.810 --> 33:25.210
Also das waren die verschiedenen, oben einmal Produkte und dann schön

33:25.210 --> 33:25.810
aufsummiert.

33:26.090 --> 33:30.470
Das waren die OVON Log-In-Schritte mit N3 durch Log-In-Prozessoren.

33:31.790 --> 33:33.210
Und das Ganze ist optimal.

33:33.210 --> 33:36.950
Einmal optimaler Zeitgewinn, aber eigentlich nicht.

33:37.590 --> 33:42.170
Weil für einen Zeitgewinn, das hatte ich extra betont, muss man immer

33:42.170 --> 33:44.510
nehmen das bestmögliche sequenzielle Verfahren.

33:45.910 --> 33:49.850
Also müsste ich hier vergleichen mit dem Verfahren von Coppersmith und

33:49.850 --> 33:54.050
Winograd mit N2.37 und ich hätte dann nicht ein optimales Ergebnis.

33:55.710 --> 33:59.290
Trotzdem, in diesem Fall sagt man, ich vergleiche einfach mit dem

33:59.290 --> 34:03.850
Verfahren mit N3-Operationen, mit der Schulmethode, ich weiche also

34:03.850 --> 34:07.350
hier schon ab von meinem Prinzip, mit dem bestmöglichen sequenziellen

34:07.350 --> 34:11.390
Verfahren vergleichen, weil für die Größenordnungen, für die wir hier

34:11.390 --> 34:15.810
parallele Matrixmodifikation betrachten, ist das jeweils das beste

34:15.810 --> 34:16.430
Verfahren.

34:17.530 --> 34:21.250
Also in dem Bereich, in dem ich argumentiere, Parallelität heißt ja

34:21.250 --> 34:24.330
nicht, ich habe Millionen von Prozessoren, sondern ich habe eine

34:24.330 --> 34:27.850
gewisse Zahl von Prozessoren, aber das sind nicht wahnsinnig viele,

34:28.330 --> 34:32.030
dann ist das durchaus sinnvoll, mit der Schulmethode zu vergleichen.

34:32.550 --> 34:35.450
Und wir hatten gesehen, wenn man also N3 durch Log N Prozessoren

34:35.450 --> 34:37.130
nimmt, hat man einen optimalen Zeitgewinn.

34:38.590 --> 34:41.010
Und da wissen wir, wie man das macht.

34:41.850 --> 34:44.810
Jetzt könnten Sie doch sagen, ich mache das einfach auf einer

34:44.810 --> 34:49.350
concurrent read, concurrent write PRAM und mache das mit dem Verfahren

34:49.350 --> 34:49.790
Summ.

34:51.290 --> 34:55.250
Also ich summiere, ich lasse einfach alle Prozessoren, die ein Produkt

34:55.250 --> 34:57.930
berechnet haben, in die gleiche Zelle schreiben.

34:58.630 --> 35:03.310
Also die haben hier alle die Produkte berechnet, die schreiben alle in

35:03.310 --> 35:06.670
eine Zelle, sind aufsummiert, ich habe einen Schritt für die Summe.

35:07.090 --> 35:07.610
Ganz toll.

35:07.810 --> 35:10.090
Spreche mir Log N, bin sogar in konstanter Zeit fertig.

35:10.590 --> 35:14.950
Aber dann habe ich natürlich einen super Operator, der N Elemente in

35:14.950 --> 35:17.350
einem Schritt addieren kann, was nicht so ganz realistisch ist.

35:20.990 --> 35:25.290
Log N ist das, was wir mit Parallelrechnern erreichen können,

35:25.470 --> 35:26.090
bestmöglich.

35:26.950 --> 35:33.810
Jetzt ist es aber, also nicht jeder hat eine PRAM und es gibt eben

35:33.810 --> 35:36.950
interessante Verfahren auf sogenannten zweidimensionalen

35:36.950 --> 35:37.690
Prozessorfeldern.

35:37.770 --> 35:41.670
Da hatte ich Ihnen schon das Verfahren von Kung und Leiserson gezeigt,

35:41.770 --> 35:46.410
mit diesem zweidimensionalen hexagonalen Feld, wo wir die Matrizen

35:46.410 --> 35:47.470
durchgeschoben haben.

35:48.670 --> 35:54.150
Und ich möchte also jetzt N x N Matrizen A und B modifizieren und das

35:54.150 --> 35:55.350
Produkt berechnen.

35:55.430 --> 35:57.690
Und jetzt mache ich das ein bisschen anders als vorher.

35:58.670 --> 36:02.350
Nicht ein hexagonales Feld, sondern ein einfaches zweidimensionales

36:02.350 --> 36:03.370
gitterverbundenes Feld.

36:04.050 --> 36:07.910
Hier ein Beispiel 4 x 4 Feld, also 16 Prozessoren.

36:08.490 --> 36:11.130
Ich möchte 4 x 4 Matrizen modifizieren.

36:11.710 --> 36:15.250
Das muss sich dafür sorgen, dass die geeigneten Elemente zueinander

36:15.250 --> 36:15.690
finden.

36:16.350 --> 36:21.530
Und hier ist also die Idee, dass wir in jeder Komponente gerade das

36:21.530 --> 36:23.370
zugeordnete Matrixelement berechnen.

36:23.470 --> 36:29.910
Also hier soll C11 stehen, da soll C12 stehen, da C14 am Ende.

36:30.830 --> 36:32.650
Und dann muss ich noch sehen, wie ich die da rauskriege.

36:33.630 --> 36:35.510
Wenn ich sie denn rauskriegen möchte.

36:35.510 --> 36:38.830
Und die Matrizen A und B sind, wie ich das letztes Mal auch schon

36:38.830 --> 36:41.270
gemacht habe, in Rot und Blau angegeben.

36:42.950 --> 36:48.230
Und im ersten Schritt werden also diese A14 und B41 eingegeben in

36:48.230 --> 36:50.810
diese Zelle hier oben, linke obere Ecke.

36:51.710 --> 36:55.670
Und dann habe ich die also hier drin, modifiziere die beiden.

36:56.150 --> 37:00.750
Und im nächsten Schritt sehen Sie, jetzt werden hier und dort A24 und

37:00.750 --> 37:02.010
B42 eingegeben.

37:02.850 --> 37:07.150
Und entsprechend A13, B31 in die linke obere Ecke.

37:07.850 --> 37:09.050
Und das geht jetzt so weiter.

37:09.330 --> 37:11.750
Die beiden werden so verschränkt durcheinander geschoben.

37:12.270 --> 37:14.970
Die Matrix geht eben in die Richtung, die immer in die Richtung.

37:15.950 --> 37:19.070
Und auf die Art und Weise treffen sich in den einzelnen Zellen genau

37:19.070 --> 37:24.290
die richtigen Elemente der Matrizen, um diese Elemente sukzessive zu

37:24.290 --> 37:25.330
berechnen, die wir brauchen.

37:25.890 --> 37:28.970
Und wenn das alles durchgelaufen ist, dann irgendwann sind wir fertig

37:28.970 --> 37:33.750
und wir haben überall die Elemente C, J drin stehen.

37:34.550 --> 37:35.610
Und wie lange braucht das?

37:37.610 --> 37:41.790
Naja, ich hatte angefangen, dass ich hier oben was eingegeben hatte.

37:42.850 --> 37:46.610
Und das dauert so lange, bis die letzten beiden Elemente hier unten

37:46.610 --> 37:47.590
eingegeben werden.

37:49.570 --> 37:54.250
Das dauert N Takte, bis ich da bin.

37:54.250 --> 37:58.590
Dann nochmal N-1 dazu, das sind für das erste Element.

38:00.570 --> 38:06.850
Es dauerte also, ich kann auch anders zählen, es dauerte N Takte, bis

38:06.850 --> 38:10.730
das A11 hier eingegeben war.

38:11.950 --> 38:17.190
Und dann muss das Ganze ja noch hier rüber laufen und ich muss von

38:17.190 --> 38:18.910
dort noch ganz runter laufen können.

38:18.910 --> 38:21.310
Das heißt, das sind insgesamt 3N-2.

38:21.890 --> 38:24.030
Also N plus N-1 plus N-1.

38:24.890 --> 38:28.170
Das ist die Zeit, die ich brauche, bis die Elemente alle berechnet

38:28.170 --> 38:29.190
sind in meinem Feld.

38:30.370 --> 38:31.330
3N-2.

38:32.290 --> 38:42.850
Jetzt habe ich einen Zeitgewinn im Vergleich zur Schulmethode von N²,

38:43.050 --> 38:45.430
weil ich von N hoch 3 auf N gekommen bin.

38:45.430 --> 38:49.350
Und die Effizienz ist optimal, ist konstant.

38:53.070 --> 38:55.930
Bestmöglich mit N² Prozessoren.

38:56.950 --> 38:58.590
Sehr einfaches Verfahren.

39:00.330 --> 39:03.790
Und damit haben wir also ein weiteres Verfahren für die Matrix

39:03.790 --> 39:04.450
-Modifikation.

39:04.550 --> 39:06.610
Wir sind auf lineare Zeit runtergekommen.

39:07.150 --> 39:13.750
Natürlich nach wie vor N hoch 3 Operationen, aber trotzdem ein schöner

39:13.750 --> 39:14.290
Gewinn.

39:14.290 --> 39:17.050
Und wir haben ein sehr einfaches Prozessor.

39:17.250 --> 39:18.590
Jetzt schauen wir uns das nochmal anders an.

39:18.950 --> 39:22.190
Was man hier nochmal sieht ist, natürlich haben wir jetzt anschließend

39:22.190 --> 39:24.070
die Elemente alle in dem Feld drin.

39:24.870 --> 39:29.570
Wenn wir die außen verfügbar haben wollen, müssten wir noch einmal die

39:29.570 --> 39:31.430
Elemente alle hier irgendwie rausschieben.

39:31.530 --> 39:33.870
Meinetwegen alle nach rechts rausschieben.

39:35.230 --> 39:37.670
Das würde nochmal N-Takte dauern.

39:38.910 --> 39:42.450
Dann hätten wir insgesamt 4N-2.

39:43.230 --> 39:45.430
Um die Elemente tatsächlich draußen zu haben.

39:46.590 --> 39:48.910
Jetzt schauen wir uns ein anderes Verfahren an.

39:49.490 --> 39:50.850
Von Kramer und von Löwen.

39:50.950 --> 39:53.410
Da haben sich viele Leute mit beschäftigt, mit Matrix-Modifikation.

39:54.410 --> 39:57.730
Und hier haben wir wieder die Standard-Operation in den Prozessoren.

39:57.850 --> 39:59.830
Das ist also wieder die Standard-Matrix-Modifikation.

40:00.090 --> 40:04.090
Aber hier jetzt ähnlich wie bei dem hexagonalen Feld, wo ja auch am

40:04.090 --> 40:06.550
Ende die Elemente alle draußen waren.

40:07.270 --> 40:10.170
Das wird also modifiziert.

40:10.310 --> 40:11.710
A und B werden modifiziert.

40:12.110 --> 40:15.170
Und aufaddiert auf das, was von links eingegeben wird.

40:15.610 --> 40:16.990
Und das wird nach rechts ausgegeben.

40:17.710 --> 40:21.330
Also diese Standard-Skalarprodukt-Operation.

40:23.210 --> 40:28.570
Und ich schiebe also jetzt meine Matrizen so, dass diese Matrix, die

40:28.570 --> 40:32.850
Ergebnis -Matrix, horizontal durchlaufen soll durch das Feld.

40:33.490 --> 40:37.130
Meine A-Matrix von oben nach unten und die B-Matrix von unten nach

40:37.130 --> 40:37.390
oben.

40:38.510 --> 40:41.670
Sie sehen, bei diesem Feld, da wird es eine Weile dauern, bis die

40:41.670 --> 40:42.610
Elemente sich treffen.

40:43.150 --> 40:45.830
Also, die gehen hier erstmal rein.

40:45.970 --> 40:47.230
Da passiert noch gar nichts.

40:47.810 --> 40:48.670
Da auch noch nicht viel.

40:49.310 --> 40:52.830
Und jetzt im nächsten Takt, da treffen sich hier, sehen Sie, die A11,

40:53.110 --> 40:55.890
B11 und C11 treffen sich.

40:55.990 --> 40:56.950
Hier wird modifiziert.

40:56.950 --> 41:01.990
Das Ganze wird nach rechts weitergegeben und darauf wird addiert A12

41:01.990 --> 41:03.810
mal B21.

41:04.570 --> 41:07.990
Und entsprechend wird hier in den anderen Zellen auch modifiziert.

41:08.670 --> 41:11.590
Und nach vier Takten kommt das Element C11 hier raus.

41:12.250 --> 41:17.170
Und hat dann hier auf dem Weg durch dieses Feld genau die vier

41:17.170 --> 41:25.130
Produkte A11 mal B11 bis A14 mal B41 aufgesammelt.

41:26.010 --> 41:26.370
So.

41:26.690 --> 41:29.070
Und das Ganze läuft entsprechend dann natürlich noch weiter.

41:29.950 --> 41:34.270
Und dann habe ich hier irgendwann das Ergebnis draußen stehen.

41:35.350 --> 41:39.810
Wenn ich hier zähle, wie lange das dauert, von der Eingabe des ersten

41:39.810 --> 41:45.310
Elements bis zur Ausgabe des letzten Elements, bekomme ich genau auf

41:45.310 --> 41:46.550
4n -2.

41:48.270 --> 41:52.050
Genau die gleiche Zahl, die wir hatten, bei dem Verfahren, was ich

41:52.050 --> 41:55.790
Ihnen gerade vorher gezeigt hatte, wenn wir verlangen, dass alle

41:55.790 --> 41:58.450
Matrix -Elemente, die berechnet wurden, auch noch nach rechts

41:58.450 --> 41:59.410
ausgegeben werden.

42:01.390 --> 42:02.710
Also ist die gleiche Zahl.

42:04.110 --> 42:10.450
Und Zeitgewinn wieder Größenordnung n², Effizienz ist konstant.

42:11.070 --> 42:12.130
Also, noch ein Verfahren.

42:13.110 --> 42:15.390
Da könnte man sich fragen, geht das noch anders?

42:15.970 --> 42:18.290
Kann ich Ihnen noch ein anderes Feld aufmalen und die vielleicht

42:18.290 --> 42:19.270
anders laufen lassen?

42:20.470 --> 42:23.210
Was interessant ist übrigens, was ich hier noch bemerken möchte, ist

42:23.210 --> 42:23.670
folgendes.

42:24.530 --> 42:27.510
Ich könnte natürlich auch folgendes, Sie erinnern sich, gehen wir

42:27.510 --> 42:28.130
nochmal zurück.

42:28.830 --> 42:34.150
Was Sie hier sehen ist ja, hier ist nur jede zweite Zelle aktiv.

42:36.730 --> 42:38.320
Das ist schlecht, halb ausgenutzt.

42:38.320 --> 42:40.180
Ich möchte die ganz ausnutzen.

42:40.680 --> 42:44.660
Also würde ich hier wieder das gleiche machen, wie bei dem, was ich

42:44.660 --> 42:47.300
auch bei dem Verfahren von Kung und Leiserson gesagt habe.

42:47.680 --> 42:54.180
Ich würde im Prinzip hier noch ein weiteres Element 1, 1, 2, 2, 3, 3

42:54.180 --> 42:54.480
usw.

42:54.640 --> 42:55.080
reinschreiben.

42:55.200 --> 42:57.040
Das heißt, das Ganze um 1 verschränken.

42:57.920 --> 43:01.360
Um 1 verschränkt, hier weitere Komponenten reinschreiben.

43:02.240 --> 43:04.440
Und die kann ich praktisch nebenläufig durchschieben.

43:04.440 --> 43:08.340
Ich kann also zwei Matrix-Multiplikationen gleichzeitig machen.

43:09.200 --> 43:10.460
Um einen Takt versetzt.

43:11.120 --> 43:14.080
Und dann habe ich eben nicht mehr nur die 11.

43:14.180 --> 43:17.120
der Zellen aktiv, sondern dann ist jede Zelle aktiv.

43:17.960 --> 43:21.600
Und zwar jeweils für eine andere Matrix-Multiplikation um einen Takt

43:21.600 --> 43:22.060
versetzt.

43:24.440 --> 43:28.140
Das läuft schön nebeneinander durch, behindert sich nicht, beeinflusst

43:28.140 --> 43:28.520
sich nicht.

43:28.520 --> 43:32.820
Und ich habe dann also zwei Matrix-Multiplikationen im Prinzip in der

43:32.820 --> 43:33.880
gleichen Zeit gemacht.

43:35.100 --> 43:38.040
Und jetzt kann ich sagen, ich habe ja hier nur ein 4x4-Feld.

43:38.220 --> 43:40.420
Also, was kann ich schon mit 4x4-Matrizen machen?

43:42.040 --> 43:45.720
Jetzt kann ich natürlich sagen, wenn ich ein großes Matrix-Produkt

43:45.720 --> 43:54.340
habe, die kann ich ja einfach aufteilen auf entsprechend 4x4-Matrizen.

43:58.860 --> 44:04.920
Beziehungsweise ich kann das Ganze betrachten als eine Matrix, nicht

44:04.920 --> 44:05.420
4x4.

44:05.480 --> 44:07.640
Ich kann also so machen, dass ich 4x4-Matrizen mache.

44:09.160 --> 44:14.180
Dann sind die Komponenten einzelne n-Viertel-kreuz-n-Viertel-Matrizen.

44:15.240 --> 44:18.240
Und ich müsste dann in meinen Prozessoren nicht einfach solche

44:18.240 --> 44:22.740
Elemente modifizieren und addieren, sondern Matrizen modifizieren und

44:22.740 --> 44:23.460
etwas drauf addieren.

44:23.540 --> 44:25.040
Das sind etwas dickere Prozessoren.

44:25.040 --> 44:26.760
Kann ich aber machen.

44:28.580 --> 44:31.860
Dann würde ich praktisch das hier als ein Netz von etwas

44:31.860 --> 44:33.820
leistungsfähigeren Prozessoren betrachten.

44:34.420 --> 44:36.420
Meine Elemente wären jetzt Matrizen.

44:37.020 --> 44:40.720
Ich kann es auch andersrum auffassen und sage, ich bleibe bei diesem

44:40.720 --> 44:44.600
Feld mit den kleinen Prozessoren, die einfach nur zwei Zahlen

44:44.600 --> 44:46.700
multiplizieren und dann einen drauf addieren können.

44:47.380 --> 44:56.640
Und jetzt multipliziere ich n-Viertel-kreuz-n-Viertel-Matrizen.

44:57.200 --> 45:03.160
Und jedes Element da drin, das sind 4x4-Matrizen.

45:05.160 --> 45:10.200
Und wenn ich jetzt 4x4-Matrizen multiplizieren muss, dann kann ich ja

45:10.200 --> 45:23.940
jedes Produkt, dann habe ich eine Summe, a i k mal b k j, k gleich 1

45:23.940 --> 45:27.220
bis, in dem Fall, n-Viertel.

45:29.660 --> 45:32.900
Und das ist dann mein entsprechendes cij in dieser Matriz.

45:34.000 --> 45:37.080
Das sind jetzt solche Matrizen.

45:39.320 --> 45:41.900
Dann kann ich aber Folgendes machen.

45:42.860 --> 45:48.520
Ich schiebe einfach hier so ein Produkt oder diese 4x4-Matrizen rein.

45:49.400 --> 45:53.180
Jetzt habe ich eine Summe von 4x4-Matrizen berechnet.

45:54.120 --> 45:56.980
Quatsch, ein Produkt berechnen, muss das addieren auf das nächste

45:56.980 --> 45:57.420
Produkt.

45:58.960 --> 46:02.020
Dann kann ich einfach das hier, was ich jetzt berechnet habe, hier

46:02.020 --> 46:03.040
vorne wieder reinschieben.

46:04.380 --> 46:06.240
Und entsprechend die nächsten Matrizen.

46:08.300 --> 46:10.420
Hier kommen lassen und da kommen lassen.

46:11.580 --> 46:15.840
Dann kann ich solch ein 4x4-Feld nutzen, um sukzessive die ganzen

46:15.840 --> 46:16.700
Berechnungen zu machen.

46:16.820 --> 46:23.480
Ich habe dann also zumindest das um diesen Faktor beschleunigt, durch

46:23.480 --> 46:27.120
Verwendung dieses Feldes für die Multiplikation von 4x4-Matrizen.

46:27.280 --> 46:28.460
Die habe ich dann parallelisiert.

46:30.340 --> 46:33.480
Das kann ich dann einfach, ich könnte also hier diese Elemente wieder

46:33.480 --> 46:33.840
reinschieben.

46:33.840 --> 46:38.280
Das heißt, ich müsste dann nicht das, was ich zu Anfang sagte, die

46:38.280 --> 46:41.500
kommen hier initialisiert als Null rein, sondern das ist dann ein

46:41.500 --> 46:46.080
vorher berechneter Wert aus dem ersten Produkt, und da drauf addiere

46:46.080 --> 46:46.900
ich dann das nächste Produkt.

46:48.040 --> 46:51.340
Dann habe ich also hier so eine iterative Nutzung eines solchen Stück

46:51.340 --> 46:54.020
Hardware mit fester Grenze.

46:58.040 --> 47:00.900
Das heißt, ich habe hier die beiden Alternativen.

47:01.800 --> 47:03.800
Es waren folgende Alternativen.

47:04.840 --> 47:22.140
Das eine ist lokal, sequenziell und global parallel, oder lokal

47:22.140 --> 47:28.840
parallel und global sequenziell.

47:28.840 --> 47:31.980
Das erste Verfahren war lokal sequenziell.

47:32.080 --> 47:36.560
Da habe ich große Prozessoren, die sequenziell in Viertelkreuz, in

47:36.560 --> 47:37.880
Viertelmatrizen multiplizieren.

47:38.720 --> 47:41.800
Das andere Verfahren, da mache ich lokal parallel.

47:42.560 --> 47:48.560
Da habe ich lokal 4x4-Matrizen multipliziert und mache das Ganze in

47:48.560 --> 47:50.480
einem großen sequenziellen Verfahren.

47:50.740 --> 47:54.640
Das sind zwei verschiedene Ansätze.

47:54.640 --> 47:57.900
Auf die Art und Weise kann man Berechnungen unterschiedlich

47:57.900 --> 48:00.520
organisieren.

48:01.020 --> 48:03.480
Man braucht natürlich unterschiedlich leistungsfähige

48:03.480 --> 48:04.700
Einzelprozessoren dafür.

48:04.800 --> 48:08.360
Einmal die ganz einfachen, oder auch etwas leistungsfähiger, wenn ich

48:08.360 --> 48:10.820
jetzt hier lokal sequenziell arbeite.

48:11.660 --> 48:14.860
Das heißt, mit diesem einen Verfahren bekommen wir eine ganze Vielfalt

48:14.860 --> 48:17.380
von möglichen Berechnungen.

48:18.000 --> 48:20.580
Das kann ich hier machen mit diesem Feld, wo wir die Matrizen so

48:20.580 --> 48:21.020
durchschieben.

48:21.020 --> 48:24.700
Ich hätte es auch mit dem Verfahren machen können, wo wir die von

48:24.700 --> 48:28.260
links nach rechts und von oben nach unten durchgeschoben haben und die

48:28.260 --> 48:30.260
Elemente anschließend in dem Feld drin saßen.

48:31.800 --> 48:32.720
Wäre auch gegangen.

48:34.060 --> 48:35.620
Mit ein bisschen anderer Art und Weise.

48:35.740 --> 48:37.940
Sie sehen, es gibt also auf einmal eine Vielfalt von Matriz

48:37.940 --> 48:38.940
-Multiplikationsverfahren.

48:40.000 --> 48:43.000
Die Frage ist, wie entscheidet man sich eigentlich für ein Verfahren?

48:43.640 --> 48:46.600
Wie entwirft man derartig unterschiedliche Algorithmen?

48:47.220 --> 48:48.980
Das eine ist natürlich...

48:48.980 --> 48:51.940
Also Kung und Leisowsan hatten die Idee, ich mache es in ein

48:51.940 --> 48:52.840
hexagonales Feld.

48:53.400 --> 48:55.700
Oder Kramer und von Löwen haben das andere genommen.

48:57.160 --> 49:00.000
Und jetzt muss man sich überlegen, wie ordentlich meine Daten an...

49:00.000 --> 49:03.540
Das ist ja ziemlich fieselig, sich zu überlegen, wann muss ich welches

49:03.540 --> 49:06.700
Datum eingeben, damit ich tatsächlich dann dafür sorge, dass die

49:06.700 --> 49:10.020
richtigen Daten im richtigen Augenblick an der richtigen Stelle sind.

49:11.940 --> 49:17.060
Und die Idee ist einfach, das Ganze sieht ja sehr systematisch, sehr

49:17.060 --> 49:17.560
einfach aus.

49:17.620 --> 49:22.140
Ich habe doch immer nur diese Operation hier, dieses C gleich C plus A

49:22.140 --> 49:22.720
mal B.

49:22.820 --> 49:26.360
Das war in all diesen Verfahren, hat man diese Operation in den

49:26.360 --> 49:29.300
einzelnen Prozessoren gemacht und das dann nur unterschiedlich

49:29.300 --> 49:30.020
angeordnet.

49:32.480 --> 49:37.020
Und die Idee ist, dass man jetzt versucht, aus der Problemdefinition

49:38.580 --> 49:42.000
oder aus einem Programm, wo das hier die innerste Schleife ist für die

49:42.000 --> 49:45.800
Matrixmodifikation, systematisch ein paralleles Verfahren zu erzeugen.

49:47.600 --> 49:50.520
Das machen wir auf den nächsten Folien.

49:51.340 --> 49:55.400
Also, wir wollen folgendes machen, wir nehmen die Problemdefinition

49:55.400 --> 49:55.780
hier.

49:56.640 --> 50:02.780
Im Prinzip also unsere Summe Aik mal Bkj.

50:05.500 --> 50:08.600
Das ist unser Cij.

50:10.360 --> 50:12.180
So, das ist die Problemdefinition.

50:12.500 --> 50:14.500
Die kann man noch ein bisschen anders aufschreiben.

50:15.780 --> 50:17.780
Und zwar kann ich das aufschreiben...

50:18.320 --> 50:19.840
Diese Formel ist ja kein Programm.

50:20.420 --> 50:22.120
Kann ich nicht direkt verwenden als Programm.

50:22.120 --> 50:25.400
Ich kann das als System von Rekurrenzgleichung aufschreiben.

50:26.040 --> 50:27.380
Oder als einen iterativen Algorithmus.

50:28.340 --> 50:30.880
Iterativen Algorithmus kennen Sie die Schuhmethode, wie ich sie

50:30.880 --> 50:31.760
aufgeschrieben habe.

50:33.380 --> 50:36.140
System von Rekurrenzgleichung werden Sie gleich kennenlernen, wie ich

50:36.140 --> 50:37.360
das meine.

50:38.220 --> 50:42.620
Und aus dieser Formulierung bekomme ich Informationen über

50:42.620 --> 50:44.820
Abhängigkeiten zwischen einzelnen Berechnungen.

50:46.880 --> 50:53.520
Ja, wenn ich erstmal das Cij berechnen muss, muss ich zunächst mal A11

50:53.520 --> 50:55.640
mal B11 rechnen.

50:55.720 --> 50:57.720
Darauf addieren, das nächste und so weiter.

50:58.640 --> 51:01.540
Das heißt, ich habe da eine gewisse Abhängigkeit der Berechnungen.

51:01.640 --> 51:07.420
Wenn ich diese Gleichung hinschreibe, C gleich C plus A mal B, dann

51:07.420 --> 51:10.280
brauche ich den alten Wert für C.

51:10.340 --> 51:13.320
Ich kann auch sagen, C' gleich C plus A mal B.

51:13.320 --> 51:15.300
Dann muss ich erstmal das C berechnet haben.

51:15.740 --> 51:18.760
Ich brauche das A, ich brauche das B, um das C' zu berechnen.

51:20.160 --> 51:20.800
Und so weiter.

51:21.340 --> 51:25.280
Wir sehen gleich, was das für Datenabhängigkeiten sind.

51:25.800 --> 51:27.320
Das gibt mir auf jeden Fall eine...

51:28.500 --> 51:32.960
Diese Abhängigkeiten, sage ich, kann die eine Berechnung erst nach der

51:32.960 --> 51:33.580
anderen machen.

51:34.040 --> 51:35.520
Logische Abhängigkeiten dazwischen.

51:36.640 --> 51:40.400
Und dann transformiere ich diesen Graphen in einer geeigneten Art und

51:40.400 --> 51:40.780
Weise.

51:42.100 --> 51:47.220
Bilde einfach die einzelnen Berechnungen so auf ein Prozessorfeld ab,

51:47.640 --> 51:51.280
dass diese logischen Abhängigkeiten alle berücksichtigt sind.

51:52.380 --> 51:56.360
Und mache das halt so, dass ich die Unabhängigkeiten da alle ausnutze

51:56.360 --> 51:58.680
und dann eben Dinge parallel machen kann.

51:59.460 --> 52:05.800
Ich transformiere auf irgendein Prozessorfeld und mache dann ein

52:05.800 --> 52:06.820
sogenanntes Retiming.

52:06.820 --> 52:12.020
Also ich erzeuge zeitunterschiedlich taktet das Ganze so, dass ich

52:12.020 --> 52:13.920
dann ein Berechnungsverfahren ausbekomme.

52:14.300 --> 52:16.840
Und ich habe dann Prozessorfelder unterschiedlicher Struktur.

52:17.400 --> 52:20.760
Und Sie werden gleich sehen, man kann auf die Art und Weise die

52:20.760 --> 52:24.020
Prozessorfelder, die ich Ihnen gerade vorgestellt habe, diese drei

52:24.020 --> 52:28.580
verschiedenen, Kung Leiserson, dann dieses, wo ich keinen Namen für

52:28.580 --> 52:33.200
habe, das einfache zweidimensionale Feld und dann das von Kramer und

52:33.200 --> 52:38.020
von Leuven, diese drei, die kann ich Ihnen auf diese Art und Weise

52:38.020 --> 52:39.360
systematisch herleiten.

52:39.440 --> 52:43.600
Einfach durch lineare Transformation eines Datenabhängigkeitsgrades.

52:45.560 --> 52:47.940
Und dann kann ich auch viele andere daraus erzeugen.

52:48.300 --> 52:50.420
Das werden Sie auch feststellen, dass es ganz einfach geht.

52:50.760 --> 52:52.340
Man muss nur einmal sich überlegen, woran das liegt.

52:53.160 --> 52:56.440
Man kann sogar das so machen, dass hier nicht nur Prozessorfelder

52:56.440 --> 52:59.520
unterschiedlicher Struktur rauskommen, sondern dass dort Programme

52:59.520 --> 53:00.040
rauskommen.

53:00.040 --> 53:04.540
Dass dort ein Programm rauskommt zur Programmierung eines

53:04.540 --> 53:10.160
Parallelrechners, der genau nach Ihren Wünschen entsprechend den

53:10.160 --> 53:13.320
Datenabhängigkeiten eine Berechnung durchführt.

53:14.920 --> 53:18.600
Und es gibt halt unterschiedliche Sachen, die man hier machen kann.

53:18.680 --> 53:20.120
Das ist der sogenannte Mapping-Ansatz.

53:20.680 --> 53:26.840
Ich nutze also Linear Maps, deswegen Mapping-Ansatz, um solche

53:26.840 --> 53:28.020
Algorithmen zu erzeugen.

53:28.800 --> 53:33.280
Kann man für viele verschiedene Verfahren machen, die so auf die Art

53:33.280 --> 53:34.600
und Weise beschrieben werden können.

53:34.680 --> 53:38.120
Wenn Sie sich anschauen in technisch-wissenschaftlichen Anwendungen,

53:38.800 --> 53:43.900
haben Sie häufig numerische Berechnungen, also irgendwelche

53:43.900 --> 53:48.040
Berechnungen, wo Sie geschachtelte Schleifen haben mit einem einfachen

53:48.040 --> 53:48.800
Rumpf dort drin.

53:49.740 --> 53:54.480
Jede solche geschachtelte Schleife mit einem einfachen Rumpf, in dem

53:54.480 --> 53:57.860
ein paar Operationen drin vorkommen, können Sie auf die Art und Weise

53:57.860 --> 53:59.720
in einen parallelen Algorithmus transformieren.

54:00.720 --> 54:01.320
Systematisch.

54:01.620 --> 54:03.920
Das, was da rauskommt, ist garantiert korrekt.

54:04.140 --> 54:04.800
Kein Fehler drin.

54:06.020 --> 54:09.080
Das heißt, Sie haben dann eine Art, wie Sie automatisch programmieren

54:09.080 --> 54:09.400
können.

54:11.660 --> 54:15.000
Also, gehen wir das Matrix-Modifikationsproblem an.

54:16.900 --> 54:18.800
Wir wollen die cj berechnen.

54:19.340 --> 54:21.980
Iterative Lösung ist Schulmethode.

54:22.060 --> 54:23.440
Das ist das, was Sie kennen.

54:23.440 --> 54:27.220
Das ist das normale geschachtelte Programm.

54:27.500 --> 54:31.780
Hier jetzt hingeschrieben, cij gleich Null und dann cj gleich cj plus

54:31.780 --> 54:32.980
aik mal bkj.

54:34.220 --> 54:41.400
Das ist jetzt etwas anders als CECO oder JAVA, das ist jetzt hier

54:41.400 --> 54:43.240
einfach eine Pseudosprache.

54:44.420 --> 54:50.800
Und jetzt wandere ich das Ganze um in eine sogenannte Single

54:50.800 --> 54:51.620
Assignment Form.

54:51.620 --> 54:52.940
Was ist der Unterschied?

54:54.020 --> 54:58.780
Hier habe ich nicht Single Assignment, sondern dem cij weise ich

54:58.780 --> 55:02.260
nacheinander mehrfach unterschiedliche Werte zu.

55:03.620 --> 55:06.160
Jetzt mache ich daraus ein Single Assignment.

55:06.840 --> 55:12.600
Das heißt, jeder Variablen in dieser Berechnung wird genau einmal

55:12.600 --> 55:13.980
einen Wert zugewiesen.

55:14.900 --> 55:20.280
Dann muss ich mein cij mit einem weiteren Index versehen.

55:20.680 --> 55:22.760
Ein Index k in dem Fall.

55:23.760 --> 55:31.680
Und ich habe also dann ein cij Null bis cij N am Ende.

55:32.860 --> 55:33.960
Bei N% Matrix.

55:34.060 --> 55:37.520
Und das cij N ist dann mein cij, was ich eigentlich haben möchte.

55:37.640 --> 55:40.560
Und jedes cij k ist dann ein Zwischenergebnis.

55:43.700 --> 55:52.360
Jetzt weiß ich, um cij k zu berechnen, brauche ich cij k-1 und ich

55:52.360 --> 55:54.160
brauche aik und bkj.

55:56.540 --> 56:00.160
Jetzt schreibe ich das einfach so auf, dass ich bei jeder Variablen

56:00.160 --> 56:02.420
drei Indizes verwende.

56:04.460 --> 56:06.980
Einfach etwas verallgemeinert.

56:06.980 --> 56:12.160
Und auf die Art und Weise bekomme ich jetzt ein System lineare

56:12.160 --> 56:12.980
Rekurrenzgleichungen.

56:14.800 --> 56:16.760
Uniform, linear.

56:18.640 --> 56:26.740
Ich habe hier nämlich überall, also unabhängig von jedem Index, die

56:26.740 --> 56:28.480
gleichen Datenabhängigkeiten.

56:30.420 --> 56:34.460
Ich habe hier konstante Datenabhängigkeiten, wie Sie sehen.

56:35.040 --> 56:44.500
ikj, cikj hängt ab von cik-1j, das ist genau diese Abhängigkeit hier,

56:45.180 --> 56:50.380
plus aikj-1, ich will doch nur aik haben.

56:51.220 --> 56:55.220
Und bi-1kj, ich will doch eigentlich nur bkj haben.

56:55.220 --> 56:58.580
Das heißt, ich habe auch bei a und b noch einen weiteren Index dazu

56:58.580 --> 56:59.140
gefügt.

56:59.900 --> 57:09.960
Jetzt muss ich dafür sorgen, dass meine Elemente aij und bij, dass die

57:09.960 --> 57:11.440
richtig zugeordnet werden.

57:11.540 --> 57:13.460
Das heißt, ich mache jetzt noch eine weitere Abhängigkeit, das sieht

57:13.460 --> 57:14.920
etwas komplizierter aus.

57:14.920 --> 57:24.360
Das aikj, sage ich, ist aikj-1, und bikj gleich bi-1kj.

57:24.820 --> 57:33.000
Und das aik0 ist gerade das klein aik, und das b0kj ist das bkj.

57:34.300 --> 57:42.780
Und mein ci0j, da haben wir die Abhängigkeit k auf k-1, das ci0j wird

57:42.780 --> 57:43.400
gleich 0.

57:45.780 --> 57:50.460
Auf diese Art und Weise habe ich jetzt hier eine Reihe von

57:50.460 --> 57:51.680
Abhängigkeiten geschaffen.

57:52.680 --> 57:55.440
Und für jeden Index habe ich jetzt die gleichen Datenabhängigkeiten.

57:56.480 --> 58:07.160
ikj, der Index, hängt bei b ab von i-1kj, bei c ab von ik-1j und bei a

58:07.160 --> 58:09.200
ab von ikj-1.

58:10.620 --> 58:15.300
Und damit kann ich jetzt c ikj berechnen.

58:16.780 --> 58:21.480
Das heißt, die Daten, wenn ich die jetzt im Raum anordne, die Daten,

58:21.660 --> 58:25.560
die ich jeweils brauche, dann habe ich also hier ein Gitter, und hier

58:25.560 --> 58:28.760
sind die Datenabhängigkeiten zu sehen, grafisch angedeutet.

58:29.500 --> 58:33.100
Beziehungsweise, ich kann hier Vektoren aufschreiben.

58:34.180 --> 58:41.660
Bei c habe ich 0, 1, 0 als Abhängigkeitsvektor.

58:43.940 --> 58:49.860
Bei a habe ich 0, 0, 1 und bei b habe ich 1, 0, 0 als diesen Vektor.

58:51.240 --> 58:55.540
So, jetzt habe ich also hier, das sind genau diese Abhängigkeiten,

58:55.880 --> 59:02.180
muss bei dem Index diesen Vektor abziehen, um zu sehen, von wo ich ein

59:02.180 --> 59:02.860
Datum brauche.

59:03.620 --> 59:06.220
Und das Ganze kann ich jetzt, dieses Bild hier, kann ich jetzt ein

59:06.220 --> 59:11.280
bisschen größer machen, für n gleich 3, dann sehen Sie alle

59:11.280 --> 59:15.200
Berechnungen, die mit der Schulmethode, beziehungsweise mit diesem

59:15.200 --> 59:19.480
Rekurrenzgleichungssystem, was ich Ihnen aufgemalt habe, für n gleich

59:19.480 --> 59:23.840
3, sehen Sie alle Berechnungen, die ausgeführt werden müssen.

59:25.200 --> 59:28.200
Und für jede Berechnung sehen Sie, wovon die abhängen.

59:28.940 --> 59:36.140
Also hier, da hängt ab von dem Element, von dem Element und da geht

59:36.140 --> 59:37.800
praktisch ein Element direkt rein.

59:37.900 --> 59:41.000
Da wird praktisch ein b irgendwas initialisiert.

59:41.380 --> 59:42.820
Und dann wandert das hier entsprechend durch.

59:43.700 --> 59:47.260
Hier habe ich alle Berechnungen, die ausgeführt werden, mit den

59:47.260 --> 59:48.060
jeweiligen Abhängigkeiten.

59:48.860 --> 59:56.400
Das ist der Datenabhängigkeitsgraf, den ich erzeuge aus meinem System

59:56.400 --> 59:59.820
von uniformen, linearen Rekurrenzgleichungen.

01:00:02.680 --> 01:00:05.180
Das sind uniform, wie gesagt, die Abhängigkeiten sind überall

01:00:05.180 --> 01:00:05.720
identisch.

01:00:06.320 --> 01:00:09.420
Man kann sich auch nicht-uniforme Abhängigkeiten anschauen, dann haben

01:00:09.420 --> 01:00:12.500
Sie unterschiedliche Abhängigkeiten für unterschiedliche Indizes, die

01:00:12.500 --> 01:00:15.720
können also vom Index abhängen, das sind ein bisschen kompliziertere

01:00:15.720 --> 01:00:16.600
Berechnungen.

01:00:17.480 --> 01:00:20.180
Hier ist es ganz einfach, uniforme Abhängigkeiten.

01:00:21.260 --> 01:00:28.620
Und jetzt mache ich eine lineare Transformation dieser Abhängigkeiten.

01:00:30.040 --> 01:00:35.500
Ich ordne einfach jedem Index, ikj, eine Zeit und einen Ort zu.

01:00:38.260 --> 01:00:43.520
Diese Transformation, zum Beispiel Transformation T, auf diese Art und

01:00:43.520 --> 01:00:44.920
Weise hier angegeben.

01:00:45.760 --> 01:00:49.820
Die erste, das was hier oben steht, soll die Zeit mir angeben.

01:00:50.620 --> 01:00:53.260
Das wäre in dem Fall also einfach i plus k plus j.

01:00:54.280 --> 01:01:00.540
Wenn ich das also modifiziere mit ikj, wäre T mal ikj, wäre also, die

01:01:00.540 --> 01:01:02.420
Zeit wäre also i plus k plus j.

01:01:04.020 --> 01:01:10.760
Und der Ort wäre entsprechend, in dem Fall, wenn ich das modifiziere,

01:01:11.440 --> 01:01:15.060
gerade k und i minus j.

01:01:17.480 --> 01:01:22.240
Also das ist, gibt mir sofort die Anordnung.

01:01:23.160 --> 01:01:26.060
Und wenn Sie sich das genauer anschauen, was passiert, kommen Sie

01:01:26.060 --> 01:01:32.220
durch Multiplikation jedes Index hier drin, jedes ikj modifiziert mit

01:01:32.220 --> 01:01:38.080
dieser Matrix T, gibt Ihnen ein Berechnungsschema, dass diese

01:01:38.080 --> 01:01:41.800
einzelnen Berechnungen, die hier oben ausgeführt werden müssen, jetzt

01:01:41.800 --> 01:01:46.320
räumlich auf ein solches Feld angeordnet werden.

01:01:47.000 --> 01:01:49.720
Und die zeitliche Reihenfolge kommt hier aus dem oberen Index.

01:01:50.440 --> 01:01:54.660
Und Sie sehen eine Berechnung, bei der eine Matrix C hier eingegeben

01:01:54.660 --> 01:01:55.860
wird, in die Richtung läuft.

01:01:55.860 --> 01:02:00.360
Eine Matrix A von unten nach oben, eine Matrix B von oben nach unten.

01:02:01.320 --> 01:02:02.460
Das haben wir doch gerade vorher gesehen.

01:02:02.620 --> 01:02:03.720
Das war Cramon von Leuven.

01:02:04.740 --> 01:02:10.760
Das heißt, diese einfache Transformationsmatrix erzeugt uns aus einem

01:02:10.760 --> 01:02:15.000
System uniformer lineare Rekurrenzgleichungen genau das Verfahren von

01:02:15.000 --> 01:02:15.840
Cramon von Leuven.

01:02:18.680 --> 01:02:23.180
Wenn Sie die Werte anders wählen, kommen dort andere Verfahren raus.

01:02:24.360 --> 01:02:29.200
Sie können also durch Veränderung der Datenabhängigkeiten,

01:02:30.040 --> 01:02:38.300
beziehungsweise durch Multiplikation, dafür sorgen, dass auf einmal C

01:02:38.300 --> 01:02:44.540
sich nicht bewegt und nur A und B sich bewegen.

01:02:44.600 --> 01:02:46.860
Dann haben Sie das andere Verfahren, was ich Ihnen vorgestellt habe.

01:02:47.520 --> 01:02:49.220
Oder Sie können das noch anders machen.

01:02:50.120 --> 01:02:52.480
Es gibt also diese vielen verschiedenen Möglichkeiten.

01:02:53.780 --> 01:02:56.280
Erst kann man nicht beliebige Transformationen wählen.

01:02:57.720 --> 01:03:01.300
Das Ganze muss eine injektive Abbildung sein auf dem Indexbereich.

01:03:01.700 --> 01:03:15.220
Jede Berechnung muss, also die Kombination von Zeitpunkt und Ort, muss

01:03:15.220 --> 01:03:16.320
injektiv sein.

01:03:16.320 --> 01:03:22.060
Ich kann nicht zwei Berechnungen am gleichen Ort zur gleichen Zeit

01:03:22.060 --> 01:03:22.500
ausführen.

01:03:22.580 --> 01:03:23.160
Das geht nicht.

01:03:25.020 --> 01:03:27.880
Und die Datenabhängigkeiten müssen berücksichtigt werden.

01:03:29.080 --> 01:03:31.280
Und das kann man einfach so prüfen, dass man für jeden

01:03:31.280 --> 01:03:34.760
Datenabhängigkeitsvektor einfach ausrechnet, T mal D, und wenn das

01:03:34.760 --> 01:03:40.580
Größergleich 0 ist, dann ist das in Ordnung.

01:03:43.400 --> 01:03:45.060
Und wenn ich jetzt...

01:03:45.060 --> 01:03:48.120
Aha, da unten steht es schon, da sehen wir gleich das Werkzeug.

01:03:49.100 --> 01:03:52.240
Der Vorteil des Ganzen ist, ich kann auf diese Art und Weise also

01:03:52.240 --> 01:03:56.320
jetzt einfach korrektheitserhaltende Transformationen ausführen und

01:03:56.320 --> 01:03:57.580
Algorithmen erzeugen.

01:03:58.720 --> 01:04:02.880
Ich habe eine mathematische Formulierung meines Problems und erzeuge

01:04:02.880 --> 01:04:04.560
daraus viele verschiedene Algorithmen.

01:04:05.680 --> 01:04:09.320
Nachteil ist, dass ich ein linearisiertes Berechnungsschema habe.

01:04:11.640 --> 01:04:15.740
Ja, ich habe ja hier dieses linearisierte Berechnungsschema, diese

01:04:15.740 --> 01:04:20.200
Standardrumpf, C gleich C plus A mal B.

01:04:20.380 --> 01:04:25.440
Das ist dieser Rumpf des iterativen Algorithmus, der auch in der

01:04:25.440 --> 01:04:26.560
Rekurrenzgleichung drin ist.

01:04:27.040 --> 01:04:30.420
Damit habe ich eine inhärente Sequenzalität in meine Berechnungen.

01:04:31.300 --> 01:04:34.240
Da steckt sofort eine Datenabhängigkeit drin, die ich nicht mehr

01:04:34.240 --> 01:04:34.760
rauskriege.

01:04:35.460 --> 01:04:40.260
Das, was wir mit dem PRAM-Algorithmus gemacht haben, in Zeitlogin

01:04:40.260 --> 01:04:43.320
etwas zu berechnen, ein Skalarprodukt, das geht hierbei nicht.

01:04:43.980 --> 01:04:45.600
Das kann ich mit diesem Ansatz nicht hinbekommen.

01:04:45.700 --> 01:04:51.120
Ich kann nur Varianten hinbekommen von Berechnungen, die aber alle,

01:04:51.380 --> 01:04:57.060
die durch diese Formel gegebene lineare Abhängigkeit zwischen den

01:04:57.060 --> 01:05:00.100
einzelnen Berechnungsschritten berücksichtigen.

01:05:00.660 --> 01:05:03.240
Das heißt, die Möglichkeiten der Parallelverarbeitung sind nur

01:05:03.240 --> 01:05:04.260
eingeschränkt nutzbar.

01:05:05.140 --> 01:05:09.620
Und das Ganze ist natürlich nur anwendbar auf solche Schleifen.

01:05:11.220 --> 01:05:14.720
Es sind natürlich unsere Programme nicht nur eine solche Schleife, ich

01:05:14.720 --> 01:05:17.100
habe in der Regel noch eine Reihe anderer Berechnungen, aber ich kann

01:05:17.100 --> 01:05:20.120
auf die Art und Weise zumindest immer Teilstücke entsprechend

01:05:20.120 --> 01:05:21.200
parallelisieren.

01:05:21.560 --> 01:05:24.460
Und ich kann natürlich für Matrixmultiplikation, für verschiedenste

01:05:24.460 --> 01:05:28.140
Anwendungen, genau solche Sachen machen, aber das sind dann

01:05:28.140 --> 01:05:29.600
Komponenten in größeren Berechnungen.

01:05:30.780 --> 01:05:35.700
So, und jetzt habe ich Ihnen also nur einen ganz einfachen Einblick

01:05:35.700 --> 01:05:36.880
gegeben, was da passiert.

01:05:37.940 --> 01:05:40.440
Man kann dazu sehr viel mehr machen.

01:05:40.720 --> 01:05:46.760
Man kann inhomogene, also heterogene Berechnungen haben, man kann

01:05:46.760 --> 01:05:52.100
nicht -uniforme Grenzgleichungen sich angucken.

01:05:52.100 --> 01:05:56.360
Wenn Sie dazu mehr lesen wollen, schauen Sie sich das Buch von Ewa

01:05:56.360 --> 01:05:59.780
Zehntner an, über die Erzeugung systotischer Felder.

01:06:01.120 --> 01:06:05.820
Der hat die ganze Theorie dort dargestellt, sehr umfangreich.

01:06:06.600 --> 01:06:11.260
Und wenn Sie mit rumspielen wollen, dann gehen Sie einfach...

01:06:11.260 --> 01:06:12.640
Ja, jetzt muss ich aber...

01:06:12.640 --> 01:06:16.260
Erstmal muss ich doch einmal kurz hier auf...

01:06:20.260 --> 01:06:22.360
Nee, wie komme ich jetzt auf den Desktop?

01:06:25.560 --> 01:06:28.580
Ich wollte jetzt gehen auf das Ding...

01:06:28.580 --> 01:06:29.340
Was wollte ich denn jetzt?

01:06:29.420 --> 01:06:31.200
Ich wollte gerne...

01:06:32.760 --> 01:06:33.860
Das ist gar nicht so einfach.

01:06:35.740 --> 01:06:36.960
Jetzt gehe ich mal hier rauf.

01:06:37.300 --> 01:06:38.280
Dann komme ich da hin, genau.

01:06:38.280 --> 01:06:42.460
So, jetzt wollte ich hier...

01:06:42.460 --> 01:06:44.660
Ich muss mich verbinden mit dem Netz.

01:06:44.800 --> 01:06:45.860
Das habe ich nämlich nicht gemacht.

01:06:53.610 --> 01:06:54.950
Ich wollte mich mit dem Netz verbinden.

01:07:04.890 --> 01:07:05.370
Perfekt.

01:07:05.790 --> 01:07:10.070
Jetzt kann ich zurück in...

01:07:33.710 --> 01:07:34.630
Achso, war ich dumm.

01:07:36.570 --> 01:07:39.670
Auf die Art und Weise hat er mir gerade eben hier meine...

01:07:42.810 --> 01:07:44.430
meine Annotation zerschossen.

01:07:45.570 --> 01:07:46.830
War sehr ärgerlich.

01:07:47.370 --> 01:07:51.030
Ich weiß nicht, warum er das beendet hat und neu gestartet hat.

01:07:52.970 --> 01:07:54.470
Ein ärgerlicher Effekt.

01:07:55.570 --> 01:07:58.410
Und wir waren hier an dieser Stelle.

01:07:59.570 --> 01:08:01.950
Und ich wollte Ihnen gerade dieses Applet zeigen.

01:08:03.670 --> 01:08:06.390
Ich werde die Präsentation nicht beendet explizit.

01:08:07.310 --> 01:08:10.290
Normalerweise fragt er nach, ob er die Annotation speichern soll.

01:08:10.690 --> 01:08:11.930
Hat er das leider nicht gemacht.

01:08:12.070 --> 01:08:13.730
Aber Sie sind ja in der Aufzeichnung alle drin.

01:08:13.810 --> 01:08:15.570
Insofern können Sie da die Annotation sehen.

01:08:16.110 --> 01:08:18.510
Und jetzt kommen wir hier zu dem Applet.

01:08:19.490 --> 01:08:21.650
Dieses Applet ist etwas, was...

01:08:23.330 --> 01:08:24.690
Ja, ich möchte die ausführen.

01:08:24.790 --> 01:08:25.450
Was sagt er hier?

01:08:25.930 --> 01:08:27.650
Ich akzeptiere das Risiko.

01:08:28.110 --> 01:08:29.310
Ich möchte die Anwendung ausführen.

01:08:30.370 --> 01:08:33.630
Und nicht wieder für diese Anwendung anzeigen.

01:08:34.410 --> 01:08:34.850
Ausführen.

01:08:35.290 --> 01:08:37.430
Ich weiß auch, was ich tue, weil ich weiß, was das für ein Programm

01:08:37.430 --> 01:08:37.730
ist.

01:08:40.080 --> 01:08:42.160
Ich muss immer vorsichtig sein, dass ich nicht alle solche Fragen

01:08:42.160 --> 01:08:43.940
sofort mit Ja, Ja, Ja beantworte.

01:08:44.940 --> 01:08:46.120
So, was sehe ich hier?

01:08:46.160 --> 01:08:47.180
Ich sehe hier ein Applet.

01:08:47.360 --> 01:08:49.920
Das ist entstanden bei uns am Lehrstuhl vor einiger Zeit im Rahmen

01:08:49.920 --> 01:08:53.100
eines Projektes.

01:08:55.400 --> 01:08:56.320
Wissenschaftswerkstatt Rechensysteme.

01:08:56.940 --> 01:09:01.340
Da haben wir verschiedenste Anwendungen, E-Learning-Module entwickelt.

01:09:01.460 --> 01:09:07.300
Und hier ist also eine Animation eines solchen Programms, um

01:09:07.300 --> 01:09:09.300
unterschiedliche Dinge zu machen.

01:09:09.840 --> 01:09:14.800
Also solchen, diesen Mapping-Ansatz auszuführen.

01:09:14.980 --> 01:09:16.300
Jetzt muss ich hier...

01:09:17.740 --> 01:09:19.880
Ups, irgendwas stimmt jetzt hier nicht.

01:09:21.080 --> 01:09:23.140
Ich komme hier nicht auf das richtige Ding.

01:09:23.280 --> 01:09:24.300
Ich kann das hier...

01:09:24.960 --> 01:09:26.340
Das Ding ist nicht in Ordnung.

01:09:26.420 --> 01:09:28.880
Ich weiß zwar, dass ich gesagt habe, es soll ausgeführt werden, aber

01:09:28.880 --> 01:09:31.340
es ist hier ein komisches Fenster da.

01:09:31.500 --> 01:09:33.420
Ich weiß nicht, warum er dieses Fenster so klein gemacht hat.

01:09:37.290 --> 01:09:38.790
Muss mit der Auflösung zu tun haben.

01:09:39.550 --> 01:09:39.650
Ja.

01:09:40.530 --> 01:09:41.830
Tut mir leid, es geht jetzt nicht.

01:09:41.830 --> 01:09:46.370
Sie finden nämlich, hier habe ich jetzt nämlich, dummerweise, nur eine

01:09:46.370 --> 01:09:47.690
andere Anwendung.

01:09:47.790 --> 01:09:49.370
Das ist eine Anwendung für Sortieren.

01:09:50.870 --> 01:09:56.390
Und hier wird also gesagt, wie ich jetzt ein Sortierverfahren, wie ich

01:09:56.390 --> 01:09:59.210
das geeignet abbilde, hier sind die Datenabhängigkeiten für Sortieren

01:09:59.210 --> 01:09:59.770
angegeben.

01:10:00.390 --> 01:10:03.210
Und hier ist jetzt, das ist eine etwas andere Darstellung, da habe ich

01:10:03.210 --> 01:10:04.070
weniger Indizes.

01:10:04.490 --> 01:10:09.290
Und hier habe ich jetzt eine Möglichkeit, das entsprechend zuzuordnen.

01:10:09.990 --> 01:10:11.350
Ich kann hier Werte eingeben.

01:10:11.470 --> 01:10:12.990
Wenn ich hier, also jetzt mache ich das einfach mal hier.

01:10:13.210 --> 01:10:14.410
Ach, ich habe da eine Eins hin.

01:10:15.730 --> 01:10:19.610
Und meinetwegen hier auch eine Eins.

01:10:19.670 --> 01:10:20.530
Ich wende das an.

01:10:20.950 --> 01:10:24.370
Dann sehen Sie dort eine bestimmte Art, etwas zu berechnen.

01:10:24.450 --> 01:10:26.350
Kann auch sein, dass das Matrixvektor-Modifikation war.

01:10:26.530 --> 01:10:27.790
Ich glaube, das ist Matrixvektor-Modifikation.

01:10:28.010 --> 01:10:29.270
Nicht das Sortieren in dem Fall.

01:10:30.250 --> 01:10:33.070
Und dann habe ich also hier die Möglichkeit, kommt hier etwas raus,

01:10:33.150 --> 01:10:36.770
hätte ich hier eine Eins angegeben, hier oben, dann würde das Ganze

01:10:36.770 --> 01:10:37.630
anders aussehen.

01:10:38.210 --> 01:10:42.570
Dann hätte ich hier entsprechend ein lineares Feld, wo hier immer

01:10:42.570 --> 01:10:44.310
Werte eingegeben werden.

01:10:44.950 --> 01:10:48.250
Und da wird Maximum berechnet.

01:10:48.370 --> 01:10:51.990
Das ist doch für Sortieren, das Feld.

01:10:52.410 --> 01:10:54.630
Hier kann ich also unterschiedliche Sortierverfahren erzeugen.

01:10:56.310 --> 01:10:58.370
Also, tut mir leid, ich kann Ihnen das jetzt nicht richtig zeigen,

01:10:58.470 --> 01:10:59.810
weil die Auflösung hier nicht richtig stimmt.

01:11:00.110 --> 01:11:01.490
Das Feld ist anders da.

01:11:01.910 --> 01:11:05.610
Das ist halt vor etwa 10 Jahren entwickelt worden.

01:11:05.610 --> 01:11:06.970
Oder noch mehr.

01:11:07.590 --> 01:11:11.790
Und damals waren die Rechenart ein bisschen anders, die Darstellungen.

01:11:11.950 --> 01:11:14.830
Und jetzt hat er irgendwie das doch nicht richtig hier angepasst in

01:11:14.830 --> 01:11:15.510
der Darstellung.

01:11:16.270 --> 01:11:19.890
Das ist in einer anderen Auflösung besser zu sehen.

01:11:23.230 --> 01:11:24.670
Oder auch nicht okay.

01:11:25.370 --> 01:11:28.410
Ich wollte jetzt wieder zurück auf meine Präsentation.

01:11:29.110 --> 01:11:30.310
Schauen Sie sich das an.

01:11:30.530 --> 01:11:32.230
Dieses Applet ist dort verfügbar.

01:11:32.930 --> 01:11:35.450
Sie haben das da hinten gerade ausprobiert und da ist es vernünftig zu

01:11:35.450 --> 01:11:36.530
sehen in der richtigen Auflösung.

01:11:37.010 --> 01:11:38.030
Also spielen Sie damit rum.

01:11:38.890 --> 01:11:41.710
Da kann man also einfach verschiedene solche Matrizen angeben.

01:11:41.890 --> 01:11:45.550
Da ist genaue Anleitung dabei, was was bedeutet bei diesen Feldern auf

01:11:45.550 --> 01:11:46.430
diesem Applet.

01:11:46.910 --> 01:11:51.270
Und dann können Sie, wenn Sie damit rumspielen, unterschiedliche Arten

01:11:51.270 --> 01:11:54.090
von Matrix-Modifikationsverfahren auf solchen zweidimensionalen

01:11:54.090 --> 01:11:55.490
Feldern erzeugen.

01:11:56.070 --> 01:11:59.230
Und dann sehen Sie, wie also dieser Mapping-Ansatz funktioniert.

01:11:59.650 --> 01:12:03.230
Und wie gesagt, man kann das Ganze auch modifizieren, sodass da am

01:12:03.230 --> 01:12:07.270
Ende ein Programm rauskommt zur Programmierung eines zweidimensionalen

01:12:07.270 --> 01:12:07.850
Feldes.

01:12:09.170 --> 01:12:11.850
Wenn Sie ein solches Feld haben, hier bei uns auf dem Rechencluster,

01:12:12.410 --> 01:12:15.850
könnten Sie entsprechend dafür ein Programm erzeugen, sodass Sie auf

01:12:15.850 --> 01:12:18.370
so einem solchen Rechencluster entsprechend diesem Verfahren mit

01:12:18.370 --> 01:12:23.610
lokal, wahrscheinlich dann lokal-sequenziell-global-parallel dann

01:12:23.610 --> 01:12:26.390
entsprechend eine Matrix-Modifikation machen können.

01:12:26.950 --> 01:12:30.590
Sie brauchen nicht explizit sich zu überlegen, welcher muss welchem

01:12:30.590 --> 01:12:31.830
Prozessor eine Nachricht schicken.

01:12:32.350 --> 01:12:33.530
Das wird alles automatisch gemacht.

01:12:34.730 --> 01:12:37.110
Ich habe ein solches Programm nicht, um das automatisch zu machen,

01:12:37.250 --> 01:12:39.430
aber es kann hier einfach eingeschlossen werden.

01:12:39.790 --> 01:12:42.570
Eine Arbeitsgruppe in Dresden hat sich mit der Problematik

01:12:42.570 --> 01:12:43.170
beschäftigt.

01:12:43.590 --> 01:12:47.150
Die haben das sehr systematisch weitergearbeitet.

01:12:47.290 --> 01:12:50.870
So, das war jetzt zur Matrix-Modifikation erstmal genug.

01:12:52.050 --> 01:12:54.570
Da haben Sie einiges darüber gelernt, wie man Matrix modifizieren

01:12:54.570 --> 01:12:54.830
kann.

01:12:55.590 --> 01:12:59.870
Und jetzt kommen wir zu einem noch anderen Problem, algebraisches

01:12:59.870 --> 01:13:02.350
Problem, das man auch ganz häufig braucht.

01:13:03.210 --> 01:13:05.990
Also Matrix-Modifikation brauchen Sie in ganz, ganz vielen

01:13:05.990 --> 01:13:06.490
Anwendungen.

01:13:06.810 --> 01:13:09.210
Das ist eines der Standard-Benchmark-Probleme, wenn Sie

01:13:09.210 --> 01:13:11.830
Parallelrechner testen auf Leistungsfähigkeit.

01:13:12.430 --> 01:13:13.930
Wie schnell werden Matrixen modifiziert?

01:13:14.250 --> 01:13:15.850
Eine Bemerkung sollte ich übrigens noch machen.

01:13:16.590 --> 01:13:20.290
Man muss aufpassen, wie sieht das aus mit der numerischen Stabilität

01:13:20.290 --> 01:13:21.050
dieser Verfahren.

01:13:21.050 --> 01:13:28.730
Sie wissen, dass man bei Gleitpunkt-Operationen aufpassen muss, wie

01:13:28.730 --> 01:13:30.290
wir dort Fehlerfortpflanzungen haben.

01:13:31.190 --> 01:13:35.330
Und wenn Sie dann unterschiedliche Berechnungsschema da haben, haben

01:13:35.330 --> 01:13:37.050
Sie unterschiedliche Fehlerfortpflanzungen.

01:13:37.870 --> 01:13:40.930
Und da zeigt sich, dass Straßen etwas Nachteile haben.

01:13:41.590 --> 01:13:45.090
Da muss man genau aufpassen, wie man Straßen anwendet, dass man nicht

01:13:45.090 --> 01:13:48.330
in dieses Problem reinkommt, dass man dort schlechtere Genauigkeit

01:13:48.330 --> 01:13:52.490
kriegt, insofern man also jetzt das anwendet für lineare

01:13:52.490 --> 01:13:56.110
Gleichungssysteme lösen, da müssen Sie halt, da haben Sie Gleitpunkt

01:13:56.110 --> 01:13:58.850
-Operationen, und dann sind auf einmal die Fehlerfortpflanzungen,

01:13:58.950 --> 01:14:01.410
können Sie dort schlechte Ergebnisse kriegen.

01:14:01.990 --> 01:14:05.130
Es gibt aber Bibliotheken, die das alles vernünftig machen, und Sie

01:14:05.130 --> 01:14:07.870
können sich auch gerne das explizit programmieren, sodass das

01:14:07.870 --> 01:14:08.610
vernünftig wird.

01:14:09.950 --> 01:14:12.090
So, jetzt lassen wir das hinter uns.

01:14:12.210 --> 01:14:14.650
Matrix-Modifikationen gehen auf ein Problem, das wir auch schon

01:14:14.650 --> 01:14:24.230
kennengelernt haben, nämlich die Auswertung von Polynomen.

01:14:25.410 --> 01:14:29.870
Ich möchte also jetzt Polynome endengerades auswerten.

01:14:30.410 --> 01:14:33.030
Das war eines der ersten Beispiele, die ich gegeben hatte, da kamen

01:14:33.030 --> 01:14:35.150
wir dann auf verschiedene Möglichkeiten, das zu tun.

01:14:35.670 --> 01:14:39.290
Ich habe also eine Summe, i gleich 0 bis n a i x o i, zu berechnen.

01:14:40.290 --> 01:14:41.210
Wieder so eine Summe.

01:14:42.190 --> 01:14:43.850
Was sind hier die wesentlichen Parameter?

01:14:43.850 --> 01:14:48.110
Das sind die Koeffizienten a 0 bis a n und die Variable x.

01:14:48.370 --> 01:14:50.650
Wenn ich die kenne, kann ich das Polynom berechnen.

01:14:52.390 --> 01:14:55.410
Problemgröße ist n, Datenstruktur, wie stelle ich das dar?

01:14:55.490 --> 01:15:00.070
Naja, ich habe meine n plus 1 Koeffizienten und noch die Variable x,

01:15:00.410 --> 01:15:04.790
kann ich als einfaches eindimensionales Feld darstellen, oder wie Sie

01:15:04.790 --> 01:15:07.170
auch immer das machen wollen, das ist hier wirklich trivial, die

01:15:07.170 --> 01:15:07.710
Datenstruktur.

01:15:08.730 --> 01:15:11.510
Die Frage ist, wie viele arithmetische Operationen brauche ich?

01:15:11.510 --> 01:15:12.830
Das sieht man doch hier.

01:15:13.030 --> 01:15:14.150
Aber sieht man das wirklich so schnell?

01:15:15.090 --> 01:15:20.270
Ich habe eine Summe von n plus 1 Elementen, also n Additionen, das

01:15:20.270 --> 01:15:20.810
sieht man sofort.

01:15:21.510 --> 01:15:23.830
Und dann ist die Frage, wie viele Modifikationen brauche ich

01:15:23.830 --> 01:15:24.350
eigentlich?

01:15:24.790 --> 01:15:29.770
Jeweils a i mal x o i, also mindestens eine jeweils, Koeffizient mal

01:15:29.770 --> 01:15:30.710
Potenz von x.

01:15:31.370 --> 01:15:33.410
Oder habe ich die ganzen Potenzen von x zu berechnen?

01:15:34.190 --> 01:15:35.490
Also wie viele brauche ich denn da?

01:15:35.490 --> 01:15:37.850
Sie kennen das aus der Einleitung Horner Schema.

01:15:38.350 --> 01:15:41.830
Macht das mit n Multiplikationen und n Additionen.

01:15:42.290 --> 01:15:44.750
Und jetzt kommt ein Beispiel, wo das deutlich schneller geht.

01:15:45.350 --> 01:15:46.310
Spezielles Polynom.

01:15:47.450 --> 01:15:48.570
Koeffizienten sind alle 1.

01:15:52.880 --> 01:15:56.960
Und ich habe die Summe, die gleich 0 bis n x o i zu berechnen.

01:15:57.880 --> 01:16:01.840
Da greifen wir in unsere Trickkiste, unsere Kenntnisschatz der

01:16:01.840 --> 01:16:05.560
Mathematik, und wissen, das kann ich auf diese Art und Weise

01:16:05.560 --> 01:16:06.020
berechnen.

01:16:06.020 --> 01:16:09.900
Ich habe hier einen Ausdruck für den Wert einer Reihe.

01:16:10.180 --> 01:16:12.040
Sie erinnern sich, das haben wir gerade vorhin gemacht, bei der

01:16:12.040 --> 01:16:15.700
Abschätzung für Straßenkomplexität.

01:16:17.060 --> 01:16:18.840
Da haben wir ganz einfach diesen Ausdruck.

01:16:19.400 --> 01:16:25.720
Und in dem Ausdruck habe ich zwei Additionen, zweimal eine 1 zu

01:16:25.720 --> 01:16:26.280
subtrahieren.

01:16:27.240 --> 01:16:29.580
Ich muss eine Division machen.

01:16:31.980 --> 01:16:33.240
Eine Division.

01:16:36.660 --> 01:16:38.700
Und dann noch eine Potenzierung.

01:16:40.460 --> 01:16:41.900
Hier, x o n plus 1.

01:16:43.500 --> 01:16:46.840
Und potenzieren, x o n berechnen geht in, das wissen wir, in

01:16:46.840 --> 01:16:48.180
Größenordnung log n Schritten.

01:16:48.800 --> 01:16:50.100
Das ist also auch relativ einfach.

01:16:52.500 --> 01:16:54.060
Also sukzessive quadrieren.

01:16:54.620 --> 01:16:56.100
Dann habe ich log n.

01:16:57.380 --> 01:17:00.540
Mit log n Schritten habe ich die größte fordernde Potenz berechnet.

01:17:00.700 --> 01:17:02.360
Und dann muss ich die noch geeignet multiplizieren.

01:17:02.680 --> 01:17:03.400
Das ist also einfach.

01:17:04.380 --> 01:17:06.740
Zwei log n Multiplikationen, eine Division.

01:17:07.700 --> 01:17:10.220
Zwei einfache Additionen oder Subtraktionen, bzw.

01:17:10.460 --> 01:17:11.640
nur minus 1 jeweils gleich.

01:17:12.020 --> 01:17:12.860
Das ist ganz einfach.

01:17:13.900 --> 01:17:18.740
Und ich habe also deutlich weniger Additionen, als ich hier intuitiv

01:17:18.740 --> 01:17:21.860
gesagt habe, na klar brauchen wir hier n Additionen.

01:17:21.940 --> 01:17:26.900
Brauchen wir eben nicht, wenn wir wissen, wir kennen die Koeffizienten

01:17:27.720 --> 01:17:32.800
und können jetzt eine andere Berechnung dieses Polynoms vornehmen.

01:17:34.780 --> 01:17:39.060
Das heißt, der Aufwand, den ich habe, um ein solches Polynom

01:17:39.060 --> 01:17:42.580
auszuwerten, hängt natürlich davon ab, wie viel Information ich vorher

01:17:42.580 --> 01:17:43.360
ausnutzen kann.

01:17:46.150 --> 01:17:48.590
Also wenn ich die Koeffizienten kenne, kann ich mehr machen, als wenn

01:17:48.590 --> 01:17:49.290
ich sie nicht kenne.

01:17:49.850 --> 01:17:51.730
Nehmen wir zunächst mal an, dass wir die nicht kennen.

01:17:52.630 --> 01:17:54.690
Ja, wir nehmen jetzt mal an.

01:17:56.270 --> 01:17:58.850
Das wird jetzt hier mathematisch formuliert.

01:17:59.730 --> 01:18:00.690
Nicht abschrecken lassen.

01:18:01.590 --> 01:18:05.390
Mathematisch formuliert heißt das, ich betrachte einen Körper.

01:18:06.850 --> 01:18:12.030
Ein Körper ist im Prinzip eine Menge M mit Additionen und

01:18:12.030 --> 01:18:12.730
Multiplikationen.

01:18:13.830 --> 01:18:18.890
Und M ist sowohl bezüglich Additionen als auch Multiplikationen eine

01:18:18.890 --> 01:18:19.510
Gruppe.

01:18:21.170 --> 01:18:21.730
Kommutativ.

01:18:23.930 --> 01:18:27.830
Und die Subtraktion ist distributiv über der Summe.

01:18:29.810 --> 01:18:32.350
Beides, also auch Assoziativ und so weiter.

01:18:33.110 --> 01:18:37.490
Das heißt im Prinzip eigentlich nur, dass ich die vier arithmetischen

01:18:37.490 --> 01:18:38.830
Operationen ausführen kann.

01:18:40.050 --> 01:18:42.270
Ich habe eine Addition, ich habe eine Multiplikation, ich habe eine

01:18:42.270 --> 01:18:46.310
Subtraktion, das ist die Existenz eines Inversen, deswegen eine

01:18:46.310 --> 01:18:46.570
Gruppe.

01:18:47.560 --> 01:18:51.490
Und ich habe die Division.

01:18:52.070 --> 01:18:53.650
Inverse zu Multiplikation.

01:18:54.250 --> 01:18:55.470
Eine Sache ist noch wichtig.

01:18:55.650 --> 01:18:59.710
Natürlich ist, also ich sagte, M plus ist eine Gruppe.

01:19:01.190 --> 01:19:12.490
Und M minus 0, dem neutralen Element der Addition, ist eine Gruppe.

01:19:14.310 --> 01:19:18.810
Das neutrale Element der Addition, die 0, für die habe ich keinen

01:19:18.810 --> 01:19:19.330
Inversen.

01:19:20.470 --> 01:19:21.550
Deswegen muss das da raus.

01:19:22.090 --> 01:19:24.010
Also das ist korrekt formuliert.

01:19:25.430 --> 01:19:28.630
Das soll einfach nur sagen, wir haben alle vier arithmetischen

01:19:28.630 --> 01:19:29.490
Operationen zur Verfügung.

01:19:30.550 --> 01:19:33.790
Und A0 bis AN und X sind transzendent über F.

01:19:35.030 --> 01:19:37.690
Das ist wichtig, wenn ich Körpererweiterungen betrachte und ähnliche

01:19:37.690 --> 01:19:38.010
Dinge.

01:19:38.010 --> 01:19:42.230
Das hat was zu tun mit theorieendlicher Körper, Körpererweiterungen

01:19:42.230 --> 01:19:42.870
und ähnliche Dinge.

01:19:43.370 --> 01:19:47.450
Wenn die transzendent sind, über diesen Körper F, heißt das, ich habe

01:19:47.450 --> 01:19:52.710
keine Informationen über irgendwelche Werte von A0 bis AN.

01:19:54.030 --> 01:19:56.810
Also ich weiß, das sind keine Elemente von M, das sind irgendwelche

01:19:56.810 --> 01:19:57.490
Unbekannten.

01:19:58.770 --> 01:20:02.310
Ich muss also diese ganzen Berechnungen machen, sie sind also nicht

01:20:02.310 --> 01:20:03.390
anders darstellbar.

01:20:05.170 --> 01:20:09.450
Ich kann nicht einen Komponenten durch einen anderen ausdrücken, das

01:20:09.450 --> 01:20:09.890
geht nicht.

01:20:10.950 --> 01:20:14.250
Und deswegen heißt das nur, ich habe keine zusätzlichen Informationen

01:20:14.250 --> 01:20:20.490
und alle diese Werte hier sind völlig, vollständig unabhängig

01:20:20.490 --> 01:20:21.150
voneinander.

01:20:21.770 --> 01:20:22.690
Keine weitere Informationen.

01:20:23.670 --> 01:20:26.770
Ich kann also nichts ausnutzen über irgendwelche Abhängigkeiten

01:20:26.770 --> 01:20:30.710
zwischen diesen Elementen beziehungsweise ich kann keinen durch einen

01:20:30.710 --> 01:20:32.970
Ausdruck aus anderen irgendwie darstellen.

01:20:33.450 --> 01:20:38.270
Wenn die Wurzeln eines oder Nullstellen eines Polynoms über F wären,

01:20:38.750 --> 01:20:40.290
könnte ich einen durch einen anderen ausdrücken.

01:20:41.430 --> 01:20:42.710
Diese Abhängigkeiten habe ich nicht.

01:20:43.350 --> 01:20:47.510
Also das hier oben ist einfach nur eine mathematische Formulierung für

01:20:47.510 --> 01:20:50.410
das, was hier steht, ich habe keine Informationen, wir sind unabhängig

01:20:50.410 --> 01:20:50.810
voneinander.

01:20:51.650 --> 01:20:54.890
Das muss man einfach nur sich überlegen und das kann man mathematisch

01:20:54.890 --> 01:20:55.690
so formulieren.

01:20:55.690 --> 01:20:58.830
Ich weiß nicht, ob Sie Algebra-Vorlesungen gehört haben,

01:20:58.990 --> 01:21:01.030
Endlichtheorie endlicher Körper und ähnliche Dinge.

01:21:01.350 --> 01:21:02.770
Da wird das alles intensiv gemacht.

01:21:02.950 --> 01:21:08.790
Da hat man die Galois-Theorie.

01:21:09.910 --> 01:21:11.270
Wir werden Galois-Felder betrachtet.

01:21:11.370 --> 01:21:12.770
Galois-Felder sind endliche Körper.

01:21:14.010 --> 01:21:17.830
Und das ist eine ganz wichtige Theorie endlicher Körper, die braucht

01:21:17.830 --> 01:21:18.690
man in der Kryptographie.

01:21:19.590 --> 01:21:29.230
Wenn Sie sich die Verfahren angucken, zum Beispiel das AIS, das

01:21:29.230 --> 01:21:33.790
Rheindahl -Verfahren, da wird ganz viel Operation in endlichen Körpern

01:21:33.790 --> 01:21:34.390
genutzt.

01:21:34.850 --> 01:21:37.110
Polynomerweiterung, Körpererweiterung und so weiter.

01:21:38.610 --> 01:21:42.490
Aber Sie brauchen keine Angst zu haben, wir gehen nicht tiefer in

01:21:42.490 --> 01:21:43.790
diese mathematischen Dinge rein.

01:21:44.610 --> 01:21:48.650
Ich zeige Ihnen nur, wie man hier mathematische Erkenntnisse nutzt, um

01:21:48.650 --> 01:21:51.490
die Dinge herauszukriegen, die wir uns eigentlich interessieren.

01:21:52.810 --> 01:21:57.870
Und jetzt sage ich also, wir betrachten jetzt solche allgemeinen

01:21:57.870 --> 01:22:01.870
Polynome, bei denen ich nichts weiß über die Elemente.

01:22:02.670 --> 01:22:09.110
Und dann ist nämlich dieses Element, Summe AIXOI, ein Element von F,

01:22:11.130 --> 01:22:18.630
X, A0 bis AN in runden Klammern, heißt, dass es eine transzendente

01:22:18.630 --> 01:22:27.270
Körpererweiterung von Körper F durch diese X, A0 bis AN.

01:22:29.030 --> 01:22:33.510
Das heißt, ich kann hier addieren, multiplizieren, subtrahieren,

01:22:33.630 --> 01:22:34.270
dividieren.

01:22:34.270 --> 01:22:37.950
Ich kann also hier irgendwelche Terme durcheinander dividieren.

01:22:38.770 --> 01:22:40.950
Das ist das, was ich hier sage.

01:22:41.110 --> 01:22:42.770
Das sind Elemente in diesem Körper.

01:22:43.230 --> 01:22:44.990
Da können irgendwelche Ausdrücke dann vorkommen.

01:22:45.190 --> 01:22:48.910
Und ich kann hier addieren, multiplizieren, subtrahieren, dividieren.

01:22:50.190 --> 01:22:53.570
Eine mehrfache transzendente Körpererweiterung von F.

01:22:54.830 --> 01:22:58.950
Was das genau ist, sehen Sie, wenn Sie Mathematikkenntnisse ein

01:22:58.950 --> 01:23:00.870
bisschen mehr haben oder wenn Sie ein Buch über Algebra nachgucken

01:23:00.870 --> 01:23:02.590
oder ein Buch über Galois-Theorie.

01:23:04.810 --> 01:23:09.170
Und wenn Sie das nicht machen wollen, merken Sie sich einfach nur, ich

01:23:09.170 --> 01:23:12.950
darf hier beliebig die Operationen Addition, Multiplikation, Division

01:23:12.950 --> 01:23:16.870
und Subtraktion anwenden.

01:23:16.950 --> 01:23:17.870
Alle vier Operationen.

01:23:18.670 --> 01:23:21.350
Und jetzt möchte ich das Ganze auswerten.

01:23:22.170 --> 01:23:23.690
Also ausrechnen.

01:23:23.690 --> 01:23:28.110
Und die Auswertung des allgemeinen Polynoms Endengradus über F ist

01:23:28.110 --> 01:23:33.050
also gerade die Konstruktion dieses Elements innerhalb dieses Körpers.

01:23:33.310 --> 01:23:34.790
Ich muss das ausrechnen.

01:23:34.990 --> 01:23:36.930
Ausgehend von irgendeiner Grundmenge.

01:23:38.830 --> 01:23:41.930
Es kommt wieder, in diese Grundmenge kann ich Anfangswissen

01:23:41.930 --> 01:23:42.510
reinstecken.

01:23:43.770 --> 01:23:48.150
Je mehr Anfangswissen ich reinstecke, desto weniger muss ich noch

01:23:48.150 --> 01:23:48.650
berechnen.

01:23:48.650 --> 01:23:50.370
Jetzt zeige ich Ihnen gleich ein Beispiel.

01:23:50.890 --> 01:23:52.610
Dann ist die heutige Vorlesung auch um.

01:23:54.210 --> 01:23:54.690
Also.

01:23:55.790 --> 01:23:57.830
Zunächst mal, welche Körper nehmen wir hier?

01:23:58.910 --> 01:24:01.530
Das können also die rationalen Zahlen sein, die reellen Zahlen.

01:24:01.930 --> 01:24:06.630
Oder irgendwelche endlichen Körper, wie Galois-Feld über zwei

01:24:06.630 --> 01:24:09.570
Elementen, über 2 hoch 8 Elementen.

01:24:09.630 --> 01:24:12.010
Das wären so Galois-Feld über Bytes im Prinzip.

01:24:14.470 --> 01:24:19.010
Da können Sie also solche Galois-Felder betrachten.

01:24:19.770 --> 01:24:24.030
Sie können also den Bytes multiplizieren, addieren, subtrahieren,

01:24:24.130 --> 01:24:24.650
dividieren.

01:24:25.330 --> 01:24:27.010
Haben entsprechende Operationsverfügung.

01:24:31.530 --> 01:24:35.050
Und jetzt Beispiele für diese Berechnung.

01:24:35.290 --> 01:24:36.090
Was heißt das?

01:24:36.090 --> 01:24:42.350
Wenn meine Grundmenge B, ich kann also Elemente aus dieser Menge

01:24:42.350 --> 01:24:44.490
nehmen, um diese Summe zu berechnen.

01:24:45.030 --> 01:24:49.150
Wenn das bereits mein ganzer Bereich ist, diese körperliche

01:24:49.150 --> 01:24:49.930
Erweiterung.

01:24:50.050 --> 01:24:55.410
Dann ist ja ein Element da drin bereits diese Summe AIXI.

01:24:56.330 --> 01:24:58.430
Dann brauche ich gar nichts zu berechnen.

01:24:59.650 --> 01:25:03.930
Wenn ich als Grundmenge habe, jede Skala, also jede reelle Zahl oder

01:25:03.930 --> 01:25:04.870
rationale Zahl.

01:25:05.730 --> 01:25:09.270
Und ich habe diese Elemente zur Verfügung.

01:25:10.690 --> 01:25:13.110
Dann kann ich das so berechnen, wie es hier steht.

01:25:14.750 --> 01:25:17.350
Dann ist das ANXON plus und so weiter.

01:25:17.530 --> 01:25:19.270
Das haben wir ganz zu Anfang mal gemacht.

01:25:19.910 --> 01:25:23.870
Wenn ich das von links nach rechts auswerte, muss ich AN mal X mal X

01:25:23.870 --> 01:25:25.050
mal X und so weiter rechnen.

01:25:25.390 --> 01:25:28.350
Kommen, wie zu Anfang auch schon mal gesagt, auf O von N²

01:25:28.350 --> 01:25:29.650
arithmetische Operationen.

01:25:29.650 --> 01:25:34.530
Wenn ich das anders ausrechne, wenn ich zunächst mal alle Potenzen

01:25:34.530 --> 01:25:37.650
ausrechne, komme ich auf N-1 Multiplikationen.

01:25:38.510 --> 01:25:42.490
Ich muss ja nur X, X² und so weiter sukzessive alle Potenzen bis X um

01:25:42.490 --> 01:25:43.170
N berechnen.

01:25:43.910 --> 01:25:46.710
Anschließend die modifizieren mit den entsprechenden Koeffizienten.

01:25:48.190 --> 01:25:49.930
Und anschließend die Summe ausrechnen.

01:25:50.910 --> 01:25:53.270
Das wären drei N-1 arithmetische Operationen.

01:25:53.350 --> 01:25:55.210
Also einfach ein bisschen anders organisiert.

01:25:57.410 --> 01:25:59.350
Ja, so habe ich so viele Operationen.

01:25:59.470 --> 01:26:04.870
Und jetzt sage ich, ich habe hier meinetwegen als Grundmenge F von X

01:26:04.870 --> 01:26:05.210
Erweiterung.

01:26:05.890 --> 01:26:07.930
Also, was ist das?

01:26:08.150 --> 01:26:12.090
Da kann ich also alles verwenden, was durch Addition, Modifikation,

01:26:12.990 --> 01:26:18.430
Subtraktion, Division mit X und irgendwelchen Skalaren entsteht.

01:26:19.590 --> 01:26:23.150
Dann heißt das, dass dieser Schritt hier kostenlos ist.

01:26:23.830 --> 01:26:26.270
Alle Potenzen von X stehen im Prinzip zur Verfügung.

01:26:27.370 --> 01:26:29.250
Ich muss nur sehen, was mache ich dann damit weiter.

01:26:29.870 --> 01:26:32.090
Dann habe ich also nur noch diese Operation hier auszuführen.

01:26:32.870 --> 01:26:34.810
Und wenn ich ein bisschen schlauer bin, dann nehme ich das Horner

01:26:34.810 --> 01:26:38.250
Schema und habe also hier dieses einfache Programm.

01:26:39.030 --> 01:26:41.810
Wir hatten das auch als geradliniges Programm uns mal angeschaut.

01:26:42.190 --> 01:26:44.490
Und dann komme ich auf meine N-Addition und N-Modifikation.

01:26:46.150 --> 01:26:49.750
Damit wollte ich jetzt nur zeigen, wenn ich also Aussagen mache

01:26:49.750 --> 01:26:52.710
darüber, wie viel Aufwand muss ich treiben, um irgendetwas

01:26:52.710 --> 01:26:57.290
auszurechnen, dann muss ich wissen, was kann ich als Ausgangspunkt

01:26:57.290 --> 01:27:00.670
verwenden, welche Informationen habe ich zur Verfügung und wie kann

01:27:00.670 --> 01:27:04.370
ich die geeignet kombinieren, um daraus die Werte am Ende zu

01:27:04.370 --> 01:27:04.830
berechnen.

01:27:05.930 --> 01:27:12.250
Und Sie sehen also, diese beiden Ansätze hier gehen von der gleichen

01:27:12.250 --> 01:27:14.990
Grundmenge aus, aber unterschiedlich intelligent eingesetzt.

01:27:16.170 --> 01:27:19.270
Und dieses hier ist noch intelligenter, das Ganze eingesetzt.

01:27:19.710 --> 01:27:22.330
Auch die gleiche Grundmenge.

01:27:23.790 --> 01:27:26.950
Und wenn ich eben mehr zur Verfügung habe, wenn die Potenzen bereits

01:27:26.950 --> 01:27:31.350
da sind, dann kann ich das auch mit zwei anatometischen Operationen

01:27:31.350 --> 01:27:34.430
machen, aber es bringt mir nichts, weil ich das ohne Annahme, dass

01:27:34.430 --> 01:27:36.270
Potenzen schon da sind, auch in der Zeit habe.

01:27:37.390 --> 01:27:38.950
Also das zu diesen Berechnungen.

01:27:39.130 --> 01:27:43.630
Wir werden uns nächstes Mal dann unsere Schranken angucken und werden

01:27:43.630 --> 01:27:48.230
sehen, das Horner Schema ist für die Auswertung eines allgemeinen

01:27:48.230 --> 01:27:52.450
Polynoms Endengrades tatsächlich ein optimales Verfahren.

01:27:52.590 --> 01:27:56.210
Es geht nicht mit weniger als N-Addition, es geht nicht mit weniger

01:27:56.210 --> 01:27:57.190
als N-Multiplikation.

01:27:58.730 --> 01:28:03.270
Das also zu dem, was nächste Woche kommt und das war es für heute.

01:28:03.410 --> 01:28:03.770
Vielen Dank.