Fast structured matrix computations: tensor rank and Cohn-Umans method

DOI10.1007/s10208-016-9332-xzbMath1454.65030arXiv1601.00292OpenAlexW2964309316MaRDI QIDQ1704813

Ke Ye, Lek-Heng Lim

Publication date: 13 March 2018

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

stabilitytensor rankbilinear complexityCohn-Umans methodsparse and structured matricesstructured matrix-vector producttensor nuclear norm

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Multilinear algebra, tensor calculus (15A69) Numerical linear algebra (65F99) Representations of group algebras (22D20) Toeplitz, Cauchy, and related matrices (15B05) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Related Items (9)

Tensors in computations ⋮ On the tensor rank of $3\times 3$ permanent and determinant ⋮ Skew-polynomial-sparse matrix multiplication ⋮ Numerical stability and tensor nuclear norm ⋮ Nuclear norm of higher-order tensors ⋮ Hankel Tensor Decompositions and Ranks ⋮ Fast bilinear algorithms for symmetric tensor contractions ⋮ Uniform matrix product states from an algebraic geometer's point of view ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor

Uses Software

• mctoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Every matrix is a product of Toeplitz matrices
• Fast matrix multiplication is stable
• Matrix multiplication via arithmetic progressions
• Rank and optimal computation of generic tensors
• The ubiquitous Kronecker product
• Ranks of tensors and a generalization of secant varieties
• Gaussian elimination is not optimal
• Fast multiplication of large numbers
• Functions of Difference Matrices Are Toeplitz Plus Hankel
• Powers of tensors and fast matrix multiplication
• Faster Integer Multiplication
• Relative bilinear complexity and matrix multiplication.
• Partial and Total Matrix Multiplication
• Stability of a Method for Multiplying Complex Matrices with Three Real Matrix Multiplications
• Computational Complexity and Numerical Stability
• Some bilinear forms whose multiplicative complexity depends on the field of constants
• Generalized Displacement Structure for Block-Toeplitz, Toeplitz-Block, and Toeplitz-Derived Matrices
• Nuclear norm of higher-order tensors
• Tensor Rank and Border Rank of Band Toeplitz Matrices
• Accuracy and Stability of Numerical Algorithms
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Multiplying matrices faster than coppersmith-winograd
• An Introduction to Iterative Toeplitz Solvers
• The Matrix Eigenvalue Problem
• Functions of Matrices
• Fast matrix multiplication using coherent configurations

This page was built for publication: Fast structured matrix computations: tensor rank and Cohn-Umans method