CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 25
  1. #1
    Join Date
    Jun 2004
    Posts
    77

    Sparse Matrix Solving

    I have a program written in c++ right now that its purpose is to solve a linear algebra problem Ax=b, A being a 2d matrix and x and b being vectors. The problem is, A and B get too large for it to be effecient in memory, so I need to do this in sparse format somehow. A is a sparse, symmetrical matrix, so somehow it has to be represented by vectors that store only the non-zero numbers with their row and column. Does anyone have any suggestions on how this can be done efficiently? I looked around and couldn't find any pre-written solvers that I could understand how to use. Any help/suggestions would be wonderful.

  2. #2
    Join Date
    Dec 2004
    Posts
    57

    Re: Sparse Matrix Solving

    Check out TNT (Template Numerical Toolkit) from NIST:

    http://math.nist.gov/tnt/

    I take it you are trying to solve for x, given A and b?

    How you solve the problem depends on the nature of A. When you say it is sparse, do you know anything else about its structure? Do you know in advance how many elements per row?

    If it's symetric, you only need to store A(i,j), for i<=j and A(i,j) != 0.

    You can make a special matrix class that stores each row with a special class that only has N elements, and each element has the column position and the value, e.g.,

    Code:
    class RowElement {
    public:
      int col;
      float value;
    };
    Then for each row, you have some chain (list, vector, etc) of these depending on how sparse the matrix is. When you do your math, you loop over each element in this chain and assume everything else is zero. I've use this for cases where there were only six non-zero elements per row, out of a few hundred thousand columns.

  3. #3
    Join Date
    Jun 2004
    Posts
    77

    Re: Sparse Matrix Solving

    Yes, I am trying to solve for x, given A and b, and I do know beforehand the number of rows and columns, so I know the number or elements in each row and column, but not the number of elements that are non-zero in each row and column.
    When you do your math, you loop over each element in this chain and assume everything else is zero. I've use this for cases where there were only six non-zero elements per row, out of a few hundred thousand columns.
    This sounds like a good idea, but what kind of math is fairly easy to do with a sparse matrix set up like this? Thanks

  4. #4
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: Sparse Matrix Solving

    What kind of matrix dimension are you talking about ? (I'm guessing several thousand otherwise it should fit in memory anyway).

    And how sparse are the matrixes to begin with ? What % of elements (average) is 0 ?


    If sparesness is not sufficiently high, then any datastructure other than a 2dim array is just going to cost you a lot in performance. If you stick with a straightforward array, there are tricks to improve locality of reference and work around the excessive paging you end up getting when you're using Virtual memory.

  5. #5
    Join Date
    Dec 2004
    Posts
    57

    Re: Sparse Matrix Solving

    Several problems that I've worked on involve solving matrices as part of a gradient descent optimization strategy. You are frequently computing things like y = Ax or y = Ax + b, so if you know the sparseness of the matrix you can reduce computation time significantly. When only 6 of 500,000 elements in a row are non-zero, you really don't want to store or even compute those results. Often these problems are specifically formulated to solve an inverse problem.

  6. #6
    Join Date
    Jun 2004
    Posts
    77

    Re: Sparse Matrix Solving

    Well from what I remember(I cant check until next monday for sure), roughly something like 10% of the values in the matrix are non-zero values. The current situation I've been working on, the main matrix is roughly 13000x13000 so 169,000,000. The files in the future will create bigger 2d arrays than this, so i think only storing non-zero values is the only way its gonna be able to be done.

  7. #7
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: Sparse Matrix Solving

    Yup. But I've seen programmers trying to create nifty 'sparse matrix' solutions for problems where only like 10% or so elements was zero. They ended up using more memory, and lots more code. A simple straightforward 2dim array solution was loads faster.

    Properly understanding the problem is key when trying to solve things like this. :-)

  8. #8
    Join Date
    Jun 2004
    Posts
    77

    Re: Sparse Matrix Solving

    Hehe alright, but heres my problem. With a 2 dimensional array of 169,000,000 complex<double> elements, it uses between 3 and 4 gigs of virtual memory. How can that be done more efficiently using less memory?

  9. #9
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: Sparse Matrix Solving

    Your calculation is 'off' a bit. The array has 169Mil elements, but the memory consumption is going to be considerably higher (4times as much when storing floats, 8 times as much for doubles).
    This is indeed going to be causing memory problems fairly quickly.

    However 10% is still 'kinda high' for a sparse matrix. You will be sacrificing quite a bit of performance to reduce memory usage.

  10. #10
    Join Date
    Jun 2004
    Posts
    77

    Re: Sparse Matrix Solving

    Well yeah I actually did do the math and ran the program with complex doubles and with something like a 3.5gig page file the computer ran out of memory, when I changed it to complex floats it used something close to 2 gigs of page file. Anyways, I cant be positive of the amount of the 2d array that is actually non-zero, but on monday morning I can quick go write a little code to see how much of the matrix is non-zero, and I can get an update for you then. Until then, thanks for the help

  11. #11
    Join Date
    Dec 2004
    Posts
    57

    Re: Sparse Matrix Solving

    If you use an approach like I suggested, you will use (I'll assume doubles here) 12 bytes per element (index + double). This is an increase of 50% over the cost of just storing a double. There is also some overhead in terms of managing the list of elements in each row, but I'll ignore that for now.

    Assuming your matrix has only 10% non-zeros, this means that you would use only 15% of the memory for storing the data elements that you would if you just stored a flat array. If you use floats, this goes to 20%.

    Ah, I just saw your latest post and you're using complex data. This means the percentage will be 12.5% (15% for floats) of what you would normally be using since the size is 16 bytes (complex double ) + 4 bytes (index), as compared to just 16 bytes. This yields 20 bytes * 0.1N = 2N vs. 16 * N, where N is the size of your matrix.

    The cost of the indexing overhead depends on how much you know about your data in advance.

  12. #12
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: Sparse Matrix Solving

    ouch, complex datatype...
    10% of 169.000.000 elements at 16 bytes each with x,y coordinate (+8) =
    405Mb, and then you still need the 'database' to locate an element at X,Y...

    And you say you're going for matrixes even bigger than that...

    I'm starting to think that what you need is not an implementation of a sparse matrix in memory. But an optimal way to do matrix calculation by loading chunks of the matrix in memory, and doing the entire calculation in several stages.

    I have a program that does matrix calculations for matrices up to 1.000.000.000 x 1.000.000.000 in size. And it does things surprisingly fast too (even when using non sparse matrices, Largest I tried was 10.000x10.000 and this took 'only' about 7 hours on a 1Ghz machine (enforced down to only 64Mb Memory), which is quite good given the amount of calculation it needed to do). The manual says it does calculations in blocks, but doesn't list a specific algorythm name.

    Maybe searching around the internet will show you on your way to do things this way.

  13. #13
    Join Date
    Jun 2004
    Posts
    77

    Re: Sparse Matrix Solving

    Well the problem is that I dont have a lot of experience programming in C++. Im in college and doing this for one of my professors as a job, and I'm an engineer, so Ive had 2 classes in c++. Doing things in blocks like you talked about would probably be a little out of my league unless I could find a good code that already did it. And yes, 7 hours for a 10,000x10,000 matrix is very fast.

  14. #14
    Join Date
    Jun 2004
    Posts
    77

    Re: Sparse Matrix Solving

    Also when you did that 10,000x10,000 matrix calculation, you still had to have all of that stored in memory before you started, correct? That right there is a rather large chunk of memory.

  15. #15
    Join Date
    Jun 2004
    Posts
    77

    Re: Sparse Matrix Solving

    And on monday I'll have a better number for the % of the matrix that is non-zeros, which I guess will really be the deciding factor on what I choose to do.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured