文件名称：Fast sparse matrix multiplication
文件大小：184KB
文件格式：PDF
更新时间：2014-07-19 11:20:24
Fast sparse matrix multiplication
最快的稀疏矩阵乘法运算，英文版 Let A and B two n £ n matrices over a ring R (e.g., the reals or the integers) each containing at most m non-zero elements. We present a new algorithm that multiplies A and B using O(m0:7n1:2 + n2+o(1)) algebraic operations (i.e., multiplications, additions and subtractions) over R. The naive matrix multiplication algorithm, on the other hand, may need to perform (mn) operations to accomplish the same task. For m · n1:14, the new algorithm performs an almost optimal number of only n2+o(1) operations. For m · n1:68, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O(n2:38) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.