I currently have implemented a basic algorithm for multiplying two sparse matrices.

In my implementation a sparse matrix has a back-bone of rows and then a list of nodes with their column attached.

I currently go throught the rows and columns of the new matrix, and increment k to get all the row and columns multiplied together.

I then do a slight optimization only accessing the non-zero elements of matrix of the row in matrix A (A*B = C).

But currently the big slow down is having to get the correct column in B. ie. A(i, k) * B(k, j). B(k, j) being super expensive as you have to iterate each time until you get column j to match.

This works but I was wondering if I could make it any faster. Thanks.

P.S. most of the posts I have seen until now focus on implementation specific, I would much prefer an algorithm, c code being a bonus.

I also tried saving the empty columns ahead of time by traversing Matrix B, but I am not sure if that significantly made it faster.

CodePudding user response：

I think there is a nice algo for this which uses every element it iterates over. I would say your algo is O(n^3) mult * ~n for accessing each jth member every time, so roughly O(n^4).

This algo is < O(n^3).

    A = [
                [0, 1, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 0, 2, 0, 4],
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0]
            ]
    B = [
                [0, 0, 0, 0, 3],
                [0, 0, 0, 2, 0],
                [0, 0, 3, 0, 0],
                [0, 0, 3, 0, 0],
                [0, 0, 0, 0, 0]
            ]

The algo works such,

1. Iterate through the rows of A, if the row is empty, skip it
2. For that column, (0, 1) = 1, so check if row 1 of B is empty, if not, iterate through it (that is the only things that 1 will interact with)
3. For each node in row ai(k) column of B (in this case 1), multiply the value of the node with the value of the node in A, and add it to the result matrix -> in our case that would be (0, 1) * (1, 3) = 1 * 2 = 2, so add 2 to the result matrix at (0, 3)

Note: Each of the m rows, n cols, and k (row-col match) form n^3, but in Sparse Matrices, there are much fewer that you have to iterate over, because of low density.

We can skip over 0 rows reducing m, we can skip over "0" row values reducing k, and we can skip over some 0 columns making k smaller again. There is no real way to reduce n in this algorithm.

In the end, our O(mnk) ie O(n^3) has a much smaller coefficient say O(1/100 * mnk) as you are using fewer of those elements.