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.

**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**

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