Document Open Access Logo

Kronecker Powers of Tensors and Strassen’s Laser Method

Authors Austin Conner, Joseph M. Landsberg, Fulvio Gesmundo , Emanuele Ventura

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.10.pdf
  • Filesize: 0.67 MB
  • 28 pages

Document Identifiers

Author Details

Austin Conner
  • Department of Mathematics, Texas A&M University, College Station, TX 77843-3368, USA
Joseph M. Landsberg
  • Department of Mathematics, Texas A&M University, College Station, TX 77843-3368, USA
Fulvio Gesmundo
  • QMATH, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen O., Denmark
Emanuele Ventura
  • Department of Mathematics, Texas A&M University, College Station, TX 77843-3368, USA

Funding

  • Landsberg, Joseph M.: supported by NSF grant AF-1814254.
  • Gesmundo, Fulvio: acknowledges support VILLUM FONDEN via the QMATH Centre of Excellence (Grant no. 10059).

Cite AsGet BibTex

Austin Conner, Joseph M. Landsberg, Fulvio Gesmundo, and Emanuele Ventura. Kronecker Powers of Tensors and Strassen’s Laser Method. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 10:1-10:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.10

Abstract

We answer a question, posed implicitly in [P. Bürgisser et al., 1997] and explicitly in [M. Bläser, 2013], showing the border rank of the Kronecker square of the little Coppersmith-Winograd tensor is the square of the border rank of the tensor for all q>2, a negative result for complexity theory. We further show that when q>4, the analogous result holds for the Kronecker cube. In the positive direction, we enlarge the list of explicit tensors potentially useful for the laser method. We observe that a well-known tensor, the 3 × 3 determinant polynomial regarded as a tensor, det_3 ∈ C^9 ⊗ C^9 ⊗ C^9, could potentially be used in the laser method to prove the exponent of matrix multiplication is two. Because of this, we prove new upper bounds on its Waring rank and rank (both 18), border rank and Waring border rank (both 17), which, in addition to being promising for the laser method, are of interest in their own right. We discuss "skew" cousins of the little Coppersmith-Winograd tensor and indicate why they may be useful for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C^3 ⊗ C^3 ⊗ C^3.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Matrix multiplication complexity
  • Tensor rank
  • Asymptotic rank
  • Laser method

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Alman. Limits on the Universal Method for Matrix Multiplication. CoRR, abs/1812.08731, 2018. URL: http://arxiv.org/abs/1812.08731.
  2. J. Alman and V. Vassilevska Williams. Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. ArXiv e-prints, October 2018. URL: http://arxiv.org/abs/1810.08671.
  3. J. Alman and V. V. Williams. Further Limitations of the Known Approaches for Matrix Multiplication. In 9th Innov. Th. Comp. Science Conf., ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 25:1-25:15, 2018. Google Scholar
  4. A. Ambainis, Y. Filmus, and F. Le Gall. Fast matrix multiplication: limitations of the Coppersmith-Winograd method. In Proc. of the 47th ACM Symp. Th. Comp., pages 585-593. ACM, 2015. Google Scholar
  5. E. Ballico, A. Bernardi, M. Christandl, and F. Gesmundo. On the partially symmetric rank of tensor products of W-states and other symmetric tensors. Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl., 30:93-124, 2019. Google Scholar
  6. A. R. Benson and G. Ballard. A Framework for Practical Parallel Fast Matrix Multiplication. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015, pages 42-53, New York, NY, USA, February 2015. ACM. URL: https://doi.org/10.1145/2688500.2688513.
  7. D. Bini. Relations between exact and approximate bilinear algorithms. Applications. Calcolo, 17(1):87-97, 1980. Google Scholar
  8. D. Bini, G. Lotti, and F. Romani. Approximate solutions for the bilinear form computational problem. SIAM J. Comput., 9(4):692-697, 1980. Google Scholar
  9. M. Bläser. Fast Matrix Multiplication. Theory of Computing, Graduate Surveys, 5:1-60, 2013. Google Scholar
  10. M. Bläser and V. Lysikov. On degeneration of tensors and algebras. In 41st International Symposium on Mathematical Foundations of Computer Science, volume 58 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 19, 11. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016. Google Scholar
  11. P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin, 1997. Google Scholar
  12. M. Christandl, F. Gesmundo, and A. K. Jensen. Border rank is not multiplicative under the tensor product. SIAM J. Appl. Alg. Geom., 3:231-255, 2019. Google Scholar
  13. M. Christandl, P. Vrana, and J. Zuiddam. Barriers for fast matrix multiplication from irreversibility. CoRR, abs/1812.06952, 2018. URL: http://arxiv.org/abs/1812.06952.
  14. H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic Algorithms for Matrix Multiplication. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS '05, pages 379-388, Washington, DC, USA, 2005. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.2005.39.
  15. H. Cohn and C. Umans. A group theoretic approach to fast matrix multiplication. Proceedings of the 44th annual Symposium on Foundations of Computer Science, 2:438-449, 2003. Google Scholar
  16. A. Conner, F. Gesmundo, J. M. Landsberg, , and E. Ventura. Tensors with maximal symmetries. arXiv, 2019. URL: http://arxiv.org/abs/1909.09518.
  17. A. Conner, F. Gesmundo, J. M. Landsberg, E. Ventura, and Y. Wang. A geometric study of Strassen’s asymptotic rank conjecture and its variants. arXiv, 2018. URL: http://arxiv.org/abs/1811.05511.
  18. D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251-280, 1990. Google Scholar
  19. H. Derksen. On the nuclear norm and the singular value decomposition of tensors. Found. Comp. Math., 16(3):779-811, 2016. Google Scholar
  20. H. Derksen and V. Makam. On non-commutative rank and tensor rank. Linear Multilinear Algebra, 66(6):1069-1084, 2018. URL: https://doi.org/10.1080/03081087.2017.1337058.
  21. K. Efremenko, A. Garg, R. Oliveira, and A. Wigderson. Barriers for rank methods in arithmetic complexity. In 9th Innovations in Theoretical Computer Science, volume 94 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 1, 19. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Google Scholar
  22. W. Fulton. Young tableaux. With applications to representation theory and geometry, volume 35 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1997. Google Scholar
  23. W. Fulton and J. Harris. Representation theory: a first course, volume 129 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991. Google Scholar
  24. D. A. Gay. Characters of the Weyl group of SU(n) on zero weight spaces and centralizers of permutation representations. Rocky Mountain J. Math., 6(3):449-455, 1976. Google Scholar
  25. F. Gesmundo, C. Ikenmeyer, and G. Panova. Geometric complexity theory and matrix powering. Diff. Geom. Appl., 55:106-127, 2017. Google Scholar
  26. N. Ilten and Z. Teitler. Product ranks of the 3 × 3 determinant and permanent. Canad. Math, Bull., 59(2):311-319, 2016. Google Scholar
  27. J. M. Landsberg. Tensors: Geometry and Applications, volume 128 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012. Google Scholar
  28. J. M. Landsberg. Geometry and complexity theory, volume 169 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2017. Google Scholar
  29. J. M. Landsberg. Tensors: Asymptotic Geometry and Developments 2016-2018, volume 132 of CBMS Regional Conference Series in Mathematics. AMS, 2019. Google Scholar
  30. J. M. Landsberg and M. Michałek. A 2n² - log(n) - 1 lower bound for the border rank of matrix multiplication. Int. Math. Res. Not., 15:4722-4733, 2018. Google Scholar
  31. J. M. Landsberg and G. Ottaviani. Equations for secant varieties of Veronese and other varieties. Ann. Mat. Pura Appl. (4), 192(4):569-606, 2013. Google Scholar
  32. J. M. Landsberg and G. Ottaviani. New lower bounds for the border rank of matrix multiplication. Th. of Comp., 11(11):285-298, 2015. Google Scholar
  33. F. Le Gall. Powers of tensors and Fast Matrix Multiplication. In Proc. 39th Int. Symp. Symb. Alg. Comp., pages 296-303. ACM, 2014. Google Scholar
  34. A. K. Lenstra, Jr. H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515-534, 1982. URL: https://doi.org/10.1007/BF01457454.
  35. T. Lickteig. Typical tensorial rank. Lin. Alg. Appl., 69:95-120, 1985. Google Scholar
  36. A. Schönhage. Partial and total matrix multiplication. SIAM J. Comp., 10(3):434-455, 1981. Google Scholar
  37. A. V. Smirnov. The Approximate Bilinear Algorithm of Length 46 for Multiplication of 4 x 4 Matrices. arXiv, 2014. URL: http://arxiv.org/abs/1412.1687.
  38. A. Stothers. On the Complexity of Matrix Multiplication. PhD thesis, U. Edinburgh, 2010. Google Scholar
  39. V. Strassen. Gaussian elimination is not optimal. Numerische mathematik, 13(4):354-356, 1969. Google Scholar
  40. V. Strassen. Rank and optimal computation of generic tensors. Lin. Alg. Appl., 52/53:645-685, 1983. Google Scholar
  41. V. Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987. Google Scholar
  42. V. Strassen. The asymptotic spectrum of tensors. J. Reine Angew. Math., 384:102-152, 1988. Google Scholar
  43. V. Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 413:127-180, 1991. URL: https://doi.org/10.1515/crll.1991.413.127.
  44. V. Strassen. Algebra and complexity. In First European Congress of Mathematics Paris, July 6-10, 1992, pages 429-446. Springer, 1994. Google Scholar
  45. V. V. Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proc. 44th ACM Symp. Th. Comp. - STOC'12, pages 887-898. ACM, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact