Fast structured matrix computations: tensor rank and Cohn-Umans method
From MaRDI portal
Publication:1704813
bilinear complexityCohn-Umans methodsparse and structured matricesstabilitystructured matrix-vector producttensor nuclear normtensor rank
Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Multilinear algebra, tensor calculus (15A69) Toeplitz, Cauchy, and related matrices (15B05) Representations of group algebras (22D20) Computational methods for sparse matrices (65F50) Numerical linear algebra (65F99) Complexity and performance of numerical algorithms (65Y20)
Abstract: We discuss a generalization of the Cohn-Umans method, a potent technique developed for studying the bilinear complexity of matrix multiplication by embedding matrices into an appropriate group algebra. We investigate how the Cohn-Umans method may be used for bilinear operations other than matrix multiplication, with algebras other than group algebras, and we relate it to Strassen's tensor rank approach, the traditional framework for investigating bilinear complexity. To demonstrate the utility of the generalized method, we apply it to find the fastest algorithms for forming structured matrix-vector product, the basic operation underlying iterative algorithms for structured matrices. The structures we study include Toeplitz, Hankel, circulant, symmetric, skew-symmetric, f-circulant, block-Toeplitz-Toeplitz-block, triangular Toeplitz matrices, Toeplitz-plus-Hankel, sparse/banded/triangular. Except for the case of skew-symmetric matrices, for which we have only upper bounds, the algorithms derived using the generalized Cohn-Umans method in all other instances are the fastest possible in the sense of having minimum bilinear complexity. We also apply this framework to a few other bilinear operations including matrix-matrix, commutator, simultaneous matrix products, and briefly discuss the relation between tensor nuclear norm and numerical stability.
Recommendations
- Fast low rank approximations of matrices and tensors
- Structured Matrix Approximations via Tensor Decompositions
- Fast computation of low rank matrix approximations
- Fast matrix rank algorithms and applications
- Fast matrix rank algorithms and applications
- Fast Multilinear Singular Value Decomposition for Structured Tensors
- Rank-one approximation to high order tensors
- Fast computation of low-rank matrix approximations
- Rank properties and computational methods for orthogonal tensor decompositions
- Numerical computation for orthogonal low-rank approximation of tensors
Cites work
- Accuracy and Stability of Numerical Algorithms
- An Algorithm for the Machine Calculation of Complex Fourier Series
- An Introduction to Iterative Toeplitz Solvers
- Computational Complexity and Numerical Stability
- Every matrix is a product of Toeplitz matrices
- Fast matrix multiplication is stable
- Fast matrix multiplication using coherent configurations
- Fast multiplication of large numbers
- Faster integer multiplication
- Functions of Difference Matrices Are Toeplitz Plus Hankel
- Functions of Matrices
- Gaussian elimination is not optimal
- Generalized Displacement Structure for Block-Toeplitz, Toeplitz-Block, and Toeplitz-Derived Matrices
- scientific article; zbMATH DE number 1682655 (Why is no real title available?)
- scientific article; zbMATH DE number 5968745 (Why is no real title available?)
- scientific article; zbMATH DE number 3650737 (Why is no real title available?)
- scientific article; zbMATH DE number 107777 (Why is no real title available?)
- scientific article; zbMATH DE number 3461412 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 1796829 (Why is no real title available?)
- scientific article; zbMATH DE number 2118874 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 3322464 (Why is no real title available?)
- Matrix multiplication via arithmetic progressions
- Multiplying matrices faster than coppersmith-winograd
- Noncommutative Noetherian rings. With the cooperation of L. W. Small.
- Nuclear norm of higher-order tensors
- Partial and Total Matrix Multiplication
- Powers of tensors and fast matrix multiplication
- Rank and optimal computation of generic tensors
- Ranks of tensors and a generalization of secant varieties
- Relative bilinear complexity and matrix multiplication.
- Some bilinear forms whose multiplicative complexity depends on the field of constants
- Stability of a Method for Multiplying Complex Matrices with Three Real Matrix Multiplications
- Tensor Rank and Border Rank of Band Toeplitz Matrices
- Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
- The Matrix Eigenvalue Problem
- The ubiquitous Kronecker product
Cited in
(16)- Tensor and border rank of certain classes of matrices and the fast evaluation of determinant, inverse matrix, and eigenvalues
- Uniform matrix product states from an algebraic geometer's point of view
- Fast bilinear algorithms for symmetric tensor contractions
- Grothendieck constant is norm of Strassen matrix multiplication tensor
- Fast low rank approximations of matrices and tensors
- Efficient Computation of Higher-Order Cumulant Tensors
- Nuclear norm of higher-order tensors
- On the tensor rank of the \(3 \times 3\) permanent and determinant
- Hankel Tensor Decompositions and Ranks
- Tensors in computations
- Skew-polynomial-sparse matrix multiplication
- Numerical stability and tensor nuclear norm
- Learning polynomial transformations via generalized tensor decompositions
- Generalizing Frobenius inversion to quaternion matrices
- Complex matrix inversion via real matrix inversions
- xPerm: fast index canonicalization for tensor computer algebra
This page was built for publication: Fast structured matrix computations: tensor rank and Cohn-Umans method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704813)
