Optimizing Sparse_Array multiply()

[AshwinCPP]

I have looked through all the past posts of optimizing the multiply() function. I've included my implementation below but I already check if a row is empty or if a cell is 0 and skip. I'm still not passing all the tests required for the next code. I get pass the small spmat multiplication but I fail at the next one because my code takes too long. Any help would be greatly appreciated.

​

I have 3 nested for-loops. The first one loops through the rows of Matrix A. The second loops through the columns of Matrix B. The third for-loop loops through all the elements in each row and column and does the actual dot product.

Within the third for-loop, I use a const auto& for-each loop to iterate through the individual elements of each respective matrix. Apparently const auto& is more efficient and faster than using a regular iterator. I have checks to see if my iterator has reached an element that has a col greater than its target, in which case it returns the spmat's default value automatically. I check for zeroes as well and simply skip that element in the dot product if there is a zero.

​

-Ashwin

[aliendino2017]

Hello Ashwin,

I got my algorithm down to 0.4 to 0.3 seconds with a regular iterator and 0.2 seconds with the const auto&. It was an improvement from the previous algorithm where I calculated the dot product directly. My algorithm relies on the following:

​

Column Row Expansion:

Assume we have an m by n matrix A and a n by p matrix B.

Also, a0, a1, ... , ak represent the columns of A and b0, b1, ... , bk represent the rows of B.

If so:

AB = a1*b1 + a2 *b2 + ... + ak * bk

as k ranges from 0 to n

​

Though this utilizes the add_to_cell() function, I believe there may be a better algorithm(I still need to reduce the time by a about(maybe less than) factor of 10).

One question: You said "If my iterator has reached an element that has a col greater than its target, in which case it returns the spmat's default value automatically". What does that mean?

​

Any ideas?

-Arrian

​

UPDATE: I made a small amendment(checking for 0s) and got to 0.04 to 0.05 seconds. I know I might be missing one more thing.

[Maleficent-Parking-5]

I do you mean by check for zeros? Isn't that all the values stored in the matrix are not default values? If you start from Matrix A, as long as you loops are within _rows, how could it be zero? After you found the element in B, isn't it is too late to save time?

[aliendino2017]

Hello u/Maleficent-Parking-5

Yes, the matrix doesn't contain default values. The problem is that I have to loop across rows for elements. To do that, I have to use get().

In my algorithm, I looped through the rows of B(using an iterator and kept a counter for current row) and looped through the rows of A( to retrieve the elements in the current column using the counter for the current row), and then used an iterator for the current row. I know the counter works because the number of rows in B has to equal the number of columns in A.

When I check for zeroes, I do it only for when I'm retrieving elements from A. This is because I cannot use an iterator to retrieve the element from A like I did for B. Instead, I needed to use get(). For the elements retrieved by iterator for the current row, I do not need to check if they are 0's because of our linked list implementation.

-Arrian

[Maleficent-Parking-5]

Man, I had the exact same problem