Answer Happy

FOR PHYTON PLEASE
A sparse matrix is a matrix in which many (most) of the elements are zero. Sparse matrices occur frequently in scientific computation and engineering applications. A 5x5 sparse matrix example is given below 1 5 0 0 30 000 0 0 7 0 9 00040 0 2008 Sparse matrices can get quite large. Storing an extremely large yet extremely sparse matrix as a list of lists" can be inefficient, since most of the memory will be consumed by the O elements. Thus, we would like to explore alternative approaches to store sparse matrices. In this homework, you will use dictionaries to store sparse matrices. Let A be a sparse matrix with N rows and M columns, stored as a list of lists. Let A, be the element of A in the ith row and th column (i=0...N-1.j=0...M-1). Then, this sparse matrix can be stored as a dictionary as follows: Let sp_ be the Python dictionary that will store A The keys are tuples of the row and column indices of non-zero elements, that is: sp_A(1,1))-A, where A 0 • A special key (-1) stores the dimensions of the matrix as a list: sp_A(-1)=[N,M] Open SparseMatrix.py and examine the code given to you. Then, solve the following parts. Part A (10 pts): Implement the function dense_to_sparse(matrix). matrix is a sparse matrix stored in list-of-lists representation. This function should convert it to dictionary representation as explained above and retum the result . For example, the input matrix A and the return value sp A could be: TO 3 0] A Sp.A(0,1)) -3, sp.A|(1,0) -1, sp.A(-1) - (2,3) Another example - consider the following matrix in list of lists representation: [C, 0, 0, 0, 1), (1, 7, 2, 3, 6), [0, 0, 0, 10, 16)] Its dictionary representation is: (-1: (3, 3), (0, 4): 1, (1, 0): 1, (1, 1): 7, (1, 3): 3, (2, 3): 10, (2, 4): 16) . Part B (5 pts): Implement the function sparse_transpos esp_matrix). sp_matrix is a sparse matrix stored in dictionary representation • This function should compute the transpose of sp_matrix and return the result. The result should also be a sparse matrix in dictionary representation Mathematically, the transpose operation is converting A -> As. For example, the input matrix A and its transpose A' could be: 30] 00 AE --B : Note that in your program, both A and AT are sparse matrices stored in dictionary representation, not as a list of lists The transpose of the example given at the end of Part Ais: (-1: [5, 3), (4, 0): 1, (0, 1): 1, (1, 1): 7, (3, 1): 3, (3, 2): 10, (4, 2): 16)

Part C (10 pts): Implement the function sparse_add(sp_matrix1, sp_matrix2). sp_matrix and sp_matrix2 are sparse matrices stored in dictionary representation. This function should compute the SUM of these matrices and retum the result. The result should also be a sparse matrix in dictionary representation Here, we are performing element-wise sum of the two matrices. Let A and Brow be two matrices. Then, their sum should have the same dimensions (Chem) and its elements should be calculated as: C = A + Bij If the dimensions of sp_matrix 1 and sp_matri2 do not match, sparse_add should return -1. For example, if we add the following two matrices: (-1: (3, 5), (C, 4): 1, (1, e): 1, (1, 1): 7, (1, 3): 3, (2, 3): 10, (2, 4): 16) 4.1:13, sj, (, 2): 5, (1, 1): 6, (2, 1): 14, (2, 2): 10, (2, 3): 2, (3, 4): 26) We should find 1: 3, 5), (0, 9): 1, (1, 0): 1, (1, 1): 13, (1, 3): 3, (2, 3): 12, (2, 4): 36, e, 2): 5, (2, 1): 14, (2, 2): 10) Part D (10 pts): Implement the function sparse_multiplyisp_matrix1, sp_matrix2). sp_matrix1 and sp_matrix2 are sparse matrices stored in dictionary representation. This function should compute the MULTIPLICATION of these matrices and return the result. The result should also be a sparse matrix in dictionary representation. Let Anza, Bunk be two matrices and let Cwek = AB be their multiplication. The elements of Care calculated as: Cij = MAX Baj For matrix multiplication to work, number of columns in sp_matrix1 should be equal to the number of rows in sp_matro(2. If that is not the case, sparse_multiply should return-1. By the end of multiplication, you may end up with O values in your result dictionary (if C; = 0). In this part only, we prefer that those Os stay in your dictionary. Do not delete them. For example, if we multiply the following two matrices: -1: [3, 5), (0, 4): 1, (1, 6): 1, (1, 1): 7, (1, 3): 3, (2, 3): 10, (2, 4): 16) 1-1: 15, 2), (1, 1): 19, (2, 6): 14, (3, 6): 16, (4, 1): 17} We should find: {-1: [3, 2), (@, e): 0, (0, 1): 17, (1, 0): 43, (1, 1): 133, (2, 6): 168, (2, 1): 272

import random import math ################################################################ ### Below are the functions you need to implement in the HW. ### ### Feel free to create your own helper functions. ### ################################################################ def dense_to_sparse(matrix): This function converts a sparse matrix in list of lists representation to a sparse matrix in dictionary representation. You need to implement this function. sp_matrix = {} return sp_matrix def sparse_transpose( sp_matrix): This function takes the transpose of the input sparse matrix (sp_matrix) and returns the result (result is also a sparse matrix). You need to implement this function. sp_transpose = {} return sp_transpose def sparse_add(sp_matrix1, sp_matrix2): This function computes the sum of the two input sparse matrices and returns the result (result is also a sparse matrix). You need to implement this function. sp_res = {} return sp_res def sparse_multiply(sp_matrix1, sp_matrix2): This function multiplies the two input sparse matrices and returns the result (result is also a sparse matrix). You need to implement this function. sp_matrix_res = {} return sp_matrix_res

################################################################ ### Below are some functions we are providing you to help ### ### you test your solutions. They won't be graded. ### ################################################################ def generate_random_sparse_matrix(nrow, ncol, sparsity=0.6): 111111 This function generates a random matrix as a list of lists with a given sparsity. row = [0]*ncol res=[] for i in range(nrow): res.append(row[:]) nr = int((1.-sparsity)*nrow*ncol) pos = random. sample (range (nrowincol), nr) for ind in pos: n_ind = math.floor(ind/ncol) m_ind = ind-n_indincol res (n_ind] [m_ind]=random. randint(1,20) return res def main(): This function contains some test cases for you to test your solutions. We recommend that you create additional test cases for yourself. 1l_sp_m1 = generate_random_sparse_matrix(3, 5) 1l_sp_m2 = generate_random_sparse_matrix(5, 2) 1l_sp_m3 = generate_random_sparse_matrix(3, 5) print(ll_sp_m1) print(ll_sp_m2) sp_m1 = dense_to_sparse(ll_sp_m1) sp_m2 = dense_to_sparse(ll_sp_m2) sp_m3 = dense_to_sparse(ll_sp_m3) #print(sp_m1) #print(sp_m2) sp_m1_transpose = sparse_transpose( sp_m1) sp_m2_transpose = sparse_transpose( sp_m2) #print(sp_m1_transpose) #print(sp_m2_transpose) add1 = sparse_add(sp_mi, sp_m3) add2 = sparse_add(sp_m1, sp_m2) #print(add1) #print(add2) mult1 = sparse_multiply(sp_mi, sp_m2) mult2 = sparse_multiply(sp_mi, sp_m3) #print(mult1) #print(mult2) main()