Ordering techniques for the preconditioned conjugate gradient method on parallel computers

We consider the parallel implementation of the preconditioned conjugate gradient method using multicolor incomplete factorization as preconditioners. We discuss numerical experiments on sample problems arising from elliptic partial differential equations, together with an analytic study of the effects of communication and artihmetic costs on loosely coupled architectures. Our main conclusion is that multicolor orderings result in slower convergence of the preconditioned conjugate gradient method than natural orderings, but that the lower parallel costs of the multicolor techniques typically make their overall performance better.