Wikimore

Summary

DescriptionMatrixMultComplexity.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, pp. 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), pp. 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), pp. 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), University of Edinburgh Virginia Vassilevska Williams (2012) "Multiplying Matrices Faster than Coppersmith-Winograd" in Howard J. Karloff and Toniann Pitassi , ed. Proc. 44th Symp. on Theory of Computing Conference (STOC), ACM, pp. 887–898 DOI: 10.1145/2213977.2214056. François Le Gall (Jul 2014) "Powers of Tensors and Fast Matrix Multiplication" in Katsusuke Nabeshima , ed. Proc. 39th Int. Symp. on Symbolic and Algebraic Computation (ISSAC), ACM, pp. 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
Date	23 February 2020
Source	Own work
Author	Jochen Burghardt
Other versions	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

Licensing

I, the copyright holder of this work, hereby publish it under the following license:

This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.

You are free:

to share – to copy, distribute and transmit the work
to remix – to adapt the work

Under the following conditions:

attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

Category:CC-BY-SA-4.0#MatrixMultComplexity.pdf

Category:Self-published work Category:Matrix multiplication Category:Images with Gnuplot source code Category:Files by User:Jochen Burghardt Category:Arnold Schönhage (mathematician) Category:Volker Strassen (mathematician) Category:Virginia Vassilevska Williams (computer scientist)

Wikimore

File:MatrixMultComplexity.pdf

Summary

Licensing