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.