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:
http://www-users.cs.umn.edu/~saad/books.html
Chapter 8 discusses solvers for the normal equations:
http://www-users.cs.umn.edu/~saad/PS/iter3.pdf
You might want to prototype these with MATLAB (or similar) before pursing a CUDA implementation.