Chapter 6: Q18E (page 572)
Question: 6.18 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.
6.18.1 [15] consider the sparse matrix X below and write C code that would store this code in Yale Sparse Matrix Format.
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, 7]
Row 6 [1, 3, 0, 0, 0, 1]
6.18.2 [10] 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.
6.18.3 [15] 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.
6.18.4 [15] Can you find a more efficient sparse matrix representation (in terms of space and computational overhead)?
Short Answer
6.18.1
The desired C code :
#include<stdio.h>
int main(){
int m,n;
int YaleSparseMatrix[6][6]={
{0,1,2,3,20,21},
{4,5,6,7,22,23},
{8,9,10,11,24,25},
{12,13,14,15,26,27},
{16,17,18,19,28,29},
{30,31,32,33,34,35}
};
for(m=0; m<6; m++) {
for(n=0;n<6;n++) {
printf("%d ", YaleSparseMatrix[m][n]);
}
}
return 0;
}
6.18.2
The matrix is as same as the 111 bytes of memory.
6.18.3
There is also included the outcome for both the brute force and a calculation that is computed by using the Yale sparse matrix format.
Production:
0 | 0 | 0 | 0 | 0 | 0 |
8 | 16 | 4 | 396 | 28 | 8 |
16 | 32 | 8 | 792 | 56 | 16 |
24 | 48 | 12 | 1188 | 84 | 24 |
32 | 64 | 16 | 1584 | 112 | 32 |
60 | 120 | 30 | 2970 | 210 | 60 |
6.18.4
There are a number of more efficient formats but there are also marginal impacts due to the small matrices that are used in this specified problem.
Step by step solution
Define the concept.
6.18.2
It is assumed that each floating-point number consumes four bytes of memory and for the index, consumes memory of two bytes as it is stored in the data type of short unsigned integer. Hence, the matrix is as same as the 111 bytes of memory.
6.18.3
The matrix X = 
The matrix Y =
And the c code for checking the production:
#include <stdio.h>
#include <stdlib.h>
#define Row1 6
#define Column1 6
#define Row2 1
#define Column2 6
void Production(int matrixX[][Column1], int matrixY[][Column2])
{
int result[Row1][Column2];
for (int i = 0; i < Row1; i++) {
for (int j = 0; j < Column2; j++) {
result[i][j] = 0;
for (int k = 0; k < Row2; k++) {
result[i][j] += matrixX[i][k] * matrixY[k][j];
}
printf("%d\t", result[i][j]);
}
printf("\n");
}
}
int main(void) {
int matrixX[Row1][Column1] = {
{0,1,2,3,20,21},
{4,5,6,7,22,23},
{8,9,10,11,24,25},
{12,13,14,15,26,27},
{16,17,18,19,28,29},
{30,31,32,33,34,35}
};
int matrixY[Row2][Column2] = {
{2, 4, 1, 99, 7, 2}
};
if (Column1 != Column2) {
printf("error!as C1 not equal to C2\n");
exit(EXIT_FAILURE);
}
Production(matrixX, matrixY);
return 0;
}
6.18.4
There are a number of more efficient formats but there are also marginal impacts due to the small matrices that are used in this specified problem.
Determine the calculation.
6.18.1
The desired C code:
#include<stdio.h>
int main(){
int m,n;
for(m=0; m<6; m++) {
for(n=0;n<6;n++) {
printf("%d ", YaleSparseMatrix[m][n]);
}
}
return 0;
}
6.18.2
The required storage must be as same as the times of the .
.Where “R” is referred to the non-zero elements’ number and “m” is referred to the number of rows.
6.18.3
The c code for checking the production of the two specified matrix “X” and “Y”:
#include <stdio.h>
#include <stdlib.h>
#define Row1 6
#define Column1 6
#define Row2 1
#define Column2 6
Over 30 million students worldwide already upgrade their learning with Vaia!
