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.
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
sensationalityMember Since 18 Mar 2011
Offline Last Active Mar 27 2011 03:33 PM
- Group Just Joined
- Active Posts 4
- Profile Views 1450
- Member Title CC Lurker
- Age 28 years old
- Birthday April 23, 1991
sensationality hasn't added any friends yet.