A Hybrid Tridiagonalization Algorithm for Symmetric Sparse Matrices

This paper considers sequential direct methods for the reduction of a sparse symmetric matrix to tridiagonal form using sequences of orthogonal similarity transformations. Currently, the best published approach combines a bandwidth-reducing preordering algorithm, perhaps Gibbs–Poole–Stockmeyer (GPS), with a band-preserving tridiagonalization such as the EISPACK BANDR routine. This paper introduces a new hybrid tridiagonalization algorithm, BANDHYB, based upon band-preserving reduction techniques that rearrange the elimination sequence of nonzero entries to take better advantage of the sparsity within the band of the permuted matrix. For many practical sparse problems a GPS-BANDHYB approach substantially reduces the CPU requirements of tridiagonalization, compared to a GPS-BANDR scheme, without increasing storage requirements. Over a wide range of sparse problems the new algorithm reduced CPU time by an average of 31%, with reductions of more than 60% observed for some problems.