•

Check out our Community Blogs sensationality

Member Since 18 Mar 2011
Offline Last Active Mar 27 2011 03:33 PM     Matrix mulitplication using Linked List

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

Need help with logic in my program

18 March 2011 - 06:30 AM

Hi,

I am making a program which stores a matrix (2D) as a list (linked list) of 1 dimension, where each node in the list stores the value and position of the element in the matrix, as well as the next node. Furthermore, only non-zero elements (value and position) from the matrix must be 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)

My problem is, given only the list without the actual 2D representation of the matrix, I need to find the transpose of the list (matrix). Transpose is found by switching the rows and columns.

The transpose of the above example would be:

0 0
2 0
1 2

and the list now becomes (2,2) --> (1,4) --> (2,5).

I was wondering if someone can guide me on the logic of how to do this. I was thinking I'd have to use recursion somehow, but I am not sure, exactly what I would do. 