A note on border rank
Approximative bilinear algorithms play an important role in the investigation of the complexity of matrix multiplication. In this paper the lower bound \(rk<n,n,n>\geq(3/2)n^ 2+n/2-1\) for the border rank \((=\) approximative bilinear complexity) of the structural tensor \(<n,n,n>\) of \(n\times n\) matrix multiplication is given. This result is based on a description of the algebraic variety \(X_ r=\{t:rk t\leq r\}\) of tensors of border rank \(\leq r\) by a certain existential condition. As another application of the given description of \(X_ r\) it can be shown that larger matrix multiplications always have larger approximative bilinear complexity, i.e., \(rk<n_ 1,n_ 2,n_ 3><rk<n_ 1,n_ 2,n_ 3+1>.\)
- A \(2\mathbf{n}^2-\log_2(\mathbf{n})-1\) lower bound for the border rank of matrix multiplication
- New lower bounds for the border rank of matrix multiplication
- A lower bound for the border rank of a bilinear map
- On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
- Equations for lower bounds on border rank
- \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
- Further Pathologies in Algebraic Geometry
- scientific article; zbMATH DE number 3530031 (Why is no real title available?)
- scientific article; zbMATH DE number 3222940 (Why is no real title available?)
- On the Asymptotic Complexity of Matrix Multiplication
- Partial and Total Matrix Multiplication
- Rank and optimal computation of generic tensors
- Typical tensorial rank
- A lower bound for the border rank of a bilinear map
- On the order of approximation in approximative triadic decompositions of tensors
- An introduction to the computational complexity of matrix multiplication
- Nontriviality of equations and explicit tensors in \(\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m\) of border rank at least \(2m - 2\)
- Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
- New lower bounds for the border rank of matrix multiplication
- The border rank of the multiplication of 2\times 2 matrices is seven
- Geometry and the complexity of matrix multiplication
- Tensor rank: matching polynomials and Schur rings
- On degeneration of tensors and algebras
- A \(2\mathbf{n}^2-\log_2(\mathbf{n})-1\) lower bound for the border rank of matrix multiplication
- On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
- On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry
- Equations for lower bounds on border rank
- Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity
- New lower bounds for matrix multiplication and
- A refined laser method and faster matrix multiplication
- The tensor Rank of \(5 \times 5\) matrices multiplication is bounded by 98 andits border Rank by 89
- Tensor rank and complexity
- On commutativity and approximation
This page was built for publication: A note on border rank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794161)
