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

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$)

• Where do these matrices come from? Are distributed sparse direct solvers an option, e.g., SuperLU_Dist, MUMPS? If you run out of memory due to fill-in, is Incomplete Cholesky(0) or Incomplete LU(0) (depending on the package you use to compute the decomposition) a viable option? Could you derive a preconditioner through other means (e.g., problem structure, physics)? PETSc (or Trilinos) is a good option for trying out different preconditioners and iterative linear solvers. – Geoff Oxberry Jul 20 '15 at 9:52
• @GeoffOxberry, thx ! I'm not allowed to install distributed software on the cluster... The matrix is coming from a d-dimentional interpolation ($2<d<20$) with compactly supported radial basis function. I was not aware of PETSc (Trilinos), I will have a look. I have no intuition on how to choose the preconditioner, so I can't really derive it by other mean... incomplete Cholesky (LU) could be an option but I don't know any software that can handle it for sparse matrices – PinkFloyd Jul 20 '15 at 10:08
• @PinkFloyd, what do you mean you're not allowed to install software? You have a directory where you can write files, right? Just because you don't have root access, that doesn't mean you can't install software. – Bill Barth Jul 20 '15 at 11:51
• @BillBarth, yeah, I know. But the IT people that handle the cluster are not at all willing to let anyone use some library that they haven't checked themselves... we had to sign something that we would only run our "own" code with no external library that they haven't checked. Plus it's quite hard to push them to check a given library... – PinkFloyd Jul 20 '15 at 14:52
• @PinkFloyd, that's insane. Good luck! Maybe move your work to a more usable system? – Bill Barth Jul 20 '15 at 15:00

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

• (-1) "You must disclose your affiliation in your answers": scicomp.stackexchange.com/help/promotion – Kirill Apr 17 '16 at 23:15
• Please see my profile; there is a clear reference to my website there. I will copy it here: ozemail.com.au/~comecau – SparseSolverCodes Apr 17 '16 at 23:22
• I think the idea is that it should be mentioned directly in your answers (including your other answers to other questions too). – Kirill Apr 17 '16 at 23:27
• Judging on the content of answers provided by other visitors to this forum, it appears that such demand is applied personally to me only. I hope there is no double standard in this case. – SparseSolverCodes Apr 17 '16 at 23:33