## Preconditioning by incomplete block cyclic reduction

HTML articles powered by AMS MathViewer

- by Garry Rodrigue and Donald Wolitzer PDF
- Math. Comp.
**42**(1984), 549-565 Request permission

## 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.## References

- O. Axelsson,
*A generalized $\textrm {SSOR}$ method*, Nordisk Tidskr. Informationsbehandling (BIT)**12**(1972), 443–467. MR**339467**, DOI 10.1007/bf01932955 - Paul Concus, Gene H. Golub, and Dianne P. O’Leary,
*A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations*, Sparse matrix computations (Proc. Sympos., Argonne Nat. Lab., Lemont, Ill., 1975) Academic Press, New York, 1976, pp. 309–332. MR**0501821**
P. Dubois & G. Rodrigue, - Ivar Gustafsson,
*A class of first order factorization methods*, BIT**18**(1978), no. 2, 142–156. MR**499230**, DOI 10.1007/BF01931691 - Don Heller,
*Some aspects of the cyclic reduction algorithm for block tridiagonal linear systems*, SIAM J. Numer. Anal.**13**(1976), no. 4, 484–496. MR**438680**, DOI 10.1137/0713042 - T. L. Jordan,
*A guide to parallel computation and some Cray-$1$ experiences*, Parallel computations, Comput. Tech., vol. 1, Academic Press, Orlando, FL, 1982, pp. 1–50. MR**759549** - David Kershaw,
*Solution of single tridiagonal linear systems and vectorization of the ICCG algorithm on the Cray-$1$*, Parallel computations, Comput. Tech., vol. 1, Academic Press, Orlando, FL, 1982, pp. 85–99. MR**759551** - David S. Kershaw,
*The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations*, J. Comput. Phys.**26**(1978), no. 1, 43–65. MR**488669**, DOI 10.1016/0021-9991(78)90098-0 - Jules J. Lambiotte Jr. and Robert G. Voigt,
*The solution of tridiagonal linear systems on the CDC STAR-100 computer*, ACM Trans. Math. Software**1**(1975), no. 4, 308–329. MR**388843**, DOI 10.1145/355656.355658
N. K. Madsen & G. H. Rodrigue, - Niel K. Madsen, Garry H. Rodrigue, and Jack I. Karush,
*Matrix multiplication by diagonals on a vector/parallel processor*, Information Processing Lett.**5**(1976), no. 2, 41–45. MR**438783**, DOI 10.1016/0020-0190(76)90077-6 - Thomas A. Manteuffel,
*Shifted incomplete Cholesky factorization*, Sparse Matrix Proceedings 1978 (Sympos. Sparse Matrix Comput., Knoxville, Tenn., 1978) SIAM, Philadelphia, Pa., 1979, pp. 41–61. MR**566370** - J. A. Meijerink and H. A. van der Vorst,
*An iterative solution method for linear systems of which the coefficient matrix is a symmetric $M$-matrix*, Math. Comp.**31**(1977), no. 137, 148–162. MR**438681**, DOI 10.1090/S0025-5718-1977-0438681-4 - Garry Rodrigue, Chris Hendrickson, and Mike Pratt,
*An implicit numerical solution of the two-dimensional diffusion equation and vectorization experiments*, Parallel computations, Comput. Tech., vol. 1, Academic Press, Orlando, FL, 1982, pp. 101–128. MR**759552** - Garry H. Rodrigue, Niel K. Madsen, and Jack I. Karush,
*Odd-even reduction for banded linear equations*, J. Assoc. Comput. Mach.**26**(1979), no. 1, 72–81. MR**514633**, DOI 10.1145/322108.322116
H. A. van der Vorst & J. M. van Kats, - Richard S. Varga,
*Matrix iterative analysis*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR**0158502** - Richard S. Varga,
*Factorization and normalized iterative methods*, Boundary problems in differential equations, Univ. Wisconsin Press, Madison, Wis., 1960, pp. 121–142. MR**0121977** - David M. Young,
*Iterative solution of large linear systems*, Academic Press, New York-London, 1971. MR**0305568**

*An Analysis of the Recursive Doubling Algorithm*, Proceedings of High Speed Computer and Algorithm Organization, Academic Press, New York, 1977. 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. A. Greenbaum & G. Rodrigue,

*The Incomplete Cholesky Conjugate Gradient Method for the*STAR (5-

*Point Operator*), LLNL Report UCID-17574, 1977.

*A Comparison of Direct Methods for Tridiagonal Systems on the*CDC-STAR-100, Report UCRL-76993, Lawrence Livermore Laboratory, July 1975.

*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.

## Additional Information

- © Copyright 1984 American Mathematical Society
- 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