|
Abstract : |
The efficiency of a parallel implementation of the conjugate gradient method preconditioned by an incomplete Cholesky factorization can vary dramatically depending on the column ordering chosen. One method to minimize the number of major parallel steps is to choose an ordering based on a coloring of the symmetric graph representing the nonzero adjacency structure of the matrix. In this paper, we compare the performance of the preconditioned conjugate gradient method using these coloring orderings with a number of standard orderings on matrices arising from finite element models. Because optimal colorings for these systems may not be known a priori, we employ a graph coloring heuristic to obtain consistent colorings. Based on lower bounds obtained from the local structure of these systems, we find that the colorings determined by the heuristic are nearly optimal. For these problems, we find that the increase in parallelism afforded by the coloring-based orderings more than offsets any increase in the number of iterations required for the convergence of the conjugate gradient algorithm. We give results from the Intel iPSC/860 to support our claims. Key words: conjugate gradient methods, distributed-memory computers, graph coloring heuristics, incomplete Cholesky, parallel algorithms, sparse matrices, |
