Skew-sparse matrix multiplication

Abstract

Based on the observation that ${\mathbb{Q}}^{(p-1)\times (p-1)}$ is isomorphic to a quotient skew polynomial ring, we propose a new method for $(p-1)\times (p-1)$ matrix multiplication over $\mathbb{Q}$, 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 $T\le p-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^{\sim }(t^{\omega -2}{p}^2+p^2\log \frac{1}{\nu })$, where $t\le p-1$ is the skew-sparsity of the product and $\nu$ is the probability parameter.