Scipy quickly initialise sparse matrix from list of coordinates

Question

I want to initialise a sparse matrix (for use with scipy minimum_spanning_tree if that matters) from a list of matrix coordinates and values.

That is, I have:

coords - Nx2 array of coordinates to be set in matrix
values - Nx1 array of the values to set.

I have tried to use lil_matrix to create this array using

A = lil_matrix((N,N))
A[coords[:,0],coords[:,1]] = values

which is unbearably slow. It's actually faster to loop over the array and set each element one at at time. i.e.:

for i in xrange(N):
  A[coords[i,0],coords[i,1]] = values[i]

which is slightly faster than the above, but not much. Because the array is so large, creating an NxN array, setting values and then converting to sparse is not an option.

Is there are better way to do it or am I stuck with this being the slowest part of my algorithm?

Answer 1

LIL matrix is horribly slow because it's construction algorithm takes quadratic time. I don't understand why the SciPy docs still recommend it.

The easiest way to construct your matrix is using the COO (coordinate) format, which seems to fit your input data perfectly:

A = coo_matrix((values, coords.T))