Efficient Algorithms for Computing the Condition Number of a Tridiagonal Matrix
Nicholas John Higham · SIAM Journal on Scientific and Statistical Computing · 1986
Let A be a tridiagonal matrix of order n. We show that it is possible to compute ${\|A^{ - 1} \|}_\infty $,and hence $\operatorname{cond}_\infty (A)$, in $O(n)$ operations. Several algorithms which perform this task are given and their numerical properties are investigated. If A is also positive definite then ${\|A^{ - 1} \|}_\infty $ can be computed as the norm of the solution to a positive definite tridiagonal linear system whose coefficient matrix is closely related to A. We show how this computation can be carried out in parallel with the solution of a linear system $Ax = b$. In particular we describe some simple modifications to the LINPACK routine SPTSL which enable this routine to compute $\operatorname{cond}_1 (A)$, efficiently, in addition to solving $Ax = b$.