Document Open Access Logo

Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras

Authors Markus Bläser, Vladimir Lysikov

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.17.pdf
  • Filesize: 495 kB
  • 15 pages

Document Identifiers

Author Details

Markus Bläser
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Vladimir Lysikov
  • QMATH, Department of Mathematical Sciences, University of Copenhagen, Denmark

Funding

  • Lysikov, Vladimir: supported by VILLUM FONDEN via the QMATH Centre of Excellence under Grant No. 10059 and the European Research Council (Grant agreement No. 818761)

Acknowledgements

We thank the anonymous reviewers for very helpful comments

Cite AsGet BibTex

Markus Bläser and Vladimir Lysikov. Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.17

Abstract

Determining the exponent of matrix multiplication ω is one of the central open problems in algebraic complexity theory. All approaches to design fast matrix multiplication algorithms follow the following general pattern: We start with one "efficient" tensor T of fixed size and then we use a way to get a large matrix multiplication out of a large tensor power of T. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over C: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. To obtain our result, we relate irreversibility to asymptotic slice rank and instability of tensors and prove that the instability of block tensors can often be decided by looking only on the sizes of nonzero blocks.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Mathematics of computing
Keywords
  • Tensors
  • Slice rank
  • Barriers
  • Matrix multiplication
  • GIT stability

Metrics

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

References

  1. Josh Alman. Limits on the universal method for matrix multiplication. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 12:1-12:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.12.
  2. Josh Alman and Virginia Vassilevska Williams. Further limitations of the known approaches for matrix multiplication. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 25:1-25:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.25.
  3. Josh Alman and Virginia Vassilevska Williams. Limits on all known (and some unknown) approaches to matrix multiplication. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 580-591. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00061.
  4. Andris Ambainis, Yuval Filmus, and François Le Gall. Fast matrix multiplication: Limitations of the coppersmith-winograd method. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 585-593. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746554.
  5. Dario Bini, Milvio Capovani, Grazia Lotti, and Francesco Romani. O(n^2.7799) complexity for matrix multiplication. Inform. Proc. Letters, 8:234-235, 1979. Google Scholar
  6. Markus Bläser. Fast matrix multiplication. Theory of Computing, Graduate Surveys, 5:1-60, 2013. URL: https://doi.org/10.4086/toc.gs.2013.005.
  7. Markus Bläser and Vladimir Lysikov. On degeneration of tensors and algebras. In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, editors, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, volume 58 of LIPIcs, pages 19:1-19:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.MFCS.2016.19.
  8. Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, and Chris Umans. On cap sets and the group-theoretic approach to matrix multiplication. Discrete Analysis, 2017:3, 2017. URL: https://doi.org/10.19086/da.1245.
  9. Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, and Chris Umans. Which groups are amenable to proving exponent two for matrix multiplication? CoRR, abs/1712.02302, 2017. URL: http://arxiv.org/abs/1712.02302.
  10. Michel Brion. Sur l'image de l'application moment. In Marie-Paule Malliavin, editor, Séminaire d'Algèbre Paul Dubreil et Marie-Paule Malliavin: Proceedings, Paris 1986, volume 1296 of Lecture Notes in Mathematics, pages 177-192. Springer, Berlin, 1987. URL: https://doi.org/10.1007/BFb0078520.
  11. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Towards a theory of non-commutative optimization: Geodesic 1st and 2nd order methods for moment maps and polytopes. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 845-861. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00055.
  12. Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 24:1-24:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.24.
  13. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Universal points in the asymptotic spectrum of tensors. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 289-296. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188766.
  14. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Barriers for fast matrix multiplication from irreversibility. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 26:1-26:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.26.
  15. Don Coppersmith and Shmuel Winograd. On the asymptotic complexity of matrix multiplication. SIAM J. Comput., 11(3):472-492, 1982. URL: https://doi.org/10.1137/0211038.
  16. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251-280, 1990. URL: https://doi.org/10.1016/S0747-7171(08)80013-2.
  17. A. Davie and A. J. Stothers. Improved bound for complexity of matrix multiplication. Proceedings of the Royal Society of Edinburgh: Section A Mathematics, 143:351-370, April 2013. URL: https://doi.org/10.1017/S0308210511001648.
  18. Yurij A. Drozd and Vladimir V. Kirichenko. Finite Dimensional Algebras. Springer, 1994. Google Scholar
  19. François Le Gall. Powers of tensors and fast matrix multiplication. In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  20. Frances Kirwan. Convexity properties of the moment mapping, iii. Inventiones mathematicae, 77(3):547-552, 1984. Google Scholar
  21. V. M. Kravtsov. Combinatorial properties of noninteger vertices of a polytope in a three-index axial assignment problem. Cybernetics and System Analysis, 43:25–33, 2007. URL: https://doi.org/10.1007/s10559-007-0023-0.
  22. David Mumford, John Fogarty, and Frances Kirwan. Geometric Invariant Theory. Springer, Berlin, third enlarged edition, 1994. Google Scholar
  23. Arnold Schönhage. Partial and total matrix multiplication. SIAM J. Comput, 10:434-455, 1981. Google Scholar
  24. Volker Strassen. Gaussian elimination is not optimal. Numer. Math., 13:354-356, 1969. Google Scholar
  25. Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987. Google Scholar
  26. Terence Tao. A symmetric formulation of the croot-lev-pach-ellenberg-gijswijt capset bound, 2016. URL: https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/.
  27. Michael Walter, Brent Doran, David Gross, and Matthias Christandl. Entanglement polytopes: Multiparticle entanglement from single-particle information. Science, 340(6137):1205-1208, 2013. URL: https://doi.org/10.1126/science.1232957.
  28. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proc. 44th Ann. ACM. Symp. on Theory of Comput. (STOC), pages 887-898, 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