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

When solving the Helmholtz equation with standard finite elements, the oscillatory behavior of the solution results in a large number of degrees of freedom (DoFs) required to resolve the wave, especially for high wave numbers. This together with the indefiniteness of the problem makes an iterative solution of the resulting linear system of equations difficult. Nevertheless, some advances for finding efficient preconditioners for wave type problems have been made recently. Well known is the shifted Laplace Preconditioner [5], or a sweeping preconditioner [4] based on an approximate block LDL ⊤ factorization, which is constructed layer by layer. Especially for parallel computing platforms domain decomposition methods are very popular. Apart from optimized Schwarz methods [8], i.e. Schwarz methods which rely on optimal transmission conditions as interface condition, the FETI-H [6] and the FETI-DPH [7] method are widely used. The last two methods can be seen as further developments of the FETI and the FETI-DP methods, respectively, specialized for Helmholtz problems.

The solution strategies presented in this work are based on a mixed hybrid discontinuous Galerkin formulation [10, 13] Since the hybrid formulation provides appropriate interface conditions an efficient iterative solution with Krylov space methods combined with domain decomposition preconditioners is possible. Apart from adapting a BDDC preconditioner [3, 11] to the current setting, a new Robin type domain decomposition preconditioner is constructed. This preconditioner solves in each iteration step local problems on subdomains by directly inverting the subdomain matrix. Thus, it is well suited for parallel computations. Good convergence properties of both preconditioners are demonstrated by numerical experiments. The results of this paper will be presented in more detail in [9].

2 The Mixed Hybrid Discontinuous Galerkin Formulation

Our formulation is based on the mixed form of the Helmholtz equation: Find a scalar function \(u\;:\;\varOmega \rightarrow \mathbb{C}\) and a vector valued function \({\boldsymbol p}\::\;\varOmega \rightarrow \mathbb{C}^{d}\)

$$\displaystyle{\mbox{ grad}\,u = \mathrm{i}\omega {\boldsymbol p}\qquad \text{and}\qquad \mbox{ div}\,{\boldsymbol p} = \mathrm{i}\omega u}$$

with an absorbing boundary condition \(-{\boldsymbol p} \cdot {\boldsymbol n} + u = g\) on Γ: = ∂ Ω. As computational domain \(\varOmega \subset \mathbb{R}^{d}\) with d = 2, 3 a Lipschitz polyhedron is considered. Furthermore, \({\boldsymbol n}\) denotes the outer normal vector, the angular frequency ω is a positive constant and g ∈ L 2(Γ). Note that [12] guarantees a unique solution.

In this paper we make use of the following notations. By \(\mathcal{T}\) a triangulation with the elements T is denoted. The set of its facets F we call \(\mathcal{F}\), \({\boldsymbol n}_{F}\) represents the normal vector onto a facet F, and \({\boldsymbol n}_{T}\) is the outer normal vector of an element T. Furthermore volume integrals are denoted by \(\big(u,v\big)_{T}:=\int _{T}u\bar{v}\;\mathrm{d}{\boldsymbol x}\) and surface integrals by \(\big\langle u,v\big\rangle _{\partial T}:=\int _{\partial T}u\bar{v}\;\mathrm{d}s\).

In order to obtain efficient solvers for the Helmholtz equation, we consider it in a mixed hybrid form. Thus, we search for \((u,{\boldsymbol p},u_{F},p_{F}) \in L^{2}(\varOmega ) \times H(\text{div},\mathcal{T} ) \times L^{2}(\mathcal{F}) \times L^{2}(\mathcal{F}) =: U \times V \times U_{F} \times V _{F}\) such that for all \((v,{\boldsymbol q},v_{F},q_{F}) \in U \times V \times U_{F} \times V _{F}\)

