Complicated matrix multiplication

Question

I have a (dense) matrix n x n x m and a sparse vector (scipy.sparse) 1 x m. If we look at my dense n x n x m matrix it could be interpreted as an n x n matrix with on each position a m x 1 vector. Now I want to compute the dot product of my sparse vector with each of the m x 1 dense vectors in the n x n matrix yielding a n x n matrix with all these dot products.

One way to do this is to build a for loop to loop through the n x n matrix and then use the .dot() function of scipy.sparse to compute the dot products with each vector in the matrix. However, I'm looking for a way to perform this calculation completely in a vectorized way for efficiency. Is this possible? If not, what's the fastest way in Python to loop through my n x n matrix?

If your n*n matrix is dense then it will not matter how you loop because you need to compute the dot product with each one of n^2 elements. So a double for loop will work just fine. — Sanjeev Kumar

Unknown Unknown · Accepted Answer · 2016-05-18T13:58:48

You could make the vector dense and use dot or einsum:

ans = arr.dot(vec.A.T)
# or
ans = numpy.einsum('ijk,k->ij', arr, vec.A.squeeze())

If the vector is very sparse, it's probably worthwile to first select items from the array corresponding to the nonzeros in the vector:

ans = arr[...,vec.nonzero()[1]].dot(vec.data)

For very large data it may be faster to use tensordot instead of dot, because it's more likely to call into a BLAS function:

ans = numpy.tensordot(arr, vec.A.T, 1)
# or, for a very sparse vec:
ans = numpy.tensordot(arr[...,vec.nonzero()[1]], vec.data, 1)

Complicated matrix multiplication

1 Answers