On degeneration of tensors and Algebras
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
On degeneration of tensors and Algebras. / Bläser, Markus; Lysikov, Vladimir.
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. red. / Anca Muscholl; Piotr Faliszewski; Rolf Niedermeier. Saarbrücken/Wadern : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. 19 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 58).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - On degeneration of tensors and Algebras
AU - Bläser, Markus
AU - Lysikov, Vladimir
PY - 2016/8/1
Y1 - 2016/8/1
N2 - 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.
AB - 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.
KW - Bilinear complexity
KW - Border rank
KW - Commutative algebras
KW - Lower bounds
UR - http://www.scopus.com/inward/record.url?scp=85012910060&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2016.19
DO - 10.4230/LIPIcs.MFCS.2016.19
M3 - Article in proceedings
AN - SCOPUS:85012910060
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
A2 - Muscholl, Anca
A2 - Faliszewski, Piotr
A2 - Niedermeier, Rolf
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
CY - Saarbrücken/Wadern
T2 - 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
Y2 - 22 August 2016 through 26 August 2016
ER -
ID: 232711677