Assignment 8

A matrix is said to be sparse if each row of it contains only few non-zero entries. Such sparse matrices occur in many situations. For example, a complicated machine may have one million components, but each component interacts with at most one hundred other components. So the interaction matrix, though million-by-million in size, has at most one hundred non-zero entries in each row and can be rightfully dubbed sparse.

In order to store a sparse matrix, it suffices to store for each row only the column indices where non-zero entries occur and also the corresponding entries. This reduces the space overhead associated with the storage. For the example in the last paragraph, a complete million-by-million array requires space for storing one trillion (10¹²) entries, whereas a sparse representation is capable of storing the same matrix in a space for only one hundred million (10⁸) entry-index pairs.

Define a suitable dynamic two-dimensional array type to represent a sparse matrix. Notice that each row is now to be allocated exactly the space required to store only the non-zero entries and the corresponding column indices.

Write a function that takes as input the dimension n of a square matrix and a limit l on the number of non-zero entries in each row. The function should output a sparse matrix with integer entries such that the number of non-zero entries in each row is a random integer between 1 and l. Also the column indices occupied by these non-zero entries should be chosen randomly between 0 and n-1. You may restrict each non-zero entry to an integer value between 1 and 9.

Write a function that takes as input two sparse matrices in your representation and stores in the first matrix the sum of the two input matrices again in your sparse format. Notice that if the input matrices have at most l non-zero entries in each row, the sum of these matrices can have at most 2l non-zero entries in each row. So if l is substantially smaller than n, then the output matrix may also be called sparse. You may pass l as a parameter to this function. You should free unused memory while changing the first matrix.

Write a function that prints a sparse matrix. Printing should also be sparse, i.e., each row is to be printed as a list of entry-index pairs.

Report the output of your program on matrices with dimension n = 10 and non-zero entry limit l = 5. Such a matrix is not really sparse. But for easy debugging and our checking of your output, it is desirable to play with small matrices.

Sample output

The following data corresponds to the parameters n = 8 and l = 4.

   Matrix A
   Row    0 : ( 9, 3)
   Row    1 : ( 6, 0) ( 6, 3) ( 1, 5)
   Row    2 : ( 7, 2) ( 1, 3) ( 4, 4) ( 5, 5)
   Row    3 : ( 2, 1) ( 5, 2) ( 8, 3) ( 2, 5)
   Row    4 : ( 1, 1) ( 5, 5) ( 1, 6)
   Row    5 : ( 8, 1) ( 5, 4) ( 2, 5) ( 5, 7)
   Row    6 : ( 8, 1) ( 8, 4) ( 4, 7)
   Row    7 : ( 7, 0) ( 8, 1) ( 4, 4)

   Matrix B
   Row    0 : ( 6, 0) ( 9, 3) ( 1, 4)
   Row    1 : ( 9, 1) ( 2, 6)
   Row    2 : ( 5, 0) ( 8, 3) ( 7, 6)
   Row    3 : ( 5, 4)
   Row    4 : ( 2, 2) ( 3, 5) ( 3, 6)
   Row    5 : ( 2, 0) ( 9, 7)
   Row    6 : ( 7, 2) ( 5, 6)
   Row    7 : ( 7, 0) ( 1, 1) ( 7, 5) ( 8, 7)

   Matrix A+B
   Row    0 : ( 6, 0) (18, 3) ( 1, 4)
   Row    1 : ( 6, 0) ( 9, 1) ( 6, 3) ( 1, 5) ( 2, 6)
   Row    2 : ( 5, 0) ( 7, 2) ( 9, 3) ( 4, 4) ( 5, 5) ( 7, 6)
   Row    3 : ( 2, 1) ( 5, 2) ( 8, 3) ( 5, 4) ( 2, 5)
   Row    4 : ( 1, 1) ( 2, 2) ( 8, 5) ( 4, 6)
   Row    5 : ( 2, 0) ( 8, 1) ( 5, 4) ( 2, 5) (14, 7)
   Row    6 : ( 8, 1) ( 7, 2) ( 8, 4) ( 5, 6) ( 4, 7)
   Row    7 : (14, 0) ( 9, 1) ( 4, 4) ( 7, 5) ( 8, 7)

---

[Submission site] [Lab home] [Course home]