Hierarchical proximal Galerkin: a fast h ​ p hp -FEM solver for variational problems with pointwise inequality constraints

Ioannis P. A. Papadopoulos · 2024

Read Hierarchical proximal Galerkin: a fast h ​ p hp -FEM solver for variational problems with pointwise inequality constraints by Ioannis P. A. Papadopoulos (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-13733.txt.

Introduction

Ioannis Papadopoulos published a 2024 mathematics paper on a fast solver for problems where the answer must respect a ceiling. Such variational problems, an elastic membrane pressed against an obstacle, for example, appear across engineering. They are posed as inequalities at every point, which standard solvers handle clumsily. A recent algorithm, proximal Galerkin, solves them in a mesh-independent way but needed a fast high-order implementation.

The author discretizes the method's saddle-point systems with a hierarchical polynomial basis on box-shaped domains. The resulting systems are sparse and admit a simple, effective preconditioner, the trick that makes big linear systems solvable quickly. Both obstacle constraints and gradient constraints are covered. Tests include obstacle problems with adaptive refinement in space and order, and a three-dimensional case. The work turns an elegant algorithm into practical software-grade machinery for constrained simulation.

Catalog record

CREATORIoannis P. A. Papadopoulos
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-13733

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hierarchical proximal Galerkin: a fast h ​ p hp -FEM solver for variational problems with pointwise inequality constraints Ioannis P. A. Papadopoulos Abstract We leverage the proximal Galerkin algorithm (Keith and Surowiec, Foundations of Computational Mathematics, 2024, DOI: 10.1007/s10208-024-09681-8 ), a recently introduced mesh-independent algorithm, to obtain a high-order finite element solver for variational problems with pointwise inequality constraints. This is achieved by discretizing the saddle point systems, arising from the latent variable proximal point method, with the hierarchical p p -finite element basis. This results in discretized sparse Newton systems that admit a simple and effective block preconditioner. The solver can handle both obstacle-type, u ≤ φ u\leq\varphi , and gradient-type, | ∇ u | ≤ φ |\nabla u|\leq\varphi , constraints. We apply the resulting algorithm to solve obstacle problems with h ​ p hp -adaptivity, a gradient-type constrained problem, and the thermoforming problem, an example of an obstacle-type quasi-variational inequality. We observe h ​ p hp -robustness in the number of Newton iterations and only mild growth in the number of inner Krylov iterations to solve the Newton systems. Crucially we also provide wall-clock timings that are faster than low-order discretization counterparts. 1 Introduction Minimizing the Dirichlet energy with an obstacle- or gradient-type pointwise constraint is known as the obstacle problem or generalized elastic-plastic torsion problem , respectively. The obstacle problem models the deflection of an elastic membrane in contact with an obstacle [ 37 , 88 ] and due to its foundational nature, has wide-ranging applications in various fields including optimal control [ 32 , 58 , 82 ] , topology optimization [ 20 , 23 , 75 ] , and elasticity theory [ 49 , 37 ] among many others. In turn, many PDE-constrained optimization problems are thoroughly reliant on an efficient obstacle problem solver. Gradient-type constraints arise in quasi-variational inequalities that model sandpile growth, river networks, semiconductors, strain-limited elastic material, and number of other applications cf. [ 8 , 94 , 90 , 26 , 80 , 79 , 7 , 65 , 35 , 84 , 91 , 30 , 83 ] . In this paper we discretize the latent variable proximal point method (LVPP) of Keith and Surowiec [ 57 ] with the hierarchical p -finite element method ( p -FEM) to construct the hierarchical proximal Galerkin algorithm (hpG), a solver that enjoys the following properties: (i) h - and p -independent number of nonlinear iterations until convergence; (ii) arbitrarily fast convergence to solutions of both the obstacle problem and minimization problems with gradient-type constraints; (iii) high-order discretizations (see Section 7.4 for a discretization with polynomials up to total degree 164 (p=82) on each quadrilateral element of a 4\times 4 mesh); (iv) competitive solve times with lower order methods to reach a prescribed error; (v) a block-diagonal preconditioner resulting in mild polylogarithmic growth in the inner Krylov method iterations as h\to 0 and p\to\infty ; (vi) fast sparse factorizations for the mass, stiffness, and preconditioner matrices; (vii) fast quasi-optimal complexity quadrature via fast transforms and the discrete cosine transform (DCT). 1.1 Motivation For nontrivial constraints, the regularity of a solution u is capped at u\in H^{s}(\Omega) , for s<5/2 , where H^{s}(\Omega) denotes the usual Sobolev spaces W^{s,2}(\Omega) [ 1 ] . This is true even if the problem is posed on a smooth domain \Omega with smooth data and a smooth obstacle [ 27 , Th. 3] 1 1 1 For a constant gradient-type constraint, the fact that u\in H^{s}(\Omega) , for s<5/2 , follows by rewriting the gradient-type constrained problem as an obstacle problem with a Lipschitz continuous obstacle [ 91 , Th. 2.2] . The result in [ 27 , Th. 3] then applies. . As such low-order discretizations are often favoured due to their simplicity, perceived reduced computational cost due to sparsity, and efficiency in convergence due to low solution regularity. For the obstacle problem, there exist efficient low-order optimal complexity (but mildly mesh dependent) multigrid (MG) techniques [ 41 , 24 , 44 , 50 , 51 , 62 , 63 , 29 , 95 ] . There is a strong correspondence between these MG solvers and active-set strategies [ 41 , Sec. 6] which require that nodal feasibility in the discretization implies pointwise feasibility. In turn this requirement typically restricts a user to the lowest-order continuous FEM basis 2 2 2 A recent study has shown success with active-set strategies and a carefully chosen quadratic or cubic FEM basis [ 59 ] . . A reader may now arrive at the following question: Why develop a high-order discretization for pointwise-constrained problems? In this paper, we argue that, per degree of freedom (dof), a high-order discretization may induce an error that is orders of magnitude smaller than the low-order counterpart – particularly in the H^{1} -norm. Of course, fewer dofs does not imply faster solve times. Matrix assembly overhead may significantly increase as sparsity is often greatly reduced, resulting in a substantial increase in the number of nonzero entries that must be evaluated. Moreover, each individual nonzero entry becomes more expensive to compute. The loss of sparsity also impacts the effectiveness of sparse linear solvers further reducing solver speed. However, in recent years, there have been a number of developments that allow for fast expansions and evaluations of the high-order orthogonal polynomials that form the hierarchical p -FEM basis which, incidently, when used to discretize the LVPP subproblems [ 57 ] , induces discretized linear systems where the loss of sparsity is heavily mitigated [ 92 , 60 , 76 ] . By leveraging these developments, we will present concrete counterexamples where accurate solutions are cheaper to obtain with high-order discretizations. Secondly, despite the cap on the regularity of the solution, convergence rates faster than O((h/p)^{3/2}) in the H^{1} -norm are achievable if the mesh aligns with the regions in the solution where the loss of regularity occurs. In our context, these regions are where the pointwise constraints transition from being active to inactive. These are not known beforehand. However, one may develop estimators to locate these regions and, particularly in the case of gradient-type constraints, the location of the transitions may sometimes be inferred from the problem data. In Section 7.1 and Section 7.3 we present two examples where we obtain convergence rates faster than 3/2 in the regimes of h and p we consider. Note that a discretization with degree p=1 will only ever converge at a rate of O(h) . Aside from solver speed and convergence rates, high-order discretizations often offer other benefits. They minimize numerical artefacts in fluid dynamics and elasticity [ 54 ] , e.g. in two dimensions, locking in linear elasticity does not occur if p\geq 4 [ 2 ] . As pointwise constraints naturally occur in models for such settings (e.g. the topology optimization of linear elasticity [ 20 , 74 ] and fluids [ 23 , 77 , 71 ] ) then utilizing a solver that is then confined to the lowest-order (continuous) FEM discretization is limiting. High-order methods are also amenable to parallelization making them suitable for modern computing architectures cf. [ 60 , 6 ] . The proximal Galerkin (pG) algorithm arises after a Galerkin discretization of LVPP

Read the complete text