Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bläser, Markus; Lysikov, Vladimir http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-64343
URL:

;

On Degeneration of Tensors and Algebras

pdf-format:


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.

BibTeX - Entry

@InProceedings{blser_et_al:LIPIcs:2016:6434,
  author =	{Markus Bl{\"a}ser and Vladimir Lysikov},
  title =	{{On Degeneration of Tensors and Algebras}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{19:1--19:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6434},
  URN =		{urn:nbn:de:0030-drops-64343},
  doi =		{10.4230/LIPIcs.MFCS.2016.19},
  annote =	{Keywords: bilinear complexity, border rank, commutative algebras, lower bounds}
}

Keywords: bilinear complexity, border rank, commutative algebras, lower bounds
Seminar: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI