I have to implement Matrix multiplication using singly linked list. The matrices are sparse matrices so only non-zero elements are stored in the list.

For example

0 2 1

0 0 2

would be represented as the (value, position): (2,1) --> (1,2) --> (2,5)

Anyways, I have completed most methods (inverse, transpose, determinant, add, subtract, etc.) I am having troubling implementing a method which multiplies matrix 1 with matrix 2 in O(s1 * s2) run-time, where s1 and s2 are the number of non-zero nodes in the list.

So far, I have checked if they have the right index for multiplication and declared the new result list.

I actually have no idea how to start the multiplication! I know you multiply row by column through the matrix, but this would be more than O(s1 s2) time since you have to constantly move through the 2nd list to get to row 1, column 1, then row 2 column 1, then row 3 column 1, etc while moving through list 1 as row 1 column 1, row 1 column 2, etc (the latter of these isnt the problem, the first one, moving through each column is my concern) ... How do I implement with this runtime restriction?

If anyone has any idea it would be great! Thanks

# sensationality

Member Since 18 Mar 2011Offline Last Active Mar 27 2011 03:33 PM

### Topics I've Started

Recommended from our users:

**Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**.**Free Download**