Publication:2062866

DOI10.1007/S00037-021-00217-YzbMATH Open1493.14088arXiv1909.04785OpenAlexW4200136360WikidataQ114231713 ScholiaQ114231713MaRDI QIDQ2062866FDOQ2062866

Austin Conner, Emanuele Ventura, Fulvio Gesmundo, J. M. Landsberg

Publication date: 3 January 2022

Published in: Computational Complexity (Search for Journal in Brave)

Abstract: We prove that the border rank of the Kronecker square of the little Coppersmith-Winograd tensor $T_{cw,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 in [Coppersmith-Winograd, 1990] and explicitly in [Bl"aser, 2013] 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, $T_{skewcw,q}$. For $q=2$, the Kronecker square of this tensor coincides with the $3imes3$ determinant polynomial, $de{t}_{3}inmathbb{C}^{9}otimesmathbb{C}^{9}otimesmathbb{C}^9$, 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 $de{t}_3$, exhibiting a strict submultiplicative behaviour for $T_{skewcw,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 $mathbb{C}^{3}otimesmathbb{C}^{3}otimesmathbb{C}^3$.

Full work available at URL: https://arxiv.org/abs/1909.04785

zbMATH Keywords

tensor rankasymptotic rankmatrix multiplication complexitylaser method

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Group actions on varieties or schemes (quotients) (14L30) Secant varieties, tensor rank, varieties of sums of powers (14N07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Powers of tensors and fast matrix multiplication
• Factoring polynomials with rational coefficients
• Gaussian elimination is not optimal
• Relative bilinear complexity and matrix multiplication.
• Partial and Total Matrix Multiplication
• Multiplying matrices faster than coppersmith-winograd
• Matrix multiplication via arithmetic progressions
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Geometric complexity theory and matrix powering
• On the nuclear norm and the singular value decomposition of tensors
• Geometry and Complexity Theory
• Equations for secant varieties of Veronese and other varieties
• Rank and optimal computation of generic tensors
• New lower bounds for the border rank of matrix multiplication
• Relations between exact and approximate bilinear algorithms. Applications
• Approximate Solutions for the Bilinear Form Computational Problem
• Degeneration and complexity of bilinear maps: Some asymptotic spectra.
• The asymptotic spectrum of tensors.
• Barriers for Rank Methods in Arithmetic Complexity
• Characters of the Weyl group of SU(n) on zero weight spaces and centralizers of permutation representations
• On degeneration of tensors and algebras
• Further Limitations of the Known Approaches for Matrix Multiplication
• Product ranks of the \(3\times 3\) determinant and permanent
• On non-commutative rank and tensor rank
• Tensor rank is not multiplicative under the tensor product
• On the partially symmetric rank of tensor products of \(W\)-states and other symmetric tensors
• Towards a geometric approach to Strassen's asymptotic rank conjecture
• Fast Matrix Multiplication
• Barriers for fast matrix multiplication from irreversibility
• Border Rank Is Not Multiplicative under the Tensor Product

Cited In (12)

• Title not available (Why is that?)
• Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity
• Border Rank Nonadditivity for Higher Order Tensors
• Title not available (Why is that?)
• Tensor Rank and Border Rank of Band Toeplitz Matrices
• An improved upper bound for the Waring rank of the determinant
• On the structure tensor of \(\mathfrak{sl}_n\)
• Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
• New lower bounds for matrix multiplication and
• Approximate real symmetric tensor rank
• Tensor and border rank of certain classes of matrices and the fast evaluation of determinant, inverse matrix, and eigenvalues
• Partial Degeneration of Tensors

Uses Software

• Macaulay2
• SageMath

Recommendations

• Title not available (Why is that?) 👍 👎
• On the ranks and border ranks of symmetric tensors 👍 👎
• Tensor Rank and Border Rank of Band Toeplitz Matrices 👍 👎
• Bounds on the tensor rank 👍 👎
• An upper bound for the tensor rank 👍 👎
• Border rank of m\(\times n\times (mn-q)\) tensors 👍 👎
• Tensor and border rank of certain classes of matrices and the fast evaluation of determinant, inverse matrix, and eigenvalues 👍 👎
• On tensors of border rank \(l\) in \({\mathbb C}^{m\times n\times l}\) 👍 👎
• Bounds on strongly orthogonal ranks of tensors 👍 👎
• Border Rank Nonadditivity for Higher Order Tensors 👍 👎

This page was built for publication: Rank and border rank of Kronecker powers of tensors and Strassen's laser method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2062866)