Jump to content

Check out our Community Blogs

Register and join over 40,000 other developers!

Recent Status Updates

View All Updates

- - - - -

Matrix mulitplication using Linked List

linked list matrix

  • Please log in to reply
No replies to this topic

#1 sensationality


    CC Lurker

  • Just Joined
  • Pip
  • 4 posts

Posted 20 March 2011 - 08:38 PM

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
  • 0

Also tagged with one or more of these keywords: linked list, matrix

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download