Skew-polynomial-sparse matrix multiplication

DOI10.1016/J.JSC.2023.102240MaRDI QIDQ6051113zbMATH OpenFDO

Authors

Publication date 19 September 2023

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

fast algorithmcomplexitymatrix multiplicationstructured matrixskew polynomials

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Numerical linear algebra (65Fxx)

Abstract: Based on the observation that $mathbb{Q}^{(p-1)imes(p-1)}$ is isomorphic to a quotient skew polynomial ring, we propose a new method for $(p-1)imes(p-1)$ matrix multiplication over $mathbbQ$, where $p$ is a prime number. The main feature of our method is the acceleration for matrix multiplication if the product is skew-sparse. Based on the new method, we design a deterministic algorithm with complexity $O(T^{omega-2}{p}^2)$, where $Tlep-1$ is a parameter determined by the skew-sparsity of input matrices and $omega$ is the asymptotic exponent of matrix multiplication. Moreover, by introducing randomness, we also propose a probabilistic algorithm with complexity $O^{h}icksim(t^{omega-2}{p}^2+p^{2}logfrac1u)$, where $tlep-1$ is the skew-sparsity of the product and $u$ is the probability parameter.

Cites work

• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• scientific article; zbMATH DE number 1350351 (Why is no real title available?)
• scientific article; zbMATH DE number 607286 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• A Class of Methods for Solving Nonlinear Simultaneous Equations
• A Fast Adaptive Multipole Algorithm for Particle Simulations
• A fast algorithm for particle simulations
• A two-pronged progress in structured dense matrix vector multiplication
• Algebraic Complexity Theory
• Computational methods of linear algebra
• Efficient determination of the transitive closure of a directed graph
• Fast Multiplication for Skew Polynomials
• Fast algorithm for sparse matrix multiplication
• Fast algorithms for the characteristic polynomial
• Fast bilinear algorithms for symmetric tensor contractions
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Fast sparse matrix multiplication
• Fast structured matrix computations: tensor rank and Cohn-Umans method
• Gaussian elimination is not optimal
• Hartmann-Tzeng bound and skew cyclic codes of designed Hamming distance
• Linear codes using skew polynomials with automorphisms and derivations
• Matrix multiplication via arithmetic progressions
• Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation
• Modern computer algebra
• Multiplying matrices faster than coppersmith-winograd
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
• On fast multiplication of polynomials over arbitrary algebras
• Partial and Total Matrix Multiplication
• Polynomials and the exponent of matrix multiplication
• Powers of tensors and fast matrix multiplication
• Probability and Computing
• Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox
• Solving sparse linear equations over finite fields
• Some properties of skew codes over finite fields
• Sparse multiplication for skew polynomials
• The ubiquitous Kronecker product
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition
• Ubiquity of the exponent of matrix multiplication
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication

Cited in

(1)

• A quasi-optimal lower bound for skew polynomial multiplication

This page was built for publication: Skew-polynomial-sparse matrix multiplication

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