The effect of ordering on preconditioned conjugate gradients. (English) Zbl 0687.65037

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.
Reviewer: P.C.Hansen


65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations


YSMP; symrcm
Full Text: DOI


[1] Adams, L. M. and Jordan, H. F. (1984).Is SOR color-blind? SIAM J. Sci. Stat. Comput.7, 490–506. · Zbl 0601.65018
[2] 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. · Zbl 0662.65090
[3] 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.
[4] 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. · Zbl 0548.65017
[5] Concus, P., Golub, G. H., and Meurant, G. (1985).Block preconditioning for the conjugate gradient method. SIAM J. Sci. Comput.6, 220–252. · Zbl 0556.65022
[6] 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.
[7] Duff, I. S., Erisman, A. M., and Reid, J. K. (1986).Direct Methods for Sparse Matrices. Oxford University Press, London. · Zbl 0604.65011
[8] Duff, I. S., Erisman, A. M., and Reid, J. K. (1976).On George’s nested dissection method. SIAM J. Numer. Anal.13, 686–695. · Zbl 0345.65015
[9] 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. · Zbl 0492.65012
[10] 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.
[11] 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.
[12] George, A. (1973).Nested dissection of a regular finite-element mesh. SIAM J. Numer. Anal.10, 345–363. · Zbl 0259.65087
[13] George, A. and Liu, J. W. H. (1981).Computer Solution of Large Sparse Positive-definite Systems. Prentice-Hall, Englewood Cliffs, New Jersey. · Zbl 0516.65010
[14] Golub, G. H. and Meurant, G. A. (1983).Résolution Numérique des Grandes Systèmes Linéaires. Eyrolles, Paris.
[15] Gustafsson, I. (1979).Stability and rate of convergence of modified incomplete Cholesky factorization methods. PhD dissertation, Chalmers University, Göteborg, Sweden. · Zbl 0417.65052
[16] Hageman, L. A. and Young, D. M. (1981).Applied Iterative Methods. Academic Press, New York and London. · Zbl 0459.65014
[17] 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.
[18] 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.
[19] 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. · Zbl 0349.65020
[20] O’Leary, D. P. (1982).Solving sparse matrix problems on parallel computers. Report 1234, Computer Science Center, University of Maryland, Maryland.
[21] Schreiber, R. and Tang, W-P. (1982)Vectorizing the conjugate gradient method. Unpublished document. Department of Computer Science, Stanford University, Stanford, California.
[22] 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.
[23] Tinney, W. F. and Walker, J. W. (1967).Direct solutions of sparse network equations by optimally ordered triangular factorization. Proc. IEEE55, 1801–1809.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.