Datei:MatrixMultComplexity.pdf

Größe der JPG-Vorschau dieser PDF-Datei: 800 × 460 Pixel. Weitere Auflösungen: 320 × 184 Pixel | 640 × 368 Pixel | 1.024 × 589 Pixel | 1.280 × 737 Pixel | 3.475 × 2.000 Pixel

Originaldatei (3.475 × 2.000 Pixel, Dateigröße: 16 KB, MIME-Typ: application/pdf)

Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.

Zur Beschreibungsseite auf Commons

Beschreibung

BeschreibungMatrixMultComplexity.pdf	English: Remake of File:Bound on matrix multiplication omega over time.svg References: Volker Strassen (Aug 1969). "Gaussian elimination is not optimal". Numerische Mathematik 13: 354–356. DOI:10.1007/BF02165411. Victor Yakovlevich Pan (Oct 1978) „Strassen's Algorithm is not Optimal: Trilinear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations“ in Proc. 19th FOCS, S. 166–176 DOI: 10.1109/SFCS.1978.34. Dario Andrea Bini and Milvio Capovani and Francesco Romani and Grazia Lotti (Jun 1979). "O(n^2.7799) complexity for n×n approximate matrix multiplication". Information Processing Letters 8: 234–235. DOI:10.1016/0020-0190(79)90113-3. Arnold Schönhage (1981). "Partial and total matrix multiplication". SIAM Journal on Computing 10 (3): 434–455. DOI:10.1137/0210032. Francesco Romani (1982). "Some properties of disjoint sums of tensors related to matrix multiplication". SIAM Journal on Computing 11 (2): 263–267. DOI:10.1137/0211020. Don Coppersmith and Shmuel Winograd (1981) „On the asymptotic complexity of matrix multiplication“ in Proc. 22nd Annual Symposium on Foundations of Computer Science (SFCS), S. 82–90 DOI: 10.1109/SFCS.1981.27. Don Coppersmith and Shmuel Winograd (1982). "On the Asymptotic Complexity of Matrix Multiplication". SIAM Journal on Computing 11 (3): 472–492. Volker Strassen (Oct 1986) „The asymptotic spectrum of tensors and the exponent of matrix multiplication“ in Proc. 27th Ann. Symp. on Foundation of Computer Science (FOCS), S. 49–54 DOI: 10.1109/SFCS.1986.52. Don Coppersmith and Shmuel Winograd (Mar 1990). "Matrix multiplication via arithmetic progressions". J. Symbolic Computation 9 (3): 251–280. Andrew James Stothers (2010) On the Complexity of Matrix Multiplication (Ph.D. thesis)^[1], University of Edinburgh Virginia Vassilevska Williams (2012) „Multiplying Matrices Faster than Coppersmith-Winograd“ in Howard J. Karloff and Toniann Pitassi (Hrsg.) Proc. 44th Symp. on Theory of Computing Conference (STOC), ACM, S. 887–898 DOI: 10.1145/2213977.2214056. François Le Gall (Jul 2014) „Powers of Tensors and Fast Matrix Multiplication“ in Katsusuke Nabeshima (Hrsg.) Proc. 39th Int. Symp. on Symbolic and Algebraic Computation (ISSAC), ACM, S. 296–303 ISBN: 978-1-4503-2501-1. Josh Alman and Virginia Vassilevska Williams (Oct 2020) A Refined Laser Method and Faster Matrix Multiplication, Harvard SEAS / MIT CSAIL Josh Alman and Virginia Vassilevska Williams (2021) „A Refined Laser Method and Faster Matrix Multiplication“ in Proc. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) Ran Duan and Hongxun Wu and Renfei Zhou (2022) Faster Matrix Multiplication via Asymmetric Hashing Virginia Vassilevska Williams and Yinzhan Xu and Zixuan Xu and Renfei Zhou (2023) New Bounds for Matrix Multiplication: from Alpha to Omega DOI: 10.48550/ARXIV.2307.07970. Josh Alman and Ran Duan and Virginia Vassilevska Williams and Yinzhan Xu and Zixuan Xu and Renfei Zhou (Oct 2024) More Asymmetry Yields Faster Matrix Multiplication
Datum	23. Februar 2020
Quelle	Eigenes Werk
Urheber	Jochen Burghardt
Andere Versionen	File:MatrixMultComplexity.pdf * File:MatrixMultComplexity_svg.svg * File:MatrixMultComplexity1990.pdf * File:MatrixMultComplexity1990_svg.svg

Gnuplot source

# all
#set xrange [1967:2032]
#set yrange [2.36:3.01]
#set ytics 2, 0.1, 3 font "Sans Serif,15"
#set mytics 10

# excerpt 1990 - 2024
set xrange [1989:2029]
set yrange [2.371:2.377]
set ytics 2, 0.001, 3 font "Sans Serif,15"
set mytics 5

set xtics 5 font "Sans Serif,15"
set encoding iso_8859_1
set mxtics 5
set xlabel "Year" font "Sans Serif,15"
set ylabel "omega" font "Sans Serif,15"
set grid

