Efficient parallel solution of sparse eigenvalue and eigenvector problems

A new algorithm for computing the characteristic polynomial of a symmetric sparse matrix is given. An interesting algebraic version of Nested Dissection is derived, which constructs a sparse factorization of the matrix A - λI where A is the input matrix. While Nested Dissection is commonly used to minimize the fill-in in the solution of sparse linear systems, the innovation is to use the separator structure to bound also the work for manipulation of rational polynomials in the recursively factored matrices. The other innovation is an interesting reduction from finding all eigenvectors to the problems of back-solving a sparse linear system and multi-point polynomial evaluation.

Duke Scholars

Author John H. Reif Computer Science