Skew-sparse matrix multiplication

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^{ω-2} p^2)$, where $T\le p-1$ is a parameter determined by the skew-sparsity of input matrices and $ω$ is the asymptotic exponent of matrix multiplication. Moreover, by introducing randomness, we also propose a probabilistic algorithm with complexity $O^\thicksim(t^{ω-2}p^2+p^2\log\frac{1}ν)$, where $t\le p-1$ is the skew-sparsity of the product and $ν$ is the probability parameter.

No reviews yet.

No comments yet.