sparse matrix representation?

[Ionel Simionescu]

[Patrick ]
| The normal representation of a matrix uses an array.  An array takes up
| memory for every location.
|
| For a sparse array, you have many locations that are zero.  You can use
| a hash (dictionary) to represent only the non-zero locations and save a
| great amount of memory.

---

As I know it, a hash/dict is still more expensive (both in terms of space
and retrieval speed) than the commonly used schemes to represent sparse
matrices.


The latter are one of the following:
1.
simply a bundle of three corresponding arrays: (row_indices, column_indices,
values)
2.
a bundle of 2 corresponding arrays (row_indices, values), plus a third one
(number_of_non_zeros_per_column).
3.
a bundle of 2 corresponding arrays (flat_row_indices, values). The shape of
the matrix is stored separately, the flat_row_index of an element is its
index corresponding to the element if the matrix is flattened ( or erected?
:-) columnwise.

The second version is used by MATLAB which has a very good support for
sparse matrices.
The first one takes more space but its easier to use for simplistic things.


Do not use a dictionary: you'd shoot your application in the foot.
Besides, using a dictionary you'll be unable to take advantage of Numeric.


ionel