CODEWITHSUNDEEP
scipysparse-matrixmatrix-multiplication
piton_hunter
piton_hunter

Reputation: 89

Dot complexity for sparse matrix and vector for different formats

I want to understand why time for dot product of sparse matrix and dense vector is increasing: csr is fastest, then csc, coo, lil and dok (slowest). In other words I measure time of this programm for diferrent fmt:

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

I want to find source code of scipy for function of dot. It is easy for csr, coo and csc (csr_matvec, coo_matvec and csc_matvec - it should be third link, if I have had 10 reputaion =) ). But I cannot find such function for lil and dok. Could anybody answer how I can find it?

Upvotes: 2

Views: 660

Answers (1)

hpaulj
hpaulj

Reputation: 231375

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

Products for a lil format are performed by first converting to 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 does it's own. A dok is a subclass of 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

but for multiplication with another sparse matrix, it does the csr conversion.

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

Note that this last code is in base.py. This is where generic sparse code resides. If the format doesn't define its own method, it uses the base version.

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

coo also converts to csr for the full matrix product.

Upvotes: 3

Related Questions