Reduction of a General Matrix to Tridiagonal Form

Abstract

An algorithm for reducing a nonsymmetric matrix to tridiagonal form as a first step toward finding its eigenvalues is described. The algorithm uses a variation of threshold pivoting, where at each step, the pivot is chosen to minimize the maximum entry in the transformation matrix that reduces the next column and row of the matrix. Situations are given where the tridiagonalization process breaks down, and two recovery methods are presented for these situations. Although no existing tridiagonalization algorithm is guaranteed to succeed, this algorithm is found to be very robust and fast in practice. A gradual loss of similarity is also observed as the order of the matrix increases.