Preconditioning by incomplete block cyclic reduction

Authors:
Garry Rodrigue and Donald Wolitzer

Journal:
Math. Comp. **42** (1984), 549-565

MSC:
Primary 65F10; Secondary 65W05

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736452-6

MathSciNet review:
736452

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Iterative methods for solving linear systems arising from the discretization of elliptic/parabolic partial differential equations require the use of preconditioners to gain increased rates of convergence. Preconditioners arising from incomplete factorizations have been shown to be very effective. However, the recursiveness of these methods can offset these gains somewhat on a vector processor. In this paper, an incomplete factorization based on block cyclic reduction is developed. It is shown that under block diagonal dominance conditions the off-diagonal terms decay quadratically, yielding more effective algorithms.

**[1]**O. Axelsson, "A generalized SSOR method,"*BIT*, v. 13, 1972, pp. 443-467. MR**0339467 (49:4226)****[2]**P. Concus, G. Golub & D. P. O'Leary, "A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations," in*Sparse Matrix Computations*(J. R. Bunch and D. J. Rose, eds.), Academic Press, New York, 1976, pp. 309-332. MR**0501821 (58:19069)****[3]**P. Dubois & G. Rodrigue,*An Analysis of the Recursive Doubling Algorithm*, Proceedings of High Speed Computer and Algorithm Organization, Academic Press, New York, 1977.**[4]**J. Ehrel, A. Lichnewsky & F. Thomasset,*Parallelism in Finite Element Computation*, Proceedings of I.B.M. Symposium on Vector Computers and Scientific Computation, Rome, 1982.**[5]**A. Greenbaum & G. Rodrigue,*The Incomplete Cholesky Conjugate Gradient Method for the*STAR (5-*Point Operator*), LLNL Report UCID-17574, 1977.**[6]**I. Gustafsson, A class of first order factorization methods,"*BIT*, v. 18, 1978, pp. 142-156. MR**499230 (81j:65057)****[7]**D. Heller, "Some aspects of the cyclic reduction algorithm for block tridiagonal linear systems,"*SIAM J. Numer. Anal.*, v. 13, no. 4, Sept. 1976, pp. 484-496. MR**0438680 (55:11588)****[8]**T. Jordan, "A guide to parallel computation and some CRAY-1 experiences,"*Parallel Computations*(G. Rodrigue, ed.), Academic Press, New York, 1982. MR**759549****[9]**D. Kershaw, "Solution of single tridiagonal linear systems and vectorization of the ICCG algorithm on the CRAY-1,"*Parallel Computations*(G. Rodrigue, ed.), Academic Press, New York, 1982. MR**759551****[10]**D. Kershaw, "The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations,"*J. Comput. Phys.*, v. 26, 1978, pp. 43-65. MR**0488669 (58:8190)****[11]**J. J. Lambiotte & R. G. Voigt,*The Solution of Tridiagonal Linear Systems on the*CDC-STAR-100*Computer*, ICASE Report, NASA Langley Research Center, Hampton, Virgina, 1974. MR**0388843 (52:9677)****[12]**N. K. Madsen & G. H. Rodrigue,*A Comparison of Direct Methods for Tridiagonal Systems on the*CDC-STAR-100, Report UCRL-76993, Lawrence Livermore Laboratory, July 1975.**[13]**N. Madsen, G. Rodrigue & J. Karush, "Matrix multiplication by diagonals on a vector parallel processor,"*J. Inform. Process.*, v. 5, No. 2, June 1976. MR**0438783 (55:11689)****[14]**T. A. Manteuffel, "The shifted incomplete-Cholesky factorization,"*Sparse Matrix Proceedings*(Iain S. Duff and G. W. Stewart, eds.), SIAM, Philadelphia, Pa., 1978. MR**566370 (81g:65052)****[15]**J. A. Meijerinck & H. A. van der Vorst, "An iterative solution method for linear systems of which the coefficient matrix is a symmetric*M*-matrix,"*Math. Comp.*, v. 31, 1977, pp. 148-162. MR**0438681 (55:11589)****[16]**G. Rodrigue, C. Hendrickson & M. Pratt, "The numerical solution of the Lagrangian diffusion equation on a vector processor,"*Parallel Computation*(G. Rodrigue, ed.), Academic Press, New York, 1982. MR**759552****[17]**G. Rodrigue, N. K. Madsen & J. T. Karush, "Odd-even reduction for banded linear systems,"*J. Assoc. Comput. Mach.*, v. 26, no. 1, January 1979, pp. 72-81. MR**514633 (80b:65040)****[18]**H. A. van der Vorst & J. M. van Kats,*Manteuffel's Algorithm with Preconditioning for the Iterative Solution of Certain Sparse Linear Systems with a Non-Symmetric Matrix*, Technical Report TR-11, ACCU-Reeks No. 29, Academic Computer Centre, University of Utrecht, The Netherlands, Aug. 1979.**[19]**R. S. Varga,*Matrix Iterative Analysis*, Prentice-Hall, Englewood Cliffs, N.J., 1962. MR**0158502 (28:1725)****[20]**R. S. Varga, "Factorization and normalized iterative methods,"*Boundary Problems in Differential Equations*(R. E. Langer, ed.), Univ. of Wisconsin Press, Madison, 1960, pp. 121-142. MR**0121977 (22:12704)****[21]**D. Young,*Iterative Solution of Large Linear Systems*, Academic Press, New York, 1972. MR**0305568 (46:4698)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F10,
65W05

Retrieve articles in all journals with MSC: 65F10, 65W05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736452-6

Article copyright:
© Copyright 1984
American Mathematical Society