Not sure if I understand the implementation of a sparse matrix.
Say I wanted to find the value of the matrix at a particular row i and column j. I'd have to search the row array for instances of i. Say I find an i at index n in the row array, I would then look up the value at index n in the column array and see if it equals j. If not, keep searching for the next instance of i in the row array until I either find or don't find entry i,j.
Is this correct?
@lucida: Sounds like you have the right idea. But as you point out, sparse matrices aren't particularly nice for doing random access lookup of entries (at least, not as described here). The reason is that, typically, one doesn't need to look up entries once the matrix is built—they simply need to do basic linear algebra operations like sparse matrix-dense vector multiplication. For these operations, efficient algorithms can easily be written.