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

This paper is concerned with the problem of computing the characteristic polynomial of a matrix. In a large number of applications, the matrices are symmetric and sparse: with \(O(n)\) non-zero entries. The problem has an efficient sequential solution in this case, requiring \(O(n^2)\) work by use of the sparse Lanczos method. A major question remaining open is: to find a polylog time parallel algorithm with matching work bounds. Unfortunately, the sparse Lanczos method cannot be parallelized to faster then time \((n)\) using \(n\) processors. Let \(M(n)\) be the processor bound to multiply two square matrices of order \(n\) in \(O(\log n)\) parallel time. This article gives a new algorithm for computing the characteristic polynomial of a sparse symmetric matrix assuming that the sparsity graph is \(s(n)\)-separable. The author derives an interesting algebraic version of nested dissection, which constructs a sparse factorization of the matrix \(A-I\) where \(A\) is the input matrix .