A sparse matrix is a matrix whose most members have zero value. Therefore, in order to save memory and storage The matrices, it is convenient to represent them using a dictionary in the following configuration: for each cell in the matrix that is not zero, a tuple key will be stored in the dictionary which represents the coordinates of the cell, and the value represents the value of the cell in the matrix (some number of type int or float) as usual in mathematics, The indices of the matrix start from one. • The cell coordinate (j, i) contains natural numbers so that the coordinate represents the cell in the i-th row and in the jth column. • The order in the dictionary is not important. Realize the function sparse_mult(n, mat2, mat1) which receives 2 dictionaries, mat1 and mat2, representing square sparse matrices of size n×n, and returns a dictionary representing the mat2×mat1 matrix multiplication matrix. pay attention:

1. There is no need to check the correctness of the matrices.
2. It can be assumed that n is a natural number < 1.
3. The repeated dictionary must represent a sparse matrix as defined above.

for i in range(1, n   1):
    temp = 0
    for j in range(1, n   1):
        if (mat1.get((i, j), 0) != 0)|(mat2.get((j, i), 0) != 0):
            temp  = mat1.get((i, j), 0) * mat2.get((j, i), 0)
    if temp !=0:
        resultrow[(i, i)]=temp

That's my code, I know I got it wrong but i just don't have a clue

CodePudding user response：

so i eventually got it, if anyone care:

initialize the result dictionary

result = {}

# iterate over the rows and columns of the result matrix
for i in range(1, n   1):
    for j in range(1, n   1):
        # initialize the sum to 0
        sum = 0

        # iterate over the columns of the first matrix and the rows of the second matrix
        for k in range(1, n   1):
            # check if the cell (i, k) in the first matrix and the cell (k, j) in the second matrix are non-zero
            if (i, k) in mat1 and (k, j) in mat2:
                sum  = mat1[(i, k)] * mat2[(k, j)]

        # add the result to the dictionary if it is non-zero
        if sum != 0:
            result[(i, j)] = sum

# return the result dictionary
return result

CodePudding user response：

It is inefficient to iterate over all indices in the 2-dimensional index set when multiplying two sparse matrices. Instead, you can iterate over all pairs of keys where 1 pair is drawn from each sparse matrix. Given such a pair (i,j) and (k,l), it contributes a product of 2 numbers if and only if j == k. In this case the corresponding product goes towards entry (i,l) in the overall product. A final dictionary comprehension can get rid of any zero entries. This last step might be inadequate if the numbers are floats and some entries are non-zero only due to round-off error. In that case a threshold approach which removes entries close to zero and not merely equal to zero.

def sparse_multiply(a,b):
    c = {}
    for i,j in a.keys():
        for k,l in b.keys():
            if j == k:
                p = a[(i,j)]*b[(k,l)]
                if (i,l) in c:
                    c[(i,l)]  = p
                else:
                    c[(i,l)] = p
    return {k:v for k,v in c.items() if v != 0}

Note that n plays no role here. The complexity is mk where m is the number of non-zero entries in the first matrix and k the number of such entries in the second. For matrices which are very sparse this will be substantially faster than the n^3 of using straight-forward matrix multiplication. There will be some threshold where mk will actually be larger than n^3, but at that stage the matrices are no longer sparse.