Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

We present two- and three-dimensional numerical results obtained using BDDC deluxe preconditioners, cf. Dohrmann and Widlund (2013), for the linear systems arising from finite element discretizations of

$$\displaystyle{ \int _{\varOmega }\alpha \ \nabla \times \mathbf{u} \cdot \nabla \times \mathbf{v} +\beta \ \mathbf{u} \cdot \mathbf{v}\ dx. }$$
(1)

This bilinear form originates from implicit time-stepping schemes of the quasi-static approximation of the Maxwell’s equations in the time domain, cf. Rieben and White (2006). The coefficient α is the reciprocal of the magnetic permeability, whereas β is proportional to the ratio between the conductivity of the medium and the time step. Anisotropic, tensor-valued, conductivities can be handled as well. We only present results for essential boundary conditions, but the generalization of the algorithms to natural boundary conditions is straightforward.

The operator ∇× is the curl operator, defined, e.g., in Boffi et al. (2013); the vector fields belong to the space H 0(curl), which is the subspace of H(curl) of functions with vanishing tangential traces over ∂ Ω. The space H(curl) is often discretized using Nédélec elements; those of lowest order use polynomials with continuous tangential components along the edges of the elements. While most existing finite element codes for electromagnetics use lowest order elements, those of higher order have shown to require fewer degrees of freedom (dofs) for a fixed accuracy; see, e.g., Schwarzbach et al. (2011) and Grayver and Kolev (2015). We note that higher order elements have been neglected in the domain decomposition (DD) literature with the exception of spectral elements. Section 3 contains novel results for two-dimensional discretizations of (1) using arbitrary order Nédélec elements of first and second kind on triangles.

The design of solvers for edge-element approximations of (1) poses significant difficulties, since the kernel of the curl operator is non-trivial. Moreover, finding logarithmically stable decompositions for edge-element approximations in three dimensions is challenging, due to the strong coupling that exists between dofs located on the subdomain edges and on the subdomain faces. Among non-overlapping DD solvers, it is worth citing the wirebasket algorithms developed by Dohrmann and Widlund (2012) and by Hu et al. (2013). To save space, we omit citing some of the related DD literature; references can be found in Dohrmann and Widlund (2012), and Dohrmann and Widlund (2016).

The edge-element approximations of (1) have also received a lot of attention from the multigrid community; for Algebraic Multigrid (AMG) methods see Hu et al. (2006) and the references therein. Robust and efficient multigrid solvers can be obtained combining AMG and auxiliary space techniques, that require some extra information on the mesh connectivity and on the dofs, cf. Hiptmair and Xu (2007), Kolev and Vassilevski (2009). This approach has recently proven to be quite successful in 3D even with higher order elements, cf. Grayver and Kolev (2015).

An analysis for 3D FETI-DP algorithms with the lowest order Nédélec elements of the first kind was given in Toselli (2006), a paper which also highlighted the importance of changing the basis on the subdomain edges. Recently, Toselli’s results have been significantly improved by Dohrmann and Widlund (2016), who were able to obtain sharp and quasi-optimal condition number bounds, with a mild dependence on the material parameters through the factor 1 +β H 2∕α. Deluxe scaling proved to be critical to obtain bounds independent on the jumps of the material coefficients in 3D.

While BDDC algorithms are often robust with respect to jumps in the material parameters, their convergence rates drastically deteriorate when these jumps are not aligned with the interface of the subdomains. After the pioneering study of Mandel and Sousedík (2007), primal space enrichment techniques have been the focus of much recent work on BDDC and FETI-DP algorithms; cf. Mandel et al. (2012), Pechstein and Dohrmann (2013), Kim et al. (2015), Klawonn et al. (2015), Calvo and Widlund (2016) and the references therein. Section 3 contains numerical results using heterogeneous material coefficient distributions, for triangular elements of both kinds, and for the lowest order tetrahedral elements of the first kind. All the results of this paper have been obtained using the BDDC implementation developed by the author, and which is available in the current version of the PETSc library (Balay et al., 2015). For details on the implementation, see Zampini (2016).

2 Adaptive BDDC Deluxe Methods

Non-overlapping DD algorithms are often designed using the stiffness matrix A (i) assembled on each subdomain Ω i . We note that for the problem of interest, these matrices are always symmetric and positive definite. The recipe for the construction of a BDDC preconditioner consists in the design of a partially continuous space \(\widetilde{\mathbf{W}}\), the direct sum of a continuous primal space W Π and a discontinuous dual space W Δ , and in the choice of an averaging operator E D for the partially continuous dofs, cf. Mandel et al. (2005). A remarkably simple formula, related to the stability of the average operator with respect to the energy norm, provides an upper bound for the condition number (κ) of the BDDC preconditioned operator

