Numpy: smart matrix multiplication by sparse result matrix

Question

In python with numpy, let's say I have two matrices:

• Ssparse matrix x*x
• Mdense matrix x*y

Now I want to do np.dot(M, M.T)which will return a dense matrix x*x S_.

However, I don’t care that the cells are non-zero in S, which means that this will not affect my application if I did

S_ = S*S_

Obviously, this would be a waste of operations, since I would like to leave all the inappropriate cells listed in Salltogether. Remember that when multiplying the matrix

S_[i,j] = np.sum(M[i,:]*M[:,j])

So, I want to do this operation only i,jto S[i,j]=True.

Is this supported in some way with numpy implementations that run in C, so that I don't need to implement it with python loops?

---

EDIT: I still have this problem, actually Mnow also sparse.

Now, if rows and columns are given S, I implemented it as follows:

data = np.array([ M[rows[i],:].dot(M[cols[i],:]).data[0] for i in xrange(len(rows)) ])
S_   = csr( (data, (rows,cols)) )

... but he is still slow. Any new ideas?

Answer 1

Here's how you can do it with NumPy / SciPy, for both dense and sparse matrices M:

import numpy as np
import scipy.sparse as sp

# Coordinates where S is True
S = np.array([[0, 1],
              [3, 6],
              [3, 4],
              [9, 1],
              [4, 7]])

# Dense M matrix
# Random big matrix
M = np.random.random(size=(1000, 2000))
# Take relevant rows and compute values
values = np.sum(M[S[:, 0]] * M[S[:, 1]], axis=1)
# Make result matrix from values
result = np.zeros((len(M), len(M)), dtype=values.dtype)
result[S[:, 0], S[:, 1]] = values

# Sparse M matrix
# Construct sparse M as COO matrix or any other way
M = sp.coo_matrix(([10, 20, 30, 40, 50],  # Data
                   ([0, 1, 3, 4, 6],      # Rows
                    [4, 4, 5, 5, 8])),    # Columns
                  shape=(1000, 2000))
# Convert to CSR for fast row slicing
M_csr = M.tocsr()
# Take relevant rows and compute values
values = M_csr[S[:, 0]].multiply(M_csr[S[:, 1]]).sum(axis=1)
values = np.squeeze(np.asarray(values))
# Construct COO sparse matrix from values
result = sp.coo_matrix((values, (S[:, 0], S[:, 1])), shape=(M.shape[0], M.shape[0]))