1. ## Sparse matrix as linked lists

Does anyone have something in mind?
I am trying to find functions for addition,multiply and solving A*x=b system for matrices which are represented as linked lists.

2. A matrix is a 2D array of elements, when you try to represent it as linked lists, it's no longer a matrix!

3. Originally Posted by Sipher
A matrix is a 2D array of elements, when you try to represent it as linked lists, it's no longer a matrix!
Sipher, you may want to google sparse matrix........

@OP: What have you tried? Or are you just looking for an answer?

4. i ve done the represetion but i cant think anything about the functions.

5. Yes, now i understand... Storing only the non-zero values will save memory space... But again, why linked lists?

6. Ok, well if you had to do it on paper, what steps would you take? Let's start there. Also, why don't you post your code which generates the linked list from your sparse matrix so we don't wind up talking apples and oranges.

7. For those whose memory of Sparse matrix is like mine(very poor).

Sparse matrix - Wikipedia, the free encyclopedia

In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros.
Tim S.

8. the steps are these;
represation,search in matrix,add 2 matrices,multiply 2 matrices, inverse matrice, converse matrice, solve A*x=b. I ll post the code tomorow cause i dont have it in my computer at the moment. I just wondering if anyone had something ready about this problem.

9. Originally Posted by ioan1ioan
Well, you see my friend, that is where we are at an impasse. We have this thing called a homework policy. No one here is just going to post the code for you; if that's what you are looking for just use google.

10. Originally Posted by Sipher
Yes, now i understand... Storing only the non-zero values will save memory space... But again, why linked lists?
How would you suggest to store the matrix?

11. Originally Posted by Sipher
Yes, now i understand... Storing only the non-zero values will save memory space... But again, why linked lists?
So you don't have to count ahead of time how many filled in cells you have in your original matrix. You can just scan the thing once, and add a node to your linked list for every non-empty cell you come across.

Originally Posted by ioan1ioan
i ve done the represetion but i cant think anything about the functions.
Another suggestion might be this:

Take the original matrix (the one with all the empty cells), and write your algorithm to work on that. You will have tons of array[x][y] type of code. The [ ] is how C looks up elements in an array with known dimensions. Your linked list doesn't support the [ ] operator for look up, so you have to write your own look up function. Now, replace all the array[x][y] stuff with a call to your look up funciton, something like find_element(sparse_list, x, y) that returns the element from the linked list.

12. Originally Posted by ioan1ioan
solve A*x=b
I suggest you state which of A,x, and b are matrices. And which is the unknown.
I am guessing A is normal (sparse) Matrix and x and b are single row/col of scalar values. Where "x" is the unknown. But, its been over 10 years since I did this stuff in school.

What is the difference between inverse matrice and converse matrice; wiki implies they are the same.

I guess you will need a determinant function to support the inverse function.

Note: I would write a getMatrixColumn(matrix M, array C) and getMatrixRow(matrix M, array R) that retrieves the column/row requested from the sparse matrix.
But, since reduce memory use is a design requirement; you might just retrieve/return a sparse array instead of a normal array.

The above is just a mild suggestion; I am not the best programmer on this site; by a very long ways.

Tim S.

13. is there any function somewhere that i can see which solves linear systems?

14. There's nothing "standard". If you wanted to look at some, you might try looking for C version of blas/lapack, or at the gsl, or at numerical recipes.