Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

Rounding Errors in Solving Block Hessenberg Systems


Authors: Urs von Matt and G. W. Stewart
Journal: Math. Comp. 65 (1996), 115-135
MSC (1991): Primary 65G05; Secondary 65F05
MathSciNet review: 1320899
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A rounding error analysis is presented for a divide-and-conquer algorithm to solve linear systems with block Hessenberg matrices. Conditions are derived under which the algorithm computes a stable solution. The algorithm is shown to be stable for block diagonally dominant matrices and for M-matrices.


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

  • 1 Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. Computer Science and Applied Mathematics. MR 544666
  • 2 Tony F. Chan, Rank revealing 𝑄𝑅 factorizations, Linear Algebra Appl. 88/89 (1987), 67–82. MR 882441, 10.1016/0024-3795(87)90103-0
  • 3 B. Char, K. Geddes, G. Gonnet, B. Leong, M. Monagan, and S. Watt, Maple V language reference manual, Springer, New York, 1991.
  • 4 Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
  • 5 Desmond J. Higham and Nicholas J. Higham, Componentwise perturbation theory for linear systems with multiple right-hand sides, Linear Algebra Appl. 174 (1992), 111–129. MR 1176455, 10.1016/0024-3795(92)90046-D
  • 6 N. J. Higham, How accurate is Gaussian elimination?, Numerical Analysis 1989, Proceedings of the 13th Dundee Conference (D. F. Griffiths and G. A. Watson, eds.), Longman Scientific and Technical, 1990, pp. 137--154. CMP 91:17
  • 7 ------, Stability and accuracy of numerical algorithms (provisional title), 1994, in preparation.
  • 8 Henryk Minc, Nonnegative matrices, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1988. A Wiley-Interscience Publication. MR 932967
  • 9 G. W. Stewart, On the solution of block Hessenberg systems, Numerical Linear Algebra with Applications 2 (1995), 287--296.
  • 10 ------, An updating algorithm for subspace tracking, IEEE Trans. Signal Processing 40 (1992), 1535--1541.
  • 11 ------, Implementing an algorithm for solving block Hessenberg systems, Tech. Report CS-TR-3295, Department of Computer Science, University of Maryland, June 1994.
  • 12 The Math-Works Inc., MATLAB, high-performance numeric computation and visualization software, Natick, Massachusetts, 1992.
  • 13 J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
  • 14 J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65G05, 65F05

Retrieve articles in all journals with MSC (1991): 65G05, 65F05


Additional Information

Urs von Matt
Affiliation: Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742
Email: vonmatt@na-net.ornl.gov

G. W. Stewart
Affiliation: Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742
Email: stewart@cs.umd.edu

DOI: https://doi.org/10.1090/S0025-5718-96-00667-9
Keywords: Rounding error analysis, linear systems, block Hessenberg matrices, block diagonally dominant matrices, M-matrices
Received by editor(s): August 22, 1994
Received by editor(s) in revised form: January 10, 1995
Additional Notes: This work was supported in part by the National Science Foundation under grant CCR 9115568
Article copyright: © Copyright 1996 American Mathematical Society