Band Reduction Algorithms Revisited

The subroutines in LAPACK for reducing a symmetric positive definite generalized eigenvalue problem to a standard symmetric banded eigenvalue problem and for reducing a symmetric banded matrix to tridagonal form are based on algorithms that were proposed for narrow banded problems. These algorithms use planar transformations which can be generated and applied independently and simultaneously and were particularly suited for parallel computation. The mechanism that LAPACK uses for tailoring codes for specific machines, the BLAS, does not include such parallel vector operations, and the performance of the banded algorithms for large bandwidths problems has been rather poor. In this paper we make a simple implementation suggestion which improves the performance for larger bandwidth problems. We also show that when one is accumulating the transformation onto the identity matrix, one can reduce the number of operations by about one third by taking advantage of the structure of the initial matrix.