On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms

In this paper we design a fast new algorithm for reducing an N x N quasiseparable matrix to upper Hessenberg form via a sequence of N - 2 unitary transformations. The new reduction is especially useful when it is followed by the QR algorithm to obtain a complete set of eigenvalues of the original matrix. In particular, it is shown that in a number of cases some recently devised fast adaptations of the QR method for quasiseparable matrices can benefit from using the proposed reduction as a preprocessing step, yielding lower cost and a simplification of implementation. (c) 2006 Elsevier Inc. All rights reserved.