9

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.

Improve this question
4
  • 1
    it's called triangular upper packed storage fiy. I do not think there are efficient ways to get entire column or row from triangular matrix. Commented Jun 24, 2010 at 4:44
  • 2
    M[i, j]==M[j, i] means that the matrix is symmetrical, not triangular. Commented Jun 24, 2010 at 7:50
  • @EOL Good point. Although according to the Wikipedia definition, this matrix is (upper) triangular too. Commented Jun 24, 2010 at 11:16
  • 1
    For your information: upper triangular is different from symmetrical: it means M[i, j<i] == 0, i.e. that the matrix has zeros in the lower left triangle… There are examples in the Wikipedia page on "Upper triangular" matrices. Commented Jun 25, 2010 at 7:13

1 Answer 1

Reset to default
2

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…

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I was afraid of that. Thanks, though.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.