Rank and border rank of Kronecker powers of tensors and Strassen's laser method
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Rank and border rank of Kronecker powers of tensors and Strassen's laser method. / Conner, Austin; Gesmundo, Fulvio; Landsberg, Joseph M.; Ventura, Emanuele.
I: Computational Complexity, Bind 31, Nr. 1, 1, 06.2022, s. 1-40.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Rank and border rank of Kronecker powers of tensors and Strassen's laser method
AU - Conner, Austin
AU - Gesmundo, Fulvio
AU - Landsberg, Joseph M.
AU - Ventura, Emanuele
N1 - Publisher Copyright: © 2021, The Author(s).
PY - 2022/6
Y1 - 2022/6
N2 - We prove that the border rank of the Kronecker square of the little Coppersmith–Winograd tensor Tcw,q is the square of its border rank for q> 2 and that the border rank of its Kronecker cube is the cube of its border rank for q> 4. This answers questions raised implicitly by Coppersmith & Winograd (1990, §11)and explicitly by Bläser (2013, Problem 9.8) and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith–Winograd tensor in this range. In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen's laser method, introducing a skew-symmetric version of the Coppersmith–Winograd tensor, Tskewcw,q. For q= 2 , the Kronecker square of this tensor coincides with the 3 × 3 determinant polynomial, det 3∈ C9⊗ C9⊗ C9, regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two. We determine new upper bounds for the (Waring) rank and the (Waring) border rank of det 3, exhibiting a strict submultiplicative behaviour for Tskewcw,2 which is promising 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 C3⊗ C3⊗ C3.
AB - We prove that the border rank of the Kronecker square of the little Coppersmith–Winograd tensor Tcw,q is the square of its border rank for q> 2 and that the border rank of its Kronecker cube is the cube of its border rank for q> 4. This answers questions raised implicitly by Coppersmith & Winograd (1990, §11)and explicitly by Bläser (2013, Problem 9.8) and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith–Winograd tensor in this range. In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen's laser method, introducing a skew-symmetric version of the Coppersmith–Winograd tensor, Tskewcw,q. For q= 2 , the Kronecker square of this tensor coincides with the 3 × 3 determinant polynomial, det 3∈ C9⊗ C9⊗ C9, regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two. We determine new upper bounds for the (Waring) rank and the (Waring) border rank of det 3, exhibiting a strict submultiplicative behaviour for Tskewcw,2 which is promising 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 C3⊗ C3⊗ C3.
KW - 14L30
KW - 15A69
KW - 68Q17
KW - Asymptotic rank
KW - Lasermethod
KW - Matrix multiplication complexity
KW - Tensor rank
UR - http://www.scopus.com/inward/record.url?scp=85121452581&partnerID=8YFLogxK
U2 - 10.1007/s00037-021-00217-y
DO - 10.1007/s00037-021-00217-y
M3 - Journal article
AN - SCOPUS:85121452581
VL - 31
SP - 1
EP - 40
JO - Computational Complexity
JF - Computational Complexity
SN - 1016-3328
IS - 1
M1 - 1
ER -
ID: 343168440