Equivalent polyadic decompositions of matrix multiplication tensors

DOI10.1016/J.CAM.2021.113941MaRDI QIDQ2074879zbMATH OpenOpenAlexWikidataFDO

Authors Guillaume O. Berger, Lieven De Lathauwer, Raphaël M. Jungers, Marc van Barel, P.-A. Absil

Publication date 11 February 2022

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.03950, https://lirias.kuleuven.be/handle/123456789/634447

zbMATH Keywords

eigenvalue decompositionfast matrix multiplicationpolyadic tensor decompositions

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Symbolic computation and algebraic computation (68W30) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: Invariance transformations of polyadic decompositions of matrix multiplication tensors define an equivalence relation on the set of such decompositions. In this paper, we present an algorithm to efficiently decide whether two polyadic decompositions of a given matrix multiplication tensor are equivalent. With this algorithm, we analyze the equivalence classes of decompositions of several matrix multiplication tensors. This analysis is relevant for the study of fast matrix multiplication as it relates to the question of how many essentially different fast matrix multiplication algorithms there exist. This question has been first studied by de~Groote, who showed that for the multiplication of $2imes2$ matrices with $7$ active multiplications, all algorithms are essentially equivalent to Strassen's algorithm. In contrast, the results of our analysis show that for the multiplication of larger matrices, (e.g., $2imes3$ by $3imes2$ or $3imes3$ by $3imes3$ matrices), two decompositions are very likely to be essentially different. We further provide a necessary criterion for a polyadic decomposition to be equivalent to a polyadic decomposition with integer entries. Decompositions with specific integer entries, e.g., powers of two, provide fast matrix multiplication algorithms with better efficiency and stability properties. This condition can be tested algorithmically and we present the conclusions obtained for the decompositions of small/medium matrix multiplication tensors.

Recommendations

• Decomposition Algorithms for Tensors and Polynomials
• Generalized canonical polyadic tensor decomposition
• A decomposition of the tensor product of matrices
• Tensor decompositions in rank \(+1\)
• Recursive decomposition of multidimensional tensors
• Decoupling multivariate polynomials: interconnections between tensorizations
• Complete decomposition of symmetric tensors in linear time and polylogarithmic precision
• Computing the polyadic decomposition of nonnegative third order tensors
• A constructive approach to tensor product decompositions.
• Multiplications and eigenvalues of tensors via linear maps

Cites work

• A non-commutative algorithm for multiplying 5 × 5 matrices using one hundred multiplications
• A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
• An algorithm for multiplying 3×3 matrices
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Gaussian elimination is not optimal
• Improving the numerical stability of fast matrix multiplication
• New Fast Algorithms for Matrix Operations
• Noncommutative Bilinear Algorithms for $3 \times 3$ Matrix Multiplication
• Numerical CP decomposition of some difficult tensors
• On bilinear complexity of multiplication of \(m\times 2\) and \(2\times 2\) matrices
• On the Asymptotic Complexity of Matrix Multiplication
• On the complexity of the multiplication of matrices of small formats
• On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry
• On the inequivalence of bilinear algorithms for \(3\times 3\) matrix multiplication
• On the optimal evaluation of a set of bilinear forms
• On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping
• On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for \(2\times 2\)-matrix multiplication
• Partial and Total Matrix Multiplication
• Powers of tensors and fast matrix multiplication
• Tensor Decompositions and Applications
• The bilinear complexity and practical algorithms for matrix multiplication
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication

Cited in

(7)

• On the order of approximation in approximative triadic decompositions of tensors
• The geometry of rank decompositions of matrix multiplication. II: \(3 \times 3\) matrices
• Atomic decompositions for tensor products and polynomial spaces
• Finding complex-valued solutions of brent equations using nonlinear least squares
• Semi-analytical solution of Brent equations
• The Geometry of Rank Decompositions of Matrix Multiplication I: 2 × 2 Matrices
• A normal form for matrix multiplication schemes

This page was built for publication: Equivalent polyadic decompositions of matrix multiplication tensors

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