Sparse matrix as linked lists

This is a discussion on Sparse matrix as linked lists within the C Programming forums, part of the General Programming Boards category; Does anyone have something in mind? I am trying to find functions for addition,multiply and solving A*x=b system for matrices ...

  1. #1
    Registered User
    Join Date
    Jul 2011
    Posts
    6

    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. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    A matrix is a 2D array of elements, when you try to represent it as linked lists, it's no longer a matrix!
    Devoted my life to programming...

  3. #3
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Quote Originally Posted by Sipher View Post
    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?
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  4. #4
    Registered User
    Join Date
    Jul 2011
    Posts
    6
    i ve done the represetion but i cant think anything about the functions.

  5. #5
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,625
    Yes, now i understand... Storing only the non-zero values will save memory space... But again, why linked lists?
    Devoted my life to programming...

  6. #6
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    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.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    2,767
    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.
    Last edited by stahta01; 07-20-2011 at 01:38 PM.

  8. #8
    Registered User
    Join Date
    Jul 2011
    Posts
    6
    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. #9
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Quote Originally Posted by ioan1ioan View Post
    .... I just wondering if anyone had something ready about this problem.
    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.
    Last edited by AndrewHunter; 07-20-2011 at 01:53 PM.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  10. #10
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Quote Originally Posted by Sipher View Post
    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?
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Quote Originally Posted by Sipher View Post
    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.

    Quote Originally Posted by ioan1ioan View Post
    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. #12
    Registered User
    Join Date
    May 2009
    Posts
    2,767
    Quote Originally Posted by ioan1ioan View Post
    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.
    Last edited by stahta01; 07-20-2011 at 02:08 PM.

  13. #13
    Registered User
    Join Date
    Jul 2011
    Posts
    6
    is there any function somewhere that i can see which solves linear systems?

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-15-2011, 11:36 AM
  2. adjacency matrix and sparse matrix
    By dpp in forum C Programming
    Replies: 3
    Last Post: 07-11-2010, 11:26 AM
  3. Accessor for Sparse Matrix
    By Clark in forum C Programming
    Replies: 1
    Last Post: 04-02-2010, 06:14 PM
  4. Sparse Matrix
    By brb9412 in forum C Programming
    Replies: 3
    Last Post: 01-02-2009, 01:12 PM
  5. Sparse matrix
    By milenkom in forum C++ Programming
    Replies: 4
    Last Post: 01-02-2008, 04:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21