$data <<EOF
1945    3                       ""              ""                                              0xff0000        0x000000
1969    3                       "naive   "      ""                                              0xff8080        0x000000
1969    2.80735492205760410746  ""              "   Strassen"                                   0xff0000        0x000000
1978    2.80735492205760410746  ""              ""                                              0xff8080        0x000000
1978    2.796                   ""              "   Pan"                                        0xff0000        0x000000
1979    2.796                   ""              ""                                              0xff8080        0x000000
1979    2.78                    ""              "   Bini, Capovani, Romani, Lotti"              0xff0000        0x000000
1980.5  2.78                    ""              ""                                              0xff8080        0x000000
1980.5  2.522                   "Schönhage   "  "   "                                           0xff0000        0x000000
1981    2.522                   ""              ""                                              0xff8080        0x000000
1981    2.517                   ""              "   Romani"                                     0xff0000        0x000000
1981.5  2.517                   ""              ""                                              0xff8080        0x000000
1981.5  2.496                   ""              "   Coppersmith, Winograd"                      0xff0000        0x000000
1986    2.496                   ""              ""                                              0xff8080        0x000000
1986    2.479                   ""              "   Strassen"                                   0xff0000        0x000000
1990    2.479                   ""              ""                                              0xff8080        0x000000
1990    2.3754770               ""              "   Coppersmith, Winograd"                      0xff0000        0x000000
2010    2.3754770               ""              ""                                              0xff8080        0x000000
2010    2.3736898               ""              "   Stothers"                                   0xff0000        0x000000
2012    2.3736898               ""              ""                                              0xff8080        0x000000
2012    2.3729                  ""              "   Williams   "                                0xff0000        0x000000
2014    2.3729                  ""              ""                                              0xff8080        0x000000
2014    2.3728639               ""              "   Le Gall"                                    0xff0000        0x000000
2020    2.3728639               ""              ""                                              0xff8080        0x000000
2020    2.3728596               ""              "   Alman, Williams"                            0xff0000        0x000000
2022    2.3728596               ""              ""                                              0xff8080        0x000000
2022    2.37188                 ""              "   Duan, Wu, Zhou"                             0xff8080        0x808080
2023    2.37188                 ""              ""                                              0xff8080        0x808080
2023    2.371552                ""              "   Williams, Xu, Xu, Zhou"                     0xff8080        0x808080
2024    2.371552                ""              ""                                              0xff8080        0x808080
2024    2.371339                ""              "   Alman,Duan,Williams,Xu,Xu,Zhou"             0xff8080        0x808080
2035    2.371339                ""              ""                                              0xff8080        0x808080
EOF

#1969   Strassen                                Numerische Mathematik
#1978   Pan                                     19th FOCS
#1979   Bini, Capovani, Romani, Lotti           Inf Proc Letters
#1981   Schönhage                               SIAM J Computing
#1982   Romani                                  SIAM J Computing
#1981   Coppersmith, Winograd                   22nd FOCS
#1986   Strassen                                27th FOCS
#1990   Coppersmith, Winograd                   J Symbolic Computation
#2010   Stothers                                PhD Thesis Univ Edinburgh
#2012   Williams                                44th STOC
#2014   Le Gall                                 ISSAC
#2020   Alman, Williams                         SODA
#2022   Duan, Wu, Zhou                          (Arxiv)
#2023   Williams, Xu, Xu, Zhou                  (Arxiv)
#2024   Alman, Duan, Williams, Xu, Xu, Zhou     (Arxiv)

  plot $data using 1:2:5 title '' with linespoints lc rgb variable lw 3 pt 7
replot $data using 1:2:4:6 title '' with labels rotate by 60 left  font "Sans Serif,15" tc rgb variable
replot $data using 1:2:3:6 title '' with labels rotate by 60 right font "Sans Serif,15" tc rgb variable
pause -1

Lizenz

Ich, der Urheber dieses Werkes, veröffentliche es unter der folgenden Lizenz:

Diese Datei ist lizenziert unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 4.0 international“.

Dieses Werk darf von dir

verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
neu zusammengestellt werden – abgewandelt und bearbeitet werden

Zu den folgenden Bedingungen:

Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.

Dateiversionen

Klicke auf einen Zeitpunkt, um diese Version zu laden.

	Version vom	Maße	Benutzer	Kommentar
aktuell	00:11, 2. Nov. 2024	3.475 × 2.000 (16 KB)	Jochen Burghardt	add Alman, Duan, Williams, Xu, Xu, and Zhou (2024)
	17:20, 19. Jul. 2023	3.475 × 2.000 (15 KB)	Jochen Burghardt	add recent (arxiv-only) publications; use dark red for improvements, light red for unchanged
	13:33, 11. Dez. 2020	3.475 × 2.045 (15 KB)	Jochen Burghardt	include all authors' names; change label angle 45-->60 deg; use left and right labels; optimize x,y range; add minor tics
	10:28, 13. Okt. 2020	3.475 × 2.045 (13 KB)	Jochen Burghardt	added recent improvement (Alman+Williams, SODA 2021); expanded some figures to more decimal places; inlined data file
	23:33, 23. Feb. 2020	3.475 × 2.045 (13 KB)	Jochen Burghardt	User created page with UploadWizard

Dateiverwendung

Keine Seiten verwenden diese Datei.

Metadaten

Diese Datei enthält weitere Informationen (beispielsweise Exif-Metadaten), die in der Regel von der Digitalkamera oder dem verwendeten Scanner stammen. Durch nachträgliche Bearbeitung der Originaldatei können einige Details verändert worden sein.

Kurztitel
Software
Umwandlungsprogramm	Qt 5.15.3
Verschlüsselt	no
Papierformat	1668 x 960 pts
Version des PDF-Formats	1.4

Datei:MatrixMultComplexity.pdf

Beschreibung

Lizenz

Kurzbeschreibungen

In dieser Datei abgebildete Objekte

Motiv

Urheber

Einige Werte ohne einen Wikidata-Eintrag

Urheberrechtsstatus

urheberrechtlich geschützt

Lizenz

Creative Commons Namensnennung – Weitergabe unter gleichen Bedingungen 4.0 International

Datum der Gründung, Erstellung, Entstehung, Erbauung

23. Februar 2020

Quelle der Datei

durch Hochlader erstelltes Original

MIME-Typ

application/pdf

Dateiversionen

Dateiverwendung

Metadaten