File:MatrixMultComplexity svg.svg
Original file (SVG file, nominally 2,088 × 1,230 pixels, file size: 177 KB)
Captions
Captions
Summary[edit]
| DescriptionMatrixMultComplexity svg.svg |
English: remake of File:Bound on matrix multiplication omega over time.svg |
| Date | |
| Source | Own work |
| Author | Jochen Burghardt |
| Other versions | File:MatrixMultComplexity.pdf - File:MatrixMultComplexity_svg.svg |
Gnuplot source code and data see File:MatrixMultComplexity.pdf.
Licensing[edit]
- 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.
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(n2.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.
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)[1], 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)
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.
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 11:31, 11 December 2020 | 2,088 × 1,230 (177 KB) | Jochen Burghardt (talk | contribs) | include all authors' names; change label angle 45-->60 deg; use left and right labels; optimize x,y range; add minor tics | |
| 08:27, 13 October 2020 | 2,085 × 1,228 (95 KB) | Jochen Burghardt (talk | contribs) | added recent improvement (Alman+Williams, SODA 2021); expanded some figures to more decimal places; inlined data file | ||
| 21:31, 23 February 2020 | 2,085 × 1,228 (98 KB) | Jochen Burghardt (talk | contribs) | crop years without improvement 1950...1965, to save hor. space | ||
| 21:24, 23 February 2020 | 2,085 × 1,228 (102 KB) | Jochen Burghardt (talk | contribs) | increased font sizes again | ||
| 21:15, 23 February 2020 | 2,085 × 1,228 (102 KB) | Jochen Burghardt (talk | contribs) | used export route "gnuplot-->pdf-->svg" to circumvent font problems | ||
| 21:07, 23 February 2020 | 2,088 × 1,230 (128 KB) | Jochen Burghardt (talk | contribs) | User created page with UploadWizard |
You cannot overwrite this file.
File usage on Commons
There are no pages that use this file.
File usage on other wikis
The following other wikis use this file:
- Usage on en.wikipedia.org
- Usage on fr.wikipedia.org
- Usage on ro.wikipedia.org
- Usage on ru.wikipedia.org
Metadata
This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.
| Short title | Qt SVG Document |
|---|---|
| Image title | Generated with Qt |
| Width | 589.139mm |
| Height | 347.133mm |