The effect of ordering on preconditioned conjugate gradients (Q1263244)

The effect of ordering of the unknowns on the convergence of the preconditioned conjugate gradient method is investigated experimentally. 17 different orderings are studied on two model problems and two more complicated elliptic equations, using a modified version of the Yale sparse matrix package. The conclusion from the study is that the number of iterations is almost directly related to the norm of the residual matrix for the preconditioner, but not to the number of fill-ins dropped in the incomplete factorization. Moreover, it seems that the best results are obtained for orderings which are ``local'' in the sense that the unknowns in the original system have numbers that are not too far apart. An example which proves that this is only a sufficient condition is also given. It appears that the harder the problem at hand (discontinuous coefficients, anisotropy, etc.) the more important is the ordering for the incomplete factorization.