Parallel Spectral Divide and Conquer Algorithms   Next: The SDC algorithm Up: The Spectral Decomposition of Previous: Introduction

# Parallel Spectral Divide and Conquer Algorithms

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.

Jack Dongarra
Mon Jan 9 11:07:50 EST 1995