Preconditioning by incomplete block cyclic reduction

Rodrigue, Garry; Wolitzer, Donald

doi:10.1090/S0025-5718-1984-0736452-6

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 𝑆𝑆𝑂𝑅 method, Nordisk Tidskr. Informationsbehandling (BIT) 12 (1972), 443–467. MR 339467, https://doi.org/10.1007/bf01932955
[2] 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
[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] Ivar Gustafsson, A class of first order factorization methods, BIT 18 (1978), no. 2, 142–156. MR 499230, https://doi.org/10.1007/BF01931691
[7] 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, https://doi.org/10.1137/0713042
[8] 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
[9] 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
[10] 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, https://doi.org/10.1016/0021-9991(78)90098-0
[11] 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, https://doi.org/10.1145/355656.355658
[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] 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 0438783, https://doi.org/10.1016/0020-0190(76)90077-6
[14] 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
[15] J. A. Meijerink and H. A. van der Vorst, An iterative solution method for linear systems of which the coefficient matrix is a symmetric 𝑀-matrix, Math. Comp. 31 (1977), no. 137, 148–162. MR 438681, https://doi.org/10.1090/S0025-5718-1977-0438681-4
[16] 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
[17] 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, https://doi.org/10.1145/322108.322116
[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] Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502
[20] 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
[21] David M. Young, Iterative solution of large linear systems, Academic Press, New York-London, 1971. MR 0305568