$$\displaystyle\begin{array}{rcl} \sum _{T\in \mathcal{T}}\Big(\big(i\omega u,v\big)_{T} -\big (\text{div}{\boldsymbol p},v\big)_{T} -\big (u,\text{div}{\boldsymbol q}\big)_{T} -\big (i\omega {\boldsymbol p},{\boldsymbol q}\big)_{T} +\big\langle u_{F},{\boldsymbol n}_{T} \cdot {\boldsymbol q}\big\rangle _{\partial T}\qquad & & \\ +\big\langle {\boldsymbol n}_{T} \cdot {\boldsymbol p},v_{F}\big\rangle _{\partial T} +\big\langle {\boldsymbol n}_{F} \cdot {\boldsymbol p} - p_{F},{\boldsymbol n}_{F} \cdot {\boldsymbol q} - q_{F}\big\rangle _{\partial T}\Big) -\big\langle u_{F},v_{F}\big\rangle _{\varGamma } = -\big\langle g,v_{F}\big\rangle _{\varGamma }.& &{}\end{array}$$
(1)

This mixed hybrid formulation was introduced and discussed in [13]. In the formulation the space \(H(\text{div},\mathcal{T} )\) represents an element wise H(div) space without continuity constraints across element interfaces, and \(L^{2}(\mathcal{F})\) is the space of L 2 functions on the facets. Consequently u F and p F are supported just on the facets, and they represent the values of u and \({\boldsymbol p} \cdot {\boldsymbol n}_{F}\) there. The problem is discretized by the finite dimensional spaces

$$\displaystyle\begin{array}{rcl} U_{h}:=\prod _{T\in \mathcal{T}}P_{k}(T),& & \qquad V _{h}:=\prod _{T\in \mathcal{T}}RT_{k}(T), {}\\ U_{Fh}:=\prod _{F\in \mathcal{F}}P_{k}(F),& & \qquad V _{Fh}:= U_{Fh}, {}\\ \end{array}$$

where polynomials of order k are denoted as P k and RT k represents a Raviart-Thomas element of order k. The discrete solutions we call u h , \({\boldsymbol p}_{h}\), u Fh and v Fh , respectively.

Since there is no global coupling for the functions u h and \({\boldsymbol p}_{h}\) across different elements, the corresponding DoFs can be eliminated cheaply on the element level via static condensation [1]. Note that this elimination corresponds on each element to the solution of a wave type problem with Robin boundary conditions, and uniqueness is guaranteed. The resulting linear system of equations needs now to be solved only for the facet DoFs.

Remark 1.

The original form of Eq. (1) in [13] contains a penalty parameter η, which was chosen to be one in our work. For this choice the local problem on the element, which needs to be solved during static condensation, corresponds to the original problem posed on the domain with g = ±p F + u F . The sign depends on the direction of the facet normal \({\boldsymbol n}_{F}\). Thus, g represents now the incoming impedance trace for the element.

In this work domain decomposition preconditioners will be used to solve the reduced linear system of equations for the facet unknowns u Fh and p Fh , which is obtained by eliminating the volume unknowns u h and \({\boldsymbol p}_{h}\). Note that this linear system of equations is related to the skeleton of a mesh, and a domain decomposition of the skeleton is induced by a decomposition of the underlying mesh. Since impedance traces are obtained from the facet unknowns by a simple transformation of variables, transmission conditions on the interface in the sense of [2] can be enforced by guaranteeing the same value of the facet unknowns of different subdomains on the subdomain interface. Thus the mixed hybrid formulation allows in a natural way for appropriate transmission conditions for domain decomposition preconditioners.

3 The BDDC Preconditioner for the Mixed Hybrid Formulation

In this section, we adapt the BDDC preconditioner introduced by Dohrmann in [3] (compare also [11]) to wave type problems. Therefore a stabilization term has to be added to the mixed hybrid formulation, more precisely, the term

$$\displaystyle{ \sum _{T\in \mathcal{T}}\gamma \Big(\big\langle ({\boldsymbol n}_{T} \cdot {\boldsymbol n}_{F})p_{F},v_{F}\big\rangle _{\partial T\setminus \varGamma } +\big\langle u_{F},({\boldsymbol n}_{T} \cdot {\boldsymbol n}_{F})q_{F}\big\rangle _{\partial T\setminus \varGamma }\Big),\qquad \gamma \in \mathbb{C} }$$
(2)

