# Problem with convergence of Jacobi iterative algorithm

I'm dealing with Jacobi iterative method for solving sparse system of linear equations. For small matrices it works well and gives right answers even if matrix is not strictly diagonal dominant, however for the case of really big matrices ($100000*100000$) it does not converge because the matrix is not diagonal. Many articles suggest to interchange rows and columns in order to make diagonal dominant matrices, however for the case of my matrix it is always not diagonal dominant. Could anyone please, suggest me how to deal with this problem? Maybe there is some method how to choose right initial approximation or maybe there is more robust algorithm exists. I'm a newcomer in this field and I would be appreciated for any help.

• If your matrix is symmetric and positive definite, Gauss-Seidel should converge (assuming you are tied to stationary methods for some reason; otherwise conjugate gradients would probably be a better choice). Commented Feb 19, 2014 at 10:58
• I'd start with GMRES and get estimates of the singular values to understand the conditioning of the system before trying something with fewer BLAS operations, like CG. In terms of preconditioners, I'd start with something like ILU (due to its robustness), before switching to a less-expensive preconditioner. Commented Feb 19, 2014 at 18:37

## 1 Answer

The Jacobi iteration is the worst possible solver for linear systems. Furthermore, contrary to your belief (but easy to show), it is entirely independent of the ordering of the unknowns, so reordering rows and columns of the system makes absolutely no difference.

There are many better methods for solving linear systems, among them CG and GMRES, and there are many good books on the subject (e.g., the one by Y. Saad). My take on many of the issues with solver and preconditioners is given in lectures 34-38 at http://www.math.tamu.edu/~bangerth/videos.html .