$$\displaystyle{\kappa \leq \max _{\mathbf{w}\in \widetilde{\mathbf{W}}}\dfrac{\mathbf{w}^{T}E_{D}^{T}SE_{D}\mathbf{w}} {\mathbf{w}^{T}S\mathbf{w}},}$$

where S is the direct sum of the subdomain Schur complements S (i), obtained by condensing out from A (i) the dofs in the interior of the subdomains. We can then control the convergence rate of the methods by enriching the primal space W Π , and this can be accomplished by solving a few local generalized eigenvalue problems, associated to the equivalence classes of the interface.

For the BDDC deluxe algorithms, a local generalized eigenvalue problem for each equivalence class C, shared by two subdomains, is given by

$$\displaystyle{ (\widetilde{S}_{CC}^{(i)-1} +\widetilde{ S}_{ CC}^{(\,j)-1})\varPhi =\lambda (S_{ CC}^{(i)-1} + S_{ CC}^{(\,j)-1})\varPhi, }$$
(2)

with S CC (i) a principal minor of S (i) relative to C. The \(\widetilde{S}_{CC}^{(i)}\) matrices are obtained by energy-minimization as \(\widetilde{S}_{CC}^{(i)}\,=\,S_{CC}^{(i)} - S_{C'C}^{(i)T}S_{C'C'}^{(i)-1}S_{C'C}^{(i)}\), with C′ the set of complementary interface dofs of C, cf. Pechstein and Dohrmann (2013). Elements in the dual space are then made orthogonal, in the inner product (S CC (i)−1 + S CC ( j)−1)−1, to a few selected eigenvectors of (2), with eigenvalues greater than a given tolerance μ.

More complicated generalized eigenvalue problems arise when controlling the energies contributed by interface classes shared by three or more subdomains; even if they lead to fully controllable condition number bounds, they could potentially generate unnecessary primal constraints, cf. Kim et al. (2015), Calvo and Widlund (2016). In our algorithm, we instead consider the eigenvectors associated to the largest eigenvalues of

$$\displaystyle{ (\widetilde{S}_{CC}^{(i)-1} +\widetilde{ S}_{ CC}^{(\,j)-1} +\widetilde{ S}_{ CC}^{(k)-1})\varPhi =\lambda (S_{ CC}^{(i)-1} + S_{ CC}^{(\,j)-1} + S_{ CC}^{(k)-1})\varPhi, }$$
(3)

that is a generalization of (2), so far without a theoretical validation. With tetrahedral meshes, classes shared by more than three subdomains are rarely encountered. Therefore, we impose full continuity on the partially assembled space for the few dofs that belong to these classes.

We also provide results for adaptive algorithms working with the economic variant of the deluxe approach (e-deluxe), where the S (i) are obtained by eliminating the interior dofs in two layers of elements next to the subdomain part of the interface.

3 Numerical Experiments

The triangulation of Ω and the assembly of the subdomain matrices have been performed with the DOLFIN library, cf. Logg and Wells (2010). ParMETIS (Karypis, 2011) is used to decompose the meshes, and each subdomain is assigned to a different MPI process. MUMPS (Amestoy et al., 2001) is used for the subdomain interior solvers and for the explicit computation of the S (i). A relative residual reduction of 10−8 is used as the stopping criterion of the conjugate gradients; random right-hand sides are always considered.

Results will be given sometimes as a function of the ratio H∕h, where \(H =\max _{i}\{\max _{P_{1},P_{2}\in \partial \varOmega _{i,h}}d(P_{1},P_{2})\}\), with P 1 and P 2 two vertices of the boundary mesh ∂ Ω i, h of Ω i , and d(P 1, P 2) their Euclidean distance. N p 1 and N p 2 denote Nédélec first and second kind elements on simplices, respectively, with p the polynomial order.

For the numerical results, we always consider decompositions of the unit domain into 40 irregular subdomains; large scale numerical results for adaptive BDDC algorithms with N 1 1 tetrahedral elements can be found in Zampini and Keyes (2016).

3.1 2D Results