is added to (1). The parameter \(\gamma \in \mathbb{C}\) is a tuning parameter, we choose based on numerical experiments. For the Helmholtz and the vector valued wave equation we made good experience with γ = −0. 5 − 0. 1i. These additional terms are just added for inner facets, and because of the different sign of \({\boldsymbol n}_{T} \cdot {\boldsymbol n}_{F}\) for the two neighboring elements, they cancel out when the global system of equations is assembled. Thus the problem does not change. But for domain decomposition preconditioners, which are based on submatrices assembled just for a subdomain the situation changes. These additional terms do not cancel out in the submatrices for DoFs located on the interface to other subdomains.

We use a BDDC preconditioner for this modified facet problem. The computational domain is divided into subdomains, and the DoFs on facets which just belong to one subdomain are considered to be primal, as well as the low order DoFs on interface facets. The high order DoFs on interface facets are the dual ones.

This choice leads to a large global system for the primal DoFs. Note that this system of equations consists due to the missing high order unknowns at the interface of weakly coupled subdomain blocks. Therefore it can be solved rather efficiently by direct solvers on parallel computing platforms.

4 A Robin Type Domain Decomposition Preconditioner

Like the BDDC preconditioner, the new Robin type domain decomposition (RDD) preconditioner will be applied to the skeleton problem, including the stabilizing terms (2) with the same value for γ.

Before describing the preconditioner, some notations are required. We assume, that the computational domain is divided into N subdomains Ω i . For each subdomain a matrix A i representing the subdomain problem is subassembled, and the global matrix A of the linear system of equations is obtained by adding these submatrices. By \(\tilde{A}_{i}\) we denote the block of A i which corresponds to DoFs on inner facets, i.e. facets which just belong to the domain Ω i . The matrix R (i) restricts a vector to the components corresponding to these inner DoFs of the domain Ω i . The matrix \(R_{D}^{(i)}\) provides a weighted restriction to the domain Ω i , i.e. when applying it, a vector entry is divided by the number of subdomains to which the corresponding DoFs belongs to. Note that an application of the prolongation matrix \(R_{D}^{(i)\top }\) results again in a division for the interface DoFs. Thus, by summing up over all subdomains, a mean value on the interface can be created.

Using this notations, a RDD step for finding \(\tilde{{\boldsymbol x}}:= C_{RDD}^{-1}{\boldsymbol b}\) with \({\boldsymbol b}\) as right hand side of the linear system of equations and C RDD as the preconditioner reads as

  1. (1)

    \({\boldsymbol y}_{0} ={\boldsymbol 0},\)

  2. (2)

    \({\boldsymbol y}_{1} ={\boldsymbol y}_{0} +\sum _{ i=1}^{N}R^{(i)\top }\tilde{A}_{i}^{-1}R^{(i)}({\boldsymbol b} - A{\boldsymbol y}_{0}),\)

  3. (3)

    \({\boldsymbol y}_{2} ={\boldsymbol y}_{1} +\sum _{ i=1}^{N}R_{D}^{(i)\top }A_{i}^{-1}R_{D}^{(i)}({\boldsymbol b} - A{\boldsymbol y}_{1}),\)

  4. (4)

    \(\tilde{{\boldsymbol x}} ={\boldsymbol y}_{2} +\sum _{ i=1}^{N}R^{(i)\top }\tilde{A}_{i}^{-1}R^{(i)}({\boldsymbol b} - A{\boldsymbol y}_{2}).\)

In step 2, the system of equations is solved exactly for the DoFs on the inner facets under the constraint that the solution on the interface is zero. Step 3 provides an update for the interface solution by partitioning the actual residual among the subdomains and solving the problem there exactly. A continuous interface solution is constructed by averaging the different subdomain solutions. Finally, in step 4 the solution is updated by solving the system of equations exactly for the DoFs on inner facets. Note that the interface solution remains unchanged.

