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). – Christian Clason Feb 19 '14 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. – Geoff Oxberry Feb 19 '14 at 18:37