The SIM, then, contains two groups of circular linked lists, one

for the rows and one for the columns. This structure differs from that

usually proposed for sparse matrix representation (Knuth, 1968) in that

each element points back to the row and column cells. This allows for

much faster access to a particular element.

 To illustrate the structure of the SIM consider the following

incidence matrix.


 2 1

 3

 4 6


A representation of the SIM data structure for this incidence matrix is

shown in Fig. A-1. For a small SIM like this there is no saving of

storage space. For an SIM with 100 rows and columns and an average of

five elements per row, the number of words of storage required is 4,100.

Were the entire incidence matrix stored in conventional fashion (a

dimensioned array) 10,000 words plus any additional space for row and

column information would be required.

 Not only does the SIM data structure provide a compact represen-

tation of a sparse incidence matrix, it also provides a structure which

can be operated on by the various algorithms efficiently.