Publications [#237118] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH, Efficient parallel solution of sparse eigenvalue and eigenvector problems, Annual Symposium on Foundations of Computer Science Proceedings (December, 1995), pp. 123-132, IEEE Comput. Soc. Press [pdf], [doi]
   (last updated on 2026/01/15)

   Abstract:
   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.