The RDD-preconditioner can also be introduced in the variational projector notation. Therefore, we denote the bilinear form representing the Schur complement system, which is defined on the facet space W: = U Fh × V Fh by a. Additionally, it is assumed that the bilinear form a can be decomposed into its subdomain contributions a i , i.e. \(a =\sum _{ i=1}^{N}a_{i}\). The subspace of W containing the functions which are supported on the subdomain Ω i is denoted by W i , and in \(\tilde{W}_{i}\) functions supported only on inner facets of the domain Ω i are collected. The operator representation of the restriction matrix \(R_{D}^{(i)}\) is called \(\mathcal{R}_{D}^{(i)}\,:\, W \rightarrow W_{i}\). Thus, when applying it to any function in W, the function is restricted to the domain Ω i , and its values on the interface facets are divided by the number of neighboring subdomains. Furthermore, \(\mathcal{R}^{(i)}\,:\, W \rightarrow \tilde{ W}_{i}\) is the restriction operator corresponding to the matrix R (i), and by \(\mathcal{R}^{(i)\top }\) the prolongation operators are denoted.

Based on this, we define the variational projector \(\mathcal{P}_{D}^{(i)}\) via \(\mathcal{P}_{D}^{(i)} = \mathcal{R}_{D}^{(i)\top }\hat{\mathcal{P}}_{D}^{(i)}\) with the projector \(\hat{\mathcal{P}}_{D}^{(i)}\,:\, W \rightarrow W_{i}\) and

$$\displaystyle{a_{i}(\hat{\mathcal{P}}_{D}^{(i)}u,\phi ) = a(u,\mathcal{R}_{ D}^{(i)\top }\phi )\qquad \forall \phi \in W_{ i}.}$$

In the same way the variational projector \(\mathcal{P}^{(i)}\) with \(\mathcal{P}^{(i)} = \mathcal{R}^{(i)\top }\hat{\mathcal{P}}^{(i)}\) can be introduced. Here, \(\hat{\mathcal{P}}^{(i)}\,:\, W \rightarrow \tilde{ W}_{i}\) is given via

$$\displaystyle{a_{i}(\hat{\mathcal{P}}^{(i)}u,\phi ) = a(u,\mathcal{R}^{(i)\top }\phi )\qquad \forall \phi \in \tilde{ W}_{ i}.}$$

If the operator \(\mathcal{A}\) corresponds to the bilinear form a, and \(\mathcal{I}\) is the identity, the error propagation operator \(\mathcal{E}\) of the RDD-preconditioner reads as

$$\displaystyle{\mathcal{E} = \mathcal{I}-\mathcal{C}_{RDD}^{-1}\mathcal{A} =\Big (\mathcal{I}-\sum _{ i=1}^{N}\mathcal{P}^{(i)}\Big)\Big(\mathcal{I}-\sum _{ i=1}^{N}\mathcal{P}_{ D}^{(i)}\Big)\Big(\mathcal{I}-\sum _{ i=1}^{N}\mathcal{P}^{(i)}\Big).}$$

Remark 2.

Because the system of equations is always solved exact for the DoFs on inner facets, both sets of facet DoFs u Fh and p Fh are not needed anymore, and the problem can be formulated just by using u Fh . On the interface, both types of unknowns are still necessary in order to fix continuity conditions of the impedance traces across the interface and to guarantee convergence of the iterative solver. Nevertheless, neglecting one type of facet unknowns on inner facets saves many DoFs in an actual calculation.

5 Numerical Results

