Source-linked AI summary
Two-level additive Schwarz preconditioners with GDSW coarse spaces for high-order discretizations in 2D
Tommaso Bevilacqua, Axel Klawonn, Martin Lanser, Adam Wasiak
TL;DR
High-order VEM overlapping Schwarz preconditioners lacked analysis beyond the lowest order. This paper studies GDSW and RGDSW for 2D Poisson discretizations, proving a condition-number bound for conforming FEM and demonstrating scalable behavior numerically for FEM and VEM. RGDSW reduces coarse-space dimension while retaining nearly identical iteration counts.
Problem
High-order VEM overlapping Schwarz methods had been studied only for k=1, with no known analysis of GDSW-type preconditioners for high-order VEM.
Source: §1 · p. 2Method
The paper analyzes two-level overlapping Schwarz preconditioners with GDSW and RGDSW coarse spaces for 2D Poisson problems discretized by high-order FEM and VEM.
Source: §1 · p. 2, §6 · p. 18Results
RGDSW reduces coarse problem dimension by about a factor of three while maintaining comparable condition numbers and iteration counts; both methods show scalability and k-robustness in experiments up to k=9.
Source: §1 · p. 2, §5 · p. 17, §6 · p. 19Takeaways & Limitations
RGDSW offers a smaller coarse space with nearly identical iteration counts across the reported FEM and VEM experiments.
Source: §6 · p. 19A condition-number analysis for high-order VEM, particularly a proof uniform in polynomial degree, remains open; three-dimensional settings and additional model problems are future work.
Source: §4.5 · p. 15, §6 · p. 19
Abstract
from arXiv · showhide
Two-level overlapping Schwarz preconditioners with Generalized Dryja-Smith-Widlund (GDSW) and Reduced GDSW (RGDSW) coarse spaces for high-order finite element methods (FEM) and virtual element methods (VEM) are investigated and applied to the Poisson problem in 2D. The GDSW coarse space is a well-established robust choice for preconditioners in domain decomposition, while the RGDSW coarse space offers a competitive alternative by reducing the coarse problem dimension while maintaining robustness. On the theoretical side, a condition number bound for both preconditioners is proved for conforming $\mathbb{P}_k$ and $\mathbb{Q}_k$ finite element spaces with explicit dependence on the polynomial degree $k$. Through numerical experiments on structured triangular and quadrilateral meshes for FEM and on polygonal meshes for VEM, it is demonstrated that both GDSW and RGDSW maintain scalability properties across polynomial orders up to $k=9$ for selected degrees. The RGDSW approach achieves a reduction in the coarse problem dimension by a factor of approximately three compared to GDSW while maintaining competitive iteration counts.
1. Introduction.
High-order VEM Schwarz methods had been studied only for k=1, and no analysis of GDSW-type overlapping Schwarz preconditioners for high-order VEM was known. This work studies GDSW and RGDSW for 2D Poisson problems, proves a condition-number bound for conforming high-order FEM, and reports scalable numerical behavior for FEM and VEM.
1. Introduction.
- Two-level additive Schwarz methods combine local solvers with a coarse-level correction for large sparse systems from high-order FEM and VEM.Source: §1 · p. 1
- GDSW coarse spaces use interface vertices and edges to form discrete harmonic extensions of local partition-of-unity functions, while RGDSW reduces coarse dimension while maintaining robustness.Source: §1 · p. 2
- High-order VEM overlapping Schwarz studies were limited to k=1, and no analysis of high-order VEM GDSW-type preconditioners was known.Source: §1 · p. 2
- The work derives a condition-number bound for GDSW and RGDSW on conforming P_k and Q_k finite element spaces, with explicit dependence on k.The authors describe this as the first such bound to their knowledge.Source: §1 · p. 2
- Numerical experiments demonstrate scalability and k-robustness for FEM and VEM up to k=9 on triangular and quadrilateral meshes, and on polygonal VEM meshes.The implementation is in-house Matlab.Source: §1 · p. 2
2. Model problem.
The section specifies a 2D Poisson problem with Dirichlet data and its FEM and VEM discretizations. FEM uses triangular or quadrilateral polynomial spaces, while VEM uses computable projections and stabilization on polygonal meshes.
2. Model problem.
- The model is the two-dimensional Poisson equation on a bounded polygonal domain with prescribed Dirichlet data, reduced to a homogeneous-boundary problem by a harmonic extension.Source: §2 · p. 2
2.1. High-order finite element discretization.
- FEM uses local polynomial spaces on triangular and quadrilateral meshes, with nodal degrees of freedom at vertices, edges, and, for higher degrees, element interiors.The quadrilateral discretization uses tensor-product polynomials; triangular elements use total-degree polynomials.Source: §2.1 · p. 3
2.2. Virtual element discretization.
- The enhanced VEM defines local spaces on polygonal meshes using vertex values, edge values, and interior moments, with projectors computable from those degrees of freedom.The discrete bilinear form combines a projected form with a stability term computable from the degrees of freedom.Source: §2.2 · pp. 3–4
- For both FEM and VEM, orthogonalizing local basis functions with respect to the L2 inner product improves local stiffness-matrix conditioning and numerical stability, especially at high polynomial degrees.Source: §2.2 · p. 4
3. Overlapping Schwarz Method with GDSW coarse spaces.
The two-level overlapping Schwarz preconditioner uses GDSW-type coarse functions built from interface components and local interior extensions. RGDSW changes the coarse basis to reduce its dimension, and the analysis covers conforming high-order FEM spaces.
3. Overlapping Schwarz Method with GDSW coarse spaces.
- GDSW basis functions use interface values on vertices or edges and are harmonically extended into subdomain interiors; the coarse matrix is formed from the resulting basis.The standard space has one basis function per interface vertex and edge.Source: §3 · p. 5, Figure 1 · p. 5
3.1. RGDSW.
- RGDSW is designed to reduce coarse problem dimension while maintaining robust convergence, using one coarse basis function per interface vertex and local interior problems.Its coarse dimension is |V|, compared with |V| + |E| for GDSW.Source: §3.1 · pp. 5–6, §3 · p. 5
3.2. GDSW and RGDSW for high-order discretizations.
- For 2D FEM and VEM, the standard interface-value construction applies without modification and represents the constant function in the coarse space.Source: §3.1 · p. 6, §3.2 · p. 6
- The condition-number bound is derived for conforming finite element spaces of order k, including both P_k and Q_k, and extends to RGDSW by decomposing its basis functions into GDSW components.Source: §3.2 · p. 6
4. Condition number bound for GDSW and RGDSW.
This section develops a high-order condition-number bound for GDSW and RGDSW, with explicit polynomial-degree dependence in the logarithmic factor, using auxiliary inequalities, stable interpolation, and a high-order edge lemma. It also explains that a corresponding VEM proof is not obtained with the available tools, noting degree-dependent constants in estimates for nonpolynomial components and an interpolation-operator issue in the edge lemma.
4. Condition number bound for GDSW and RGDSW.
- The GDSW condition-number bound has explicit polynomial-degree dependence in its logarithmic factor, and the stated constant is independent of h, H, k, and δ.The constant is said to depend only on mesh shape regularity; the theorem statement is fragmented in the supplied passages.Source: §4 · p. 6
4.1. Auxiliary results.
- The proof requires generalized discrete Sobolev inequalities, appropriate interpolation operators, and an edge lemma extended to elementwise high-order finite element spaces.A Poincaré inequality is also used throughout the auxiliary analysis.Source: §4.1 · p. 7
4.2. Discrete Sobolev inequality for high-order FEM.
- The high-order FEM analysis supplies a discrete Sobolev inequality for conforming spaces on triangular or quadrilateral meshes, with constants independent of h, H, and k and a logarithmic factor involving Hk^2/h.The self-contained proof extends an inverse-inequality approach to a more general L_r space; the supplied passages do not include the full inequality formula.Source: §4.2 · pp. 7–9
4.3. High-order interpolation inequality.
- Degree-reduction interpolation operators are used to map high-order conforming finite element functions while retaining uniform H1 stability independent of k.The operators support interpolation of the partition-of-unity restriction products used in the proof.Source: §4.3 · pp. 9–10
4.4. Edge lemma.
- The edge lemma is extended to arbitrary polynomial degrees, bounding the energy of discrete harmonic extensions of edge-function products as well as the edge functions’ energy and L2 norm.The argument uses high-order vertex and edge functions that are discrete harmonic in the subdomain and piecewise linearly interpolated on boundary degrees of freedom.Source: §4.4 · p. 10
4.5. Proof of the condition number bound.
- The condition-number proof applies abstract two-level Schwarz theory through a stable decomposition, but the authors could not establish a similar result for VEM with the available interpolation tools.They state that the remaining RGDSW proof proceeds analogously to the GDSW proof.Source: §4.5 · pp. 12, 15
- For each fixed k, controlling the nonpolynomial VEM component in the discrete Sobolev inequality uses [10, (4.5.3) Lemma], yielding the correct bound with a k-dependent constant; the high-order edge lemma inherits the same interpolation-operator issue.The interpolation operators are described as uniformly H1-stable and having optimal approximation properties.Source: §4.5 · p. 15
5. Numerical results.
On structured meshes, RGDSW reduces coarse-space dimension while retaining condition numbers and iteration counts comparable to GDSW; both methods show the predicted condition-number growth with polynomial degree. On Lloyd-regularized polygonal meshes, both methods retain robust scalability, with logarithmic scaling observed less closely than on structured meshes.
5. Numerical results.
- The experiments use an in-house Matlab implementation, estimate condition numbers with Lanczos, and stop PCG when the unpreconditioned residual norm falls by 10^-8.Polygonal meshes are generated from Voronoi tessellations and regularized with 300 Lloyd iterations.Source: §5 · p. 15
- On structured meshes, condition numbers decrease as subdomain counts rise and grow gradually from k = 1 to k = 9, consistent with the predicted logarithmic dependence.At higher polynomial degrees, VEM condition numbers are moderately larger than FEM values.Source: Table 1 · p. 16, Table 2 · p. 16, §5 · p. 17
- About threefold lower coarse-space dimension with RGDSW than GDSW accompanies comparable condition numbers and iteration counts on the structured-mesh experiments.At 32 × 32 subdomains, the condition-number difference is negligible for both FEM and VEM.Source: Table 1 · p. 16, Table 2 · p. 16, §5 · p. 17
- Across 16–1,024 subdomains, both methods retain robust scalability on Lloyd-regularized VEM meshes, with mild condition-number growth in k and nearly identical iteration counts.Condition numbers are higher than on structured meshes, and growth beyond k = 5 is slight; the logarithmic fit is less close.Source: §5 · p. 18, Table 3 · p. 18, Figure 5 · p. 18
6. Conclusion.
The paper analyzes GDSW and RGDSW two-level overlapping Schwarz preconditioners for two-dimensional high-order FEM and VEM Poisson discretizations, with an explicit-degree condition-number estimate for conforming finite element spaces. Numerical results show scalability and k-robustness for both methods, while a uniform-in-k analysis for high-order VEM remains open.
6. Conclusion.
- For the analyzed two-dimensional Poisson discretizations, the main theoretical result is a condition-number estimate with explicit dependence on polynomial degree for conforming finite element spaces.The paper analyzes GDSW and RGDSW preconditioners.Source: §6 · pp. 18–19
- For k=1,...,9 and 16–1,024 subdomains, both methods remain scalable and k-robust; condition numbers grow slightly, with VEM slightly higher than FEM at higher k.For k=1, FEM and VEM condition numbers are almost identical.Source: §6 · p. 19
- RGDSW substantially reduces coarse-space dimension compared with GDSW while delivering nearly identical iteration counts.The condition numbers are consistent with the logarithmic dependence predicted by the theory.Source: §6 · p. 19
- A uniform-in-polynomial-degree proof for high-order VEM remains open.The extension of the analysis to high-order VEM also remains open.Source: §6 · p. 19