Reliable Computation of the Condition Number of a Tridiagonal Matrix in O(n) Time
- 1 July 1998
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 19 (3) , 776-796
- https://doi.org/10.1137/S0895479897314747
Abstract
We present one more algorithm to compute the condition number (for inversion) of an n X n tridiagonal matrix J in O(n) time. Previous O(n) algorithms for this task given by Higham [SIAM J. Sci. Statist. Comput., 7 (1986), pp. 150--165] are based on the tempting compact representation of the upper (lower) triangle of J-1 as the upper (lower) triangle of a rank-one matrix. However they suffer from severe overflow and underflow problems, especially on diagonally dominant matrices. Our new algorithm avoids these problems and is as efficient as the earlier algorithms.Keywords
This publication has 15 references indexed in Scilit:
- On Computing an Eigenvector of a Tridiagonal Matrix. Part I: Basic ResultsSIAM Journal on Matrix Analysis and Applications, 1997
- Faster numerical algorithms via exception handlingIEEE Transactions on Computers, 1994
- A Survey of Condition Number Estimation for Triangular MatricesSIAM Review, 1987
- Efficient Algorithms for Computing the Condition Number of a Tridiagonal MatrixSIAM Journal on Scientific and Statistical Computing, 1986
- Condition EstimatesSIAM Journal on Scientific and Statistical Computing, 1984
- Estimating Matrix Condition NumbersSIAM Journal on Scientific and Statistical Computing, 1980
- Towards a formal definition of numerical stabilityNumerische Mathematik, 1977
- Methods of inverting tridiagonal matricesUSSR Computational Mathematics and Mathematical Physics, 1973
- Inverses of Matrices $\{a_{ij}\}$ which Satisfy $a_{ij} = 0$ for $j > i+p$.MATHEMATICA SCANDINAVICA, 1959
- Finite Boundary Value Problems Solved by Green's Matrix.MATHEMATICA SCANDINAVICA, 1959