LIPIcs.MFCS.2016.19.pdf
- Filesize: 454 kB
- 11 pages
Document
On Degeneration of Tensors and Algebras
Authors
-
Part of:
Volume:
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-19
Cite As Get BibTex
Markus Bläser and Vladimir Lysikov. On Degeneration of Tensors and Algebras. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 19:1-19:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.19
Abstract
An important building block in all current asymptotically fast algorithms for matrix multiplication are tensors with low border rank, that is, tensors whose border rank is equal or very close to their size. To find new asymptotically fast algorithms for matrix multiplication, it seems to be important to understand those tensors whose border rank is as small as possible, so called tensors of minimal border rank. We investigate the connection between degenerations of associative algebras and degenerations of their structure tensors in the sense of Strassen. It allows us to describe an open subset of n*n*n tensors of minimal border rank in terms of smoothability of commutative algebras. We describe the smoothable algebra associated to the Coppersmith-Winograd tensor and prove a lower bound for the border rank of the tensor used in the "easy construction" of Coppersmith and Winograd.
Subject Classification
Keywords
- bilinear complexity
- border rank
- commutative algebras
- lower bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1997. URL: http://dx.doi.org/10.1007/978-3-662-03338-8.
- Dustin Cartwright, Daniel Erman, Mauricio Velasco, and Bianca Viray. Hilbert schemes of 8 points. Algebra &Number Theory, 3(7):763-795, 2009. URL: http://dx.doi.org/10.2140/ant.2009.3.763.
- Pierre Comon. Tensor decompositions: State of the art and applications. In Mathematics in Signal Processing V, pages 1-24. Oxford University Press, 2002. URL: http://arxiv.org/abs/0905.0454.
- Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comp., 9(3):251-280, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80013-2.
- Hans F. de Groote. On varieties of optimal algorithms for the computation of bilinear mappings i. the isotropy group of a bilinear mapping. Theor. Comp. Sci., 7(1):1-24, 1978. URL: http://dx.doi.org/10.1016/0304-3975(78)90038-5.
- Daniel Erman and Mauricio Velasco. A syzygetic approach to the smoothability of zero-dimensional schemes. Adv. Math., 224(3):1143-1166, 2010. URL: http://dx.doi.org/10.1016/j.aim.2010.01.009.
- Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. SIAM Rev., 51(3):455-500, 2009. URL: http://dx.doi.org/10.1137/07070111X.
- Hanspeter Kraft. Geometric methods in representation theory. In Representations of algebras, pages 180-258. Springer, 1982. URL: http://dx.doi.org/10.1007/BFb0094059.
- Joseph M. Landsberg. Tensors: Geometry and Applications, volume 128 of Graduate Studies in Mathematics. AMS, Providence, 2012. URL: http://dx.doi.org/10.1090/gsm/128.
- Joseph M. Landsberg and Mateusz Michałek. Abelian tensors. Preprint, ArXiv, 2015. URL: http://arxiv.org/abs/1504.03732.
- Joseph M. Landsberg and Mateusz Michałek. On the geometry of border rank algorithms for matrix multiplication and other tensors with symmetry. Preprint, ArXiv, 2016. URL: http://arxiv.org/abs/1601.08229.
- François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296-303. ACM, 2014. URL: http://dx.doi.org/10.1145/2608628.2608664.
- James S. Milne. Algebraic geometry (v6.01), 2015. URL: http://www.jmilne.org/math/CourseNotes/ag.html.
- Bjorn Poonen. The moduli space of commutative algebras of finite rank. J. Eur. Math. Soc., 10(3):817-836, 2008. URL: http://dx.doi.org/10.4171/JEMS/131.
- Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987. URL: http://dx.doi.org/10.1515/crll.1987.375-376.406.