COMPUTING THE CONDITION NUMBER OF TRIDIAGONAL AND DIAGONAL-PLUS-SEMISEPARABLE MATRICES IN LINEAR TIME

Abstract. For an n n tridiagonal matrix we exploit the structure of its QR factorization to devise two new algorithms for computing the 1-norm condition number in O(n) operations. The algorithms avoid under ow and over ow, and are simpler than existing algorithms since tests are not required for degenerate cases. An error analysis of the rst algorithm is given, while the second algorithm is shown to be competitive in speed with existing algorithms. We then turn our attention to an n n diagonal-plus-semiseparable matrix, A, for which several algorithms have recently been developed to solve Ax = b in O(n) operations. We again exploit the QR factorization of the matrix to present an algorithm that computes the 1-norm condition number in O(n) operations. Key words. condition number, tridiagonal matrix, diagonal-plus-semiseparable matrix, QR factorization AMS subject classications. 15A09, 65F35, 15A12 1. Introduction. Consider a nonsingular matrix A 2 Rn