Parallel Performance of Domain-Decomposed Preconditioned Krylov Methods for PDEswith Adaptive Refinement

摘要

Preconditioners based on domain decomposition appear natural for the Krylovsolution of implicitly discretized partial differential equations on parallel computers. Two-scale preconditioners (involving independent subdomain solves and a global crosspoint system, as well as independent solves over interfaces of lower physical dimension) have been known since the early 1980's to be near optimal in the sense of providing a bounded or at most logarithmically growing iteration count as the mesh is refined. However, overall computational complexity depends on the components of the preconditioner as well as the iteration count. The cost of exact subdomain solves grows superlinearly in arithmetic complexity, and that of the crosspoint system superlinearly in communication complexity. These factors make the preconditioner granularity and the choice of its