Efficient parallel computation of the characteristic polynomial of a sparse, separable matrix

This paper is concerned with the problem of computing the characteristic po lynomial of a matrix. In a large number of applications, the matrices are s ymmetric and sparse: with O(n) non-zero entries. The problem has an efficie nt sequential solution in this case, requiring O (n(2)) work by use of the sparse Lanczos method. A major remaining open question is: to find a polylo g time parallel algorithm with matching work bounds. Unfortunately, the spa rse Lanczos method cannot be parallelized to faster than time Ohm (n) using n processors. Let M(n) be the processor bound to multiply two n x n matric es in O(log n) parallel time. Giesbrecht [G2] gave the best previous polylo g time parallel algorithms for the characteristic polynomial of a dense mat rix with O(M(n)) processors. There is no known improvement to this processo r bound in the case where the matrix is sparse. Often, in addition to being symmetric and sparse, the matrix has a sparsity graph (which has edges bet ween indices of the matrix with non-zero entries) that has small separators . This paper gives a new algorithm for computing the characteristic polynom ial of a sparse symmetric matrix, assuming that the sparsity graph is s(n)- separable and has a separator bf size s(n) = O(n(gamma)), for some gamma, 0 < <gamma> < 1, that when deleted results in connected components of <less than or equal to> alphan vertices, for some 0 < <alpha> < 1, with the same property. We derive an interesting algebraic version of Nested Dissection, which constructs a sparse factorization of the matrix A - <lambda>I-n where A is the input matrix and I-n is the n x n identity matrix. While Nested D issection is commonly used to minimize the fill-in in the solution of spars e linear systems, our innovation is to use the separator structure to bound also the work for manipulation of rational functions in the recursively fa ctored matrices. The matrix elements are assumed to be over an arbitrary fi eld. We compute the characteristic polynomial of a sparse symmetric matrix in polylog time using P(n) (n + M(s(n))) less than or equal to P(n)(n + s(n )(2,376)) processors, where P (n) is the processor bound to multiply two de gree n polynomials in O (log n) parallel time using a PRAM (P(n) = O (n) if the held supports an FFT of size n but is otherwise O(n log log n) [CK]). Our method requires only that a matrix be symmetric and non-singular (it ne ed not be positive definite as usual for Nested Dissection techniques). For the frequently occurring case where the matrix has small separator size, o ur polylog parallel algorithm has work bounds competitive with the best kno wn sequential algorithms (i.e., the Ohm (n(2)) work of sparse Lanczos metho ds), for example, when the sparsity graph is a planar graph, s(n) less than or equal to O(rootn), and we require polylog time with only P(n)n(1.188) p rocessors.