Equivalent polyadic decompositions of matrix multiplication tensors

DOI10.1016/J.CAM.2021.113941zbMATH Open1486.15030arXiv1902.03950OpenAlexW3217647593WikidataQ114201950 ScholiaQ114201950MaRDI QIDQ2074879FDOQ2074879

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)

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.

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

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

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)

Cites Work

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

Cited In (6)

• On the order of approximation in approximative triadic decompositions of tensors
• 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)