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.
- O. Axelsson, A generalized ${\rm SSOR}$ method, Nordisk Tidskr. Informationsbehandling (BIT) 12 (1972), 443–467. MR 339467, DOI https://doi.org/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, 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.
- Ivar Gustafsson, A class of first order factorization methods, BIT 18 (1978), no. 2, 142–156. MR 499230, DOI https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0021-9991%2878%2990098-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 https://doi.org/10.1145/355656.355658 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.
- 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 https://doi.org/10.1016/0020-0190%2876%2990077-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 https://doi.org/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 https://doi.org/10.1145/322108.322116 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.
- 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. of 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
Retrieve articles in Mathematics of Computation with MSC: 65F10, 65W05
Retrieve articles in all journals with MSC: 65F10, 65W05
Additional Information
Article copyright:
© Copyright 1984
American Mathematical Society
