Fast Parallel Direct Solvers for Coarse Grid Problems

We have developed 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 on a (quasi-) sparse factorization of the inverse of A. If A is n×n and the number of processors is P, the algorithm requires O(n^γlogP) time for communication and O(n^1+γ/P) time for computation, where γ≡d-1d. The method is particularly suited to leading-edge multicomputer systems having thousands of processors. It achieves minimal message startup costs and substantially reduced message volume and arithmetic complexity compared with competing methods, which require O(nlogP) time for communication and O(n^1+γ) or O(n²/P) time for computation. Timings on the Intel Paragon and ASCI-Red machines reflect these complexity estimates.