Reliable Computation of the Condition Number of a Tridiagonal Matrix in O ( n ) Time
Inderjit S. Dhillon · SIAM Journal on Matrix Analysis and Applications · 1998
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.