Abstract
We investigate the effect of the ordering of the unknowns on the convergence of the preconditioned conjugate gradient method. We examine a wide range of ordering methods including nested dissection, minimum degree, and red-black and consider preconditionings without fill-in. We show empirically that there can be a significant difference in the number of iterations required by the conjugate gradient method and suggest reasons for this marked difference in performance.
We also consider the effect of orderings when an incomplete factorization which allows some fill-in is performed. We consider the effect of automatically controlling the sparsity of the incomplete factorization through drop tolerances and level of fill-in.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adams, L. M. and Jordan, H. F. (1984).Is SOR color-blind? SIAM J. Sci. Stat. Comput.7, 490–506.
Adams, L. M., LeVeque, R. J., and Young, D. M. (1988).Analysis of the SOR iteration for the q-point Laplacian. SIAM J. Numer. Anal.25, 1156–1180.
Axelsson, O. and Eijkhout, V. (1988).Robust vectorizable preconditioners for three-dimensional elliptic difference equations with anisotropy. InAlgorithms and Applications on Vector and Parallel Computers. H J J te Riele, Th J Dekker, and H A van der Vorst (editors). North-Holland, Amsterdam, New York, and London.
Behie, A. and Forsyth, P. A. (1984).Incomplete factorization methods for fully implicit simulation of enhanced oil recovery. SIAM J. Sci. Stat. Comput.5, 543–561.
Concus, P., Golub, G. H., and Meurant, G. (1985).Block preconditioning for the conjugate gradient method. SIAM J. Sci. Comput.6, 220–252.
Cuthill, E. and McKee, J. (1969).Reducing the bandwidth of sparse symmetric matrices. Proceedings 24th National Conference of the Association for Computing Machinery, Brandom Press, New Jersey, 157–172.
Duff, I. S., Erisman, A. M., and Reid, J. K. (1986).Direct Methods for Sparse Matrices. Oxford University Press, London.
Duff, I. S., Erisman, A. M., and Reid, J. K. (1976).On George's nested dissection method. SIAM J. Numer. Anal.13, 686–695.
Eisenstat, S. C., Gursky, M. C., Schultz, M. H., and Sherman, A. H. (1982).Yale sparse matrix package. 1: The symmetric codes. Int. J. Numer. Meth. Engng.18, 1145–1151.
Eisenstat, S. C., Elman, H. C., and Schultz, M. H. (1988).Block-preconditioned conjugate gradient-like methods for numerical reservoir simulations. SPE Reservoir Engineering. (Feb. 1988), 307–312.
George, A. (1971).Computer implementation of the finite-element method. Report Stan CS-71-208, Ph.D Thesis, Department of Computer Science, Stanford University, Stanford, California.
George, A. (1973).Nested dissection of a regular finite-element mesh. SIAM J. Numer. Anal.10, 345–363.
George, A. and Liu, J. W. H. (1981).Computer Solution of Large Sparse Positive-definite Systems. Prentice-Hall, Englewood Cliffs, New Jersey.
Golub, G. H. and Meurant, G. A. (1983).Résolution Numérique des Grandes Systèmes Linéaires. Eyrolles, Paris.
Gustafsson, I. (1979).Stability and rate of convergence of modified incomplete Cholesky factorization methods. PhD dissertation, Chalmers University, Göteborg, Sweden.
Hageman, L. A. and Young, D. M. (1981).Applied Iterative Methods. Academic Press, New York and London.
Kuo, C. C. J. and Chan, T. F. (1988).2-color Fourier analysis of iterative algorithms for elliptic problems with red/black ordering. CAM Report 88-15, Computational and Applied Mathematics, University of California, Los Angeles.
Lichnewsky, A. (1984).Some vector and parallel implementations for preconditioned conjugate gradient algorithms. InHigh-speed Computation. NATO ASI Series. Vol. F.7, edited by J. S. Kowalik. Springer-Verlag, Berlin, 343–359.
Meijerink, J. A. and van der Vorst, H. A. (1977).An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comp.31, 148–162.
O'Leary, D. P. (1982).Solving sparse matrix problems on parallel computers. Report 1234, Computer Science Center, University of Maryland, Maryland.
Schreiber, R. and Tang, W-P. (1982)Vectorizing the conjugate gradient method. Unpublished document. Department of Computer Science, Stanford University, Stanford, California.
Simon, H. D. (1985).Incomplete LU preconditioners for conjugate-gradient-type iterative methods. Paper SPE 13533, Proceedings of the 1985 Reservoir Simulation Symposium, Dallas, Feb. 10–13, 1985, 387–396.
Tinney, W. F. and Walker, J. W. (1967).Direct solutions of sparse network equations by optimally ordered triangular factorization. Proc. IEEE55, 1801–1809.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Duff, I.S., Meurant, G.A. The effect of ordering on preconditioned conjugate gradients. BIT 29, 635–657 (1989). https://doi.org/10.1007/BF01932738
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01932738