U&

| ¢

¡

In order to take advantage of the large number of zero elements, special schemes are re-

£

quired to store sparse matrices. The main goal is to represent only the nonzero elements,

and to be able to perform the common matrix operations. In the following, denotes the

total number of nonzero elements. Only the most popular schemes are covered here, but

additional details can be found in books such as Duff, Erisman, and Reid [77].

The simplest storage scheme for sparse matrices is the so-called coordinate format.

The data structure consists of three arrays: (1) a real array containing all the real (or com-

plex) values of the nonzero elements of in any order; (2) an integer array containing

£

their row indices; and (3) a second integer array containing their column indices. All three

arrays are of length , the number of nonzero elements.

¥ ¡T

© © §¦

¥

The matrix

‘ 3444 “ p¢ p

u p z

z

99 8 7

7 7

p 9

7 7

z £ 5 ¢

z p z‘Y p 7 z¥

7

¤

z p p A z

7 7 7

z

u%

7 7 7 7

will be represented (for example) by

AA 12. 9. 7. 5. 1. 2. 11. 3. 6. 4. 8. 10.

JR 5 3 3 2 1 1 4 2 3 2 3 4

JC 5 5 3 4 1 4 4 1 1 2 4 3

In the above example, the elements are listed in an arbitrary order. In fact, they are

–

usually listed by row or columns. If the elements were listed by row, the array which

contains redundant information might be replaced by an array which points to the begin-

ning of each row instead. This would involve nonnegligible savings in storage. The new

data structure has three arrays with the following functions:

• H…z‚

£

(X ˜

A real array contains the real values stored row by row, from row 1 to .

The length of is .

• p… ‚

An integer array contains the column indices of the elements as stored in

(

the array . The length of is Nz.

( •

An integer array contains the pointers to the beginning of each row in the arrays

C rB

PB ( —D˜ B

and . Thus, the content of is the position in arrays and where

—D˜

£

the -th row starts. The length of is with containing the number

C

—˜ — C

, i.e., the address in and of the beginning of a ¬ctitious row

number .

¤ © ¥ © §¢ © §¥ ¡ £ ¡

¨

¡ £

§

Thus, the above matrix may be stored as follows:

AA 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

JA 1 4 1 2 4 1 3 4 5 3 4 5

IA 1 3 6 10 12 13

This format is probably the most popular for storing general sparse matrices. It is

called the Compressed Sparse Row (CSR) format. This scheme is preferred over the coor-

dinate scheme because it is often more useful for performing typical computations. On the

other hand, the coordinate scheme is advantageous for its simplicity and its ¬‚exibility. It is

often used as an “entry” format in sparse matrix software packages.

There are a number of variations for the Compressed Sparse Row format. The most

obvious variation is storing the columns instead of the rows. The corresponding scheme is

known as the Compressed Sparse Column (CSC) scheme.

Another common variation exploits the fact that the diagonal elements of many ma-

trices are all usually nonzero and/or that they are accessed more often than the rest of the

elements. As a result, they can be stored separately. The Modi¬ed Sparse Row (MSR) for-

˜ ”˜

X

mat has only two arrays: a real array and an integer array . The ¬rst positions in

X — (

contain the diagonal elements of the matrix in order. The position of the array

is not used, but may sometimes be used to carry other information concerning the matrix.

—h˜ X

Starting at position , the nonzero elements of , excluding its diagonal elements,

C (

B B

are stored by row. For each element , the integer represents its column index

c˜ C

—

on the matrix. The ¬rst positions of contain the pointer to the beginning of each

X

row in and . Thus, for the above example, the two arrays will be as follows:

AA 1. 4. 7. 11. 12. * 2. 3. 5. 6. 8. 9. 10.

JA 7 8 10 13 14 14 4 1 4 1 4 5 3