Exercise 7.21 When performing computations on sparse matrices, latency in the memory hierarchy becomes much more of a factor. Sparse matrices lack the spatial locality in the data stream typically found in matrix operations. As a result, new matrix representations have been proposed.

One of the earliest sparse matrix representations is the Yale Sparse Matrix Format.

It stores an initial sparse m × n matrix, M in row form using three one-dimensional arrays. Let R denote the number of nonzero entries in M; we can construct an array A of length R that contains all nonzero entries of M (in left-to-right top-to-bottom order). We also construct a second array IA of length m + 1 (i.e., one entry per row, plus one). IA(i) contains the index in A of the fi rst nonzero element of row i. Row i of the original matrix extends from A(IA(i)) to A(IA(i + 1)−1). The third array, JA, contains the column index of each element of A, so it also is of length R.

7.21.1 [15] <7.9> Consider the sparse matrix X below and write C code that would store this code in Yale Sparse Matrix Format.

Row 1 [0, 0, 0, 0, 10]

Row 2 [0, 0, 0, 0, 0]

Row 3 [8, 0, 0, 0, 6]

Row 4 [0, 1, 8, 7, 0]

Row 5 [7, 0, 0, 0, 0]

7.21.2 [10] <7.9> In terms of storage space, assuming that each element in matrix X is single precision fl oating-point format, compute the amount of storage used to store the matrix above in Yale Sparse Matrix Format.
7.21.3 [15] <7.9> Perform matrix multiplication of Matrix X by Matrix Y shown below.
[9, 8, 7, 100, 2]
Put this computation in a loop, and time its execution. Make sure to increase the number of times this loop is executed to get good resolution in your timing measurement. Compare the runtime of using a naïve representation of the matrix and the Yale Sparse Matrix Format.
7.21.4 [15] <7.9> Can you fi nd a more effi cient sparse matrix representation (in terms of space and computational overhead)?