Computing approximate eigenpairs of symmetric block tridiagonal matrices

A divide-and-conquer method for computing approximate eigenvalues and eigenvectors of a block tridiagonal matrix is presented. In contrast to a method described earlier [W. N. Gansterer, R. C. Ward, and R. P. Muller, ACM Trans. Math. Software, 28 ( 2002), pp. 45-58], the off-diagonal blocks can have arbitrary ranks. It is shown that lower rank approximations of the off-diagonal blocks as well as relaxation of deflation criteria permit the computation of approximate eigenpairs with prescribed accuracy at significantly reduced computational cost compared to standard methods such as, for example, implemented in Lapack.