Scipy sparse triangular matrix?

Question

Hi, I am using Scipy to construct a large, sparse (250k X 250k) co-occurrence matrix using scipy.sparse.lil_matrix. Co-occurrence matrices are triangular; that is, M[i,j] == M[j,i]. Since it would be highly inefficient (and in my case, impossible) to store all the data twice, I'm currently storing data at the coordinate (i,j) where i is always smaller than j. So in other words, I have a value stored at (2,3) and no value stored at (3,2), even though (3,2) in my model should be equal to (2,3). (See the matrix below for an example)

My problem is that I need to be able to randomly extract the data corresponding to a given index, but, at least the way, I'm currently doing it, half the data is in the row and half is in the column, like so:

M = 
    [1 2 3 4
     0 5 6 7
     0 0 8 9
     0 0 0 10]

So, given the above matrix, I want to be able to do a query like M[1], and get back [2,5,6,7]. I have two questions:

1) Is there a more efficient (preferably built-in) way to do this than first querying the row, and then the column, and then concatenating the two? This is bad because whether I use CSC (column-based) or CSR (row-based) internal representation, one of the two queries is highly inefficient.

2) Am I even using the right part of Scipy? I have seen a few functions in the Scipy library that mention triangular matrices, but they seem to revolve around getting triangular matrices from a full matrix. In my case, (I think) I already have a triangular matrix, and want to manipulate it.

Many thanks.

Answer 1

I would say that you can't have the cake and eat it too: if you want efficient storage, you cannot store full rows (as you say); if you want efficient row access, I'd say that you have to store full rows.

While real performances depend on your application, you could check whether the following approach works for you:

1. You use Scipy's sparse matrices for efficient storage.

2. You automatically symmetrize your matrix (there is a small recipe on StackOverflow, that works at least on regular matrices).

3. You can then access its rows (or columns); whether this is efficient depends on the implementation of sparse matrices…