On the Geometry of Border Rank Decompositions for Matrix Multiplication and Other Tensors with Symmetry

DOI10.1137/16M1067457zbMATH Open1365.15034arXiv1601.08229MaRDI QIDQ5347291FDOQ5347291

Mateusz Michalek, J. M. Landsberg

Publication date: 23 May 2017

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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.

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

zbMATH Keywords

tensordeterminantnormal formscommuting matricesborder rankmatrix multiplication complexityStrassen's equations

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Power sums, Gorenstein algebras, and determinantal loci. With an appendix `The Gotzmann theorems and the Hilbert scheme' by Anthony Iarrobino and Steven L. Kleiman
• Gaussian elimination is not optimal
• Title not available (Why is that?)
• Title not available (Why is that?)
• A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
• Title not available (Why is that?)
• Description de Hilb sup(n) C{X,Y}
• Real and complex Waring rank of reducible cubic forms
• On the ranks and border ranks of symmetric tensors
• Geometric aspects of iterated matrix multiplication
• On the projective geometry of rational homogeneous varieties
• New Lower Bounds for the Rank of Matrix Multiplication
• On the rank of a symmetric form
• Algebraic geometry and local differential geometry
• Rank and optimal computation of generic tensors
• New lower bounds for the border rank of matrix multiplication
• A note on border rank
• Determinantal equations for secant varieties and the Eisenbud-Koh-Stillman conjecture
• On the third secant variety
• Relations between exact and approximate bilinear algorithms. Applications
• On the complexity of the multiplication of matrices of small formats
• The bilinear complexity and practical algorithms for matrix multiplication
• The border rank of the multiplication of $2\times 2$ matrices is seven
• Equations for Lower Bounds on Border Rank
• Abelian tensors
• Constructions of \(k\)-regular maps using finite local schemes
• On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
• Examples of \(k\)-regular maps and interpolation spaces
• Explicit Tensors
• Local finite-dimensional Gorenstein \(k\)-algebras having Hilbert function (1,5,5,1) are smoothable

Cited In (21)

• Finite mixtures, projection pursuit and tensor rank: a triangulation
• Title not available (Why is that?)
• Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity
• Equivalent polyadic decompositions of matrix multiplication tensors
• Examples of \(k\)-regular maps and interpolation spaces
• Border Rank Nonadditivity for Higher Order Tensors
• Real rank boundaries and loci of forms
• On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
• An introduction to the computational complexity of matrix multiplication
• On the structure tensor of \(\mathfrak{sl}_n\)
• Abelian tensors
• Computing images of polynomial maps
• Apolarity, border rank, and multigraded Hilbert scheme
• 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
• Spaces of sums of powers and real rank boundaries
• New lower bounds for matrix multiplication and
• Plethysm and fast matrix multiplication
• A Counterexample to Comon's Conjecture
• Tensor and border rank of certain classes of matrices and the fast evaluation of determinant, inverse matrix, and eigenvalues
• Rank decomposition and symmetric rank decomposition over arbitrary fields

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)