Ordering strategies and related techniques to overcome the trade-off between parallelism and convergence in incomplete factorizations

This paper is concerned with the parallel implementation of the incomplete factorization preconditioned iterative method. Although the use of such par allel ordering as multicolor ordering may increase parallelism in factoriza tion, it often slows convergence when used in the preconditioned method, an d thus may offset the gain in speed obtained with parallelization. Further, the higher the parallelism of an ordering, the slower the convergence; the lower the parallelism, the faster the convergence. This well-known trade-o ff between parallelism and convergence is well explained by the property of compatibility, the level of which can be clearly seen when ordering is pre sented in graph form (S. Doi, A. Lichnewsky, A graph-theory approach for an alyzing the effects of ordering on ILU preconditioning, INRIA report 1452, 1991). In any given method, the fewer the incompatible local graphs in an o rdering (i.e., the lower the parallelism), the faster the convergence (S. D oi, Appl. Numer. Math. 7 (1991) 417-436; S. Doi, in: T. Nodera (Ed.), Advan ces in Numerical Methods for Large Sparse Sets of Linear Systems, 7 Keio Un iversity, 1991). An ordering with no incompatible local graphs, for example , such as that implemented on Vector multiprocessors by using the nested di ssection technique, will have excellent convergence, but its parallelism wi ll be limited (S. Doi, A. Lichnewsky, Int. J. High Speed Comput. 2 (1990) 1 43-179). To attain a better balance, a certain degree of incompatibility is necessary. Ln this regard, increasing the number of colors in multicolor o rdering can be a useful approach (S. Fujino, S. Doi, in R. Beauwens (Ed.), Proceeding of the IMACS Internation Symposium on Iterative Methods in Linea r Algebra, March 1991; S. Doi, A. Hoshi, Int. J. Comput. Meth. 44 (1992) 14 3-152). Two related techniques also presented here are the overlapped multi color ordering (T. Washio, K. Hayami, SIAM J. Sci. Comput. 16 (1995) 631-65 0), and a fill-in strategy selectively applied to incompatible local graphs . Experiments conducted with an SX-5/16A vector parallel supercomputer show the relative effectiveness of increasing the number of colors and also of using this approach in combination with overlapping and with fill-ins. (C) 1999 Published by Elsevier Science B.V. All rights reserved.