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