Based on the observation that \mathbb{Q}^{(p-1) \times (p-1)} is isomorphic to a quotient skew polynomial ring, we propose a new deterministic algorithm for (p-1)\times(p-1) matrix multiplication over \mathbb{Q}, where p is a prime number. The algorithm has complexity O(T^{\omega-2} p^2), where T\le p-1 is a parameter determined by the skew-polynomial-sparsity of input matrices and \omega is the asymptotic exponent of matrix multiplication. Here a matrix is skew-polynomial-sparse if its corresponding skew polynomial is sparse. Moreover, by introducing randomness, we also propose a probabilistic algorithm with complexity O^\thicksim(t^{\omega-2}p^2+p^2\log\frac{1}{\nu}), where t\le p-1 is the skew-polynomial-sparsity of the product and \nu is the probability parameter. The main feature of the algorithms is the acceleration for matrix multiplication if the input matrices or their products are skew-polynomial-sparse.  

　　Publication:  

　　Journal of Symbolic Computation, Volume 121, March–April 2024, 102240  

　　http://dx.doi.org/10.1016/j.jsc.2023.102240  

　　Author:  

　　Qiao-Long Huang  

　　School of Mathematics, Shandong University, China  

　　Ke Ye  

　　KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, China  

　　University of Chinese Academy of Sciences, China  

　　Email: keyk@amss.ac.cn  

　　Xiao-Shan Gao  

　　KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, China  

　　University of Chinese Academy of Sciences, China  

　　Email: xgao@mmrc.iss.ac.cn