Jump to content
  • Advertisement
Sign in to follow this  
rumble

SVD, linear algebra library for my problem?

This topic is 3801 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

According to a paper, I need SVD to calculate pseudoinverses. I need the pseudoinverse because the paper says it would calculate the least square solution to a system of equations that may be singular. In other words, a solution that fits the equations best, though does not solve it exactly. I would prefer one in C++ that calculates SVD, eigenvalues, eigenvectors, pseudoinverses, and other linear algebra routines I may use later on. A simple search yields LINPACK and LAPACK. I am unfamiliar with either. Any others recommended?

Share this post


Link to post
Share on other sites
Advertisement
rumble,

It depends on your needs. Are you working with dense matrices alone, or sparse matrices as well? What is the order of the size of your matrices? I ran into a need for this type of software in my research, and finding a package that suited my needs and did not have a an absolutely disgusting interface was difficult. I needed eigendecomposition of large (order of hundreds of thousands), sparse, possibly asymmetric matrices. Further I wanted to speed up the computation of eigenvectors by taking advantage of the Shift-Invert spectral transform to avoid the super-linearity in the number of requested eigen-pairs. My original code was in Matlab, where everything was trivial. However, as you can imagine, I didn't want to have to run all my data through Matlab. First I tried different combination of the "standard packages", tied together for C++ by using Arpack++. I eventually found that package to be so broken as to be unusable. I finally settled on SlepC. This package requires a lot of others, but provides all the functionality I want and more. However, it still has an absolutely ugly interface, so I've been wrapping all the stuff I need in some nicer looking function calls. If you NEED the functionality, then I recommend this package. However, if you are dealing with much smaller matrices,the I suggest you avoid all of these industrial strength Linear Algebra packages in favor of something simpler and prettier. In the past I've used newmat for the SVD and eigendecomposition of small matrices and found it a pleasure to work with.

Cheers,
Rob

Share this post


Link to post
Share on other sites
My problem revolve around contouring of geometric data; for example, the best fit intersection of several planes. If there are two planes, I need to choose a point on the intersection line; if there are more than three planes, I need to find a point that approximately these planar intersections the closest. (In theory, these three or more planes should intersect exactly at one point. But in practice, numeric accuracy may prevent that)

Thus in either case I deal with matrices that cannot be inverted. From my vague understandings so far, pseudoinverses of these matrices can give me a best fit solution, hence my need for SVD.

Thanks for the input. I will investigate your recommendations. I also became aware MatLab has a C++ version of their library functions. Could you have used that instead?


Quote:
Original post by gfxnomad
rumble,

It depends on your needs. Are you working with dense matrices alone, or sparse matrices as well? What is the order of the size of your matrices? I ran into a need for this type of software in my research, and finding a package that suited my needs and did not have a an absolutely disgusting interface was difficult. I needed eigendecomposition of large (order of hundreds of thousands), sparse, possibly asymmetric matrices. Further I wanted to speed up the computation of eigenvectors by taking advantage of the Shift-Invert spectral transform to avoid the super-linearity in the number of requested eigen-pairs. My original code was in Matlab, where everything was trivial. However, as you can imagine, I didn't want to have to run all my data through Matlab. First I tried different combination of the "standard packages", tied together for C++ by using Arpack++. I eventually found that package to be so broken as to be unusable. I finally settled on SlepC. This package requires a lot of others, but provides all the functionality I want and more. However, it still has an absolutely ugly interface, so I've been wrapping all the stuff I need in some nicer looking function calls. If you NEED the functionality, then I recommend this package. However, if you are dealing with much smaller matrices,the I suggest you avoid all of these industrial strength Linear Algebra packages in favor of something simpler and prettier. In the past I've used newmat for the SVD and eigendecomposition of small matrices and found it a pleasure to work with.

Cheers,
Rob


Share this post


Link to post
Share on other sites
Quote:
Original post by rumble
I also became aware MatLab has a C++ version of their library functions. Could you have used that instead?


Do you know if there is something similar with GNU Octave (Matlab clone)?

Share this post


Link to post
Share on other sites
Quote:
Original post by Maze Master
Quote:
Original post by rumble
I also became aware MatLab has a C++ version of their library functions. Could you have used that instead?


Do you know if there is something similar with GNU Octave (Matlab clone)?


I would think if it is open source, you can mine out the c++ functions the Octave language calls?

Share this post


Link to post
Share on other sites
The nice thing about Matlab is that they go through all the trouble to wrap their stuff in C++ and expose their math library nicely. AFIK, nothing comparable is done by Octave, so if you want to use Octave's routines, you'll have some seriously dirty hacking to do. I really do like Matlab's library, but I want to eventually release my code w/o non-free dependencies, so it's not really an option for me. However, if you're not burdened by the same restrictions, it seems like one of the easier paths.

Share this post


Link to post
Share on other sites
Hi Rob

Just a rant. I set up newmat and went through hours debugging why SVD gives incorrect results. That is, after SVD and reconstruct the original matrix M, I get M != transpose(U)*D*V

Fortunately I noticed eventually this below gives the correct result, contrary to usual conventions, unless I m mistaken.

M = U*D*transpose(V)
and
inverse(M) = V*invese(D)*transpose(U)

Anyways, what do you do in a situation like this? No active community for support; who knows if the author would reply within time.

Also, it's hard to examine the data in the matrices. I always have to print them out.

Quote:
Original post by gfxnomad
The nice thing about Matlab is that they go through all the trouble to wrap their stuff in C++ and expose their math library nicely. AFIK, nothing comparable is done by Octave, so if you want to use Octave's routines, you'll have some seriously dirty hacking to do. I really do like Matlab's library, but I want to eventually release my code w/o non-free dependencies, so it's not really an option for me. However, if you're not burdened by the same restrictions, it seems like one of the easier paths.


Share this post


Link to post
Share on other sites
when you write

M!= U D transpose(V)

how different where they? also typically SVD algorithms first construct

M "=" Uprime bD transpose(Vprime)

where bD is a matrix with entries on the diaganol and possibly some 1's on he upper diaganol. The step to from from bD to D can sometimes get sticky... by "=" i mean approximately equal.

LAPACK and LINPACK originate from (drum roll of despair) Fortran! icky old style Fortran77 usually.... so naturally the C++/C interface looks awful!

also, it really is important to understand the nature of your matrices:

1) are they sparse?
2) are they huge or small?

LAPACK and LINPACK are mostly for full matrices, and the SVD is O(I N^3) where N is the dimension and I is the number of iterations (in the bD to D step), so beware!



Share this post


Link to post
Share on other sites
I have used GSL for SVD some times ago. It has C interface. IIRC compilation was not exactly trivial but not too difficult either.

http://www.gnu.org/software/gsl/

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!