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(n1+γ/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(n1+γ) or O(n2/P) time for computation. Timings on the Intel Paragon and ASCI-Red machines reflect these complexity estimates.
- Direct solver; sparse factorization; nested dissection; parallel computing; coarse grid problems
ASJC Scopus subject areas
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence