WEBVTT NOTE PGD034 – automatic transcript (Whisper large-v3, wav2vec2 alignment, Sortformer + speaker embeddings). Generated by tools/transcribe/pi3tx.py, may contain errors. 00:00:00.641 --> 00:00:03.868 Gut, herzlich willkommen, liebe Zuhörerinnen und Zuhörer, 00:00:03.868 --> 00:00:07.145 zur Nummer 34 von Pi ist genau 3. 00:00:07.576 --> 00:00:09.049 Mit mir ist heute 00:00:09.320 --> 00:00:11.514 … Thomas Kahle, ganz neu hier am Start. 00:00:11.514 --> 00:00:12.482 Nee, wie immer. 00:00:12.482 --> 00:00:14.349 Total überraschend. Nein, wie immer. 00:00:14.349 --> 00:00:17.410 Genau, Thomas Kahle am anderen Ende und ich bin Petra Schwer. 00:00:17.549 --> 00:00:20.935 Hallo, Petra. Hi, Thomas. Wie immer, habe ich keine Ahnung, worum es geht. 00:00:20.935 --> 00:00:22.183 Du bist vorbereitet heute. 00:00:22.183 --> 00:00:25.390 Genau. Hast du schon mal den Film Die Matrix gesehen, The Matrix? 00:00:27.106 --> 00:00:28.908 Ja, ist aber Jahre her. 00:00:28.923 --> 00:00:31.762 Bei mir auch, bei mir auch. Erinnerst du dich noch an irgendwas von dem Film? 00:00:32.195 --> 00:00:33.669 Also Keanu Reeves später? 00:00:33.904 --> 00:00:35.452 Ja genau, an die schwarzen und grünen Nullen, 00:00:35.452 --> 00:00:36.417 die im Hintergrund immer so vorbeifahren. 00:00:36.417 --> 00:00:40.510 Aber wenn man jetzt mal mathematisch denkt, was fällt einem auf an dem Film? 00:00:41.642 --> 00:00:45.890 Mathematisch, ehrlich gesagt, ich habe so ein irre schlechtes Filmgedächtnis. 00:00:46.643 --> 00:00:48.930 Was würdest du denn bei dem Titel erwarten? 00:00:50.561 --> 00:00:54.732 Also, er kommt in dem Film nicht aufs Matrizen. 00:00:54.732 --> 00:00:54.972 Nee, 00:00:54.972 --> 00:00:57.849 es kommt keine Matrix vor. 00:00:57.921 --> 00:01:00.876 Genau. Nee, ich will heute über Matrizen mit dir reden. 00:01:01.107 --> 00:01:01.798 Und zwar 00:01:02.871 --> 00:01:05.606 insbesondere über wie man Matrizen multipliziert. 00:01:05.797 --> 00:01:07.710 Hast du schon mal Matrizen multipliziert? 00:01:07.942 --> 00:01:10.090 Ich habe schon mal Matrizen multipliziert. 00:01:10.182 --> 00:01:11.387 Wissen eigentlich alle, was eine Matrix ist? 00:01:11.387 --> 00:01:13.576 Können wir das einfach so, können wir das annehmen, dass alle wissen, 00:01:13.576 --> 00:01:15.467 was eine Matrix ist? Was ist eine Matrix? 00:01:15.467 --> 00:01:17.013 Das ist wieder so eine philosophische Frage. 00:01:17.013 --> 00:01:18.830 Wir machen ja auch philosophische Fragen. 00:01:19.533 --> 00:01:20.150 Ja. 00:01:20.347 --> 00:01:21.770 Was ist eigentlich eine Matrix? 00:01:22.002 --> 00:01:23.853 Ich beantworte die jetzt mal ganz profan. 00:01:23.853 --> 00:01:26.493 Das ist so ein Grid. Ein Grid? 00:01:26.493 --> 00:01:27.195 Ein Raster. 00:01:27.884 --> 00:01:30.888 Ein Raster, ja. Angeordneter Skalare. 00:01:30.888 --> 00:01:32.854 Also es gibt irgendwie wie eine Tabelle. 00:01:32.854 --> 00:01:39.489 Es gibt Zeilen und Spalten. Sagen wir mal N Zeilen und M Spalten. 00:01:39.489 --> 00:01:40.882 Und in jeder 00:01:42.235 --> 00:01:46.550 Zeilen-Spalten-Kombination an jedem Tabelleneintrag steht ein Skalar. 00:01:46.662 --> 00:01:48.478 Damit meinst du eine Zahl? Wenn Petra das kapiert hat. 00:01:48.478 --> 00:01:50.850 Eine Zahl. Fancy Language für Zahlen. 00:01:50.850 --> 00:01:51.900 Also Petra nennt Zahlen Skalare. 00:01:51.900 --> 00:01:53.703 Ich nenne die Skalare, weil die aus der Affen kommen. 00:01:53.703 --> 00:01:56.583 Weil sie im Kontext der linearen Algebra ist. 00:01:56.583 --> 00:01:58.310 Genau, also so eine Tabelle von Zahlen. 00:01:58.310 --> 00:02:00.930 Eine rechteckige Tabelle von Zahlen. 00:02:00.951 --> 00:02:01.301 Ja, genau. 00:02:01.301 --> 00:02:04.189 Und wenn die quadratisch sind, dann kann man die irgendwie multiplizieren. 00:02:04.189 --> 00:02:08.190 Also so eine Tabelle mal eine Tabelle ergibt eine andere Tabelle. 00:02:08.343 --> 00:02:10.668 Ja, die müssen nicht quadratisch sein zum Multiplizieren. 00:02:10.801 --> 00:02:14.545 Ja, aber dann, ich habe nur eine Implikation gesagt. 00:02:14.545 --> 00:02:16.567 Wenn die quadratisch sind vom gleichen Format, 00:02:16.567 --> 00:02:17.818 das habe ich auch nicht richtig gesagt. 00:02:18.029 --> 00:02:21.843 Also wenn die quadratisch sind vom gleichen Format, zum Beispiel 2 x 2. 00:02:22.253 --> 00:02:24.816 Also die einfachste Matrix ist vielleicht eine 1 x 1. 00:02:24.816 --> 00:02:26.758 Wir nennen das immer diese mit Kreuz. 00:02:26.758 --> 00:02:28.590 Ich sage das immer mit Kreuz. Sagst du das auch so? 00:02:28.769 --> 00:02:29.439 Ja. 1 x 1. 00:02:29.440 --> 00:02:32.302 Oder 1 x 1. Ja, genau. Also sagt man irgendwie so. 00:02:32.302 --> 00:02:32.905 Aber das bedeutet, 00:02:32.905 --> 00:02:36.510 wenn wir 2 x 2 sagen, dann meinen wir halt so zwei Zeilen, zwei Spalten. 00:02:36.831 --> 00:02:37.462 Genau. 00:02:37.462 --> 00:02:41.804 Und wenn du eine 2 x 2 Matrix mit einer 2 x 2 Matrix multiplizierst, 00:02:42.095 --> 00:02:44.140 also kommt wieder eine 2 x 2 Matrix raus. 00:02:45.862 --> 00:02:50.730 Und ich will heute über die Komplexität von diesem Problem sprechen. 00:02:51.202 --> 00:02:52.681 Von Matrizen multiplizieren, genau. 00:02:53.481 --> 00:02:54.723 Okay. 00:02:54.723 --> 00:02:57.329 Aber Komplexität im Computersinne, 00:02:57.329 --> 00:03:02.820 also im Informatik-Sinne von Komplexitätstheorie oder profane …? 00:03:02.820 --> 00:03:03.904 Hm, schon. Okay, schon. Okay. 00:03:03.904 --> 00:03:07.270 Was gibt es denn noch, die Komplexität? 00:03:07.662 --> 00:03:11.890 Keine Ahnung. Also es gibt ja noch den allgemeinen Sprachgebrauch des Wortes 00:03:11.890 --> 00:03:16.421 Komplex oder Komplexität im linguistischen Sinne, im Sinne von Schwierigkeit. 00:03:16.421 --> 00:03:16.921 Hm. 00:03:19.200 --> 00:03:21.353 Naja, also hat man damit Schwierigkeiten? 00:03:21.403 --> 00:03:24.827 Hast du, was für Schwierigkeiten hat man denn mit der Matrixmultiplikation? 00:03:24.827 --> 00:03:27.650 Man muss irgendwie verstehen, dass es das, die nicht-kommutativ ist. 00:03:27.650 --> 00:03:31.665 Ist es vielleicht die erste nicht-kommutative Multiplikation, die man sieht? 00:03:32.016 --> 00:03:35.990 Wenn man die Matrizen A und B heißt, ist A mal B im Allgemeinen nicht B mal A. 00:03:36.364 --> 00:03:39.288 Ja, aber ich glaube, Funktionsverkettung sieht man vorher, ne? 00:03:39.641 --> 00:03:40.718 Mhm. 00:03:41.395 --> 00:03:41.677 Genau. 00:03:41.677 --> 00:03:46.150 Ist auch, äh… Also es ist eigentlich dasselbe, ja, Problem sozusagen. 00:03:46.644 --> 00:03:47.890 Auf gewisse Weise. 00:03:48.201 --> 00:03:49.813 So diese Matrizen übrigens, also, 00:03:50.023 --> 00:03:53.477 ähm, ja, ich hab mal versucht so zu googeln, was die Geschichte von Matrizen ist. 00:03:53.688 --> 00:03:55.390 Kommt man natürlich auf die Geschichte der linearen Algebra, 00:03:55.390 --> 00:03:57.843 aber es gibt irgendwie auch schon so Zahlen, so, so… 00:03:58.334 --> 00:04:00.987 Lineare Gleichungen sind ja irgendwie viel älter noch als 00:04:02.119 --> 00:04:03.390 lineare Algebra. 00:04:03.461 --> 00:04:05.125 Und da gibt's schon so alte chinesische Texte, 00:04:05.125 --> 00:04:07.600 wo so Zahlen, Tabellen irgendwie waren. 00:04:07.630 --> 00:04:09.635 Also wo man, naja, ist eigentlich eine natürliche Idee, 00:04:09.635 --> 00:04:11.869 wenn man lineare Gleichungen irgendwie… 00:04:12.421 --> 00:04:13.472 Weiß nicht genau, wie es… 00:04:13.743 --> 00:04:15.947 Naja, mit alter chinesischer Mathematik kenn ich mich nicht so aus. 00:04:15.947 --> 00:04:17.540 Das muss ich nochmal recherchieren. 00:04:17.771 --> 00:04:22.670 Aber das Matrix-Produkt taucht irgendwie 1812 in der Veröffentlichung auf. 00:04:23.429 --> 00:04:27.883 Wer hat das? Hat man jetzt gar nicht aufgeschrieben, wer das war. 00:04:28.054 --> 00:04:29.830 Irgendjemand, den man nicht so kannte. 00:04:29.943 --> 00:04:31.407 Ich meine, Kramer kennt man ja. 00:04:31.407 --> 00:04:35.370 Also so Kramersche Regel oder so, die für die Expertinnen und Experten. 00:04:35.423 --> 00:04:37.779 Das war noch früher, das war 1750. 00:04:37.851 --> 00:04:40.970 Also Determinanten, in der Kramerschen Regel kommen irgendwie Determinanten vor. 00:04:41.125 --> 00:04:43.750 Die gab es schon nochmal 60 Jahre vorher. 00:04:44.123 --> 00:04:46.192 Also die Determinanten und die Kramersche Regel? 00:04:46.192 --> 00:04:47.638 Oder ich weiß gar nicht, von wann ist die denn? 00:04:47.638 --> 00:04:48.882 Die Kramersche Regel 1750. 00:04:50.361 --> 00:04:56.330 Und Matrixmultiplikation habe ich mir gerade 1812 aufgeschrieben. 00:04:56.722 --> 00:04:59.833 Hast du aufgeschrieben, in welchem Kontext es da aufgetaucht ist? 00:04:59.833 --> 00:05:01.720 Also waren da Matrizen schon? 00:05:01.720 --> 00:05:02.623 Hintereinanderausführung. 00:05:02.623 --> 00:05:06.654 Also dieses 1812, das war Hintereinanderausführung von linearen Abbildungen, 00:05:06.654 --> 00:05:08.729 die als Matrizen gegeben sind. 00:05:09.143 --> 00:05:13.110 Doch das ist in dem Kontext, in dem man das jetzt so kennenlernt. 00:05:13.441 --> 00:05:13.762 Genau. 00:05:13.762 --> 00:05:15.928 So würde man es ja auch einführen jetzt oder motivieren, 00:05:15.928 --> 00:05:18.234 warum man es so definiert, die Matrixmultiplikation. 00:05:18.234 --> 00:05:19.905 Sind wir schon mitten im Fach Chinesisch. 00:05:19.905 --> 00:05:20.734 Ja, das war jetzt schon ganz schön fachchinesisch. 00:05:20.734 --> 00:05:21.162 Also für alle, 00:05:21.162 --> 00:05:24.944 die jetzt jemals lineare Algebra gehört haben, wissen, wovon ich geredet habe. 00:05:25.698 --> 00:05:26.099 Alle anderen nicht. 00:05:26.099 --> 00:05:27.745 Soll ja welche geben, die das hier hören, 00:05:27.745 --> 00:05:29.067 die mal schon mal lineare Algebra gemacht haben. 00:05:29.067 --> 00:05:30.520 So, jetzt wollen wir auch mal Komplexität. 00:05:30.551 --> 00:05:31.974 Also ich will jetzt Komplexität messen. 00:05:31.974 --> 00:05:35.130 Wir wissen ja alle, das Teuerste ist, Zahlen zu multiplizieren. 00:05:35.343 --> 00:05:37.950 Zahlen zu multiplizieren ist teurer als Zahlen zu addieren. 00:05:37.964 --> 00:05:38.084 Ja, 00:05:38.084 --> 00:05:40.981 vielleicht sollst du auch erst nochmal sagen, was Komplexität ist. 00:05:40.981 --> 00:05:43.014 Genau, also ich frage jetzt einen Computer, 00:05:43.386 --> 00:05:48.284 der kriegt irgendwie als Eingabe die Matrizen und soll jetzt 00:05:49.176 --> 00:05:51.364 das Produkt ausrechnen, dieses Matrix-Produkt. 00:05:51.364 --> 00:05:55.130 Und dafür gibt es eine Formel, da können wir diese Formel einfach eintippen. 00:05:56.121 --> 00:05:57.862 Und dann kommt man da so drauf, dass man, 00:05:57.862 --> 00:06:01.185 wenn das eine n-Kreuz-n-Matrix und eine n-Kreuz-n-Matrix multipliziert, 00:06:01.185 --> 00:06:03.076 um eine n-Kreuz-n-Matrix rauszukriegen, 00:06:03.186 --> 00:06:08.650 dann braucht man ungefähr n hoch 3 Operationen, also höchstens n hoch 3. 00:06:08.650 --> 00:06:11.382 Und damit meine ich jetzt die Ordnung n hoch 3. 00:06:11.793 --> 00:06:15.666 Also das ist ja in der Komplexitätstheorie, da lässt man immer sozusagen, wenn 00:06:16.917 --> 00:06:21.230 man betrachtet, wie verhält sich ein Algorithmus, wenn dieses n wächst. 00:06:21.943 --> 00:06:23.334 Also es gibt sozusagen verschiedene Bereiche. 00:06:23.334 --> 00:06:24.350 Wie schnell wächst das? 00:06:25.021 --> 00:06:26.987 Kleine Optimierung für kleine Probleme, 00:06:26.987 --> 00:06:31.370 also wie kann ich jetzt wirklich am effizientesten zwei 2x2-Matrizen multiplizieren? 00:06:31.521 --> 00:06:36.070 Oder was ist sozusagen die Komplexität von Matrixmultiplikation allgemein? 00:06:36.070 --> 00:06:40.299 Und da würde ich das jetzt betrachten, als wenn dieses n wächst für große Matrizen. 00:06:40.299 --> 00:06:43.670 Das Problem wird immer schwieriger, aber wie schnell wird es schwieriger? 00:06:44.102 --> 00:06:49.209 Und man kann sich ja, also so eine Matrix hat ja n mal n gleich n Quadrat Einträge. 00:06:50.001 --> 00:06:52.268 Und also das ist auf jeden Fall eine untere Schranke, weil man muss ja, 00:06:52.268 --> 00:06:56.730 wenn man die multipliziert, muss man jeden Eintrag einmal in das Ergebnis schreiben. 00:06:56.902 --> 00:06:59.629 Oder auch jeden Eintrag von der Eingabe mal lesen. 00:06:59.629 --> 00:07:04.170 Da hat man 2 mal n Quadrat. Also unter n Quadrat geht nichts. 00:07:05.323 --> 00:07:08.130 Aber dass n hoch 3 eine obere Schranke ist, 00:07:08.130 --> 00:07:12.029 das sieht man an der normalen Formel, die man für das Matrix-Produkt kennt. 00:07:13.022 --> 00:07:15.447 Leute kennen vielleicht so Skalarprodukt von einem Vektor. 00:07:15.447 --> 00:07:17.933 Also weiß nicht, ob es jetzt irgendjemand gibt, der Matrix-Produkt nicht kennt. 00:07:17.933 --> 00:07:20.750 Aber für 2x2-Matrizen können wir es ja mal erklären. 00:07:21.241 --> 00:07:22.193 Da steht in 00:07:23.185 --> 00:07:27.853 dem linken oberen Eintrag das Ergebnis, wir brauchen 4 Zahlen. 00:07:27.853 --> 00:07:31.970 Und im linken oberen Eintrag steht das Skalarprodukt von der 00:07:33.360 --> 00:07:36.143 ersten Zeile. Na ja. 00:07:36.143 --> 00:07:38.745 Mit der ersten Spalte. Meine Englischlehrerin in der 7. 00:07:38.745 --> 00:07:41.917 Klasse hat, wenn jemand irgendwie so 00:07:42.568 --> 00:07:44.740 Erklärungen von irgendwas 00:07:44.930 --> 00:07:47.452 für irgendwas Schwieriges mit irgendwas anderem Schwierigem gebracht hat, 00:07:47.452 --> 00:07:49.253 gesagt, Chin ist Chin-Chin. 00:07:49.253 --> 00:07:50.204 Chin ist Chin-Chin. 00:07:50.595 --> 00:07:53.217 Ja, da muss ich gerade dran denken, als du gesagt hast, ja, 00:07:53.217 --> 00:07:54.968 wir schreiben da jetzt das Skalarprodukt rein. 00:07:55.218 --> 00:07:57.931 Ja, das ist auch ein Teil. Das ist auch ein technischer Begriff. 00:07:58.081 --> 00:08:00.714 Also jedenfalls, was passiert, ich kann nur sagen, was passiert. 00:08:00.904 --> 00:08:05.489 In jedem Eintrag von dem Ergebnis steht ein Produkt, 00:08:05.489 --> 00:08:07.841 es steht eine Summe von zwei Produkten 00:08:10.213 --> 00:08:12.866 von Einträgen der ursprünglichen Matrizen. 00:08:12.936 --> 00:08:17.050 Also die werden da irgendwie so gemischt, da steht so, in dem ersten steht, äh … 00:08:17.802 --> 00:08:19.835 A1 … nee, nee, ich mach das jetzt nicht. 00:08:19.835 --> 00:08:20.358 Also in jedem … 00:08:20.358 --> 00:08:20.824 Mach's nicht. 00:08:20.824 --> 00:08:21.976 In jedem, in jedem steht … 00:08:21.976 --> 00:08:23.942 Seitdem du das aufgeschrieben hast, kannst du es ablesen. 00:08:23.942 --> 00:08:24.443 In jedem, 00:08:24.443 --> 00:08:26.711 in jedem steht, naja, ich muss ja so Indizes einführen, 00:08:26.711 --> 00:08:29.850 aber in jedem Eintrag steht eine Summe … 00:08:30.141 --> 00:08:31.274 von zwei Produkten. 00:08:31.345 --> 00:08:34.586 Ein Produkt von zwei Einträgen plus ein Produkt von zwei anderen Einträgen. 00:08:34.918 --> 00:08:35.259 Und … 00:08:35.259 --> 00:08:37.568 Also du brauchst vier Zahlen für jeden Eintrag, ne? 00:08:37.622 --> 00:08:38.163 Ich brauche vier, 00:08:38.163 --> 00:08:40.197 ich muss vier Zahlen anfassen oder lesen 00:08:40.429 --> 00:08:44.498 und dann dieses zwei Multiplikationen ausführen und eine Addition pro Eintrag. 00:08:44.498 --> 00:08:49.857 Genau. Und das heißt, ich habe zwei Multiplikationen in jedem Eintrag 00:08:50.408 --> 00:08:53.353 und zwei ist das N in diesem Fall bei zwei Kreuz zwei Matrizen. 00:08:53.353 --> 00:08:57.860 Und dann komme ich eben auf N hoch drei, weil ich pro Eintrag brauche ich N … 00:08:57.860 --> 00:09:02.595 … äh, Multiplikation im Allgemeinen bei diesem einfachen Algorithmus mit der Formel. 00:09:03.066 --> 00:09:04.548 Und komme so auf N hoch drei, 00:09:04.548 --> 00:09:07.251 weil ich für jeden Eintrag N Multiplikationen mache und habe N Quadrat. 00:09:07.251 --> 00:09:08.832 Genau, also hast du N Einträge. 00:09:08.832 --> 00:09:11.545 Genau, N Quadrat mal N ist dann N hoch drei. 00:09:11.595 --> 00:09:15.841 So, und, äh, wenn wir mal kurz überlegen, wenn ich jetzt zwei Matrizen addiere … 00:09:15.841 --> 00:09:18.155 Dann, ähm, brauche ich N Quadrat. 00:09:18.266 --> 00:09:20.812 Äh, Addition, also das scheint irgendwie … 00:09:20.812 --> 00:09:22.184 Die Welt ist konsistent, oder? 00:09:22.215 --> 00:09:24.490 Also sozusagen Addition ist leichter als Multiplikation. 00:09:24.763 --> 00:09:27.313 Ähm, man hat, sozusagen N Quadrat geht die Addition, 00:09:27.313 --> 00:09:28.661 N hoch drei geht die Multiplikation. 00:09:28.661 --> 00:09:30.946 N hoch drei ist auch ungefähr so die Komplexität, 00:09:30.946 --> 00:09:32.290 die man irgendwie beim Gauss-Algorithmus, 00:09:32.290 --> 00:09:34.234 wenn man da so ein bisschen zählt, rauskriegt. 00:09:34.234 --> 00:09:36.750 Also, äh, ist die Welt konsistent. 00:09:37.403 --> 00:09:41.710 So, und jetzt gibt's einen, ähm, deutschen Mathematiker namens Volker Strassen. 00:09:42.321 --> 00:09:46.884 Und der hat, äh, das versucht zu beweisen, äh, dass das, äh, n hoch 3, 00:09:47.256 --> 00:09:51.499 ähm, optimal ist. Und, äh, das ist ihm aber nicht gelungen. 00:09:51.872 --> 00:09:53.438 Ähm, und aus Versehen hat er dann... 00:09:53.438 --> 00:09:55.310 Es war falsch, ne? Es war falsch, genau. 00:09:55.310 --> 00:09:56.930 Er hatte eine Verbesserung gefunden. 00:09:57.223 --> 00:10:00.830 Und, äh, der konnte es mit 7, äh, Multiplikationen machen. 00:10:01.260 --> 00:10:02.121 Also der Preis... 7, 00:10:02.121 --> 00:10:03.822 egal wie groß die Matrix ist? 00:10:03.822 --> 00:10:05.163 Nee, nee, 2x2-Matrixen. Ah, 2x2. 00:10:05.163 --> 00:10:08.055 Also wir würden 2x2-Matrixen multiplizieren. 00:10:08.686 --> 00:10:10.608 Das ist jetzt, also wir sind jetzt im 20. 00:10:10.608 --> 00:10:11.989 Jahrhundert. 00:10:11.989 --> 00:10:17.313 Also statt 2 hoch 3, 7. Also statt 8, 7. 00:10:17.313 --> 00:10:20.416 Genau. Also 2, ja genau. Also ich habe behauptet n hoch 3. 00:10:20.416 --> 00:10:23.788 Bei meinem 2x2 mal 2x2 komme ich also auf 8. 00:10:24.619 --> 00:10:25.870 Und es geht aber mit 7. 00:10:27.282 --> 00:10:30.102 Klingt jetzt noch nicht nach so einer irren Verbesserung, ne? 00:10:30.213 --> 00:10:32.230 Also es ist schön, dass es besser geht. 00:10:32.744 --> 00:10:33.513 Naja, jetzt mal… 00:10:33.513 --> 00:10:35.495 Aber wo hat er die eine eingespart? 00:10:35.495 --> 00:10:36.203 Kann man das so genau sagen? Ja genau, 00:10:36.203 --> 00:10:40.528 also er hat sich die eine Multiplikation erkauft durch 14 zusätzliche Additionen. 00:10:41.091 --> 00:10:41.442 Okay. 00:10:41.442 --> 00:10:43.490 Aber das ist asymptotisch, ist das alles nicht so schlimm. 00:10:43.490 --> 00:10:45.025 Ich sag gleich noch was zur Asymptotik. 00:10:45.338 --> 00:10:45.838 Und… 00:10:47.060 --> 00:10:50.433 Also ohne das jetzt zu technisch machen zu wollen, er macht folgendes. 00:10:50.643 --> 00:10:53.185 Er bildet bestimmte Summen aus den Einträgen, 00:10:53.185 --> 00:10:56.037 weil die Denkeweise ist, Additionen sind billig. 00:10:56.307 --> 00:11:00.440 Also er bestimmt erst sozusagen bestimmte Linearkombinationen der Einträge, 00:11:01.251 --> 00:11:05.624 multipliziert dann, macht dann sieben Produkte aus diesen Linearkombinationen 00:11:06.695 --> 00:11:11.358 und aus den Ergebnissen macht er vier Linearkombinationen, 00:11:11.358 --> 00:11:13.970 die genau die Einträge des Produkts ergeben. 00:11:14.880 --> 00:11:19.475 Also erst irgendwie lustige Summen bilden aus den Einträgen, die man hat, 00:11:19.746 --> 00:11:23.059 dann sieben Multiplikationen machen statt acht aus diesen Summen 00:11:24.071 --> 00:11:25.553 und dann diese Produkte, 00:11:25.553 --> 00:11:27.335 die man da, diese sieben Produkte auf geschickte Art 00:11:27.335 --> 00:11:30.248 und Weise wieder voneinander abziehen, aufeinander summieren, 00:11:30.678 --> 00:11:32.250 um die vier Einträge zu bekommen. 00:11:32.500 --> 00:11:34.926 Also er braucht viel mehr Rechenoperationen, 00:11:34.926 --> 00:11:37.914 aber weil er sozusagen viel mehr Summen gemacht hat, 00:11:37.914 --> 00:11:40.422 kann er jetzt eine Multiplikation einsparen. 00:11:40.422 --> 00:11:44.684 Genau. Er spart eine Multiplikation auf Kosten von in diesem Fall 14 Additionen, 00:11:45.016 --> 00:11:46.289 14 zusätzlichen Additionen. 00:11:46.822 --> 00:11:47.845 Okay, also es ist nichts, 00:11:47.845 --> 00:11:51.134 was man jetzt den Studis im ersten Semester als Trick verraten könnte, 00:11:51.134 --> 00:11:53.429 wie man schneller Matrizen multiplizieren kann. 00:11:53.762 --> 00:11:56.580 Ja, für zwei Kreuzzweiß ist es vielleicht noch nicht so spektakulär, 00:11:57.072 --> 00:11:59.990 aber jetzt kommt der nächste Trick. 00:12:00.302 --> 00:12:03.268 Dauert wahrscheinlich viel länger, weil man diese 14 extra machen muss. 00:12:03.283 --> 00:12:06.450 Also man braucht die Matrizen nicht sehr groß machen, damit das besser ist. 00:12:07.082 --> 00:12:13.010 Also wenn du jetzt eine 4x4-Matrix mit einer 4x4-Matrix multiplizieren willst, 00:12:13.062 --> 00:12:15.040 erteilst du deine 4x4-Matrix in vier 2x2-Blöcke ein. 00:12:18.003 --> 00:12:20.170 Und dann gibt es so eine, also für alle, 00:12:20.170 --> 00:12:22.922 die jetzt noch so an eine 4x4, 16 Zahlen denken, 00:12:22.922 --> 00:12:26.650 also wir teilen das jetzt so in Blöcke ein, dass wir vier mal 2x2 Blöcke haben. 00:12:27.201 --> 00:12:29.938 Und jetzt hat dieses Matrixprodukt die magische Eigenschaft, 00:12:29.969 --> 00:12:31.754 dass wenn man jetzt zwei Matrizen multipliziert, 00:12:31.754 --> 00:12:33.384 dann kann man die auch so in diesen Blöcken multiplizieren. 00:12:33.384 --> 00:12:35.450 So blockweise multiplizieren, genau. 00:12:35.581 --> 00:12:38.455 Und jetzt für diese, wenn ich eine 4x4-Matrizen habe, 00:12:38.605 --> 00:12:41.920 dann mache ich eine blockweise Multiplikation von diesen, 00:12:42.371 --> 00:12:44.924 ja, mache ich eine 2x2-Matrix aus 2x2-Matrizen, 00:12:45.055 --> 00:12:48.804 wende dafür diese mit nur sieben Matrixmultiplikationen an. 00:12:48.804 --> 00:12:51.095 Für jede von diesen Matrixmultiplikationen mache ich auch wieder nur den 00:12:51.095 --> 00:12:54.840 Siemer-Algorithmus. Das ist der quadratische Einsparung. 00:12:54.840 --> 00:12:57.870 Und so weiter. Also für eine 2 hoch n, Kreuz 2 hoch n Matrix, 00:12:57.870 --> 00:13:01.010 teile ich das immer so in Blöcke, Blöcke, Blöcke, Blöcke, Blöcke. 00:13:01.101 --> 00:13:04.678 Und womit ich dann rauskomme mit dieser Methode ist eben so ein Exponent. 00:13:04.908 --> 00:13:09.507 Ich mache meine Matrixmultiplikation in n hoch, Logarithmus von 7. 00:13:09.638 --> 00:13:10.729 Logarithmus zur Basis 2. 00:13:11.483 --> 00:13:15.245 Und das ist, das habe ich mir mal hier auch irgendwo aufgeschrieben, ungefähr 2,807. 00:13:17.881 --> 00:13:18.411 Okay. 00:13:18.502 --> 00:13:18.983 Also mit diesem, 00:13:18.983 --> 00:13:23.172 indem man das einfach nur so immer wieder hintereinander ausführt, 00:13:23.172 --> 00:13:25.808 kriegt man auf asymptotisch n hoch 2,807. 00:13:27.163 --> 00:13:29.881 Geht aber nur für Zweierpotenzen, ne? 00:13:29.881 --> 00:13:33.606 Ja, genau. Also du kannst die Matrix, das macht nichts. 00:13:33.606 --> 00:13:35.138 Also erstmal machen wir es asymptotisch 00:13:35.349 --> 00:13:38.053 und dann kannst du die Matrix irgendwie so auffüllen mit so einer, 00:13:38.053 --> 00:13:40.296 was so der Rest von einer Identität aussieht, ja? 00:13:40.296 --> 00:13:42.625 Also mit ganz vielen Nullen und Einsen auf der Diagonalen. 00:13:42.625 --> 00:13:43.981 Heißt du machst sie dann künstlich größer? 00:13:43.981 --> 00:13:46.116 Machst sie künstlich größer oder so. 00:13:46.388 --> 00:13:47.571 Aber das drücken wir ins Guard, 00:13:47.571 --> 00:13:50.829 weil wir ja sowieso an dem Verhalten für große N interessiert sind. 00:13:53.493 --> 00:13:56.815 So. Das war jetzt erstmal interessant. 00:13:56.815 --> 00:13:58.050 Hilft mir das irgendwas? 00:14:00.142 --> 00:14:04.836 Wenn du Google bist, dann hilft dir das was. 00:14:06.508 --> 00:14:10.381 Also der Volker Strassen hat auch in dem gleichen Paper gezeigt, dass die 00:14:11.513 --> 00:14:12.864 Inversion von Matrizen 00:14:13.114 --> 00:14:15.927 und das Lösen von linearen Gleichungssystemen mit dem Gauss-Algorithmus 00:14:16.317 --> 00:14:19.350 alle die gleiche, asymptotisch die gleiche Komplexität haben. 00:14:19.561 --> 00:14:23.519 Also diese verschiedenen Probleme, die man so mit Matrizen hat, 00:14:23.971 --> 00:14:27.950 lineares Gleichungssystem lösen, Determinante berechnen. 00:14:28.764 --> 00:14:29.708 Das ist nicht so überraschend, 00:14:29.708 --> 00:14:32.222 weil das macht man auch mit denselben Algorithmen irgendwie. 00:14:32.222 --> 00:14:34.327 Genau, also kann man ja immer aufeinander zurückführen. 00:14:34.327 --> 00:14:36.812 Also im Prinzip so lineares Gleichungssystem, 00:14:36.812 --> 00:14:40.249 wenn es invertierbar ist, ist einmal Multiplikation mit der Inversen. 00:14:40.783 --> 00:14:44.970 Und Inverse berechnen ist auch lineares Gleichungssystem lösen und so weiter. 00:14:46.540 --> 00:14:49.763 Okay, so dann, also das war was? 00:14:49.763 --> 00:14:54.996 1969. Okay, so dann geht's weiter. 00:14:56.327 --> 00:15:02.832 Es wird eine neue Methode entwickelt, die auf der Analyse von Tensoren basiert. 00:15:02.832 --> 00:15:03.863 Komme ich später nochmal drauf. 00:15:04.473 --> 00:15:10.447 Und das kombiniert in den 90ern beim Coppersmith-Winograd-Algorithmus. 00:15:10.838 --> 00:15:12.649 Und da sind wir dann schon bei 2,375. 00:15:13.140 --> 00:15:13.640 fünf. 00:15:14.561 --> 00:15:15.084 Als Exponenten. 00:15:15.084 --> 00:15:17.597 Für diesen Exponenten der Verbesserung sozusagen. 00:15:17.597 --> 00:15:18.330 Okay. 00:15:18.763 --> 00:15:23.094 Der hilft uns jetzt übrigens für die 2x2-Matrizen überhaupt nicht mehr weiter. 00:15:23.094 --> 00:15:25.330 Man kann nämlich zeigen, dass die 7 optimal ist. 00:15:25.883 --> 00:15:27.648 Für die 2x2-Matrizen. 00:15:27.648 --> 00:15:29.945 Genau. Also für die 2x2-Matrizen gibt's ne… 00:15:30.898 --> 00:15:31.398 also… 00:15:33.524 --> 00:15:37.810 Was macht dieser Coppersmith, wie hieß der noch gleich, Winograd-Algorithmus? 00:15:38.861 --> 00:15:43.250 Also macht der auch aus Produkten Summen oder hat der nen neuen Trick gefunden? 00:15:44.022 --> 00:15:45.264 Das ist immer das Gleiche, genau. 00:15:45.264 --> 00:15:49.493 Also der, das ist sozusagen ne große, ne andere Art und Weise, 00:15:49.493 --> 00:15:52.870 diese immer komplizierteren Arrangements von… 00:15:54.481 --> 00:15:58.606 weniger Multiplikationen auf Kosten von vorher geschickt summierend zu finden. 00:15:58.606 --> 00:15:59.591 Vielen Summen. Ja. 00:15:59.902 --> 00:16:01.756 Also man hat das sozusagen systematisch, es gibt, 00:16:01.867 --> 00:16:04.041 da sag ich am Ende vielleicht noch was dazu, 00:16:04.312 --> 00:16:07.902 über eben so Tensor-Algebra systematisch organisiert. 00:16:07.902 --> 00:16:11.258 Und man kann, man hat wieder sowas wie oft in der Mathematik, 00:16:11.269 --> 00:16:13.483 dass man ein geometrisches Objekt gefunden hat, 00:16:13.975 --> 00:16:16.329 in dem ein Punkt ein Algorithmus ist. 00:16:18.082 --> 00:16:22.363 Und man kann sozusagen die Familien von Algorithmen untersuchen mit, 00:16:22.634 --> 00:16:25.030 ja, algebraisch-geometrischen Methoden. 00:16:26.363 --> 00:16:30.120 Aber ist der jetzt optimal, dieser neue, aus den 80er Jahren, der neue Algorithmus? 00:16:30.120 --> 00:16:31.023 Who knows? 00:16:31.023 --> 00:16:33.679 Nee, nee, nee, das Rennen geht weiter. 00:16:33.850 --> 00:16:37.730 Und 2014 war ich mal in Japan, in Kobe. 00:16:38.281 --> 00:16:39.834 Auf einer Computer-Algebra-Konferenz. 00:16:39.945 --> 00:16:42.421 Und da wurde so einer, das ist so ein Rekordrennen, weißt du? 00:16:42.451 --> 00:16:46.150 Also wo dir immer dann immer jemand wieder neu mit einem Rekord rauskommt. 00:16:46.361 --> 00:16:52.779 Und da hat ein Mathematiker namens Legal ein Tutorial gegeben über 00:16:52.889 --> 00:16:54.701 die schnelle Matrixmultiplikation. 00:16:55.052 --> 00:16:56.163 Und da hatte er den 00:16:57.655 --> 00:16:59.307 Rekord von 2,37287. 00:17:02.601 --> 00:17:06.607 Und davor habe ich gesagt 2,375 und jetzt habe ich gesagt 2,372. 00:17:06.607 --> 00:17:11.745 Also das hat sich auf der dritten Nachkommastelle nur noch verbessert zwischen 00:17:11.896 --> 00:17:12.707 1990 und 2014. 00:17:15.504 --> 00:17:20.550 Ich glaube der Zugewinn durch Schnelligkeit der Computer war wesentlich größer. 00:17:20.862 --> 00:17:23.840 Ja, das ist mit Sicherheit richtig. 00:17:24.353 --> 00:17:25.886 Aber wer weiß. 00:17:28.845 --> 00:17:31.188 Also die Antwort ist immer, es kommt drauf an, wie groß deine Matrizen sind. 00:17:31.242 --> 00:17:36.221 Ja, natürlich. Aber so große Matrizen hat selbst Google nicht, glaube ich. 00:17:36.221 --> 00:17:39.717 Weiß nicht was, Google, müssen die natürlich irgendwie so den 00:17:40.609 --> 00:17:44.946 Eigenvektor zu so einer Milliarde-Kreuz-Milliarde-Matrix irgendwie schnell den 00:17:45.197 --> 00:17:46.950 Eigenvektor zum kleinsten Eigenwert finden? 00:17:47.062 --> 00:17:48.285 Ja, aber da gibt es doch bestimmt, 00:17:48.285 --> 00:17:50.310 die werden doch auch nicht solche Algorithmen anwenden, 00:17:50.310 --> 00:17:53.849 da gibt es doch bestimmt so statistische Rate-Methoden, wo du erst irgendwie… 00:17:54.501 --> 00:17:56.428 Wo du approximativ vorgehst. Ja, 00:17:56.428 --> 00:18:00.030 keine Ahnung, die geheime Zutat von Google. 00:18:00.382 --> 00:18:01.905 Ja, aber es gibt doch so Methoden, 00:18:01.905 --> 00:18:03.910 auch Eigenwerte und Eigenvektoren zu bestimmen, 00:18:03.910 --> 00:18:08.120 wo man erst mal rät und dann sozusagen diese geratenen Eigenrichtungen… 00:18:08.120 --> 00:18:08.785 So iterative… 00:18:08.785 --> 00:18:10.419 Ja, iterativ verbessert, genau. 00:18:10.419 --> 00:18:15.035 …als dynamisches System. Ja, ja, stimmt. 00:18:15.035 --> 00:18:18.937 Variationsprinzipien oder so. Das ist wahrscheinlich die Kabler. 00:18:18.937 --> 00:18:23.997 Ja. Naja, jedenfalls der aktuelle Rekord ist übrigens vom Oktober letzten Jahres 00:18:25.591 --> 00:18:29.945 von Josh Alman and Virginia Vassilevska Williams und der ist… 00:18:29.945 --> 00:18:31.458 Auf welcher Nachkommastelle hat der das jetzt? 00:18:31.458 --> 00:18:36.142 Ja, ja, genau. Der ist 2,37286. 00:18:36.193 --> 00:18:39.121 Und die, die gut aufgepasst haben, werden… 00:18:39.121 --> 00:18:40.424 bemerkt haben, dass es jetzt nur noch eine, 00:18:40.424 --> 00:18:44.783 die fünfte Nachkommastelle sich um eins verbessert hat gegenüber legal in den 00:18:45.255 --> 00:18:46.959 sechs Jahren, die da vergangen sind. 00:18:46.959 --> 00:18:49.544 Gibt's irgendeine Vermutung, wohin das konvergiert? 00:18:49.544 --> 00:18:51.754 Ha! Das ist die richtige Frage. 00:18:51.754 --> 00:18:53.190 Was würdest du denn sagen? 00:18:53.822 --> 00:18:56.852 Keine Ahnung. Ich hab mich mit dieser Frage noch nie beschäftigt. 00:18:56.852 --> 00:18:59.461 Da jetzt was zu raten, wäre irgendwie sehr vermissen. 00:18:59.461 --> 00:19:01.073 So, jetzt die Vermutung ist, 00:19:01.103 --> 00:19:03.707 und es gibt wirklich Leute, die die Vermutung vertreten, 00:19:03.707 --> 00:19:07.061 dass es zwei ist oder beliebig nah dran an zwei. 00:19:07.111 --> 00:19:10.325 Ja, also dass man diesen Exponenten der Matrixmultiplikation 00:19:10.897 --> 00:19:13.350 beliebig nah dran an zwei bekommen kann. 00:19:13.763 --> 00:19:17.930 Mhm. Also auf Kosten sozusagen beliebig vieler Summen. 00:19:18.144 --> 00:19:18.426 Ja, 00:19:18.426 --> 00:19:20.610 das ist eine philosophische Frage. 00:19:23.841 --> 00:19:26.714