不同格式的稀疏矩阵和向量的点复杂度

Question

我想了解为什么稀疏矩阵和密集向量的点积时间在增加：csr最快，然后是csc、coo、lil和dok（最慢）。换句话说，我针对不同的 fmt:

测量了该程序的时间

A = scipy.sparse.random(1000, 1000, format=fmt)
b = np.random.randn(1000, 1)
res = %timeit -o A * b

我想找到 scipy 的点功能的源代码。 csr、coo 和 csc 很容易（csr_matvec, coo_matvec 和 csc_matvec - 它应该是第三个 link，如果我有 10 个声誉=））。但是我找不到 lil 和 dok 这样的函数。谁能回答我如何找到它？

Answer 1

In [298]: M=sparse.coo_matrix(np.eye(3))

lil 格式的产品首先转换为 csr:

In [299]: Ml=M.tolil()
In [300]: Ml._mul_vector??
Signature: Ml._mul_vector(other)
Source:   
    def _mul_vector(self, other):
        return self.tocsr()._mul_vector(other)
File:      /usr/lib/python3/dist-packages/scipy/sparse/base.py
Type:      method

dok 是它自己的。 dok 是 dict.

的子类

In [303]: Md=M.todok()
In [304]: Md._mul_vector??
Signature: Md._mul_vector(other)
Source:   
    def _mul_vector(self, other):
        # matrix * vector
        result = np.zeros(self.shape[0], dtype=upcast(self.dtype,other.dtype))
        for (i,j),v in iteritems(self):
            result[i] += v * other[j]
        return result
File:      /usr/lib/python3/dist-packages/scipy/sparse/dok.py

但对于与另一个稀疏矩阵的乘法，它会进行 csr 转换。

In [305]: Md._mul_sparse_matrix??
Signature: Md._mul_sparse_matrix(other)
Source:   
    def _mul_sparse_matrix(self, other):
        return self.tocsr()._mul_sparse_matrix(other)
File:      /usr/lib/python3/dist-packages/scipy/sparse/base.py

请注意，最后一个代码在 base.py 中。这是通用稀疏代码所在的位置。如果格式没有定义自己的方法，则使用基本版本。

In [306]: Md.__class__.__mro__
Out[306]: 
(scipy.sparse.dok.dok_matrix,
 scipy.sparse.base.spmatrix,
 scipy.sparse.sputils.IndexMixin,
 dict,
 object)

coo 也转换为 csr 全矩阵乘积。

不同格式的稀疏矩阵和向量的点复杂度

Dot complexity for sparse matrix and vector for different formats

scipy

sparse-matrix

matrix-multiplication