1. In this assignment, you will be implementing a sparse matrix-vector multiply.
3. Read the descriptions and implement the following functions: a) convert_coo_to_csr(row_ind, col_ind, val, m, n, nnz, &csr_row_ptr, &csr_col_ind, &csr_vals); i. Make sure the code is using O(N) algorithm, as described in class. Any code that runs for longer than 10 minutes will be considered non-functional for that data set (there WILL be large matrices in evaluation). ii. Do NOT use any sorting algorithms. iii. The code should work even when the non-zero elements are randomly rearranged. b) spmv(csr_row_ptr, csr_col_ind, csr_vals, m, n, nnz, vector_x, res); 4. Test the functions on the two given sets of input files, stored in test1 and test2 directories. a) A.mtx is the sparse matrix. b) x.mtx is the vector that you are multiplying the matrix with (i.e., A * x) c) ans.mtx is the answer to A*x. Your results should be identical to ans.mtx, using the 'diff command. row_ind /* This function coverts a sparse matrix stored in coo format to CSR. input parameters: these are 'consumed' by this function int* row index for the non-zeros in coo int* col_ind column index for the non-zeros in coo double* val values for the non-zeros in coo int # of rows in the matrix int # of columns in the matrix int nnz # of non-zeros in the matrix n these are 'produced' by this function unsigned int** csr_row_ptr row pointers to csr_col_ind and csr_vals in CSR unsigned int** csr_col_ind column index for the non-zeros in CSR double** csr_vals values for the non-zeros in CSR return parameters: none void convert_coo_to_csr(int* row_ind, int* col_ind, double* val, int m, int n, int nnz, unsigned int** csr_row_ptr, unsigned int** csr_col_ind, double** csr_vals) { TODO */ } /* This function calculates the sparse matrix-vector multiply from the matrix in CSR format (i.e., csr_row_ptr, csr_col_ind, and csr_vals) and the vector in an array (i.e., vector_x). It stores the result in another array (i.e., res) input parameters: these are 'consumed' by this function unsigned int** csr_row_ptr row pointers to csr_col_ind and csr_vals in CSR unsigned int** csr_col_ind column index for the non-zeros in CSR double** csr_vals values for the non-zeros in CSR int # of rows in the matrix int # of columns in the matrix int nnz # of non-zeros in the matrix double vector_x input vector n res these are 'produced by this function double* Result of SpMV. res = A * X, where A is stored in CSR format and x is stored in vector_x return parameters: none void spmv(unsigned int* csr_row_ptr, unsigned int* csr_col_ind, double* csr_vals, int n, int n, int nnz, double* vector_x, double* res) { /* TODO */ } 3. Read the descriptions and implement the following functions: a) convert_coo_to_csr(row_ind, col_ind, val, m, n, nnz, &csr_row_ptr, &csr_col_ind, &csr_vals); i. Make sure the code is using O(N) algorithm, as described in class. Any code that runs for longer than 10 minutes will be considered non-functional for that data set (there WILL be large matrices in evaluation). ii. Do NOT use any sorting algorithms. iii. The code should work even when the non-zero elements are randomly rearranged. b) spmv(csr_row_ptr, csr_col_ind, csr_vals, m, n, nnz, vector_x, res); 4. Test the functions on the two given sets of input files, stored in test1 and test2 directories. a) A.mtx is the sparse matrix. b) x.mtx is the vector that you are multiplying the matrix with (i.e., A * x) c) ans.mtx is the answer to A*x. Your results should be identical to ans.mtx, using the 'diff command. row_ind /* This function coverts a sparse matrix stored in coo format to CSR. input parameters: these are 'consumed' by this function int* row index for the non-zeros in coo int* col_ind column index for the non-zeros in coo double* val values for the non-zeros in coo int # of rows in the matrix int # of columns in the matrix int nnz # of non-zeros in the matrix n these are 'produced' by this function unsigned int** csr_row_ptr row pointers to csr_col_ind and csr_vals in CSR unsigned int** csr_col_ind column index for the non-zeros in CSR double** csr_vals values for the non-zeros in CSR return parameters: none void convert_coo_to_csr(int* row_ind, int* col_ind, double* val, int m, int n, int nnz, unsigned int** csr_row_ptr, unsigned int** csr_col_ind, double** csr_vals) { TODO */ } /* This function calculates the sparse matrix-vector multiply from the matrix in CSR format (i.e., csr_row_ptr, csr_col_ind, and csr_vals) and the vector in an array (i.e., vector_x). It stores the result in another array (i.e., res) input parameters: these are 'consumed' by this function unsigned int** csr_row_ptr row pointers to csr_col_ind and csr_vals in CSR unsigned int** csr_col_ind column index for the non-zeros in CSR double** csr_vals values for the non-zeros in CSR int # of rows in the matrix int # of columns in the matrix int nnz # of non-zeros in the matrix double vector_x input vector n res these are 'produced by this function double* Result of SpMV. res = A * X, where A is stored in CSR format and x is stored in vector_x return parameters: none void spmv(unsigned int* csr_row_ptr, unsigned int* csr_col_ind, double* csr_vals, int n, int n, int nnz, double* vector_x, double* res) { /* TODO */ }
