Sparse Matrix and its 3-Tuple representation

Question

This Sparse Matrix and its 3-Tuple representation is not getting into my head... Either its bit tricky or my resources from where I am studying are really not that good... here is the URI Sparse Matrix Slide

So if you have any thing to share please go ahead.

Thanks

Answer 1

The ppt presentation you reference is pretty straightforward. The basic ideas is that you only want to record the array entries that aren't zero. Of course, you skip a bunch of 0 entries, so you need to also record the row and column indices along with the non-zero-value.

He presents a couple of ways to do this. One is just a long list, with the entries ordered by row then column. Then he looks at performance of a couple of matrix operations.

1) Transpose is pretty fast; just a sort of the list on the indices by column then row basically. 2) Addition of two matrices is also fast; you traverse the two lists of the two matrices together adding values appropriately, kind of like a merge of the two ordered lists. Note that you only traverse each list once.

These two operations take slightly longer for the linked list option.

These operations take waaaay longer when using a full matrix in memory, because you're basically paging in and out almost continuously, which is much slower than working mostly in the higher speed cache memory.

He doesn't measure performance of matrix multiplication or computing the inverse. Maybe these operations are not usually needed in the applications that use sparse matrices. Maybe you can think about them as an exercise.