# 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