Project Topics
Get Complete Project Material File(s) Now! »
Robustness with respect to the polynomial degree p
Due to the role of the linear solvers in obtaining a computable approximation of the discrete solution, their behavior with respect to the discretization parameters, mesh size h and polynomial degree p, should be considered. While we mentioned that certain solvers are robust with respect to the mesh size h, e:g: geometric multigrid solvers and certain preconditioners, we now focus on the behavior of solvers with respect to p. Very often the performance of linear solvers degrades with the increase of the polynomial degree, i:e:, the algebraic error decreases in each iteration more slowly when p increases. When the solver is immune to this degradation, we refer to it as a p-robust solver.
In Quarteroni and Sacchi Landriani [1988], a p-robust domain decompostion method was presented for a speci c domain con guration, and later advances on the topic were made in Pavarino [1994] for quadrilateral/hexahedral meshes, where a p-robust domain decomposition method using additive Schwarz was introduced. The generalization of this result for triangular/tetrahedral meshes was achieved by Schoberl et al. [2008] and the additive Schwarz method was used here to construct a p-robust preconditioner. For results for multigrid solvers also covering more general meshes, see e:g:, Antonietti et al. [2018] and Antonietti and Pennesi [2019], where p-robustness is achieved when the number of smoothing steps is chosen su ciently large. For a computational survey on multigrid solvers for high-order discretizations, see e:g: Sundar et al. [2015].
Two central building blocks for the results of the thesis
We wish to acknowledge the important role of the two following works in the de-velopment of our theoretical results: 1) The p-robust results of this thesis crucially rely on the p-robust stable decomposition based on local problems of Schoberl et al. [2008]. In Schoberl et al. [2008] this is developed on one given mesh (one-level), whereas we generalize it here to the multilevel setting. Moreover, the analysis in Schoberl et al. [2008] serves to construct a (symmetric) preconditioner, whereas in our work, the decomposition is a crucial ingredient of a standalone (non-symmetric) solver. 2) The multilevel piecewise a ne stable decomposition of Xu et al. [2009], in particular for graded meshes generated by bisection. In Xu et al. [2009] the nite element hierarchy only uses order p approximations in the nest level and the estimates are not p-robust, whereas in our work, the hierarchy can be more general as long as the level-wise nite element spaces are nested, and the estimates are p-robust. By combining the above two results together, we obtain a p-robust multilevel stable splitting, essential for our analysis.
Model problem and its discretization
In this thesis, we will consider of a second-order elliptic di usion problem posed over Rd, d2f1; 2; 3g, an open bounded polytope with a Lipschitz-continuous boundary. Below, f 2 L2( ) denotes the source term and K 2 [L1( )]d d is a bounded tensor-valued di usion coe cient taking symmetric and uniformly positive de nite values. The problem consists in nding u : ! R such that Kru = f in ; (1) u = 0 on @ .
Main results: p-robust e ciency of the a posteriori estimator and p-robust solver contraction
We prove that the a posteriori estimator of the algebraic error is e cient and that the associated a-posteriori-steered algebraic solver contracts the algebraic error at each iteration. These two main results can be presented as follows:
Theorem v.5 (p-robust reliable and e cient bound on the algebraic error). Let uJ 2 VJp be the (unknown) nite element solution of (4) and let uiJ 2 VJp be arbitrary, i 0. Let algi be given by De nition v.2. Then, in addition to 1 uJi ) K r(uJ 2 algi from (20), there holds ; algi 1 uJi ) (21) K r(uJ 2 where 0 < < 1 depends on the space dimension d, the mesh shape regularity parameter, the ratio of the largest and the smallest eigenvalue of the di usion coef-cient K, at most linearly on the number of mesh levels J, and additionally on the mesh hierarchy parameters like the strength of re nement and quasi-uniformity of the coarse mesh (graded bisections) or all meshes (uniform re nement). In partic-ular, is independent of the polynomial degree p.
Algebraic system, approximate solution, and algebraic residual
If one introduces Jl , 1 l NJ , a basis of VJp, then problem (1.4) is equivalent to solving a system of linear algebraic equations. Denoting by (AJ )lm := (r Jm; r Jl ) the symmetric, positive de nite (sti ness) matrix and by (FJ )l := (f; Jl ) the right- hand side (load) vector, one obtains u = NJ (U ) m, where U J 2 RNJ is the solution of J Pm=1 J m J AJUJ = FJ.
For any approximation UJi 2 RNJ of UJ given by an arbitrary algebraic solver at iteration step i 0, the associated continuous piecewise polynomial of degree p is N m p i P J i 2 J by m=1 (UJ )m J V : The associated algebraic residual vector is given uJ = RJi := FJ AJ UJi .
Note, however, that RJi depends on the choice of the basis functions Jl , 1 lp NJ .
To avoid this dependence, we work instead with a residual functional on VJ given by vJ 7!(f; vJ ) (ruJi ; rvJ ) 2 R; vJ 2 VJp: (1.5) We emphasize that the forthcoming results are independent of the choice of the basis.
Performance of the weighted restrictive additive Schwarz (wRAS) con-struction of the solver
As observed in the literature, replacing the damping with parameter w1 in (1.19) by hat function weighting via a restrictive additive Schwarz often performs better; cf: Cai and Sarkis [1999], Efstathiou and Gander [2003], or Loisel et al. [2008]. Thus, in addition to the dAS construction (1.37), we now numerically also explore the weighted restricted additive Schwarz (wRAS) construction of the lifting iJ;alg: J X X Ijq( ja s j;ia); 1 j J; (1.38) wRAS: J;i alg := ji and ji := j=0 a2Vj s j 1 (r j;ia; rvj;a)!j;sa = (f; vj;a)!j;sa X (ruJi ; rvj;a)!j;sa (r ki; rvj;a)!j;sa k=0 with q = p0 except for j = J where q = p, we denote by Ijq the Pq Lagrange interpolation operator on the mesh level j, i:e:, Ijq : C0( ) ! Vjq, Ijq(v) preserves the values of v in the nodes corresponding to the Lagrange degrees of freedom. No damping weights are to be chosen here.
We summarize the results obtained for each of the problems (1.32){(1.34) in Table 1.2. In addition to one post-smoothing step, = 1, we also present the results for = 3 post-smoothing steps. In both cases, no pre-smoothing has been employed. In the last two columns for each problem, we present a comparison of our solver of De nition 4.4 employing (1.38) with two standard smoothers for multigrid, namely the Jacobi (J) and the Gauss{Seidel (GS) ones. Here, we employ no pre-smoothing step, one post-smoothing step, and a coarse solve with polynomials of order 1 as in (1.15) to compare with our approach.
The results using the wRAS (1.38) construction of the lifting indicate an im-provement in the error contraction factors with respect to dAS (1.37) of Section 6.1 and, moreover, present a complete numerical independence of the number of levels J. Furthermore, the iteration numbers drop by at least half when three post-smoothing steps are employed. In contrast to these results, we see that the multigrid with stan-dard smoothers degrades violently with respect to the polynomial degree p. Note in this respect that for p = 1, the only di erence between wRAS of (1.38) with small patches and = 1 and standard Jacobi lies in the optimally chosen step-size of Lemma 4.3. This gives a spectacular gain in the number of iterations, and makes the method convergent even when the standard Jacobi fails.
Comparison with other multilevel solvers
Some recent comparisons of state-of-the-art solvers for Poisson problems with multi-grid methods in the high-order setting include Gholami et al. [2016], Sundar et al. [2015], and Kronbichler and Wall [2018]. In Sundar et al. [2015], it was in partic-ular reported that none of the methods considered behaves fully independently of the polynomial degree. In this subsection, we compare our developments with four well-established methods. We focus on the number of iterations, but we also indi-cate CPU times of our vectorized Matlab implementation1, trusting the reader to understand the trickiness inherent in such implementation- and machine-dependent measurements. The timings below involve the solution time only; i:e:, they do not include the assembly time of the matrices. The methods we consider for the comparison are as follows:
wRAS, = 1 ( MG(0,1)-bJ): De nition 4.4, small patches, p0 = p in (1.10a) (to illustrate the associated space hierarchy, we write \1; p ! p »), wRAS con-struction (1.38).
wRAS, = 3 ( MG(0,3)-bJ): De nition 4.4, small patches, p0 = p in (1.10a) (\1; p ! p »), wRAS construction (1.38), three post-smoothing steps employed.
wRAS, = 1 ( MG(0,1)-bJ): De nition 4.4, small patches, p0 = 1 in (1.10a) (\1 ! 1; p »), wRAS construction (1.38).
Table of contents :
Resume
Abstract v
Acknowledgements
List of Figures
List of Tables
Introduction
i Finite element method
ii Linear solvers
ii.1 Direct solvers
ii.2 Iterative solvers
ii.3 Adaptive linear solvers
ii.4 Robustness with respect to the polynomial degree p
iii Two central building blocks for the results of the thesis
iv Model problem and its discretization
v A posteriori point of view and goals of the thesis
v.1 Multilevel setting
v.2 Multilevel procedure for constructing an a posteriori estimator of the algebraic error and a linear solver
v.3 Main results: p-robust eciency of the a posteriori estimator and p-robust solver contraction
v.4 Alternative approaches
v.5 Extension to the mixed nite element method
vi Adaptivity in a-posteriori-steered solvers
vi.1 Adaptive number of post-smoothing steps
vi.2 Adaptive local smoothing
vii Contents and contributions of the thesis
vii.1 Chapter 1
vii.2 Chapter 2
vii.3 Chapter 3
vii.4 Chapter 4
vii.5 Implementation notes
viii Perspectives
1 A multilevel algebraic error estimator and the corresponding iterative solver with p-robust behavior
1 Introduction
2 Setting
2.1 Model problem
2.2 Finite element discretization
2.3 Algebraic system, approximate solution, and algebraic residual
2.4 A hierarchy of meshes
2.5 A hierarchy of spaces
2.6 Two types of patches
3 Multilevel lifting of the algebraic residual
3.1 Exact algebraic residual lifting
3.2 Coarse solve
3.3 Multilevel algebraic residual lifting
4 An a posteriori estimator on the algebraic error and a multilevel solver
4.1 A posteriori estimate on the algebraic error
4.2 Multilevel solver
5 Main results
6 Numerical experiments
6.1 Performance of the damped additive Schwarz (dAS) construction of the solver
6.2 Performance of the weighted restrictive additive Schwarz (wRAS) construction of the solver
6.3 Comparison with other multilevel solvers
7 Proofs of the main results
7.1 Upper bound on kri J;algk
7.2 Lower bound on (f; i J;alg) (rui J ;ri J;alg)
7.3 Polynomial-degree-robust multilevel stable decomposition
7.4 Upper bound on kr~i J;algk
7.5 Proof of Theorem 5.1
7.6 Proof of Corollary 5.6
8 Conclusions and outlook
2 A-posteriori-steered p-robust multigrid with optimal step-sizes and adaptive number of smoothing steps
1 Introduction
2 Setting
2.1 Model problem, nite element discretization, and algebraic system
2.2 A hierarchy of meshes and spaces
3 Motivation: level-wise orthogonal decomposition of the error
4 Multilevel solver
5 A posteriori estimator on the algebraic error
6 Main results
6.1 Setting, mesh, and regularity assumptions
6.2 Main results
6.3 Additional results
7 Adaptive number of smoothing steps
8 Complexity of the solver
9 Numerical experiments
9.1 Performance of the multilevel solver of Denition 4.1
9.2 Adaptive number of smoothing steps using Denition 7.1
9.3 Examples in three space dimensions
9.4 Comparison with solvers from literature
10 Proof of Theorem 6.6
10.1 Properties of the estimator i alg
10.2 Properties of the exact residual lifting ~i J;alg
10.3 Proof of Theorem 6.6 under the minimal H1 0 ( )-regularity assumption
10.4 Proof of Theorem 6.6 under the H2( )-regularity assumption
11 Conclusions and future work
3 Contractive local adaptive smoothing based on Dor er’s marking in aposteriori- steered p-robust multigrid solvers
1 Introduction
2 Setting
2.1 Model problem and its nite element discretization
2.2 A hierarchy of meshes and spaces
3 Adaptive multilevel solver
3.1 Algorithmic description of the solver
3.2 Mathematical description of the solver
4 A posteriori estimator on the algebraic error
5 Main results
5.1 Mesh assumptions
5.2 Main result
5.3 Additional results
6 Numerical experiments
6.1 Can we predict the distribution of the algebraic error?
6.2 Does the adaptivity pay o?
6.3 Dependence on the marking parameter
7 Proofs of the main results
7.1 Proof of contraction: full-smoothing substep
7.2 Proof of contraction: adaptive-smoothing substep
8 Conclusions
4 p-robust multilevel and domain decomposition methods with optimal stepsizes for mixed nite element discretizations of elliptic problems
1 Introduction
2 Model problem and its mixed nite element discretization
2.1 Discrete mixed nite element problem
3 Multilevel setting
3.1 A hierarchy of meshes
3.2 A hierarchy of spaces
4 An a-posteriori-steered multigrid solver
4.1 Multigrid solver
4.2 A posteriori estimator on the algebraic error
5 An a-posteriori-steered domain decomposition solver
5.1 Two-level hierarchy
5.2 Two-level iterative solver: overlapping additive Schwarz .
5.3 A posteriori estimator on the algebraic error
6 Main results
7 Proofs of the main results
7.1 Multilevel setting results
7.2 Two-level domain decomposition setting results
8 Conclusions
