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

DOI:
https://doi.org/10.1090/S0025-5718-96-00667-9

MathSciNet review:
1320899

Full-text PDF

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.

**1**A. Berman and R. J. Plemmons,*Nonnegative matrices in the mathematical sciences*, Academic Press, New York, 1979.MR**82b:15013****2**T. F. Chan,*Rank revealing QR factorizations*, Linear Algebra Appl.**88/89**(1987), 67--82.MR**88c:15011****3**B. Char, K. Geddes, G. Gonnet, B. Leong, M. Monagan, and S. Watt,*Maple*V*language reference manual*, Springer, New York, 1991.**4**G. H. Golub and C. F. Van Loan,*Matrix computations*, 2nd ed., The Johns Hopkins University Press, Baltimore, MD, 1989.MR**90d:65055****5**D. J. Higham and N. J. Higham,*Componentwise perturbation theory for linear systems with multiple right-hand sides*, Linear Algebra Appl.**174**(1992), 111--129.MR**93e:65041****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**H. Minc,*Nonnegative matrices*, Wiley, New York, 1988.MR**89i:15001****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, Englewood Cliffs, NJ, 1963.MR**28:4661****14**------,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965.MR**32:1894**

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