Fast Parallel Direct Solvers For Coarse Grid Problems

We develop a fast direct solver for parallel solution of "coarse grid" problems, Ax = b, such as arise when domain decomposition or multigrid methods are applied to elliptic partial differential equations in d space dimensions. The approach is based upon a (quasi-) sparse factorization of the inverse of A. If the dimension of the system is n and the number of processors is P , our approach requires O(n fl log 2 P ) time for communication and O(n 1+fl =P ) time for computation, where fl j d\Gamma1 d . Results from a 512 node Intel Paragon show that our algorithm compares favorably to more commonly used approaches which require O(n log 2 P ) time for communication and O(n 1+fl ) or O(n 2 =P ) time for computation. Moreover, for leading edge multicomputer systems with thousands of processors and n = P (i.e., communication dominated solves), we expect our algorithm to be markedly superior as it achieves substantially reduced message volume and arithmetic complexity over current c..