Both spectral divide and conquer (SDC) algorithms discussed in this paper can be presented in the following framework. Let

be the Jordan canonical form of , where the eigenvalues of the submatrix are the eigenvalues of inside a selected region in the complex plane, and the eigenvalues of the submatrix are the eigenvalues of outside . We assume that there are no eigenvalues of on the boundary of , otherwise we reselect or move the region slightly. The invariant subspace of the matrix corresponding to the eigenvalues inside are spanned by the first columns of . The matrix

is the corresponding spectral projector. Let be the rank revealing QR decomposition of the matrix , where is unitary, is upper triangular, and is a permutation matrix chosen so that the leading columns of span the range space of . Then yields the desired spectral decomposition:

where the eigenvalues of are the eigenvalues of inside , and the eigenvalues of are the eigenvalues of outside . By substituting the complementary projector for in (2.4), will have the eigenvalues outside and will have the eigenvalues inside .

The crux of a parallel SDC algorithm is to efficiently compute the desired spectral projector without computing the Jordan canonical form.

- The SDC algorithm with Newton iteration
- The SDC algorithm with inverse free iteration
- Spectral Transformation Techniques
- Tradeoffs

Mon Jan 9 11:07:50 EST 1995