An extension of the divide-and-conquer method for a class of symmetric block-tridiagonal eigenproblems

Abstract

A divide-and-conquer method for computing eigenvalues and eigenvectors of a block-tridiagonal matrix with rank-one off-diagonal blocks is presented. The implications of unbalanced merging operations due to unequal block sizes are analyzed and illustrated with numerical examples. It is shown that an unfavorable order for merging blocks in the synthesis phase of the algorithm may lead to a significant increase of the arithmetic complexity. A strategy to determine a good merging order that is at least close to optimal in all cases is given. The method has been implemented and applied to test problems from a quantum chemistry application.