seeking for linear solver for over-determined systems

Hi everybody,

Right now I am doing research which requires me to solve an sparse over-determined system many times, which takes plenty of time (usually 3-4 days). So I wonder is there a decent implementation of GMRES or BiConjugate gradient methods for this problem?

I searched a while and found out CNC’s code uses CG and it won’t work for over-determined system…

If so, please leave me a reply and It will be really appreciated!

We’re working on a library called Cusp that will eventually implement standard Krylov methods like GMRES and BiCG. However, it only implements CG at the moment.

How do you intend to solve your over-determined system with GMRES or BiGC? If you’re using the normal equations ( A^T * A x = A^T b ) then CG should be fine since A^T * A is an SPD matrix. Of course the normal equations can be poorly conditioned.

You can always build your own sparse solving using these SpMV kernels.

Thanks for your Info.

I am trying to solve a over-determined system like this: (Ax= B ) a nXn SPD matrix and a additional (m-n) set of equations which fills only one cell of each line, so this makes a mXn matrix A.

Then I don’t know much about the pros and cons of different solvers, so will this normal euquations method work for my problem? If not, do u have any suggestions?

The normal equations should solve your problem, but there are other techniques that may be better. I would recommend looking in Yousef Saad’s book titled “Iterative Methods for Sparse Linear Systems”. The first edition of this book is available for free online:

Chapter 8 discusses solvers for the normal equations:

You might want to prototype these with MATLAB (or similar) before pursing a CUDA implementation.