Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
Automotive Acoustics Conference 2025

Call for Papers - Deadline: 01/13/2025. 

We would like to invite you to submit your proposals for a presentation and join us as we explore new practices in sustainable noise control. We are looking forward to your insights on innovative, eco-friendly, and smart ways to shape the future of automotive acoustics.
EXTENDED SEARCH
Log in
Top
Foundations of Computational Mathematics
Published in:

12-08-2022

Bad and Good News for Strassen’s Laser Method: Border Rank of \(\mathrm{Perm}_3\) and Strict Submultiplicativity

Authors: Austin Conner, Hang Huang, J. M. Landsberg

Published in: Foundations of Computational Mathematics | Issue 6/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We determine the border ranks of tensors that could potentially advance the known upper bound for the exponent \(\omega \) of matrix multiplication. The Kronecker square of the small \(q=2\) Coppersmith–Winograd tensor equals the \(3\times 3\) permanent, and could potentially be used to show \(\omega =2\). We prove the negative result for complexity theory that its border rank is 16, resolving a longstanding problem. Regarding its \(q=4\) skew cousin in \({\mathbb {C}}^5{\mathord { \otimes } }{\mathbb {C}}^5{\mathord { \otimes } }{\mathbb {C}}^5\), which could potentially be used to prove \(\le 2.11\), we show the border rank of its Kronecker square is at most 42, a remarkable sub-multiplicativity result, as the square of its border rank is 64. We also determine moduli spaces VSP for the small Coppersmith–Winograd tensors.
previous article Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time
next article Sampling Rates for -Synthesis

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
J. Alman and V. Vassilevska Williams, Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (2018).
2.
Josh Alman, Limits on the universal method for matrix multiplication, 34th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 137, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, pp. Art. No. 12, 24.
3.
Josh Alman and Virginia Vassilevska Williams, A refined laser method and faster matrix multiplication, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2021, pp. 522–539.
4.
Josh Alman and Virginia Vassilevska Williams, Further limitations of the known approaches for matrix multiplication, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, 2018, pp. 25:1–25:15.
5.
Andris Ambainis, Yuval Filmus, and François Le Gall, Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract), STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 585–593.
6.
Dario Bini, Grazia Lotti, and Francesco Romani, Approximate solutions for the bilinear form computational problem, SIAM J. Comput. 9 (1980), no. 4, 692–697.MathSciNetCrossRefMATH
7.
Markus Bläser, Fast matrix multiplication, Graduate Surveys, no. 5, Theory of Computing Library, 2013.
8.
Markus Bläser and Vladimir Lysikov, On degeneration of tensors and algebras, 41st International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 58, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, pp. Art. No. 19, 11.
9.
Jerome Brachat, Pierre Comon, Bernard Mourrain, and Elias Tsigaridas, Symmetric tensor decomposition, Linear Algebra Appl. 433 (2010), no. 11-12, 1851–1872.MathSciNetCrossRefMATH
10.
Weronika Buczyńska and Jarosław Buczyński, Secant varieties to high degree Veronese reembeddings, catalecticant matrices and smoothable Gorenstein schemes, J. Algebraic Geom. 23 (2014), no. 1, 63–90.MathSciNetCrossRefMATH
11.
Weronika Buczyńska and Jarosław Buczyński, Apolarity, border rank, and multigraded Hilbert scheme, Duke Math. J. 170 (2021), no. 16, 3659–3702.MathSciNetCrossRefMATH
12.
Jarosław Buczyński and J. M. Landsberg, On the third secant variety, J. Algebraic Combin. 40 (2014), no. 2, 475–502.
13.
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997, With the collaboration of Thomas Lickteig.
14.
Luca Chiantini, Jonathan D. Hauenstein, Christian Ikenmeyer, Joseph M. Landsberg, and Giorgio Ottaviani, Polynomials and the exponent of matrix multiplication, Bull. Lond. Math. Soc. 50 (2018), no. 3, 369–389.MathSciNetCrossRefMATH
15.
Matthias Christandl, Fulvio Gesmundo, and Asger Kjærulff Jensen, Border rank is not multiplicative under the tensor product, SIAM J. Appl. Algebra Geom. 3 (2019), no. 2, 231–255.
16.
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam, Barriers for fast matrix multiplication from irreversibility, 34th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 137, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, pp. Art. No. 26, 17.
17.
18.
Austin Conner, Fulvio Gesmundo, Joseph M. Landsberg, and Emanuele Ventura, Tensors with maximal symmetries, arXiv e-prints (2019), arXiv:​1909.​09518.
19.
Austin Conner, Fulvio Gesmundo, Joseph M. Landsberg, and Emanuele Ventura, Rank and border rank of Kronecker powers of tensors and Strassen’s laser method, Comput. Complexity 31 (2022), no. 1, Paper No. 1, 40.
20.
Austin Conner, Alicia Harper, and J.M. Landsberg, New lower bounds for matrix mulitplication and\(\operatorname{det}_3\), arXiv:​1911.​07981.
21.
D. Coppersmith and S. Winograd, On the asymptotic complexity of matrix multiplication, SIAM J. Comput. 11 (1982), no. 3, 472–492.MathSciNetCrossRefMATH
22.
Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280.MathSciNetCrossRefMATH
23.
Harm Derksen, On the nuclear norm and the singular value decomposition of tensors, Found. Comput. Math. 16 (2016), no. 3, 779–811.MathSciNetCrossRefMATH
24.
Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson, Barriers for rank methods in arithmetic complexity, 9th Innovations in Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 94, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 1, 19.
25.
26.
27.
Nathan Ilten and Zach Teitler, Product ranks of the\(3\times 3\)determinant and permanent, Canad. Math. Bull. 59 (2016), no. 2, 311–319.MathSciNetCrossRefMATH
28.
Thomas A. Ivey and Joseph M. Landsberg, Cartan for beginners, Graduate Studies in Mathematics, vol. 175, American Mathematical Society, Providence, RI, 2016, Differential geometry via moving frames and exterior differential systems, Second edition [of MR2003610].
29.
J. M. Landsberg, The border rank of the multiplication of\(2\times 2\)matrices is seven, J. Amer. Math. Soc. 19 (2006), no. 2, 447–459.MathSciNetCrossRefMATH
30.
J. M. Landsberg, Geometry and complexity theory, Cambridge Studies in Advanced Mathematics, vol. 169, Cambridge University Press, Cambridge, 2017.CrossRef
31.
J. M. Landsberg and Mateusz Michałek, Abelian tensors, J. Math. Pures Appl. (9) 108 (2017), no. 3, 333–371.
32.
J. M. Landsberg and Mateusz Michałek, On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry, SIAM J. Appl. Algebra Geom. 1 (2017), no. 1, 2–19.
33.
J. M. Landsberg and Giorgio Ottaviani, Equations for secant varieties of Veronese and other varieties, Ann. Mat. Pura Appl. (4) 192 (2013), no. 4, 569–606.
34.
Joseph M. Landsberg and Mateusz Michałek, A\(2n^2-\log _2(n)-1\)lower bound for the border rank of matrix multiplication, Int. Math. Res. Not. IMRN (2018), no. 15, 4722–4733.
35.
Joseph M. Landsberg and Giorgio Ottaviani, New lower bounds for the border rank of matrix multiplication, Theory Comput. 11 (2015), 285–298.
36.
François Le Gall, Powers of tensors and fast matrix multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (New York, NY, USA), ISSAC ’14, ACM, 2014, pp. 296–303.
37.
Kenneth Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168.MathSciNetCrossRefMATH
38.
39.
Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441.MathSciNetCrossRef
40.
Victor Pan, How to multiply matrices faster, Lecture Notes in Computer Science, vol. 179, Springer-Verlag, Berlin, 1984.
41.
Kristian Ranestad and Frank-Olaf Schreyer, Varieties of sums of powers, J. Reine Angew. Math. 525 (2000), 147–181. (2001m:14009)
42.
43.
Alexandre Sedoglavic and Alexey V. Smirnov, The tensor rank of\(5\times 5\)matrices multiplication is bounded by 98 and its border rank by 89, ISSAC ’21—Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation, ACM, New York, [2021] \(\copyright \) 2021, pp. 345–351.
44.
45.
46.
A. V. Smirnov, The bilinear complexity and practical algorithms for matrix multiplication, Comput. Math. Math. Phys. 53 (2013), no. 12, 1781–1795.MathSciNetCrossRef
47.
A. V. Smirnov, The Approximate Bilinear Algorithm of Length 46 for Multiplication of 4 x 4 Matrices, ArXiv e-prints (2014).
48.
A. Stothers, On the complexity of matrix multiplication, PhD thesis, University of Edinburgh, 2010.
49.
50.
V. Strassen, Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math. 375/376 (1987), 406–443. (88h:11026)
51.
V. Strassen, Algebra and complexity, First European Congress of Mathematics, Vol. II (Paris, 1992), Progr. Math., vol. 120, Birkhäuser, Basel, 1994, pp. 429–446.
52.
53.
Toshio Sumi, Mitsuhiro Miyazaki, and Toshio Sakata, About the maximal rank of 3-tensors over the real and the complex number field, Ann. Inst. Statist. Math. 62 (2010), no. 4, 807–822.MathSciNetCrossRefMATH
54.
55.
Virginia Williams, Breaking the coppersimith-winograd barrier, preprint.
Metadata
Title
Bad and Good News for Strassen’s Laser Method: Border Rank of and Strict Submultiplicativity
Authors
Austin Conner
Hang Huang
J. M. Landsberg
Publication date
12-08-2022
Publisher
Springer US
Published in
Foundations of Computational Mathematics / Issue 6/2023
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-022-09579-3

Other articles of this Issue 6/2023

Sampling Rates for -Synthesis

Families of Polytopes with Rational Linear Precision in Higher Dimensions

  • Open Access

Potential Singularity of the 3D Euler Equations in the Interior Domain

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time

  • Open Access

Potentially Singular Behavior of the 3D Navier–Stokes Equations

Premium Partner

    Image Credits