For all numerical examples which are presented in this section, we made good experience by taking a CG-solver, although, there exists no convergence theory for complex symmetric problems. We start the numerical results section by comparing the preconditioners for a simple two dimensional model problem. There, the Helmholtz equation is solved on a square Ω = [−1, 1]2 with an incoming wave from above of Gaussian amplitude, fixed by the absorbing boundary condition. The computations were done with the MPI-parallel finite element code Netgen/Ngsolve (see http://sourceforge.net/projects/ngsolve or [14]), which contains the software package Metis for partitioning the domain. If not said differently, a Dell R-910 Server (4 Xeon E7 CPUs with 10 cores a 2.2 GHz, 512 GB RAM) was used.

Table 1 Iteration numbers of the BDDC/RDD preconditioner using nine subdomains (p = 4) for different mesh sizes and wavelength λ
Full size table

In Table 1 the iteration numbers for the BDDC and the RDD preconditioner for different wavelengths \(\lambda:= \frac{2\pi } {\omega }\) and mesh sizes h are given. For all computations the polynomial order was kept constant to four, and nine subdomains were used for the preconditioners.

According to the table, the BDDC preconditioner shows the highest iteration numbers close to the resolution limit at h ≈ λ, which corresponds for a polynomial order of p = 4 to about four unknowns per wavelength. When increasing the number of unknowns per wavelength, either by decreasing the mesh size or by increasing the wavelength, the number of iterations stays constant or grows slightly. For the RDD preconditioner the situation is vice versa. Although, for a large wavelength and a small mesh size the RDD preconditioner needs much more iterations than the BDDC preconditioner, it gets more and more competitive if the number of degrees of freedom per wavelength is reduced. Considering, that the RDD preconditioner is faster than the BDDC preconditioner with respect to setup-time and time per iteration, it is the method of choice for discretizations close to the resolution limit of the wave.

One reason for this behavior could be the different structure of the two solvers. While the RDD preconditioner allows just for local corrections, the BDDC solver benefits additionally from a coarse grid solution. For a decreasing wavelength, the solution gets more and more oscillatory, and the coarse grid correction, which provides communication across the whole subdomain loses its importance.

Fig. 1
figure 1

Number of iterations plotted versus the size of one subdomain H for the BDDC and the RDD preconditioner. The polynomial order was 4 and \(h = \frac{1} {64}\)

Full size image

The number of iterations of the BDDC and the RDD preconditioner is also influenced by the size of the subdomains the computational domain is divided into. In Fig. 1 iteration numbers of these two preconditioners are plotted for different wavelengths against the subdomain size H, both in logarithmic scale. Note that the partitioning of the domain was done by Metis, and therefore, H represents an average subdomain size. In the corresponding experiments the mesh size was kept constant to \(\frac{1} {64}\) and the polynomial order to four. For the RDD preconditioner the number of iterations decreases with an increasing subdomain size. Figure 1 indicates that this decrease is proportional to H −α. According our experimental data α was estimated to be approximately 0.65. The situation is slightly different for the BDDC preconditioner. While it shows the same features for small wavelengths, i.e. for settings close to the resolution limit, the iterations stay almost constant for large wavelengths. A reason for this is, that for less oscillatory solutions the BDDC preconditioner benefits from its coarse grid correction.

Fig. 2
figure 2

Real part of the solution (left) and its absolute value (right) for a wave diffracted at a grating

Full size image

Finally, we want to demonstrate the efficiency of our preconditioners with a three dimensional large scale example. The computational results presented in the following have been achieved using the Vienna Scientific Cluster 2 (VSC2). In this example, the solution of the Helmholtz equation for a grating (compare Fig. 2) with period 0.14 was computed. The diameter of the computational domain was two. Thus, assuming a wave incoming from the top with Gaussian amplitude and wavelength 0.025 corresponds to an effective domain size of 80 wavelengths. For this setting, the left hand plot in Fig. 2 shows the real part of the solution, and the absolute value is plotted on in the righthand plot. In the calculation, the underlying mesh had about 1.61 million elements with a maximal mesh size of 0.021. Selecting a polynomial order of p = 4 results in approximately 288.8 million volume unknowns (56.5 M. for u and 232.3 M. for \({\boldsymbol p}\)) and 98.0 million facet unknowns (49.0 M. for u F and p F ). Using 1,200 subdomains, the assembly of the matrix took 58 s and the setup of the RDD preconditioner 33 s. The problem was solved in 12.9 min with 399 iterations on 1,200 processors. Recovering the volume DoFs u h and \({\boldsymbol p}_{h}\) from the facet DoFs u Fh and p Fh took 53 s.