An Algorithm for the Banded Symmetric Generalized Matrix
Linda Kaufman · SIAM Journal on Matrix Analysis and Applications · 1993
This paper derives an algorithm for finding the eigenvalues of the symmetric banded generalized eigenvalue problem $A{\bf x} = \lambda B{\bf x}$ where A and B are $n \times n$ symmetric positive definite matrices of bandwidth $2k + 1$. Traditionally, for the nonbanded symmetric problem the Martin–Wilkinson algorithm has been used. This algorithm has been adapted to banded problems by Crawford and the current author has shown how to rearrange Crawford’s algorithm to take advantage of parallel machines. Wang and Zhao have recently proposed another algorithm for the nonbanded symmetric generalized problem which seems to be able to compute small eigenvalues more accurately than the Martin–Wilkinson algorithm on problems with graded eigenvalues and ill-conditioned B. Their algorithm, like the Martin–Wilkinson algorithm, has a direct reduction phase requiring $O( n^3 )$ operations followed by an iterative phase requiring $O( n^2 )$ operations. In this paper the Wang–Zhao algorithm is reworked for banded matrices so that it requires $O( nk )$ space and $O( n^2 k )$ operations, a reduction of $O( n/k )$ operations over the general algorithm. On a vector machine the new algorithm requires $O( nk^2 )$ vector operations with vector lengths as long as $n/k$ elements.