We first report on the quasi-optimality and on the dependence of p. The material coefficients are subdomain-wise constant, but they have jumps between subdomains, which are subdivided in even and odd groups according to their MPI rank. α = β = 100 for odd subdomains, α = β = 0. 01 for even subdomains. The primal space is characterized in terms of the continuity of the tangential traces along the subdomain edges, cf. Toselli and Vasseur (2005). The quadrature weights for such constraints can easily be obtained by exploiting the Stokes theorem, i.e.,

$$\displaystyle{\int _{\varOmega _{i}}\nabla \times \mathbf{u}\ dx =\int _{\partial \varOmega _{i}}\mathbf{u} \cdot \mathbf{t}\ ds.}$$

Figure 1 shows the quasi-optimality of the deluxe methods with N p 1 (left) and N p 2 (center) elements. The results in the right panel, obtained with a fixed mesh and by increasing p, seem to indicate a polylogarithmic bound.

Fig. 1
figure 1

2D results. κ as a function of H∕h. Left: N p 1. Center: N p 2. Right: κ as a function of p (H∕h = 66)

Full size image

We then analyze adaptive BDDC deluxe algorithms with the heterogeneous coefficients distribution given in Fig. 2. The mesh is fixed (H∕h=140.7), as well as the number of dofs, which varies from 800K for N 1 1 to 11M for N 4 2. Figure 3 shows the condition number, the iteration count, and the relative size, in terms of the number interface dofs, of the adaptively generated coarse spaces, all given as a function of the eigenvalue threshold. The latter appears to be a very good indicator of κ; the iteration count constantly decrease as the threshold approaches 1. The number of primal dofs is always smaller than 10% of the interface dofs, even with values of μ close to the limit; we note that more favorable coarsenings are obtained with higher order elements.

Fig. 2
figure 2

2D distributions of α (left) and β (center). Right: decomposition in 40 subdomains

Full size image
Fig. 3
figure 3

2D results. κ (left), iterations (center), and relative size of W Π (right) as a function of μ. Top: N p 1. Bottom: N p 2. α, β as in Fig. 2

Full size image

3.2 3D Results

As first highlighted by Toselli (2006), the existence of a stable decomposition in 3D is precluded if a change of basis of the dofs of the subdomain edges is not performed. This change of basis, which consists in the splitting of the dofs of each subdomain edge E in a constant and a gradient component, is not local to E, as it involves all the other interface dofs associated to those elements which have a fine edge in common with E. In our 3D experiments, we consider only N 1 1 elements; constructing suitable changes of basis for higher order elements could be the subject of future research.

As already noted by Dohrmann and Widlund (2016), some care must be exercised when considering a decomposition obtained by mesh partitioners, since the proper detection of subdomain edges is crucial for the success of the algorithm. To this end, we first construct the connectivity graph of the mesh vertices through mesh edges, and analyze its connected components. We then mark the corners that have been found, i.e. the connected components made up by just one element, and proceed by analyzing the connectivity graph of the mesh edges through mesh vertices, excluding the connections through the corners. The connected components of this graph are further refined in order to avoid any possible subdomain edge which does not have endpoints. Once that the subdomain edges have been properly identified, we then assign them a unique orientation across the set of sharing subdomains, and construct the change of basis as outlined in Toselli (2006), using the modification for non-straight edges proposed by Dohrmann and Widlund (2016).

For the 3D results, we consider a mesh of 750K elements, with H∕h=26.3; the number of dofs is approximatively 1M. In Fig. 4 we report the results of adaptive algorithms using an extrusion in the z-direction of the coefficients distributions in Fig. 2, and compare the deluxe and e-deluxe generated primal spaces. Notably, e-deluxe gives very similar results to the deluxe case. The eigenvalue threshold results in a very good indicator of κ even in 3D, despite the lack of a theoretical validation for the eigenvalue problem (3). The iterations constantly decrease as the threshold approaches one in both cases. The relative size of the primal problem is larger than in the 2D case, but it still shows interesting coarsening factors.

Fig. 4
figure 4

3D results. κ (left), iterations (center) and relative size of W Π (right) as a function of μ. (x, y) distributions of α and β as in Fig. 2 (extruded in the z-direction)

Full size image

We close with a test case where α and β are exponentially and randomly chosen in \([10^{-q_{\alpha }},10^{q_{\alpha }}]\) and \([10^{-q_{\beta }},10^{q_{\beta }}]\), and using μ = 10. The results, provided in Table 1 as a function of q α and q β , provide a clear evidence that the condition number is fully controllable.

Table 1 3D results
Full size table