Reliable computation of the Condition Number of a Tridiagonal Matrix in O(n) Time

Inderjit Dhillon

Abstract:   We present one more algorithm to compute the condition number (for inversion) of an n × 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.