SVD, linear algebra library for my problem?

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

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 on other sites
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 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 gfxnomadrumble, 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 on other sites
Quote:
 Original post by rumbleI 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 on other sites
Quote:
Original post by Maze Master
Quote:
 Original post by rumbleI 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 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 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 gfxnomadThe 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 on other sites
M = U D V* is the normal convention in math at least. Perhaps gamedev conventions are different?

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 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/

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 12
• 30
• 9
• 16
• 12