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 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 be the number of nonzero entries in M. We 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 first 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.

1. Consider the sparse matrix X below and write C code that would store this code in Yale Sparse Matrix Format.

2. In terms of storage space, assuming that each element in matrix X is single precision floating point, compute the amount of storage used to store the Matrix above in Yale Sparse Matrix Format.

3. Perform matrix multiplication of Matrix X by Matrix Y shown below.

[2, 4, 1, 99, 7, 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.

4. Can you find a more efficient sparse matrix representation (in terms of space and computational overhead)?

Transcribed Image Text:

Row 1 [1, 2, 0, 0, 0, 0] Row 2 [0, 0, 1, 1, 0, 0] Row 3 [0, 0, 0, 0, 9, 0] Row 4 [2, 0, 0, 0, 0, 2] Row 5 [0, 0, 3, 3, 0, Row 6 [1, 3, 0, 0, 0, 1] 7]