《稀疏矩阵的行压缩存储(CRS)》由会员分享，可在线阅读，更多相关《稀疏矩阵的行压缩存储(CRS)（8页珍藏版）》请在金锄头文库上搜索。
1、Lab 3Why Compressed Row Storage A sparse matrix has a lot of elements of value zero. Using a two dimensional array to store a sparse matrix wastes a lot of memory. Compressed Row Storage (CRS) format only stores the nonzero elements. Using CRS format to store a sparse matrix will save a lot of memor
2、y.Compressed Row Storage val array stores the values of the nonzero elements in a row-wise fashion. col_ind array stores the corresponding column indices of the elements in the val array. E.g. col_ind5 stores the column index of val5. row_ptr array stores the locations in the val array and col_ind a
3、rray that start a row.val10-239378742-1col_ind151262342560 1 2 3 4 5 0 1 2 3 4 5row_ptr02581216190 2 5 16The number of nonzero elements of row i = row_ptri+1 - row_ptr i The value of nonzero elements of row i: val row_ptr i , . , val row_ptr i+1 -1 the number of rows +1the number of nonzero elements
4、 in a matrix/Compressed Row Storage format /for a sparse square (mSize X mSize) matrix public class CRS /the values of the nonzero elements of the matrix float val; /the column indices of the elements in val array int col_idx; /locations in the val and col_idx array that start a row int row_ptr; /th
5、e size of the matrix: the number of rows int mSize=0;/constructor that takes a sparse matrix and convert it to a CRS object CRS( float matrix). /print the matrix in CRS format. public void printCRS()./test the program public static void main(String args). CRS( float matrix) int i, j, index; /the tot
6、al number of nonzero in the matrix int totalNonZeros; /get the number of rows and columns mSize = matrix.length;/get the total number of nonzero entries in the matrix totalNonZeros = 0; for( i=0; imSize; i+) for( j=0; jmSize; j+) if(matrixij != 0) totalNonZeros+; /allocate memory for val and col_idx
7、 array val = new float totalNonZeros ; col_idx = new int totalNonZeros ;/allocate memory for row_ptr row_ptr = new int mSize+1; row_ptr 0 = 0;/store the matrix in CRS formatindex = 0;/ point to the next position to store the value for( i=0; imSize; i+ )/each row for( j=0; jmSize; j+ )/each column if
8、( matrixij != 0 ) /add the value to val val index = matrix i j ; /record the column index in col_idx col_idx index = j; index+; /update row_ptr row_ptr i+1 = index; /end of CRS( float matrix)xx.indexval/test the program public static void main(String args) float matrix = 10, 0, 0, 0, -2, 0,3, 9, 0,
9、0, 0, 3,0, 7, 8, 7, 0, 0,3, 0, 8, 7, 5, 0,0, 8, 0, 9, 9, 13,0, 4, 0, 0, 2, -1; System.out.println(“the original sparse matrix“); for(int i=0; i6; i+) for(int j=0; j6; j+) System.out.print(matrixij+“, “); System.out.println(); System.out.println();CRS crs = new CRS(matrix); crs.printMatrix(); crs.printCRS();
