Rounding errors in solving block Hessenberg systems
HTML articles powered by AMS MathViewer
- by Urs von Matt and G. W. Stewart PDF
- Math. Comp. 65 (1996), 115-135 Request permission
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
- Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 544666
- Tony F. Chan, Rank revealing $QR$ factorizations, Linear Algebra Appl. 88/89 (1987), 67–82. MR 882441, DOI 10.1016/0024-3795(87)90103-0
- B. Char, K. Geddes, G. Gonnet, B. Leong, M. Monagan, and S. Watt, Maple V language reference manual, Springer, New York, 1991.
- 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
- 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, DOI 10.1016/0024-3795(92)90046-D
- 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.
- —, Stability and accuracy of numerical algorithms (provisional title), 1994, in preparation.
- 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
- G. W. Stewart, On the solution of block Hessenberg systems, Numerical Linear Algebra with Applications 2 (1995), 287–296.
- —, An updating algorithm for subspace tracking, IEEE Trans. Signal Processing 40 (1992), 1535–1541.
- —, Implementing an algorithm for solving block Hessenberg systems, Tech. Report CS-TR-3295, Department of Computer Science, University of Maryland, June 1994.
- The MathWorks Inc., MATLAB, high-performance numeric computation and visualization software, Natick, Massachusetts, 1992.
- J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
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
- 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
- © Copyright 1996 American Mathematical Society
- 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