'Sparse Matrix' and Data Structures

This is a discussion on 'Sparse Matrix' and Data Structures within the C Programming forums, part of the General Programming Boards category; Hi everyone, thanks in advance for taking the time to read and respond to this post. To be clear this ...

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    10

    'Sparse Matrix' and Data Structures

    Hi everyone, thanks in advance for taking the time to read and respond to this post. To be clear this is part of a University course I am doing so I'm not looking to cheat or 'blag' the answers from others! Quite simply we have no support or guidance and I'm a fairly novice programmer so I was hoping to post the question here where some of the more experienced programmers may offer some advice or guidance.


    An unstructured sparse matrix is simply a matrix where a significant number of elements are zero.
    Using a suitable in-memory data structure that stores only non-zero elements, it is possible to
    represent such a matrix in a much more compact way than a dense equivalent (where all elements
    are stored whether zero or not).

    1. Implement a data structure that can represent a sparse matrix. It is essential that the data
    structure is space efficient since your solution will be tested with matrices whose
    dimensions are many orders of magnitude larger than those provided.
    2. Implement functions that enable an in-memory instance of the sparse matrix data structure
    to be read from or written to an on-disk file as per the format above.
    One example given is:
    5,5
    0,0,-1
    0,4,2
    1,1,5
    1,3,6
    2,2,7
    3,1,8
    3,3,9
    4,0,3
    4,4,-4
    represents a (5 x 5)-element matrix M =
    -1 0 0 0 2
    0 5 0 6 0
    0 0 7 0 0
    0 8 0 9 0
    3 0 0 0 -4
    Although It does not suggest this is the best or preferable way forward.

    I'm not particularly well versed on data structures but I remember sorting data and writing it to a linked list by building it node by node last year and I'm wondering if a linked list could be a useful data structure to start with??

    This is just Part of stage 1 and there are 5 stages. Later on I will have to compute the sum, product etc.. I thought this might be important to bring up in case this affects my choice of data structure.

    Furthermore:
    Although there may be multiple valid approaches at each stage, your solution should aim to be as efficient as possible
    wrt. execution time. Within reason, a trade-off favouring time over space is encouraged.
    Thanks again - as you can probably tell I'm a little lost.

  2. #2
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    I'm wondering if a linked list could be a useful data structure to start with??
    That is a useful data structure to start with. Think of a matrix as a list of columns or rows, and columns or rows as lists of elements. If each element knows it's position and any missing element is assumed to be 0 - you can store any matrix with a minimum number of elements. You just need to think about how you would populate this matrix from their format and how to do things like products.

  3. #3
    Registered User
    Join Date
    Nov 2012
    Posts
    978
    Using a direct conversion of the "list" approach, you might represent this conveniently using structs
    Code:
     typedef struct {
        int row;
        int col;
        int val;
    } SMEntry;
    
    typedef struct {
        int rows;
        int cols;
        SMEntry x[10000];
    } SparseMatrix;
    Then you can create a SparseMatrix with arbtirary number of rows and columns and up to 9999 nonzero entries (saving one array slot for an end-marker).

    Example to initialize the example you gave from above:

    Code:
    SparseMatrix m = {
        5, 5, 
        {
            (SMEntry){0, 0, -1},
            (SMEntry){0, 4, 2},
            (SMEntry){1, 1, 5},
            (SMEntry){1, 3, 6},
            (SMEntry){2, 2, 7},
            (SMEntry){3, 1, 8},
            (SMEntry){3, 3, 9},
            (SMEntry){4, 0, 3},
            (SMEntry){4, 4, -4},
            (SMEntry){-1,-1,-1}  // end marker    
        }
    };
    Then I would define the functions that you want to use to access your data structure. You need to at least create a sparse matrix, read it from a file, write it to a file, and most likely to print it out in normal matrix format (maybe its not required explicitly but its basically required for debugging)
    Last edited by c99tutorial; 12-12-2012 at 08:55 AM.

  4. #4
    Registered User
    Join Date
    Dec 2010
    Posts
    10
    Fantastic thanks for your help! I'll get cracking on trying to implement this tomorrow and let you know how I get on - I'm sure there will be some stumbling blocks along the way!
    Cheers

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. adjacency matrix and sparse matrix
    By dpp in forum C Programming
    Replies: 3
    Last Post: 07-11-2010, 10:26 AM
  2. Free Sparse Matrix
    By kavka3 in forum C Programming
    Replies: 1
    Last Post: 02-06-2009, 11:01 AM
  3. Sparse Matrix
    By brb9412 in forum C Programming
    Replies: 3
    Last Post: 01-02-2009, 12:12 PM
  4. Genrate sparse matrix - C99
    By anirban in forum C Programming
    Replies: 0
    Last Post: 06-10-2008, 11:44 PM
  5. Sparse matrix
    By milenkom in forum C++ Programming
    Replies: 4
    Last Post: 01-02-2008, 03:17 PM

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