Sparse Matrix-vector multiplication

You will be given a matrix AA as a nested dictionary, the shape of the matrix as a tuple shape = (n,m) and a (densely stored) vector xx as a numpy array.

The nested dictionary storage for AA works as follows:

• The outermost dictionary maps a row index of the matrix to another inner dictionary, representing the row.

  If a given row of AA consists of all zeros, its row index will not be present in the dictionary.

• The inner dictionary maps the column index to an element of AA.

  If an element of AA is zero, the inner dictionary will not contain an entry for it.

For example, the matrix

A= 0017310005000001400 A=[0017310005000001400]

corresponds to the following Python data structure:

 A = {0: {2: 17, 3: 31}, 1: {3: 5}, 3: {1: 14}} 

Write a code snippet that assigns the numpy array Ax to the matrix-vector product AxAx. Your code should efficiently perform this matrix-vector multiplication, taking advantage of the sparse format of the matrixAxAx.

The amount of work should be proportional to the number of non-zero entries in AA, and not proportional to nmnm, where nmnm is the shape of AA. The autograder will not check that your code runs in the correct asymptotic time, so you should think carfully about the efficiency of your solution.

The setup code gives the following variables:

Name	Type	Description
x	1-D Numpy Array	given dense vector
A	dict	given sparse matrix
shape	tuple	shape of the matrix A (in dense format)

Your code snippet should define the following variable:

Name	Type	Description
Ax	1-D Numpy Array	result of matrix-vector multiplication

python

You will be given a matrix A as a nested dictionary, the shape of the matrix as a tuple shape (n,m) and a (densely stored) vector x as a numpy array. The nested dictionary storage for A works as follows: The outermost dictionary maps a row index of the matrix to another inner dictionary, representing the row. If a given row of A consists of all zeros, its row index will not be present in the dictionary. The inner dictionary maps the column index to an element of A If an element of A is zero, the inner dictionary will not contain an entry for it. For example, the matrix T0 0 17 31 0 14 0 0 corresponds to the following Python data structure Write a code snippet that assigns the numpy array Ax to the matrix-vector product Ax. Your code should efficiently perform this matrix-vector multiplication, taking advantage of the sparse format of the matrix Ax. The amount of work should be proportional to the number of non-zero entries in A, and not proportional to nm, where n x m is the shape of A. The autograder will not check that your code runs in the correct asymptotic time, so you should think carfully about the efficiency of your solution. The setup code gives the following variables: Description given dense vector given sparse matrix shape of the matrix A (in dense format) Name Type 1-D Numpy Array dict shape uple Your code snippet should define the following variable: Name Ax Type Description result of matrix-vector multiplication 1-D Numpy Array user_code.py 1 mport numpy as np 2 Ax np.zeros(shape [o])