Efficient parallel solution of sparse eigenvalue and eigenvector problems


Journal Article

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 Authors

Cited Authors

  • Reif, JH

Published Date

  • December 1, 1995

Published In

Start / End Page

  • 123 - 132

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus