Efficient Algorithms for Computing the Condition Number of a Tridiagonal Matrix

Let A be a tridiagonal matrix of order n. We show that it is possible to compute \|A- 1 \|_∞,and hence cond_∞ (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 \|_∞ 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 cond₁ (A), efficiently, in addition to solving $Ax = b$.