Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems

This paper gives a new algorithm for computing the characteristic polynomial of a symmetric sparse matrix. We derive an interesting algebraic version of nested dissection, which constructs a sparse factorization the matrix A-/spl lambda/ where A is the input matrix. While nested dissection is commonly used to minimize the fill-in in the solution of sparse linear systems, our innovation is to use the separator structure to bound also the work for manipulation of rational polynomials in the recursively factored matrices. We compute the characteristic polynomial sparse symmetric matrix in polylog time using O(n(n+P(s(n))))/spl les/O(n(n+s(n)/sup 2. 376/)) processors, where the sparsity graph of the matrix has separator size s(n). Our method requires only that the matrix be symmetric and nonsingular (it need not be positive definite as usual for nested dissection techniques); we use perturbation methods to avoid singularities. For the frequently occurring case where the matrix has small separator size our polylog parallel algorithm requires work bounds competitive with the best known sequential algorithms (i. e. sparse Lanczos methods), for example: (1) when the sparsity graph is a planar graph, s(n)/spl les//spl radic/n, and we require only n/sup 2. 188/ processors, and (2) in the case where the input matrix is b-banded, we require only O(nP(b))=O(n) processors, for constant b.

Authors

• John H. Reif

Keywords

• Eigenvalues and eigenfunctions
• Sparse matrices
• Symmetric matrices
• Transmission line matrix methods
• Polynomials
• Particle separators
• Linear systems
• Technological innovation
• Perturbation methods
• Parallel algorithms
• Eigenvectors
• Eigenvalue Problem
• Parallel Efficiency
• Sparse Eigenvalue
• Engineering Applications
• Parallelization
• Linear System
• Symmetric Matrix
• Eigenvalues Of Matrix
• Sparse Matrix
• Input Matrix
• Algorithm For Problem
• Separate Structures
• Parallel Algorithm
• Characteristic Polynomial
• Time Matrix
• Computational Model
• Efficient Algorithm
• Matrix Size
• Positive Definite Matrix
• Separate Graphs
• Distinct Eigenvalues
• QR Decomposition
• Perturbation Technique
• LU Factorization
• Indeterminism
• Singular Matrix
• Polynomial Coefficients
• Matrix Integrity
• Input Bits