Skew-polynomial-sparse matrix multiplication
Skew-polynomial-sparse matrix multiplication
复制标题
斜多项式稀疏矩阵乘法
DOI：
10.1016/j.jsc.2023.102240
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Xiao
中科院分区：
文献类型：
--
作者：
Qiao;Ke Ye;Xiao
基于Q（p− 1）×（p− 1）同构于商斜多项式环的观察，提出了Q上（p− 1）×（p− 1）矩阵乘法的一个新的确定性算法，其中p为素数.该算法的复杂度为O（T ω− 2 p 2），其中T≤ p− 1是由输入矩阵的斜多项式稀疏性决定的参数，ω是矩阵乘法的渐近指数。这里矩阵是斜多项式稀疏的，如果它对应的斜多项式是稀疏的。此外，通过引入随机性，我们还提出了一个复杂度为O <$（t ω− 2 p 2+ p 2 log <$1 ν）的概率算法，其中t≤ p− 1是乘积的斜多项式稀疏性，ν是概率参数。该算法的主要特点是当输入矩阵或其乘积为斜多项式稀疏矩阵时，可加速矩阵乘法运算。
Based on the observation that Q (p− 1)×(p− 1) is isomorphic to a quotient skew polynomial ring, we propose a new deterministic algorithm for (p− 1)×(p− 1) matrix multiplication over Q, where p is a prime number. The algorithm has complexity O (T ω− 2 p 2), where T≤ p− 1 is a parameter determined by the skew-polynomial-sparsity of input matrices and ω 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∼(t ω− 2 p 2+ p 2 log 1 ν), where t≤ p− 1 is the skew-polynomial-sparsity of the product and ν 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.
DOI：
10.1109/micro50266.2020.00068
发表时间：
2020-10
期刊：
2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)
影响因子：
--
作者：
Nitish Srivastava;Hanchen Jin;Jie Liu-;D. Albonesi;Zhiru Zhang
通讯作者：
Nitish Srivastava;Hanchen Jin;Jie Liu-;D. Albonesi;Zhiru Zhang