Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Backward error analysis of cyclic reduction for the solution of tridiagonal systems

Authors: Pierluigi Amodio and Francesca Mazzia
Journal: Math. Comp. 62 (1994), 601-617
MSC: Primary 65G05; Secondary 15A06, 65F05
MathSciNet review: 1208836
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Tridiagonal systems play a fundamental role in matrix computation. In particular, in recent years parallel algorithms for the solution of tridiagonal systems have been developed. Among these, the cyclic reduction algorithm is particularly interesting. Here the stability of the cyclic reduction method is studied under the assumption of diagonal dominance. A backward error analysis is made, yielding a representation of the error matrix for the factorization and for the solution of the linear system. The results are compared with those for LU factorization.

References [Enhancements On Off] (What's this?)

  • [1] P. Amodio, Optimized cyclic reduction for the solution of linear tridiagonal systems on parallel computers, Comput. Math Appl. 26 (1993), 45-53. MR 1221197
  • [2] P. Amodio and L. Brugnano, Parallel factorizations and parallel solvers for tridiagonal linear systems, Linear Algebra Appl. 172 (1992), 347-364. MR 1168511 (93b:15014)
  • [3] P. Amodio, L. Brugnano, and T. Politi, Parallel factorizations for tridiagonal matrices, SIAM J. Numer. Anal. 30 (1993), 813-823. MR 1220654 (94d:65025)
  • [4] B. L. Buzbee, G. H. Golub, and C. W. Nielson, On direct methods for solving Poisson's equations, SIAM J. Numer. Anal. 7 (1970), 627-656. MR 0287717 (44:4920)
  • [5] F. W. Dorr, An example of ill-conditioning in the numerical solution of singular perturbation problems, Math. Comp. 25 (1971), 271-283. MR 0297142 (45:6200)
  • [6] D. Heller, Some aspects of the Cyclic Reduction Algorithm for block tridiagonal linear systems, SIAM J. Numer. Anal. 13 (1976), 484-496. MR 0438680 (55:11588)
  • [7] N. J. Higham, Efficient algorithms for computing the condition number of a tridiagonal matrix, SIAM J. Sci. Statist. Comput. 7 (1986), 150-165. MR 819464 (87b:65053)
  • [8] -, Bounding the error in Gaussian elimination for tridiagonal systems, SIAM J. Matrix Anal. Appl. 11 (1990), 521-530. MR 1066155 (91f:65060)
  • [9] S. L. Johnsson, Solving tridiagonal systems on ensemble architectures, SIAM J. Sci. Statist. Comput. 8 (1987), 354-392. MR 883776 (88j:65063)
  • [10] 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, pp. 85-99. MR 759551
  • [11] J. J. Lambiotte, R. G. Voigt, The solution of tridiagonal linear systems on the CDC Star-100 computer, ACM Trans. Math. Software 1 (1975), 308-329. MR 0388843 (52:9677)
  • [12] F. Mazzia and D. Trigiante, Numerical methods for second order singular perturbation problems, Comput. Math. Appl. 23 (1992), 81-89. MR 1158140 (92m:65104)
  • [13] J. M. Ortega, Introduction to parallel and vector solution of linear systems, Plenum Press, New York, 1988. MR 1106195 (92i:65220a)
  • [14] H. S. Stone, An efficient parallel algorithm for the solution of a tridiagonal linear system of equations, J. Assoc. Comput. Mach. 20 (1973), 27-38. MR 0334473 (48:12792)
  • [15] H. A. Van der Vorst, Large tridiagonal and block tridiagonal linear systems on vector and parallel computers, Parallel Comput. 5 (1987), 45-54. MR 898034 (88d:65192)
  • [16] J. H. Wilkinson, The algebraic eigenvalue problem, Oxford Univ. Press, Oxford, 1965. MR 0184422 (32:1894)
  • [17] -, Error analysis of direct methods of matrix inversion, J. Assoc. Comput. Mach. 8 (1961), 281-330. MR 0176602 (31:874)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65G05, 15A06, 65F05

Retrieve articles in all journals with MSC: 65G05, 15A06, 65F05

Additional Information

Keywords: Tridiagonal linear systems, cyclic reduction, backward error analysis
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society