Parallel complexity of domain decomposition methods and optimal coarse grid size

Tony F. Chan*, Jian Ping Shao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


In this paper, we analyze the parallel complexity of domain decomposition method through estimating the arithmetic time as well as the communication time. In most domain decomposition (DD) methods, a coarse grid solve is employed to provide global coupling and obtain an optimal convergence rate. Generally, a small coarse grid size H improves the convergence rate at the cost of a larger coarse grid problem and a large number P of processors results in more costly global communication, whereas a large H and a small P have the opposite effect. Therefore, there often exists an optimal H such that the execution time on the parallel machine reaches a minimum. Our main goal here is to find this optimal coarse grid size H in the parallel environment. We assume the same solver is used for the subdomains as well as the coarse problem. By expressing the parallel complexity as a function of H and h, we can derive the analytic optimal coarse grid size Hopt. When the number of processors is equal to the number of subdomains, we can prove that the choice of Hopt = √h asymptotically minimises the execution time as h tends to zero. This optimal coarse grid size is independent of the choice of subproblem solvers and the spatial dimension. However, when the number of processors is much less than the number of subdomains, the optimal coarse grid size depends on the number of processors, the subdomain solver and dimension.

Original languageEnglish (US)
Pages (from-to)1033-1049
Number of pages17
JournalParallel Computing
Issue number7
StatePublished - Jul 1995
Externally publishedYes


  • Arithmetic time
  • Communication time
  • Computation time
  • Domain decomposition
  • Execution time
  • Optimal coarse grid size choice H
  • Parallel complexity

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


Dive into the research topics of 'Parallel complexity of domain decomposition methods and optimal coarse grid size'. Together they form a unique fingerprint.

Cite this