We present a practical algorithm for multiplication of two sparse matrices. In fact if A and B are two matrices of size n with m 1 and m 2 non-zero elements respectively, then our algorithm performs O(min{m 1 n, m 2 n, m 1 m 2}) multiplications and O(k) additions where k is the number of non-zero elements in the tiny matrices that are obtained by the columns times rows matrix multiplication method. Note that in the useful case, k ≤ m 2 n. However, in Proposition 3.3 and Proposition 3.4 we obtain tight upper bounds for the complexity of additions. We also study the complexity of multiplication in a practical case where non-zero elements of A (resp. B) are distributed independently with uniform distribution among columns (resp. rows) of them and show that the expected number of multiplications is O(m 1 m 2). Finally a comparison of number of required multiplications in the na?ve matrix multiplication, Strassen’s method and our algorithm is given.
展开▼
机译：我们提出了两个稀疏矩阵相乘的实用算法。实际上，如果A和B分别是大小为n的两个矩阵，分别具有m 1和m 2个非零元素，则我们的算法将执行O（min {m 1 n，m 2 n，m 1 m 2}）乘法和O（min k）加法，其中k是列乘行矩阵乘法方法所获得的微小矩阵中非零元素的数量。注意，在有用的情况下，k≤m 2 n。但是，在命题3.3和命题3.4中，我们为加法的复杂性获得了严格的上限。在实际情况下，我们还研究了乘法的复杂性，其中A的非零元素（resp。B）独立分布，并且它们的列（resp。行）之间均匀分布，并表明期望的乘法次数为O（m 1 m 2 / n）。最后，比较了朴素矩阵乘法，Strassen方法和我们的算法中所需乘法的数量。
展开▼
