An optimal Schwarz preconditioner for a class of parallel adaptive finite elements

  • a Department of Mathematics, Heriot-Watt University, Riccarton, Edinburgh, EH14 4AS, United Kingdom
  • b Institute of Research and Development, Duy Tan University, 3 Quang Trung, Danang, Vietnam


A Schwarz-type preconditioner is formulated for a class of parallel adaptive finite elements where the local meshes cover the whole domain. With this preconditioner, the convergence rate of the conjugate gradient method is shown to depend only on the ratio of the second largest and smallest eigenvalues of the preconditioned system. These eigenvalues can be bounded independently of the mesh sizes and the number of subdomains, which proves the proposed preconditioner is optimal. Numerical results are provided to support the theoretical findings.


  • 65N55;
  • 65N22;
  • 65F08


  • Domain decomposition;
  • Preconditioner;
  • Bank-Holst paradigm;
  • Two-grid discretizations;
  • Parallel adaptivity

1. Introduction

Adaptive finite element method (AFEM) has been a very popular method for solving partial differential equations in science and engineering  [1]. AFEM automatically refines or coarsens meshes to adapt to the computed solutions, thus offering great reliability, robustness and efficiency. Recently, there has been a great demand to use AFEM on parallel distributed supercomputers with many processors to tackle large-scale problems. In order to improve the scalability of AFEM on supercomputers, it is usually combined with a domain decomposition method (DDM). In DDM, the domain is partitioned into a number of subdomains and smaller problems on these subdomains are solved in parallel to determine the overall solution  [2] ;  [3].

Combining AFEM with DDM, however, introduces challenges that are not present in the traditional version of AFEM. One of the notable challenges is that AFEM builds its meshes gradually and global or near-neighbour information is usually needed. The information can be approximated solutions, error estimates on intermediate meshes or mesh information utilised in adaptive meshing procedures. Since communication costs are high on distributed supercomputers, one wants to avoid communicating as much as possible. This can be achieved when each processor has a mesh of the whole domain and its adaptive enrichment is performed almost independently with those of other processors. In general, the adaptive enrichment on each processor focus mainly on its subdomain. Consequently, after the adaptive enrichment phase, each processor has a composite mesh of the whole domain, which is fine in its subdomain and much coarser elsewhere. The final global mesh is the union of the refined submesh provided by each processor. Fig. 1 shows an example of the meshes before and after adaptive enrichment, and the final global mesh.

A coarse mesh with its partition (left), a local mesh on a processor after ...
Fig. 1. 

A coarse mesh with its partition (left), a local mesh on a processor after adaptive enrichment (middle), and the global fine mesh.

The initial idea of using local meshes of the whole domain was first introduced by Mitchell for a parallel multigrid method  [4]. Then it was further developed into parallel adaptive algorithms. The notable ones include the Bank-Holst algorithm   [5] ;  [6] and the local and parallel algorithms based on two-grid discretizations   [7]; [8] ;  [9]. Several variants of these algorithms are studied in  [10]; [11]; [12]; [13] ;  [14]. The two algorithms and their variants have been demonstrated to work well for many problems in both science and engineering  [5]; [15]; [16]; [17]; [6]; [18]; [19]; [12]; [20]; [21]; [22] ;  [23].

Different components contribute to their success. For discussions on how to obtain a suitable partition, where each subdomain contributes roughly the same amount of error, we refer to  [5] ;  [6]. For how to regularise the local meshes to make the global fine mesh conforming, we refer the readers to  [24]. In this paper, we focus on solving the final global linear system. There is no restriction in the type of solvers can be used. However, it would be ideal if the solver can take advantage of the special formulation of the algorithms. In  [25], Bank and Lu developed a dedicated domain decomposition solver for the Bank-Holst algorithm. The solver is empirically shown to be robust and efficient for many problems  [6]; [25]; [20] ;  [22]. However, its theoretical convergence can only be fully analysed for a special case where the global interface system is completely presented on all processors  [26]. For this to happen, all elements attached to the interface, including ones that are far away from the considered subdomain, are required to be refined to the same level of the corresponding elements in the global fine mesh. In addition, the global iteration matrix of the solver is not symmetric, even if all of the local matrices are symmetric. Consequently, conjugate gradient acceleration cannot be used.

In this paper, we propose a novel Additive Schwarz (AS) preconditioner that can be combined with the CG method to efficiently solve the global linear system in these parallel adaptive algorithms. Our preconditioner is formulated using the local meshes after adaptive enrichment. We recall that these are meshes of the whole domain. They are fine and identical with the global fine mesh in their corresponding subdomains, but generally much coarser elsewhere. If the adaptive meshes are nested, all the finite element spaces associated with the local meshes contain the coarse space associated with the starting coarse mesh. Therefore, there is no need to explicitly add a coarse space as in the traditional two-level AS. However, having the coarse space contained in every subspace introduces the number of subdomains as the largest eigenvalue, which might damages the scalability of the preconditioner. Fortunately, we can show that this largest eigenvalue is isolated and the convergence rate of the CG method can be bounded by a quantity that depends only on the ratio of the second largest eigenvalue and the smallest eigenvalue. The ratio is called the effective condition number. Our main theoretical results lies in the analysis of these eigenvalues.

The estimate for the second largest eigenvalue is obtained by establishing a comparison to the largest eigenvalue in a related AS method. Our estimate takes advantage of the strengthened Cauchy–Schwarz inequality for the hierarchical decomposition of local subspaces into a low frequency component and a high frequency component. For estimating the smallest eigenvalue, we follow the subspace correction framework proposed by Xu  [27] and prove the existence of a stable decomposition associated with the local meshes. Since these meshes are generally very different from one another and with the global fine mesh outside of their associated subdomains, the classical analysis of AS method (cf.  [28] ;  [3]) does not apply. Our analysis requires new sophisticated interpolation operators based on the work of Scott and Zhang  [29]. These operators are defined in conjunction with a colouring scheme in order to construct the stable decomposition recursively.

Note to users:
Accepted manuscripts are Articles in Press that have been peer reviewed and accepted for publication by the Editorial Board of this publication. They have not yet been copy edited and/or formatted in the publication house style, and may not yet have the full ScienceDirect functionality, e.g., supplementary files may still need to be added, links to references may not resolve yet etc. The text could still change before final publication.

Although accepted manuscripts do not have all bibliographic details available yet, they can already be cited using the year of online publication and the DOI, as follows: author(s), article title, Publication (year), DOI. Please consult the journal's reference style for the exact appearance of these elements, abbreviation of journal names and use of punctuation.

When the final article is assigned to volumes/issues of the Publication, the Article in Press version will be removed and the final version will appear in the associated published volumes/issues of the Publication. The date the article was first made available online will be carried over.