Summary
The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, “repeated red-black” ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Axelsson, O., Gustavsson, I. (1980): On the use of preconditioned conjugate gradient methods for red-black ordered five-point difference schemes. J. Comput. Phys.35, 284–289
Behie, G.A., Collins, D.A., Forsyth, P.A. Jr. (1984): Incomplete factorization methods for three-dimensional non-symmetric problems. Comput. Methods Appl. Mech. Eng.42, 287–299
Behie, G.A., Forsyth, P.A. (1984): Incomplete factorization methods for fully implicit simulation of enhanced oil recovery. SIAM J. Sci. Stat. Comput.5, 543–561
Brand, C.W., Heinemann, Z.E. (1990): A new iterative solution technique for reservoir simulation equations on locally refined grids. Paper SPE 18410, SPE Reservoir Eng.5, 555–560
Concus, P., Golub, G.H., Meurant, G. (1985): Block preconditioning for the conjugate gradient method. SIAM J. Sci. Stat. Comput.6, 220–252
Concus, P., Golub, G.H., O'Leary, D.P. (1976): A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations. In: Bunch, J.R., Rose, D.J., eds., Sparse matrix computations. Academic Press, New York, pp. 309–332
Duff, I.S., Meurant, G.A. (1989): The effect of ordering on preconditioned conjugate gradients. BIT29, 635–657
Dupont, T., Kendall, R.P., Rachford, H. (1968): An approximate factorization procedure for solving self adjoint elliptic difference equations. SIAM J. Numer. Anal.5, 559–573
Elman, H.C., Golub, G.H. (1988): Iterative methods for cyclically reduced non-self-adjoint linear systems. Computer Science Technical Report Series CS-TR-2145, Univ. of Maryland
George, A. (1973): Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal.10, 345–363
Golub, G.H., Van Loan, C.F. (1983): Matrix computations. John Hopkins, Baltimore
Gustavsson, I. (1978): A class of first order factorization methods. BIT18, 142–156
Meijerink, J.A., van der Vorst, H.A. (1977): Iterative solution method for linear systems of which the coefficient matrix is a symmetricM-matrix. Math. Comput.31, 148–162
Price, H.S., Coats, K.H. (1974): Direct methods in reservoir simulation. Trans. AIME257, II, 295–308
Tan, T.B.S., Letkeman, J.P. (1982): Application of D4 ordering and minimization in an effective partial matrix inverse iteration method. Paper SPE 10493, presented at the Sixth SPE Symposium on Reservoir Simulation, New Orleans
Varga, R.S. (1962): Matrix iterative analysis. Prentice Hall, Englewood Cliffs, NJ
Vinsome, P.K.W. (1976): ORTHOMIN, an iterative method for solving sparse sets of simultaneous linear equations. Paper SPE 5729, presented at the Fourth SPE Symposium on Reservoir Simulation, Los Angeles
Watts, J.W. (1981): A conjugate gradient truncated direct method for the iterative solution of the reservoir simulation pressure equation. Soc. Pet. Eng. J.21, 345–353
Young, D.M. (1971): Iterative solution of large linear systems. Academic Press, New York San Francisco London
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Brand, C.W. An incomplete-factorization preconditioning using repeated red-black ordering. Numer. Math. 61, 433–454 (1992). https://doi.org/10.1007/BF01385519
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01385519