On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry
From MaRDI portal
Publication:5347291
tensordeterminantnormal formscommuting matricesborder rankmatrix multiplication complexityStrassen's equations
Multilinear algebra, tensor calculus (15A69) Determinants, permanents, traces, other special matrix functions (15A15) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Vector spaces, linear dependence, rank, lineability (15A03) Homogeneous spaces and generalizations (14M17)
Abstract: We establish basic information about border rank algorithms for the matrix multiplication tensor and other tensors with symmetry. We prove that border rank algorithms for tensors with symmetry (such as matrix multiplication and the determinant polynomial) come in families that include representatives with normal forms. These normal forms will be useful both to develop new efficient algorithms and to prove lower complexity bounds. We derive a border rank version of the substitution method used in proving lower bounds for tensor rank. We use this border-substitution method and a normal form to improve the lower bound on the border rank of matrix multiplication by one, to 2n^2- n+1. We also point out difficulties that will be formidable obstacles to future progress on lower complexity bounds for tensors because of the "wild" structure of the Hilbert scheme of points.
Recommendations
Cites work
- scientific article; zbMATH DE number 5968745 (Why is no real title available?)
- scientific article; zbMATH DE number 436950 (Why is no real title available?)
- scientific article; zbMATH DE number 1820149 (Why is no real title available?)
- scientific article; zbMATH DE number 3572315 (Why is no real title available?)
- scientific article; zbMATH DE number 2038305 (Why is no real title available?)
- A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
- A note on border rank
- Abelian tensors
- Algebraic geometry and local differential geometry
- Constructions of \(k\)-regular maps using finite local schemes
- Description de Hilb sup(n) C{X,Y}
- Determinantal equations for secant varieties and the Eisenbud-Koh-Stillman conjecture
- Equations for lower bounds on border rank
- Examples of \(k\)-regular maps and interpolation spaces
- Explicit tensors
- Gaussian elimination is not optimal
- Geometric aspects of iterated matrix multiplication
- Local finite-dimensional Gorenstein \(k\)-algebras having Hilbert function (1,5,5,1) are smoothable
- New lower bounds for the border rank of matrix multiplication
- New lower bounds for the rank of matrix multiplication
- On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
- On the complexity of the multiplication of matrices of small formats
- On the projective geometry of rational homogeneous varieties
- On the rank of a symmetric form
- On the ranks and border ranks of symmetric tensors
- On the third secant variety
- Power sums, Gorenstein algebras, and determinantal loci. With an appendix `The Gotzmann theorems and the Hilbert scheme' by Anthony Iarrobino and Steven L. Kleiman
- Rank and optimal computation of generic tensors
- Real and complex Waring rank of reducible cubic forms
- Relations between exact and approximate bilinear algorithms. Applications
- The bilinear complexity and practical algorithms for matrix multiplication
- The border rank of the multiplication of $2\times 2$ matrices is seven
Cited in
(28)- Tensor and border rank of certain classes of matrices and the fast evaluation of determinant, inverse matrix, and eigenvalues
- On the geometry of geometric rank
- An introduction to the computational complexity of matrix multiplication
- Border Rank Nonadditivity for Higher Order Tensors
- Geometric complexity theory and tensor rank
- Abelian tensors
- Finite mixtures, projection pursuit and tensor rank: a triangulation
- On degeneration of tensors and algebras
- Geometry and the complexity of matrix multiplication
- Explicit lower bounds via geometric complexity theory
- Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity
- Apolarity, border rank, and multigraded Hilbert scheme
- Computing images of polynomial maps
- A counterexample to Comon's conjecture
- Equivalent polyadic decompositions of matrix multiplication tensors
- On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
- scientific article; zbMATH DE number 7689792 (Why is no real title available?)
- On the structure tensor of \(\mathfrak{sl}_n\)
- Real rank boundaries and loci of forms
- Rank decomposition and symmetric rank decomposition over arbitrary fields
- On Comon's conjecture over arbitrary fields
- Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
- Partial Degeneration of Tensors
- The geometry of rank decompositions of matrix multiplication. II: \(3 \times 3\) matrices
- Spaces of sums of powers and real rank boundaries
- Examples of \(k\)-regular maps and interpolation spaces
- New lower bounds for matrix multiplication and
- Plethysm and fast matrix multiplication
This page was built for publication: On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5347291)
