solve linear system of equation of a large sparse symetric positive definite matrix

Question

I want to invert large matrices ($10^4 \times 10^4$ to $10^6 \times 10^6$) but sparse (less than $100$ non-zero entries per line) on clusters with $16$ to $48$ processors per node.

I'm looking for an efficient method to do so. I've tried a few different solutions but I face some problems.

• As the matrix is big, my first attempt to use lapack failed because it doesn't handle sparse matrix
• The condition number can be quite large
• It seems that with that kind of matrix, the exact solvers are not efficient

On the positive side, I don't need an exact inverse or an exact solution to the equation $Ax=b$, therefore iterative methods may be more efficient. I think I'm going to use the conjugate gradient method because I could efficiently make use of the many processors.

My question comes now : do you think that this method could be efficient ? if so, what preconditioner should I use ? (I can't really use the Jacobi preconditioner because $A_{ii}=1$ and $\sum_{j\neq i}|A_{ij}|\approx 10$)

Answer 1

Yes, you can solve such system (up to several million equations) on an ordinary PC. You will need to use a very accurate implementation of the CG method. The problem is with (a) storing such large matrix in the RAM; and (b) efficient implementation of the major mathematical operation, namely: the matrix-by-vector multiplication. There is a solver that satisfies the above-mentioned requirements; please follow the link below (in particular, that webpage provides an example of a very large system, arising from the Finite Element Method):

http://members.ozemail.com.au/~comecau/CMA_Sparse.htm