betaFeedback

WorksMathematics

A unified variational framework for augmented Lagrangian preconditioning of saddle point systems: applications to mixed-dimensional and fictitious domain methods

Abstract

We present a general framework to derive augmented Lagrangian preconditioners for saddle point systems arising from mixed finite element discretizations. Our approach is based on augmenting the variational formulation at the continuous level prior to discretization, providing a unified strategy for designing efficient preconditioners that are robust under mesh refinement for a broad class of problems leading to symmetric saddle point systems. The robustness of the proposed preconditioners is established through a detailed spectral analysis. This framework is applied to different model problems, focusing on mixed-dimensional and fictitious domain formulations involving Lagrange multipliers, with some configurations featuring large coefficient jumps. Extensive numerical experiments on different test cases and geometries are presented, validating the effectiveness and robustness of our preconditioners when used in conjunction with flexible GMRES.

Introduction

The mathematical modeling of many physical and engineering problems leads to systems of partial differential equations subject to constraints. A classical approach to the treatment of such constraints consists in introducing Lagrange multipliers, which enforce the constraints in a weak sense within the variational formulation. After discretization with inf-sup stable elements, this procedure gives rise to algebraic saddle point systems of the form

\begin{pmatrix} A & C^{T} \\ C & 0 \end{pmatrix} \begin{pmatrix} u \\ \lambda\end{pmatrix} = \begin{pmatrix} f \\ g \end{pmatrix}, \tag*{(1)}\end{pmatrix}

where CC is the discretization of the constraint operator, and λ\lambda denotes the vector of coefficients associated with the Lagrange multiplier. Besides enforcing the constraints, the multiplier often has a direct physical interpretation and its computation is therefore of independent interest.

Examples of fields where these large-scale saddle point problems naturally arise include computational fluid dynamics, constrained optimization, contact mechanics, optimal control, and many others. In recent years, mixed-dimensional models, in which the constraint operator CC couples problems posed on domains of different dimensionality, have gained increasing attention [29, 18, 19], as have fictitious domain methods, which give rise to a particularly challenging and relevant class of saddle

Funding: MF and LH acknowledge support of the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (call HORIZON-EUROHPC-JU-2023-COE-03, grant agreement No. 101172493 ”dealii-X”). The authors thank the Barcelona Supercomputing Center for the computational resources made available through the EuroHPC project EHPC-DEV-2026D02-275. The authors are members of Gruppo Nazionale per il Calcolo Scientifico (GNCS), Istituto Nazionale di Alta Matematica (INdAM). point problems [24, 15, 16]. Rather than constructing a body-fitted mesh conforming to a geometrically complex or evolving physical domain, these methods embed the geometry of interest into a simpler background domain that can be meshed independently, often by means of a structured grid. The interaction between the physical and background domains is then enforced weakly through a Lagrange multiplier field, resulting in a saddle point formulation. Depending on the support of the multiplier, one distinguishes between distributed Lagrange multiplier (DLM) formulations, where the constraint is imposed through volumetric integrals, and boundary Lagrange multiplier (BLM) formulations, where the multiplier is defined only on the lower-dimensional interface between the background and immersed domains. Fictitious domain methods based on distributed Lagrange multipliers have been successfully employed for elliptic interface problems [3, 16, 1] as a preliminary step to study fluid-structure interaction problems [15]. The resulting algebraic systems exhibit an intricate structure. In particular, the use of independent grids for the physical and background domains requires the assembly of coupling operators that encode interactions between basis functions supported on non-matching and possibly overlapping meshes [14, 13]. As a consequence, the off-diagonal block CC in (1) couples discrete spaces defined on different meshes, leading to saddle point systems whose analysis and implementation are considerably more challenging than in standard boundary-fitted settings.

We cast all the problems discussed above into the following abstract framework, which we borrow from [17]. For a Hilbert space XX, we denote by X′X^{\prime} its dual and by ⟨⋅,⋅⟩X×X′\langle\cdot,\cdot\rangle_{X\times X^{\prime}} the duality pairing, where the subscript indicates the spaces to which the first and second arguments belong. We denote by (⋅,⋅)X(\cdot,\cdot)_X the inner product on XX. Let VV, Λ\Lambda, and HH be real Hilbert spaces such that

Λ⊆H≡H′⊆Λ′\Lambda\subseteq H \equiv H^{\prime} \subseteq\Lambda^{\prime}

is a Gelfand triple, with dense and continuous embeddings, where HH is identified with its dual. This structure allows us to identify the duality pairing with the inner product of HH whenever the second argument belongs to HH, i.e., ⟨w,μ⟩Λ×Λ′=(w,μ)H\langle w,\mu\rangle_{\Lambda\times\Lambda^{\prime}}=(w,\mu)_H for all w∈Λw\in\Lambda and μ∈H\mu\in H.

Let a0:V×V→Ra_0: V\times V\to\mathbb{R} be a continuous bilinear form and L:V→ΛL: V\to\Lambda a continuous linear operator. We consider the following classical variational formulation: for f∈V′f\in V^{\prime} and g∈Λg\in\Lambda, find (u,λ)∈V×Λ′(u,\lambda)\in V\times\Lambda^{\prime} such that

a0(u,v)+⟨Lv,λ⟩Λ×Λ′=⟨f,v⟩V′×V∀v∈V,⟨Lu,μ⟩Λ×Λ′=⟨g,μ⟩Λ×Λ′∀μ∈Λ′.(2)\begin{aligned} a_0(u,v)+\langle Lv,\lambda\rangle_{\Lambda\times\Lambda^{\prime}}&=\langle f,v\rangle_{V^{\prime}\times V} &&\forall v\in V,\\ \langle Lu,\mu\rangle_{\Lambda\times\Lambda^{\prime}}&=\langle g,\mu\rangle_{\Lambda\times\Lambda^{\prime}} &&\forall\mu\in\Lambda^{\prime}. \tag*{(2)} \end{aligned}

It is well known that Problem (2) is well-posed if a0a_0 is coercive on the kernel K={v∈V:Lv=0}K=\{v\in V:Lv=0\} and LL is surjective [12].

The finite element approximation with Vh⊂VV_h\subset V and Λh⊂H\Lambda_h\subset H yields the discrete problem4: find (uh,λh)∈Vh×Λh(u_h,\lambda_h)\in V_h\times\Lambda_h such that

a0(uh,vh)+⟨Lvh,λh⟩Λ×Λ′=⟨f,vh⟩V′×V∀vh∈Vh,⟨Luh,μh⟩Λ×Λ′=⟨g,μh⟩Λ×Λ′∀μh∈Λh.(3)\begin{aligned} a_0(u_h,v_h)+\langle Lv_h,\lambda_h\rangle_{\Lambda\times\Lambda^{\prime}}&=\langle f,v_h\rangle_{V^{\prime}\times V} &&\forall v_h\in V_h,\\ \langle Lu_h,\mu_h\rangle_{\Lambda\times\Lambda^{\prime}}&=\langle g,\mu_h\rangle_{\Lambda\times\Lambda^{\prime}} &&\forall\mu_h\in\Lambda_h. \tag*{(3)} \end{aligned}

Classical results on saddle point problems [12] show that problem (3) is uniquely solvable if there exist mesh-independent positive constants αh\alpha_h and βh\beta_h such that

a0(vh,vh)≥αh∥vh∥V2∀vh∈Kh,(4)a_0(v_h,v_h)\geq\alpha_h\lVert v_h\rVert_V^2 \qquad\forall v_h\in K_h, \tag*{(4)}
inf⁡μh∈Λhsup⁡vh∈Vh⟨Lvh,μh⟩Λ×Λ′∥vh∥V∥μh∥Λ′=inf⁡μh∈Λhsup⁡vh∈Vh(Lvh,μh)H∥vh∥V∥μh∥Λ′≥βh,(5)\inf_{\mu_h\in\Lambda_h}\sup_{v_h\in V_h}\frac{\langle Lv_h,\mu_h\rangle_{\Lambda\times\Lambda'}}{\lVert v_h\rVert_V\lVert\mu_h\rVert_{\Lambda'}}=\inf_{\mu_h\in\Lambda_h}\sup_{v_h\in V_h}\frac{(Lv_h,\mu_h)_H}{\lVert v_h\rVert_V\lVert\mu_h\rVert_{\Lambda'}}\ge\beta_h, \tag*{(5)}

where Kh={vh∈Vh:(Lvh,μh)H=0 ∀μh∈Λh}K_h=\{v_h\in V_h:(Lv_h,\mu_h)_H=0\ \forall\mu_h\in\Lambda_h\}.

Motivation and main contributions

Owing to the ubiquitous nature of large and sparse saddle point systems whose conditioning may deteriorate under mesh refinement and with variations in the physical and model parameters, a large variety of iterative solvers and preconditioning techniques have been developed in the literature [35, 20, 9, 32]. Among them, augmented Lagrangian (AL) techniques have emerged as a particularly powerful strategy. The basic idea consists in replacing the original system (1.1) with the equivalent augmented formulation

\begin{pmatrix} A+\gamma C^{T}W^{-1}C & C^{T}\\ C & 0 \end{pmatrix} \begin{pmatrix} u\\ \lambda \end{pmatrix} = \begin{pmatrix} f+\gamma C^{T}W^{-1}g\\ g \end{pmatrix}, \tag*{(6)}\end{pmatrix}

where WW is a suitable symmetric positive definite (SPD) matrix and γ>0\gamma>0 is a positive real number. An effective block triangular preconditioner is

Pγ=(A+γCTW−1CCT0−1γW).(7)\mathcal{P}_{\gamma}= \begin{pmatrix} A+\gamma C^{T}W^{-1}C & C^{T}\\ 0 & -\frac{1}{\gamma}W \end{pmatrix}. \tag*{(7)}

With an appropriate choice of the matrix WW, increasing γ\gamma clusters the spectrum and often leads to convergence rates that are independent of the mesh size and remarkably robust with respect to the physical parameters. Successful applications include linearizations of the stationary Navier–Stokes equations [10, 22], as well as multiphysics problems such as the coupled Stokes-Darcy problem [5] and magnetohydrodynamic problems [30]. Even if the ideal preconditioner is replaced in practice by an inexact version, in which the diagonal blocks (or the action of their inverses) are replaced by suitable approximations, the large kernel of CTW−1CC^{T}W^{-1}C makes the augmented block difficult to invert efficiently. Achieving optimal complexity therefore typically requires specialized, problem-dependent multigrid methods [10, 22, 38], often based on the ideas introduced in [36]. Modified AL variants have also been proposed [11], while more general algebraic strategies were tackled in [6]. In the fictitious domain setting, we recently investigated AL preconditioners in [8, 7]; related ideas were subsequently extended to mixed-dimensional beam-solid coupling in [23]. In these works, the augmentation is introduced algebraically by modifying the discrete system as in (1.6). Although effective, this approach may require the explicit formation of CTW−1CC^{T}W^{-1}C, leading to a substantial computational cost and reduced sparsity of the resulting global system.

Motivated by these limitations and following the abstract theory of augmented Lagrangian formulations for mixed finite element schemes developed in [17], we directly augment the formulation (1.2) with γ(Lu−g,Lv)Λ\gamma(Lu-g,Lv)_{\Lambda}, associated with the constraint Lu=gLu=g in Λ\Lambda. Moreover, exploiting the continuous inclusion Λ⊆H\Lambda\subseteq H and incorporating an appropriate mesh-dependent scaling, we use γh−α(Luh−g,Lvh)H\gamma h^{-\alpha}(Lu_h-g,Lv_h)_H as the augmentation term in the discrete formulation, employing the more practical inner product on HH rather than that on Λ\Lambda. The resulting augmented bilinear form, a0(uh,vh)+γh−α(Luh,Lvh)Ha_0(u_h,v_h)+\gamma h^{-\alpha}(Lu_h,Lv_h)_H, can be directly assembled and avoids the explicit construction of the triple matrix product CTW−1CC^{T}W^{-1}C, preserving locality of assembly, reducing memory requirements, and facilitating the design of efficient solvers for the augmented subproblems.

This approach allows us to derive augmented formulations whose associated preconditioners admit a unified spectral analysis under the assumption that the bilinear form a0(⋅,⋅)a_0(\cdot,\cdot) is symmetric and positive semidefinite. We identify general conditions on the augmentation operator WW ensuring favorable spectral properties of the preconditioned systems. In particular, WW is the matrix representation of the scaled Riesz map associated with a suitable inner product on the multiplier space.

However, unlike algebraic augmentation, modifying the variational formulation may alter the discrete solution. In some cases, as for Grad–Div stabilization with Taylor–Hood elements [26, 33], the resulting error can be shown to vanish as the mesh is refined. In such cases, the continuous augmentation asymptotically retains the properties of the algebraic augmentation while providing a more favorable framework for preconditioning. In other cases, however, the presence of a power of the mesh size in the formulation may make this error non-trivial to control. A possible alternative is to use the projected counterpart (πH(Luh−g),πHLvh)H(\pi_H(Lu_h-g),\pi_HLv_h)_H rather than (Luh−g,Lvh)H(Lu_h-g,Lv_h)_H, where πH\pi_H is the HH-orthogonal projector onto Λh\Lambda_h, together with piecewise-constant multiplier spaces, when feasible [10, 22]. Indeed, we prove that the projected realization coincides with the algebraic augmentation, and therefore does not alter the discrete solution. Moreover, when piecewise-constant multiplier spaces are used, the projected term can be implemented efficiently, avoiding the computational cost of explicitly forming CTW−1CC^T W^{-1} C. A concrete example is presented in § 6.3.

We apply the resulting framework to the imposition of Dirichlet boundary conditions through Lagrange multipliers [4], BLM and DLM fictitious domain formulations [7, 8], and immersed linear elasticity, thereby unifying and extending our earlier AL preconditioners developed for fictitious domain methods [8, 7] within a common variational framework amenable to a much wider class of saddle point problems.

Outline

The remainder of the paper is organized as follows. § 2 introduces the notation, while § 3 presents the augmented formulation. The relationship between continuous and algebraic augmentation is discussed in § 4, followed by the development and spectral analysis of the AL preconditioners in § 5. § 6 reports numerical experiments aimed at validating the theoretical results and assessing the practical performance of the proposed preconditioning strategy. Finally, § 7 summarizes the main findings and outlines directions for future research.

Notation

Given an open and bounded domain DD, we denote by L2(D)L^2(D) the space of square-integrable functions on DD, endowed with the norm ∥⋅∥0,D\|\cdot\|_{0,D} induced by the inner product (⋅,⋅)D(\cdot,\cdot)_D. Sobolev spaces are denoted by Ws,p(D)W^{s,p}(D), where s∈Rs \in\mathbb{R} refers to the differentiability index and p∈[1,∞]p \in[1,\infty] is the integrability exponent. In the case p=2p=2, we use the notation Hs(D)=Ws,2(D)H^s(D)=W^{s,2}(D), with associated norm ∥⋅∥s,D\|\cdot\|_{s,D} and seminorm ∣⋅∣s,D|\cdot|_{s,D}. Dual spaces and duality pairings are denoted as in § 1. The spectrum of a matrix is indicated by Spec⁡(⋅)\operatorname{Spec}(\cdot), while vectors appear in boldface, e.g., v\mathbf{v}. We will use the letter λ\lambda for the Lagrange multiplier in the weak formulation. Finally, the letter cc will refer to a constant independent of the discretization parameters, possibly taking different values from one formula to another.

Augmented Lagrangian formulation

We start by recalling the abstract framework developed by Boffi & Lovadina in [17] for augmented Lagrangian formulations of mixed finite element schemes. Adding the term γ(Lu−g,Lv)Λ\gamma(Lu-g,Lv)_\Lambda, with γ>0\gamma>0, to the first equation of (2) does not change the continuous solution, since $Lu=g. in Λ\Lambda. The corresponding discrete scheme seeks (uh,λh)∈Vh×Λh(u_h,\lambda_h) \in V_h \times\Lambda_h such that

a0(uh,vh)+γ(Luh−g,Lvh)Λ+⟨Lvh,λh⟩Λ×Λ′=⟨f,vh⟩V′×V∀vh∈Vh,⟨Luh,μh⟩Λ×Λ′=⟨g,μh⟩Λ×Λ′∀μh∈Λh.(8)\begin{aligned} a_0(u_h,v_h)+\gamma(Lu_h-g,Lv_h)_{\Lambda}+\langle Lv_h,\lambda_h\rangle_{\Lambda\times\Lambda'}&=\langle f,v_h\rangle_{V'\times V} &&\forall v_h\in V_h,\\ \langle Lu_h,\mu_h\rangle_{\Lambda\times\Lambda'}&=\langle g,\mu_h\rangle_{\Lambda\times\Lambda'} &&\forall\mu_h\in\Lambda_h. \tag*{(8)} \end{aligned}

This is the natural augmentation, since the constraint residual Luh−gLu_h-g is measured in the norm of the space in which LL takes its values. If a0a_0 is positive semidefinite (as will be assumed throughout), and the assumptions ensuring the well-posedness of the original problem (2) hold, then for every γ>0\gamma>0 it can be shown that the coercivity condition (4) is automatically satisfied for the bilinear form a0(⋅,⋅)+γ(L⋅,L⋅)Λa_0(\cdot,\cdot)+\gamma(L\cdot,L\cdot)_{\Lambda}. Hence, only the discrete inf-sup condition (5) remains to be verified [17 Section 2].

In practice, computing the inner product on Λ\Lambda may be impractical, for instance when Λ=H12(⋅)\Lambda=H^{\frac{1}{2}}(\cdot). We therefore consider instead the inner product on HH. This substitution, however, requires an appropriate mesh-dependent scaling.

Following the second augmented formulation of [17 Section 3], we use γh−α(Luh−g,Lvh)H\gamma h^{-\alpha}(Lu_h-g,Lv_h)_H with α≥0\alpha\geq0 left unspecified. The spectral analysis in § 5 will determine the choice of α\alpha. The resulting scheme seeks (uh,λh)∈Vh×Λh(u_h,\lambda_h)\in V_h\times\Lambda_h, for γ>0\gamma>0, such that

a0(uh,vh)+γh−α(Luh−g,Lvh)H+⟨Lvh,λh⟩Λ×Λ′=⟨f,vh⟩V′×V∀vh∈Vh,⟨Luh,μh⟩Λ×Λ′=⟨g,μh⟩Λ×Λ′∀μh∈Λh.(9)\begin{aligned} a_0(u_h,v_h)+\gamma h^{-\alpha}(Lu_h-g,Lv_h)_H+\langle Lv_h,\lambda_h\rangle_{\Lambda\times\Lambda'}&=\langle f,v_h\rangle_{V'\times V} &&\forall v_h\in V_h,\\ \langle Lu_h,\mu_h\rangle_{\Lambda\times\Lambda'}&=\langle g,\mu_h\rangle_{\Lambda\times\Lambda'} &&\forall\mu_h\in\Lambda_h. \tag*{(9)} \end{aligned}

Throughout this section, we only assume a0a_0 to be positive semidefinite on VV, that L:V→ΛL:V\to\Lambda is continuous and surjective, and that the discrete inf-sup condition (5) holds.

Since the HH-norm used in the augmentation is weaker than the Λ\Lambda-norm, well-posedness of (9) additionally requires the following coercivity condition [17]: there exist constants ξ,δ>0\xi,\delta>0, independent of hh, such that

a0(v,v)+ξ∥Lv∥H2≥δ∥v∥V2∀v∈V.(10)a_0(v,v)+\xi\lVert Lv\rVert_H^2\geq\delta\lVert v\rVert_V^2\qquad\forall v\in V. \tag*{(10)}

This condition is application-dependent and must be verified on a case-by-case basis.

Algebraic problem

3.1. Algebraic problem. Given basis functions {ϕi}i=1n\{\phi_i\}_{i=1}^n and {ψk}k=1m\{\psi_k\}_{k=1}^m such that Vh:=span⁡{ϕi}i=1nV_h:=\operatorname{span}\{\phi_i\}_{i=1}^n and Λh:=span⁡{ψk}k=1m\Lambda_h:=\operatorname{span}\{\psi_k\}_{k=1}^m, we have that Problem (3.2) can be written in matrix form as the following algebraic problem with unknowns u\mathbf{u} and λ\boldsymbol{\lambda}:

\begin{pmatrix} \widetilde{A} & C^T\\ C & 0 \end{pmatrix} \begin{pmatrix} \mathbf{u}\\ \boldsymbol{\lambda} \end{pmatrix} = \begin{pmatrix} \widetilde{\mathbf{f}}\\ \mathbf{g} \end{pmatrix}. \tag*{(11)}\end{pmatrix}

where

A~ij:=a~(ϕj,ϕi)i,j=1,…,nCki:=(Lϕi,ψk)Hi=1,…,nk=1,…,mf~i:=⟨f,ϕi⟩V′×V+γh−α(g,Lϕi)Hi=1,…,ngk:=⟨g,ψk⟩Λ×Λ′k=1,…,m,\begin{aligned} \widetilde{A}_{ij}&:=\widetilde{a}(\phi_j,\phi_i) && i,j=1,\ldots,n\\ C_{ki}&:=(L\phi_i,\psi_k)_H && i=1,\ldots,n\quad k=1,\ldots,m\\ \widetilde{f}_i&:=\langle f,\phi_i\rangle_{V'\times V}+\gamma h^{-\alpha}(g,L\phi_i)_H && i=1,\ldots,n\\ g_k&:=\langle g,\psi_k\rangle_{\Lambda\times\Lambda'} && k=1,\ldots,m, \end{aligned}

and a~(ϕi,ϕj):=a0(ϕi,ϕj)+γh−α(Lϕi,Lϕj)H\widetilde{a}(\phi_i,\phi_j):=a_0(\phi_i,\phi_j)+\gamma h^{-\alpha}(L\phi_i,L\phi_j)_H denotes the augmented bilinear form.

In the next section, we will take a closer look at the augmented term (Luh,Lvh)H(Lu_h,Lv_h)_H, describing its finite dimensional representation in terms of known matrices.

Connection between continuous and algebraic augmentation

In this section, we show that the augmented term (Luh,Lvh)H(L u_h,L v_h)_H appearing in the augmented bilinear form a~(uh,vh)=a0(uh,vh)+γh−α(Luh,Lvh)H\widetilde{a}(u_h,v_h)=a_0(u_h,v_h)+\gamma h^{-\alpha}(L u_h,L v_h)_H, shares the same algebraic properties as the triple matrix product CTM−1CC^T M^{-1}C, where MM is the mass matrix defined on the multiplier space. This observation generalizes the results of [26], where the specific case of Grad-Div stabilization for the Oseen problem is considered.

This naturally raises the question of whether considering the augmented formulation in (9) is equivalent to augmenting the discrete saddle point system as in (6) with W=MW=M. As already observed in [26] for Grad-Div stabilization, the two approaches are generally not equivalent. Nevertheless, we will show that the term (Luh,Lvh)H(L u_h,L v_h)_H admits a decomposition into the sum of an algebraic term and a projection-type stabilization term, where the former coincides exactly with the entries of CTW−1CC^T W^{-1}C when W=MW=M.

We emphasize that, also in this section, we only assume a0(⋅,⋅)a_0(\cdot,\cdot) to be positive semidefinite, but not necessarily symmetric.

Let πH:H→Λh\pi_H:H\to\Lambda_h be the HH-orthogonal projector, i.e.

(w−πHw,χh)H=0∀χh∈Λh.(12)(w-\pi_Hw,\chi_h)_H=0 \quad\forall\chi_h\in\Lambda_h. \tag*{(12)}

For uh,vh∈Vhu_h,v_h\in V_h, the term (Luh−g,Lvh)H(L u_h-g,L v_h)_H can be split into the following sum:

(Luh−g,Lvh)H=(πH(Luh−g),Lvh)H+(κ(Luh−g),Lvh)H,(13)(L u_h-g,L v_h)_H=(\pi_H(L u_h-g),L v_h)_H+(\kappa(L u_h-g),L v_h)_H, \tag*{(13)}

where κ:=I−πH\kappa:=I-\pi_H is the so-called fluctuation operator. By the projection property of πH\pi_H, we have:

(Luh−g,Lvh)H=(πH(Luh−g),πH(Lvh))H+(κ(Luh−g),κ(Lvh))H.(14)(L u_h-g,L v_h)_H=(\pi_H(L u_h-g),\pi_H(L v_h))_H+(\kappa(L u_h-g),\kappa(L v_h))_H. \tag*{(14)}

Following [26], we call the first summand algebraic term and the second one stabilizing term. The following lemma shows that, after moving the term (g,Lvh)H(g,L v_h)_H to the right-hand side of the first equation in (9), the contribution (πH(Luh),πH(Lvh))H(\pi_H(L u_h),\pi_H(L v_h))_H can be represented as a product of known and computable matrices.

Lemma 4.1. Let {ϕi}i=1n\{\phi_i\}_{i=1}^n be a basis of VhV_h and {ψk}k=1m\{\psi_k\}_{k=1}^m a basis of Λh\Lambda_h. Let CC and MM be the following matrices, defined as:

Cki:=(Lϕi,ψk)H,Mkl:=(ψk,ψl)H.C_{ki}:=(L\phi_i,\psi_k)_H,\qquad M_{kl}:=(\psi_k,\psi_l)_H.

Then,

(πH(Lϕi),πH(Lϕj))H=(CTM−1C)ij.(\pi_H(L\phi_i),\pi_H(L\phi_j))_H=(C^T M^{-1}C)_{ij}.

Proof. Let whiw_{h i} be the orthogonal projection of LϕiL\phi_i onto Λh\Lambda_h with respect to the inner product (⋅,⋅)H(\cdot,\cdot)_H, that is whi:=πH(Lϕi)∈Λhw_{h i}:=\pi_H(L\phi_i)\in\Lambda_h. Since {ψk}k=1m\{\psi_k\}_{k=1}^m is a basis of Λh\Lambda_h, we may expand whiw_{h i} as whi=∑k=1mmk(i)ψkw_{h i}=\sum_{k=1}^m m_k^{(i)}\psi_k, where m(i)=(m1(i),…,mm(i))∈Rm\mathbf{m}^{(i)}=(m_1^{(i)},\ldots,m_m^{(i)})\in\mathbb{R}^m is the corresponding coefficient column vector. By definition of orthogonal projection,

(whi,χh)H=(Lϕi,χh)H∀χh∈Λh.(w_{h i},\chi_h)_H=(L\phi_i,\chi_h)_H \quad\forall\chi_h\in\Lambda_h.

Therefore, for each basis function ψl\psi_l we obtain

(whi,ψl)H=(Lϕi,ψl)H.(15)(w_{h i},\psi_l)_H=(L\phi_i,\psi_l)_H. \tag*{(15)}

Substituting the expansion of whiw_{h i} yields ∑k=1mmk(i)(ψk,ψl)H=(Lϕi,ψl)H\sum_{k=1}^m m_k^{(i)}(\psi_k,\psi_l)_H=(L\phi_i,\psi_l)_H. Moreover, using the definition of matrices CC and MM and letting ei∈Rne_i\in\mathbb{R}^n denote the ii-th canonical basis vector, the system (15) can be written in matrix form as Mm(i)=CeiM\mathbf{m}^{(i)}=C\mathbf{e}_i. We now compute the (i,j)(i,j)-entry of CTM−1CC^{T}M^{-1}C:

eiTCTM−1Cej=(M−1Cei)TM(M−1Cej)=(m(i))TMm(j)=(whi,whj)H,\mathbf{e}_i^{T}C^{T}M^{-1}C\mathbf{e}_j=(M^{-1}C\mathbf{e}_i)^{T}M(M^{-1}C\mathbf{e}_j)=(\mathbf{m}^{(i)})^{T}M\mathbf{m}^{(j)}=(\mathbf{w}_{h_i},\mathbf{w}_{h_j})_H,

where the last equality follows from expanding both whi\mathbf{w}_{h_i} and whj\mathbf{w}_{h_j} in the basis {ψk}k=1m\{\psi_k\}_{k=1}^m. Finally, recalling that whi=πH(Lϕi)\mathbf{w}_{h_i}=\pi_H(L\phi_i), we conclude that

(CTM−1C)ij=(πH(Lϕi),πH(Lϕj))H.(C^{T}M^{-1}C)_{ij}=(\pi_H(L\phi_i),\pi_H(L\phi_j))_H.

Lemma 4.2. Let (uh,λh)(u_h,\lambda_h) be a solution of the augmented Lagrangian formulation (9), and let (u,λ)(u,\lambda) solve the original problem (2). We define the augmentation residual, namely, the term by which (9) differs from (3), as

r(vh):=γh−α(Luh−g,Lvh)H,∀vh∈Vh.r(v_h):=\gamma h^{-\alpha}(Lu_h-g,Lv_h)_H,\qquad\forall v_h\in V_h.

Then, the following bound holds:

∣r(vh)∣≤γh−α∥κ(L(uh−u))∥H∥κ(Lvh)∥H.(16)|r(v_h)|\leq\gamma h^{-\alpha}\|\kappa(L(u_h-u))\|_H\|\kappa(Lv_h)\|_H. \tag*{(16)}

In particular, if L(Vh)⊂ΛhL(V_h)\subset\Lambda_h and g∈Λhg\in\Lambda_h, then r(vh)≡0r(v_h)\equiv0.

Proof. The second equation of the augmented problem (9) gives

(Luh−g,μh)H=0,∀μh∈Λh,(Lu_h-g,\mu_h)_H=0,\qquad\forall\mu_h\in\Lambda_h,

since (Luh−g)∈Λ⊆H(Lu_h-g)\in\Lambda\subseteq H and μh∈Λh⊂H\mu_h\in\Lambda_h\subset H, so that the duality pairing between Λ\Lambda and Λ′\Lambda' can be identified with the scalar product in HH. Using the definition of HH-orthogonal projection onto Λh\Lambda_h (12), the relation above implies πH(Luh−g)=0\pi_H(Lu_h-g)=0. Then, using the decomposition in (14), we obtain

r(vh)=γh−α(κ(Luh−g),κ(Lvh))H,r(v_h)=\gamma h^{-\alpha}(\kappa(Lu_h-g),\kappa(Lv_h))_H,

which contains the stabilizing term introduced in (14). Finally, using Cauchy-Schwarz inequality and the fact that Luh−g=L(uh−u)Lu_h-g=L(u_h-u) we obtain the desired bound

∣r(vh)∣=γh−α∣(κ(Luh−g),κ(Lvh))H∣≤γh−α∥κ(Luh−g)∥H∥κ(Lvh)∥H=γh−α∥κ(L(uh−u))∥H∥κ(Lvh)∥H.\begin{aligned} |r(v_h)|&=\gamma h^{-\alpha}|(\kappa(Lu_h-g),\kappa(Lv_h))_H|\\ &\leq\gamma h^{-\alpha}\|\kappa(Lu_h-g)\|_H\|\kappa(Lv_h)\|_H=\gamma h^{-\alpha}\|\kappa(L(u_h-u))\|_H\|\kappa(Lv_h)\|_H. \end{aligned}

Remark 4.3. The above bound is clearly problem-dependent. For instance, in the context of Grad-Div stabilization, where LL is the divergence operator and g=0g=0, it was shown in [26] that, for Taylor–Hood elements, ∥κ(div⁡(uh−u))∥0,Ω→0\|\kappa(\operatorname{div}(u_h-u))\|_{0,\Omega}\to0 as h→0h\to0. Whenever this occurs, we can conclude that the continuous augmentation asymptotically retains the same properties as the algebraic one, while avoiding the computational drawbacks associated with the explicit formation of CTM−1CC^{T}M^{-1}C. In § 5.2, we will show another illustrative example for which the stabilizing term can be proved to vanish as the mesh is refined. A further possibility is to choose, if feasible, discrete spaces satisfying L(Vh)⊂ΛhL(V_h)\subset\Lambda_h. This is the case for the classic Stokes problem discretized with divergence-free pairs, such as Scott–Vogelius elements.

In the following section, we introduce the proposed AL preconditioner and provide a detailed spectral analysis that accounts for the effects of the stabilizing term arising from the continuous augmentation.

We define the symmetric positive semidefinite matrix EE associated with the bilinear form (κ(Luh),κ(Lvh))H(\kappa(Lu_h),\kappa(Lv_h))_H, i.e.

vTEv=∥κ(Lvh)∥H2,∀vh∈Vh.(17)\mathbf{v}^{T}E\mathbf{v}=\|\kappa(Lv_h)\|_{H}^{2},\qquad\forall v_h\in V_h. \tag*{(17)}

Preconditioning and spectral analysis

Using the decomposition (14) and Lemma 4.1, the matrix A~\widetilde{A} in (11) can be decomposed as A~=A^+γh−αCTM−1C\widetilde{A}=\widehat{A}+\gamma h^{-\alpha}C^{T}M^{-1}C, where A^:=A+γh−αE\widehat{A}:=A+\gamma h^{-\alpha}E and EE is the matrix in (17). We denote the matrix in system (11) by

A~γ=(A~CTC0).(18)\widetilde{\mathcal{A}}_{\gamma}= \begin{pmatrix} \widetilde{A} & C^{T}\\ C & 0 \end{pmatrix}. \tag*{(18)}

By analogy with the algebraic augmentation, it is natural to consider a corresponding preconditioner of the form

P~γ=(A^CT0−1γhαM).(19)\widetilde{\mathcal{P}}_{\gamma}= \begin{pmatrix} \widehat{A} & C^{T}\\ 0 & -\frac{1}{\gamma}h^{\alpha}M \end{pmatrix}. \tag*{(19)}

We derive lower and upper bounds for the eigenvalues of the preconditioned matrix and then investigate the behavior of the smallest eigenvalue as the mesh is refined.

While eigenvalue information alone is generally insufficient to fully characterize the convergence of non-symmetric Krylov subspace methods, especially when the problem is far from normal [25], rapid convergence is commonly observed when the spectrum is real and positive and lies within a bounded interval away from zero. The spectral analysis below is performed for the ideal preconditioner (19). However, we anticipate using a more practical approximation thereof in the numerical experiments.

From now on, we will assume a0(⋅,⋅)a_0(\cdot,\cdot) to be not only positive semidefinite, but also symmetric, and CC to have full row rank, consistently with the inf-sup condition (5).

Note that, in principle, the natural choice of WW in (6) should be consistent with the norm on Λ\Lambda used in the augmented formulation (8). However, since we move from the norm on Λ\Lambda to that on HH in (9), a mesh-dependent scaling factor arises in the choice of this matrix. To emphasize this correspondence, we set W~:=hαM\widetilde{W}:=h^{\alpha}M and rewrite the matrix in (18) and the preconditioner in (19) accordingly.

Theorem 5.1. Assume that A~γ\widetilde{\mathcal{A}}_{\gamma} and P~γ\widetilde{\mathcal{P}}_{\gamma} are defined by the matrices in Equations (18) and (19), respectively. The eigenvalues of the preconditioned matrix P~γ−1A~γ\widetilde{\mathcal{P}}_{\gamma}^{-1}\widetilde{\mathcal{A}}_{\gamma} are all real and positive. It holds

Spec⁡(P~γ−1A~γ)⊆[η,1],\operatorname{Spec}\left(\widetilde{\mathcal{P}}_{\gamma}^{-1}\widetilde{\mathcal{A}}_{\gamma}\right)\subseteq[\eta,1],

where

η:=min⁡0≠v∈SγvTCTW~−1CvvTA^v+γvTCTW~−1Cv,\eta:=\min_{0\ne v\in S}\frac{\gamma v^{T}C^{T}\widetilde{W}^{-1}Cv}{v^{T}\widehat{A}v+\gamma v^{T}C^{T}\widetilde{W}^{-1}Cv},

and ν=1\nu=1 is an eigenvalue of algebraic multiplicity at least nn. Here SS denotes the set

S:={v∈Rn∣uTA^v=0 ∀u∈ker⁡(C)}.(20)S:=\left\{v\in\mathbb{R}^{n}\mid u^{T}\widehat{A}v=0\ \forall u\in\ker(C)\right\}. \tag*{(20)}

Proof. Since both the original system matrix A~γ\widetilde{\mathcal{A}}_{\gamma} and the preconditioner are nonsingular, the preconditioned matrix is also nonsingular, and therefore ν=0\nu=0 cannot be an eigenvalue. Let ν≠0\nu\ne0 be an arbitrary eigenvalue of the preconditioned matrix, with a corresponding eigenvector (x;y)(\mathbf{x};\mathbf{y}). The generalized eigenvalue problem can be stated as:

(A^+γCTW~−1CCTC0)(xy)=ν(A^+γCTW~−1CCT0−1γW~)(xy).\begin{pmatrix} \widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C & C^{T}\\ C & 0 \end{pmatrix} \begin{pmatrix} \mathbf{x}\\ \mathbf{y} \end{pmatrix} = \nu \begin{pmatrix} \widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C & C^{T}\\ 0 & -\frac{1}{\gamma}\widetilde{W} \end{pmatrix} \begin{pmatrix} \mathbf{x}\\ \mathbf{y} \end{pmatrix}.

which can be written explicitly as the following system of equations:

(A^+γCTW~−1C)x+CTy=ν((A^+γCTW~−1C)x+CTy)(21)(\widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C)\mathbf{x}+C^{T}\mathbf{y}=\nu\left((\widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C)\mathbf{x}+C^{T}\mathbf{y}\right) \tag*{(21)}
Cx=−νγW~y.(22)C\mathbf{x}=-\frac{\nu}{\gamma}\widetilde{W}\mathbf{y}. \tag*{(22)}

Notice that x≠0\mathbf{x}\ne0; otherwise, the positive definiteness of W~\widetilde{W} implies y=0\mathbf{y}=0, in contradiction with the fact that (x,y)(\mathbf{x},\mathbf{y}) is an eigenvector. Therefore, we can assume x≠0\mathbf{x}\ne0.

It is evident from Equation (21) that ν=1\nu=1 is an eigenvalue of P~γ−1A~γ\widetilde{P}_{\gamma}^{-1}\widetilde{A}_{\gamma}, with associated eigenvector (x;−γW~−1Cx)(\mathbf{x};-\gamma\widetilde{W}^{-1}C\mathbf{x}). Moreover, when x∈ker⁡(C)\mathbf{x}\in\ker(C), we have (x;0)(\mathbf{x};0) as associated eigenvector.

We now assume ν≠1\nu\ne1. From (21) we derive

(A^+γCTW~−1C)x+CTy=0,(23)(\widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C)\mathbf{x}+C^{T}\mathbf{y}=0, \tag*{(23)}

whereas from (22) we obtain y=−γνW~−1Cx\mathbf{y}=-\frac{\gamma}{\nu}\widetilde{W}^{-1}C\mathbf{x}, which plugged into the previous equation gives

(A^+γCTW~−1C)x−γνCTW~−1Cx=0.(24)(\widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C)\mathbf{x}-\frac{\gamma}{\nu}C^{T}\widetilde{W}^{-1}C\mathbf{x}=0. \tag*{(24)}

Multiplying both sides of (24) by νx∗\nu\mathbf{x}^{*}, we get

νx∗(A^+γCTW~−1C)x−γx∗CTW~−1Cx=0.(25)\nu\mathbf{x}^{*}(\widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C)\mathbf{x}-\gamma\mathbf{x}^{*}C^{T}\widetilde{W}^{-1}C\mathbf{x}=0. \tag*{(25)}

Therefore,

ν=γx∗CTW~−1Cxx∗A^x+γx∗CTW~−1Cx=γx∗CTW~−1Cxx∗Ax+γh−αx∗Ex+γx∗CTW~−1Cx.(26)\nu=\frac{\gamma\mathbf{x}^{*}C^{T}\widetilde{W}^{-1}C\mathbf{x}}{\mathbf{x}^{*}\widehat{A}\mathbf{x}+\gamma\mathbf{x}^{*}C^{T}\widetilde{W}^{-1}C\mathbf{x}}=\frac{\gamma\mathbf{x}^{*}C^{T}\widetilde{W}^{-1}C\mathbf{x}}{\mathbf{x}^{*}A\mathbf{x}+\gamma h^{-\alpha}\mathbf{x}^{*}E\mathbf{x}+\gamma\mathbf{x}^{*}C^{T}\widetilde{W}^{-1}C\mathbf{x}}. \tag*{(26)}

Since CC has full rank, a necessary and sufficient condition for the saddle point matrix A~γ\widetilde{A}_{\gamma} to be nonsingular is ker⁡(A~)∩ker⁡(C)={0}\ker(\widetilde{A})\cap\ker(C)=\{0\}, which implies ker⁡(A^)∩ker⁡(C)={0}\ker(\widehat{A})\cap\ker(C)=\{0\}. Therefore, the augmented matrix A^+γCTW~−1C\widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C is still symmetric positive definite even if AA is SPSD. The positive definiteness of A^+γCTW~−1C\widehat{A}+\gamma C^{T}\widetilde{W}^{-1}C and the positive semidefiniteness of CTW~−1CC^{T}\widetilde{W}^{-1}C imply that all the eigenvalues are positive and real.5 Moreover, note that in this case x\mathbf{x} cannot belong to ker⁡(A^)\ker(\widehat{A}), since ν≠1\nu\ne1, nor to ker⁡(C)\ker(C) since ν≠0\nu\ne0.

From (26), we also deduce that ν<1\nu<1, and that all eigenvalues satisfying (26) cluster towards 1 as γ→+∞\gamma\to+\infty when the augmentation does not contain the term γh−αE\gamma h^{-\alpha}E. In view of Lemmas 4.1 and 4.2, this is precisely the case for algebraic augmentation, for which no stabilizing term is present, consistently with the theory of classical AL-based preconditioners [10].

To conclude, we know that all nonunit eigenvalues of P~γ−1A~γ\widetilde{P}_{\gamma}^{-1}\widetilde{A}_{\gamma} satisfy (25), hence, by the theory of generalized Rayleigh quotients, the smallest positive eigenvalue is characterized by:

η:=min⁡0≠v∈SγvTCTW~−1CvvTA^v+γvTCTW~−1Cv,\eta:=\min_{0\ne\mathbf{v}\in S}\frac{\gamma\mathbf{v}^{T}C^{T}\widetilde{W}^{-1}C\mathbf{v}}{\mathbf{v}^{T}\widehat{A}\mathbf{v}+\gamma\mathbf{v}^{T}C^{T}\widetilde{W}^{-1}C\mathbf{v}},

which concludes the proof.

Remark 5.2. There are particular cases in which the matrix A~γ\widetilde{A}_{\gamma} is actually singular, for example, in the presence of enclosed flows in the Stokes problem, where a0(⋅,⋅)a_0(\cdot,\cdot) is positive definite but the divergence matrix CC is rank deficient by one. However, the presence of a zero eigenvalue does not necessarily hinder the convergence of preconditioned GMRES, provided that the system is consistent [11, 20].

Mesh-independence of the lower bound

The behavior of η\eta upon mesh refinement relies on the algebraic formulation of the inf-sup condition (5). Whenever Λ⊆H\Lambda\subseteq H, we assume that the multiplier space satisfies an inverse estimate of the form

∥μh∥Λ′≥chs∥μh∥H∀μh∈Λh,(27)\lVert\mu_h\rVert_{\Lambda'} \geq ch^s\lVert\mu_h\rVert_H \qquad\forall\mu_h \in\Lambda_h, \tag*{(27)}

where hh is the mesh size of the grid over which the multiplier space is defined. Practical examples of such estimates will be discussed later in Remark 5.5. Note that the case Λ≡H\Lambda\equiv H can be interpreted as the limiting case corresponding to s=0s=0, as no inverse estimate is needed.

Furthermore, let {vi}i=1n\{v_i\}_{i=1}^n and {μk}k=1m\{\mu_k\}_{k=1}^m be the expansion coefficients of vhv_h and μh\mu_h with respect to their bases, and let TT denote the matrix corresponding to the inner product on VV, so that ∥vh∥V2=vTTv\lVert v_h\rVert_V^2=v^T Tv. After exploiting inequality (27), we have the following algebraic interpretation of the discrete inf-sup stability condition (5):

inf⁡0≠μ0≠vsup⁡vTCTμ(vTTv)1/2(μTh2sMμ)1/2≥β~h,(28)\inf_{\substack{0\ne\mu\\0\ne v}}\sup\frac{v^T C^T\mu}{(v^T Tv)^{1/2}(\mu^T h^{2s}M\mu)^{1/2}} \geq\widetilde{\beta}_h, \tag*{(28)}

where the realization of the dual norm has been replaced by the matrix h2sMh^{2s}M, which represents the mesh-dependent norm h2s∥⋅∥H2h^{2s}\lVert\cdot\rVert_H^2. It is well known that the constant β~h\widetilde{\beta}_h can be identified through a generalized eigenvalue problem (see, e.g., [31, 12, 20] for details).

Proposition 5.3. Let β~h\widetilde{\beta}_h be the inf-sup constant in (28), and let νmin⁡\nu_{\min} be the smallest positive generalized eigenvalue of

CT(h2sM)−1Cv=νTv.C^T(h^{2s}M)^{-1}Cv=\nu Tv.

Then,

β~h2=νmin⁡=min⁡0≠v∈RvTCT(h2sM)−1CvvTTv,\widetilde{\beta}_h^2=\nu_{\min}=\min_{0\ne v\in\mathcal{R}}\frac{v^T C^T(h^{2s}M)^{-1}Cv}{v^T Tv},

where R\mathcal{R} denotes the set R:={v∈Rn∣uTTv=0 ∀ u∈ker⁡(C)}\mathcal{R}:=\{v\in\mathbb{R}^n\mid u^T Tv=0\ \forall\,u\in\ker(C)\}.

In the next theorem, we show that requiring the smallest eigenvalue η\eta to be independent of the mesh size leads to a relation between the exponent α\alpha in the augmented formulation (9) and the exponent ss appearing in inequality (27). In addition, we quantify the influence of the stabilizing term when it is nonzero. To this aim, we define

cκ(v):=h−2svTEvvTTv=h−2s∥κ(Lvh)∥H2∥vh∥V2.(29)c_{\kappa}(v):=\frac{h^{-2s}v^T Ev}{v^T Tv}=\frac{h^{-2s}\lVert\kappa(Lv_h)\rVert_H^2}{\lVert v_h\rVert_V^2}. \tag*{(29)}

Theorem 5.4. Let γ\gamma be a positive constant, and assume that the inf-sup condition (5) holds and that the multiplier space satisfies the inverse estimate (27).

Then, for α=2s\alpha= 2s, the lower bound η\eta for the spectrum of P~γ−1A~γ\widetilde{P}_{\gamma}^{-1}\widetilde{A}_{\gamma} in Theorem 5.1 satisfies

η:=min⁡0≠v∈SγvTCTW~−1CvvTA^v+γvTCTW~−1Cv≥min⁡0≠v∈S11+caγβ~h2+cκ(v⊥)β~h2(30)\eta:= \min_{0 \ne\mathbf{v} \in S} \frac{\gamma\mathbf{v}^{T} C^{T}\widetilde{W}^{-1}C\mathbf{v}}{\mathbf{v}^{T}\widehat{A}\mathbf{v}+\gamma\mathbf{v}^{T}C^{T}\widetilde{W}^{-1}C\mathbf{v}} \ge\min_{0 \ne\mathbf{v} \in S} \frac{1}{1+\frac{c_a}{\gamma\widetilde{\beta}_h^{2}}+\frac{c_{\kappa}(\mathbf{v}_{\perp})}{\widetilde{\beta}_h^{2}}} \tag*{(30)}

where cac_a denotes the continuity constant of a0(⋅,⋅)a_0(\cdot,\cdot) and v⊥\mathbf{v}_{\perp} is the component of v\mathbf{v} that is TT-orthogonal to ker⁡(C)\ker(C). In particular, if cκ(⋅)c_{\kappa}(\cdot) is uniformly bounded in hh, then η\eta is bounded away from 0 as h→0h \to0.

Proof. We first observe that S∩ker⁡(C)={0}S \cap\ker(C) = \{0\}. Indeed, let v∈S∩ker⁡(C)\mathbf{v} \in S \cap\ker(C). Taking u=v\mathbf{u}=\mathbf{v} in the definition of SS in (20), we obtain vTA^v=0\mathbf{v}^{T}\widehat{A}\mathbf{v}=0. Since A^\widehat{A} is symmetric positive semidefinite, it follows that A^v=0\widehat{A}\mathbf{v}=0, that is, v∈ker⁡(A^)\mathbf{v} \in\ker(\widehat{A}). Hence, v∈ker⁡(A^)∩ker⁡(C)={0}\mathbf{v} \in\ker(\widehat{A}) \cap\ker(C)=\{0\}, which proves that S∩ker⁡(C)={0}S \cap\ker(C)=\{0\}.

Now let v∈S\mathbf{v} \in S be nonzero. In order to use the results in Proposition 5.3, we decompose v\mathbf{v} in a TT-orthogonal fashion as

v=v⊥+v0,v0∈ker⁡(C),v⊥TTv0=0,\mathbf{v}=\mathbf{v}_{\perp}+\mathbf{v}_0,\qquad\mathbf{v}_0\in\ker(C),\qquad\mathbf{v}_{\perp}^{T}T\mathbf{v}_0=0,

so that v⊥\mathbf{v}_{\perp} is TT-orthogonal to ker⁡(C)\ker(C) and vTTv=v⊥TTv⊥+v0TTv0\mathbf{v}^{T}T\mathbf{v}=\mathbf{v}_{\perp}^{T}T\mathbf{v}_{\perp}+\mathbf{v}_0^{T}T\mathbf{v}_0. Note that v⊥≠0\mathbf{v}_{\perp}\ne0, otherwise v=v0∈ker⁡(C)\mathbf{v}=\mathbf{v}_0\in\ker(C).

Since W~\widetilde{W} is SPD and v0∈ker⁡(C)\mathbf{v}_0\in\ker(C), the augmented term only sees the component v⊥\mathbf{v}_{\perp}:

CTW~−1Cv=CTW~−1Cv⊥.C^{T}\widetilde{W}^{-1}C\mathbf{v}=C^{T}\widetilde{W}^{-1}C\mathbf{v}_{\perp}.

As v⊥\mathbf{v}_{\perp} is TT-orthogonal to ker⁡(C)\ker(C), it belongs to RR. Therefore, Proposition 5.3 yields

v⊥TCTM−1Cv⊥≥β~h2h2sv⊥TTv⊥.(31)\mathbf{v}_{\perp}^{T}C^{T}M^{-1}C\mathbf{v}_{\perp}\ge\widetilde{\beta}_h^{2}h^{2s}\mathbf{v}_{\perp}^{T}T\mathbf{v}_{\perp}. \tag*{(31)}

Moreover, the defining property of SS gives v0TA^v=0\mathbf{v}_0^{T}\widehat{A}\mathbf{v}=0, whence v0TA^v⊥=−v0TA^v0\mathbf{v}_0^{T}\widehat{A}\mathbf{v}_{\perp}=-\mathbf{v}_0^{T}\widehat{A}\mathbf{v}_0. Using the symmetry and positive semidefiniteness of A^\widehat{A} together with the continuity of a0(⋅,⋅)a_0(\cdot,\cdot), we obtain

vTA^v=v⊥TA^v⊥−v0TA^v0≤v⊥TA^v⊥≤cav⊥TTv⊥+γh−αv⊥TEv⊥,(32)\mathbf{v}^{T}\widehat{A}\mathbf{v}=\mathbf{v}_{\perp}^{T}\widehat{A}\mathbf{v}_{\perp}-\mathbf{v}_0^{T}\widehat{A}\mathbf{v}_0\le\mathbf{v}_{\perp}^{T}\widehat{A}\mathbf{v}_{\perp}\le c_a\mathbf{v}_{\perp}^{T}T\mathbf{v}_{\perp}+\gamma h^{-\alpha}\mathbf{v}_{\perp}^{T}E\mathbf{v}_{\perp}, \tag*{(32)}

where cac_a is the continuity constant for a0(⋅,⋅)a_0(\cdot,\cdot). Using the definition of W~\widetilde{W}, rewriting η\eta in a more convenient form and using (31) and (32) together with the definition of cκ(v)c_{\kappa}(\mathbf{v}) in (29) we obtain:

η:=min⁡0≠v∈SγvTCTh−αM−1CvvTA^v+γvTCTh−αM−1Cv=min⁡0≠v∈S11+vTA^vγvTCTh−αM−1Cv≥min⁡0≠v∈S11+cav⊥TTv⊥+γh−αv⊥TEv⊥γβ~h2h2s−αv⊥TTv⊥=α=2smin⁡0≠v∈S11+caγβ~h2+cκ(v⊥)β~h2.\begin{aligned} \eta:= \min_{0 \ne\mathbf{v} \in S}\frac{\gamma\mathbf{v}^{T}C^{T}h^{-\alpha}M^{-1}C\mathbf{v}}{\mathbf{v}^{T}\widehat{A}\mathbf{v}+\gamma\mathbf{v}^{T}C^{T}h^{-\alpha}M^{-1}C\mathbf{v}} =\min_{0 \ne\mathbf{v}\in S}\frac{1}{1+\frac{\mathbf{v}^{T}\widehat{A}\mathbf{v}}{\gamma\mathbf{v}^{T}C^{T}h^{-\alpha}M^{-1}C\mathbf{v}}} \\ &\ge\min_{0 \ne\mathbf{v}\in S}\frac{1}{1+\frac{c_a\mathbf{v}_{\perp}^{T}T\mathbf{v}_{\perp}+\gamma h^{-\alpha}\mathbf{v}_{\perp}^{T}E\mathbf{v}_{\perp}}{\gamma\widetilde{\beta}_h^{2}h^{2s-\alpha}\mathbf{v}_{\perp}^{T}T\mathbf{v}_{\perp}}} \mathrel{\mathop{=}^{\alpha=2s}} \min_{0 \ne\mathbf{v}\in S}\frac{1}{1+\frac{c_a}{\gamma\widetilde{\beta}_h^{2}}+\frac{c_{\kappa}(\mathbf{v}_{\perp})}{\widetilde{\beta}_h^{2}}}. \end{aligned}

For algebraic augmentation, the term involving cκ(v⊥)c_{\kappa}(\mathbf{v}_{\perp}) is absent. Hence, for α=2s\alpha=2s, the lower bound in (30) is independent of hh, since β~h\widetilde{\beta}_h is the mesh-independent inf-sup constant. Moreover, in agreement with Theorem 5.1, increasing the penalization parameter γ\gamma drives η\eta closer to 1.

For continuous augmentation, on the other hand, additional problem-dependent assumptions on cκ(⋅)c_{\kappa}(\cdot) are generally required to establish a mesh-independent lower bound for η\eta.

Remark 5.5. The previous analysis relates the choice for the exponent α\alpha in the augmented formulation (9) to the power in the inverse estimate (27) on the multiplier space. This estimate depends on the problem, and it has to be verified on a case-by-case basis. We briefly list here some examples, which will also be considered in the numerical experiments.

When Λ=H12(Γ)\Lambda= H^{\frac{1}{2}}(\Gamma) and H=L2(Γ)H = L^{2}(\Gamma), where Γ\Gamma denotes either the boundary of the domain or an immersed interface, the inverse estimate (27) holds with s=12s = \frac{1}{2}. Consequently, α=1\alpha= 1 and W~=hΓM\widetilde{W} = h_{\Gamma}M, where hΓh_{\Gamma} denotes the mesh size of the codimension-one manifold Γ\Gamma. This setting arises, for instance, in the weak imposition of Dirichlet boundary conditions and in fictitious domain formulations with boundary Lagrange multipliers [24].

When Λ=H1(Ω2)\Lambda= H^{1}(\Omega_{2}) and H=L2(Ω2)H = L^{2}(\Omega_{2}), where Ω2\Omega_{2} is a subdomain of Ω\Omega, the inverse estimate (27) holds with s=1s = 1, yielding α=2\alpha= 2 and W~=h22M\widetilde{W} = h_{2}^{2}M, where h2h_{2} denotes the mesh size associated with the codimension-zero immersed domain Ω2\Omega_{2}.

If Λ≡H\Lambda\equiv H (as in the case of Grad-Div stabilization where both spaces coincide with L2(Ω)L^{2}(\Omega)), no inverse estimate is needed. Therefore, s=0=αs = 0 = \alpha, and W~=M\widetilde{W} = M, the standard pressure mass matrix. More generally, this rule determines the exponent for the applications in § 6.

We now validate the preceding framework on a concrete yet simple example involving the weak imposition of essential boundary conditions by means of Lagrange multipliers.

Example: boundary conditions through Lagrange multiplier

We consider the weak imposition of essential boundary conditions through Lagrange multipliers on a convex domain Ω⊂Rd\Omega\subset\mathbb{R}^{d} (d=2,3d = 2, 3), introduced in Babuška’s seminal work [4].

Let Γ=∂Ω\Gamma= \partial\Omega and Λ=H12(Γ)\Lambda= H^{\frac{1}{2}}(\Gamma). Let g∈H12(Γ)g \in H^{\frac{1}{2}}(\Gamma) be the prescribed boundary datum and f∈L2(Ω)f \in L^{2}(\Omega) the forcing term. The operator L:V→ΛL : V \to\Lambda, with V=H1(Ω)V = H^{1}(\Omega), is the trace operator, namely Lu=u∣ΓLu = u|_{\Gamma}. The saddle-point formulation in [4] seeks (u,λ)∈V×Λ′(u, \lambda) \in V \times\Lambda' such that

{(∇u,∇v)Ω+(u,v)Ω+⟨v,λ⟩Λ×Λ′=(f,v)Ω∀v∈V,⟨u,μ⟩Λ×Λ′=⟨g,μ⟩Λ×Λ′∀μ∈Λ′.(33)\begin{cases} (\nabla u, \nabla v)_{\Omega} + (u, v)_{\Omega} + \langle v, \lambda\rangle_{\Lambda\times\Lambda'} = (f, v)_{\Omega} & \forall v \in V, \\ \langle u, \mu\rangle_{\Lambda\times\Lambda'} = \langle g, \mu\rangle_{\Lambda\times\Lambda'} & \forall\mu\in\Lambda'. \tag*{(33)} \end{cases}

Let us introduce suitable finite-dimensional spaces Vh⊂VV_{h} \subset V and Λh⊂H⊂Λ′\Lambda_{h} \subset H \subset\Lambda' where H=L2(Γ)H = L^{2}(\Gamma). This choice is admissible since, identifying L2(Γ)L^{2}(\Gamma) with its dual, we have the dense and continuous inclusion

H12(Γ)⊆L2(Γ)⊆H−12(Γ).H^{\frac{1}{2}}(\Gamma) \subseteq L^{2}(\Gamma) \subseteq H^{-\frac{1}{2}}(\Gamma).

For this problem, Remark 5.5 suggests s=1/2s = 1/2, and hence α=1\alpha= 1 as power of the mesh-size.6

Let hΓh_{\Gamma} and hΩh_{\Omega} denote the mesh sizes on Γ\Gamma and Ω\Omega, respectively, and assume that both meshes are shape regular and quasi-uniform. Furthermore, since Λh⊂L2(Γ)\Lambda_h \subset L^2(\Gamma), the pairings in (33) reduce to L2(Γ)L^2(\Gamma) scalar products at the discrete level, so that the discrete augmented formulation reads as follows: find (uh,λh)∈Vh×Λh(u_h,\lambda_h) \in V_h \times\Lambda_h such that

(∇uh,∇vh)Ω+(uh,vh)Ω+γhΓ−1(uh,vh)Γ+(vh,λh)Γ=(f,vh)Ω+γhΓ−1(g,vh)Γ∀vh∈Vh,(uh,μh)Γ=(g,μh)Γ∀μh∈Λh.(34)\begin{aligned} (\nabla u_h,\nabla v_h)_{\Omega}+(u_h,v_h)_{\Omega}+\gamma h_{\Gamma}^{-1}(u_h,v_h)_{\Gamma}+(v_h,\lambda_h)_{\Gamma} &=(f,v_h)_{\Omega}+\gamma h_{\Gamma}^{-1}(g,v_h)_{\Gamma} && \forall v_h \in V_h,\\ (u_h,\mu_h)_{\Gamma}&=(g,\mu_h)_{\Gamma} && \forall\mu_h \in\Lambda_h. \tag*{(34)} \end{aligned}

Upon discretization, a classical choice is to use linear conforming elements for VhV_h and Λh\Lambda_h (either Q1Q^1 or P1P^1 elements, depending on the mesh type). In [4], it is shown that the corresponding discrete formulation, with equal order spaces, is inf-sup stable if hΓ/hΩ≥c>0h_{\Gamma}/h_{\Omega} \ge c > 0, with cc chosen sufficiently large.

Note that the augmented term involves the inner product on H=L2(Γ)H=L^2(\Gamma). Albeit simple, this example shows an instance of a mixed-dimensional problem where Λ≠H\Lambda\ne H.

As explained in [17], since the norm in HH is weaker than the one in Λ\Lambda, we ought to check the coercivity assumption in (10) for the well-posedness of the problem, which reads now

∃δ>0:  (∇v,∇v)Ω+(v,v)Ω+ξ∥v∥0,Γ2≥δ∥v∥V2∀v∈V,\exists\delta> 0:\;(\nabla v,\nabla v)_{\Omega}+(v,v)_{\Omega}+\xi\|v\|_{0,\Gamma}^{2}\ge\delta\|v\|_{V}^{2}\quad\forall v\in V,

with ξ>0\xi>0. The condition is satisfied automatically with δ=1\delta=1.

We start by showing that the bound in (16) tends to zero as the mesh is refined, implying that the proposed continuous augmentation is consistent. To this end, we adapt the following result from the error analysis in [17], setting γ=1\gamma=1 for ease of exposition. Note that, since γ\gamma is a mesh-independent constant, this choice does not affect the following results. For simplicity, we assume that the mesh sizes are comparable, i.e., hΓ≃hΩh_{\Gamma}\simeq h_{\Omega}, and denote both by hh.

Theorem 5.6 ([17]). Assume the hypotheses of § 3. Let (u,λ)(u,\lambda) be the solution of the original problem (2) and (uh,λh)(u_h,\lambda_h) be the solution of the discrete augmented problem (9). Moreover, assume that λ∈H\lambda\in H, α≥0\alpha\ge0, and γ=1\gamma=1. Then, the following error estimates hold:

∥u−uh∥V≤c((1+h−α2)inf⁡vh∈Vh∥u−vh∥V+hα2inf⁡μh∈Λh∥λ−μh∥H),\|u-u_h\|_{V}\le c\left((1+h^{-\frac{\alpha}{2}})\inf_{v_h\in V_h}\|u-v_h\|_{V}+h^{\frac{\alpha}{2}}\inf_{\mu_h\in\Lambda_h}\|\lambda-\mu_h\|_{H}\right),
∥λ−λh∥Λ′≤c((1+h−α2+h−α)inf⁡vh∈Vh∥u−vh∥V+inf⁡μh∈Λh∥λ−μh∥H).\|\lambda-\lambda_h\|_{\Lambda'}\le c\left((1+h^{-\frac{\alpha}{2}}+h^{-\alpha})\inf_{v_h\in V_h}\|u-v_h\|_{V}+\inf_{\mu_h\in\Lambda_h}\|\lambda-\mu_h\|_{H}\right).

As observed in [17], the previous a priori estimates are not optimal, since ∥λ−λh∥Λ\|\lambda-\lambda_h\|_{\Lambda} is controlled by the HH-norm of the interpolation error. In this specific case, such bounds are not sharp. Nevertheless, we use them to characterize the behavior of the stabilizing term. To satisfy the hypothesis λ∈H\lambda\in H, we assume additional regularity g∈H32(Γ)g\in H^{\frac{3}{2}}(\Gamma), so that by elliptic regularity u∈H2(Ω)u\in H^2(\Omega). In particular, λ=−∂u∂n∈H12(Γ)\lambda=-\frac{\partial u}{\partial n}\in H^{\frac{1}{2}}(\Gamma) [4], and hence λ∈H\lambda\in H.

The following approximation properties hold for the chosen finite element spaces:

inf⁡vh∈Vh∥u−vh∥V=O(h),inf⁡μh∈Λh∥λ−μh∥H=O(h12).\inf_{v_h\in V_h}\|u-v_h\|_{V}=\mathcal{O}(h),\qquad \inf_{\mu_h\in\Lambda_h}\|\lambda-\mu_h\|_{H}=\mathcal{O}(h^{\frac{1}{2}}).

Using Theorem 5.6 with α=1\alpha=1 and standard conforming interpolation estimates, yields the following a-priori error estimate for the augmented formulation:

∥u−uh∥V≤c((h+h12)∣u∣2,Ω+h∣λ∣12,Γ).\|u-u_h\|_{V}\le c\left((h+h^{\frac{1}{2}})|u|_{2,\Omega}+h|\lambda|_{\frac{1}{2},\Gamma}\right).

Moreover, for v∈V\mathbf{v} \in V, it holds

∥κ(Lv)∥H=∥κ(v∣Γ)∥H=∥v∣Γ−πH(v∣Γ)∥H≤ch12∣v∣1,Γ≤ch12∥v∥1,Ω,(35)\lVert\kappa(L\mathbf{v})\rVert_H = \lVert\kappa(\mathbf{v}|_{\Gamma})\rVert_H = \lVert\mathbf{v}|_{\Gamma} - \pi_H(\mathbf{v}|_{\Gamma})\rVert_H \leq c h^{\frac{1}{2}} |\mathbf{v}|_{1,\Gamma} \leq c h^{\frac{1}{2}} \lVert\mathbf{v}\rVert_{1,\Omega}, \tag*{(35)}

where we have used the approximation property of the L2L^2-projection πH\pi_H (see, e.g., [37 Chapter 10]) and the trace theorem. Exploiting twice the bound (35) in Lemma 4.2 yields

∣r(vh)∣≤γh−1∥κ(L(uh−u))∥H∥κ(Lvh)∥H≤γh−1c2h∥u−uh∥V∥vh∥V→0,h→0.|r(\mathbf{v}_h)| \leq\gamma h^{-1}\lVert\kappa(L(\mathbf{u}_h-\mathbf{u}))\rVert_H\lVert\kappa(L\mathbf{v}_h)\rVert_H \leq\gamma h^{-1}c^2h\lVert\mathbf{u}-\mathbf{u}_h\rVert_V\lVert\mathbf{v}_h\rVert_V \to0,\qquad h\to0.

We now turn our attention to the computational advantages of continuous over algebraic augmentation in terms of matrix sparsity and assembly cost. We provide numerical evidence of this matter through the following three-dimensional example.

Example 5.7 (Computational gains). We set Ω=B1(0,0,0)\Omega=B_1(0,0,0), the three-dimensional unit ball centered at the origin, and report in Figure 1 the sparsity patterns and the number of nonzero entries (nnz) of the matrix AA associated with the original bilinear form a0(⋅,⋅)a_0(\cdot,\cdot), the matrix A~\widetilde{A} associated with the augmented bilinear form, and the algebraically augmented (1,1)(1,1)-block, Aalg=A+CTM−1CA_{\mathrm{alg}} = A + C^T M^{-1}C. The global size of the (1,1)(1,1)-block is 3,817. The original matrix AA and the matrix A~\widetilde{A} share the same sparsity pattern, whereas AalgA_{\mathrm{alg}} is clearly much denser, by a factor larger than 16. Although the augmentation considered here involves only a surface integral, the algebraic augmentation still leads to a dramatic increase in the number of nonzero entries.

To further highlight the benefits of our approach, we compare the wall-clock times of the continuous and algebraic augmentations (the latter computed using the cheaper variant CTdiag⁡(M)−1CC^T\operatorname{diag}(M)^{-1}C) over a sequence of mesh refinements in Figure 2.

The continuous augmentation is substantially sparser, and on the finest mesh is 90× faster to assemble. Motivated by these examples, we will not compute any triple matrix product in the numerical tests of § 6, but rather we will directly assemble the augmented bilinear form.

Figure 1. Sparsity patterns of the original matrix AA and of the augmented matrices A~\widetilde{A}, and AalgA_{\mathrm{alg}} for the weak imposition of Dirichlet boundary conditions à la Babuška. Q1Q_1–Q1Q_1 elements are employed.

Figure 2. Comparison of wall-clock time (in seconds) against number of dof for the algebraic and continuous augmentations. Here a0(uh,vh)=(∇uh,∇vh)Ω+(uh,vh)Ωa_0(u_h,v_h) = (\nabla u_h,\nabla v_h)_\Omega+ (u_h,v_h)_\Omega, and AA is its associated matrix representation.

Finally, we establish the mesh-independence of η\eta in Theorem 5.4 for the present problem, namely, we show that the term cκ(v)c_\kappa(\mathbf{v}) remains bounded as the mesh is refined. Indeed, using estimate (35) in the definition (29) yields

h−1∥κ(L(vh))∥H2∥vh∥V2≤c2.\frac{h^{-1}\lVert\kappa(L(\mathbf{v}_h))\rVert_H^2}{\lVert\mathbf{v}_h\rVert_V^2} \leq c^2.

We also validate the mesh-independence of η\eta numerically. To avoid solving large generalized eigenvalue problems, we consider the two-dimensional analogue of the previous example, setting Ω=B1(0,0)\Omega= B_1(0, 0). We perform a series of uniform refinement cycles to investigate the behavior of η\eta as the mesh resolution increases. Furthermore, we also verify that increasing the augmentation parameter using values γ∈{10,100,1000}\gamma\in\{10, 100, 1000\} produces a tightly clustered spectrum near 1, as predicted at the end of Theorem 5.4. We compute the eigenvalues of the preconditioned matrices using the Python scipy.linalg package. The plots in Figure 3 validate the developed theory: all eigenvalues are real and positive, with the smallest eigenvalue indicated in each plot. Fixing each column, we observe that the smallest eigenvalue remains uniformly bounded upon mesh refinement. Fixing each row, instead, we observe an increasingly clustered spectrum near 1 as the constant γ\gamma increases.

Figure 3. Spectrum of P~γ−1A~γ\widetilde{P}_\gamma^{-1}\widetilde{A}_\gamma for the weak imposition of essential boundary conditions. Each row corresponds to a refinement cycle in which both meshes are uniformly refined. Along rows: influence of the AL parameter γ∈{10,100,1000}\gamma\in\{10, 100, 1000\} (increasing from left to right). Along columns: mesh-independence of lower bound η\eta. Cycle 0 has sizes n=337n = 337 and m=16m = 16, cycle 1 has n=1,313n = 1,313 and m=32m = 32, and cycle 2 has n=5,185n = 5,185 and m=64m = 64.

Interplay between h−αh^{-\alpha}, convergence rates, and iteration counts.

In [17], the power of hh is tuned to improve a-priori estimates, whereas in the present work α=1\alpha= 1 is dictated by preconditioning requirements. Since this choice is not driven by accuracy considerations, we have to verify that it does not deteriorate the convergence of the discrete solution.

To this end, we consider again Problem (34), with Ω=(0,1)2\Omega= (0, 1)^2, manufactured solution u=sin⁡(π(x+0.3))sin⁡(π(y+0.3))u = \sin(\pi(x+0.3))\sin(\pi(y+0.3)), and Q1Q^1–Q1Q^1 elements. This pair is balanced, and the non-augmented scheme already achieves the best-approximation rate [4], so no accuracy can be gained from the augmentation. The purpose of the experiment is therefore to confirm that none is lost with α=1\alpha= 1, and to show that, in contrast, the performance of the iterative solver is strongly dependent on the choice of α\alpha. We use FGMRES with an inexact variant of the ideal preconditioner to account for its variable application resulting from the iterative solution of the diagonal blocks. The absolute stopping tolerance is set to 10−1210^{-12}. The augmented block uses conjugate gradient (CG) with one V-cycle of algebraic multigrid and tolerance 10−210^{-2}, while the mass matrix uses CG with point-Jacobi preconditioning. Details are provided in § 6. We set the augmentation parameter to γ=10\gamma= 10.

Errors, convergence rates, and iteration counts are reported in Table 1, where α=1\alpha= 1 is compared with α=12\alpha= \frac{1}{2}.

dof_udof_λW^=hΓ2M\widehat{W}=h_{\Gamma}^{2}M ∣u−uh∣0,Ω|u-u_h|_{0,\Omega}∣u−uh∣1,Ω|u-u_h|_{1,\Omega}∣λ−λh∣0,Γ|\lambda-\lambda_h|_{0,\Gamma}FGMRES its.W^=hΓM\widehat{W}=h_{\Gamma}M ∣u−uh∣0,Ω|u-u_h|_{0,\Omega}∣u−uh∣1,Ω|u-u_h|_{1,\Omega}∣λ−λh∣0,Γ|\lambda-\lambda_h|_{0,\Gamma}FGMRES its.
81167.89×10−37.89\times10^{-3}2.60×10−12.60\times10^{-1}8.47×10−18.47\times10^{-1}107.66×10−37.66\times10^{-3}2.56×10−12.56\times10^{-1}8.47×10−18.47\times10^{-1}10
289322.01×10−32.01\times10^{-3} (1.97)1.31×10−11.31\times10^{-1} (0.99)5.75×10−15.75\times10^{-1} (0.56)141.92×10−31.92\times10^{-3} (2.00)1.28×10−11.28\times10^{-1} (1.00)5.75×10−15.75\times10^{-1} (0.56)12
1,089645.12×10−45.12\times10^{-4} (1.97)6.62×10−26.62\times10^{-2} (0.99)4.02×10−14.02\times10^{-1} (0.51)184.81×10−44.81\times10^{-4} (2.00)6.39×10−26.39\times10^{-2} (1.00)4.03×10−14.03\times10^{-1} (0.51)12
4,2251281.30×10−41.30\times10^{-4} (1.97)3.34×10−23.34\times10^{-2} (0.99)2.84×10−12.84\times10^{-1} (0.50)211.20×10−41.20\times10^{-4} (2.00)3.20×10−23.20\times10^{-2} (1.00)2.84×10−12.84\times10^{-1} (0.50)12
16,6412563.31×10−53.31\times10^{-5} (1.98)1.68×10−21.68\times10^{-2} (0.99)2.00×10−12.00\times10^{-1} (0.50)243.01×10−53.01\times10^{-5} (2.00)1.60×10−21.60\times10^{-2} (1.00)2.01×10−12.01\times10^{-1} (0.50)12
66,0495128.38×10−68.38\times10^{-6} (1.98)8.48×10−38.48\times10^{-3} (0.99)1.42×10−11.42\times10^{-1} (0.50)277.51×10−67.51\times10^{-6} (2.00)7.99×10−37.99\times10^{-3} (1.00)1.42×10−11.42\times10^{-1} (0.50)11
263,1691,0242.11×10−62.11\times10^{-6} (1.99)4.24×10−34.24\times10^{-3} (0.99)1.00×10−11.00\times10^{-1} (0.50)301.88×10−61.88\times10^{-6} (2.00)3.99×10−33.99\times10^{-3} (1.00)1.00×10−11.00\times10^{-1} (0.50)11
1,050,6252,0485.34×10−75.34\times10^{-7} (1.99)2.14×10−32.14\times10^{-3} (0.99)7.10×10−27.10\times10^{-2} (0.50)344.70×10−74.70\times10^{-7} (2.00)2.00×10−32.00\times10^{-3} (1.00)7.10×10−27.10\times10^{-2} (0.50)11

Table 1. Convergence study for the weak imposition of boundary conditions on Ω=(0,1)2\Omega= (0, 1)^2, u=sin⁡(π(x+0.3))sin⁡(π(y+0.3))u = \sin(\pi(x+0.3))\sin(\pi(y+0.3)), Q1Q^1–Q1Q^1 elements, γ=10\gamma= 10. Comparison between W^=hΓ2M\widehat{W} = h_{\Gamma}^{2}M and the exponent, α=1\alpha= 1, predicted by Remark 5.5, implying W^=hΓM\widehat{W} = h_{\Gamma}M. Convergence rates are reported in parentheses.

For both powers, the optimal convergence rates are confirmed (two in L2L^2 and one in semi-H1H^1), and the errors are essentially unaffected by α\alpha. The iteration counts, instead, remain bounded only for W^=hΓM\widehat{W} = h_{\Gamma}M (cf. also Table 3 in § 6).

Weak bcs. through multipliers (2D)
dofu_udofλ_{\lambda}FGMRES its.Inner (avg.)
811662
2893272
1,0896462
4,22512865
16,64125655
66,04951255
263,1691,02456
1,050,6252,04846
4,198,4014,09657

Table 3. FGMRES(30) iteration counts for the AL preconditioner P~γBabusˇka\widetilde{P}^{\mathrm{Babuška}}_{\gamma} applied to weakly imposed boundary conditions (5.17) on Ω=(0,1)2\Omega= (0,1)^2, with g=x+yg = x+y, γ=10\gamma= 10, s=12s = \frac{1}{2}.

Numerical experiments

We evaluate the performance of the proposed preconditioners for linear systems stemming from mixed finite element discretizations of mixed-dimensional and fictitious domain formulations with Lagrange multipliers. Our previous works [8, 7] demonstrated the robustness of algebraic AL approaches for fictitious domain problems, showing superior performance compared with other methods. Here, we focus on improving and generalizing the framework developed therein, while referring to our previous works for comparisons with alternative methods.

Computations have been carried out on a laptop equipped with an AMD Ryzen 9 PRO 7940HS processor and 64 GB of RAM. Experiments have been performed using the C++ finite element library DEAL.II [2].

Our implementation allows exploiting several features, such as adaptive mesh refinement, efficient handling of non-matching meshes in parallel setting, as well as state-of-the-art algebraic multigrid preconditioners available in well-established linear algebra libraries. When we use conforming elements on quadrilaterals or hexahedra, local refinement induces hanging nodes. Continuity of the discrete solution is enforced by imposing constraints on the degrees of freedom (dof). The nodal unknowns associated with such nodes are eliminated by restricting them to an interpolation of the nodal values of the finite element solution on the corresponding parent element [2].

Table 2 summarizes the problems, preconditioners, and stable finite element pairs, including three-dimensional elasticity with different Lamé constants in each subdomain.

ProblemPreconditionerFinite element space
Babuška LMP~γBabusˇka\widetilde{\mathcal{P}}^{\mathrm{Babuška}}_{\gamma} (36)Q1Q^{1}–Q1Q^{1} (2D), P1P^{1}–P1P^{1} (3D)
FD-BLMP~γBLM\widetilde{\mathcal{P}}^{\mathrm{BLM}}_{\gamma} (37)Q1Q^{1}–P1P^{1}
FD-DLMP~γ1,γ2DLM\widetilde{\mathcal{P}}^{\mathrm{DLM}}_{\gamma_{1},\gamma_{2}} (42)Q1Q^{1}–(Q1+B)(Q^{1}+\mathcal{B})–Q0Q^{0}
FD-DLM (linear elasticity)P~γ1,γ2DLM\widetilde{\mathcal{P}}^{\mathrm{DLM}}_{\gamma_{1},\gamma_{2}} (42)Q1Q^{1}–(Q1+B)(Q^{1}+\mathcal{B})–Q0Q^{0}

Table 2. Problems considered in this section, corresponding AL preconditioners, and finite element spaces.

We use simplicial, quadrilateral, or hexahedral meshes according to the geometry. As usual in fictitious domain experiments, we use a structured background mesh Th\mathcal{T}_{h} on Ω\Omega.

The outer Krylov solver is set to FGMRES [34] with a restart every 30 iterations. All iterations start from a zero initial guess and, unless otherwise specified, are stopped when the relative residual norm drops below 10−910^{-9}, or when the absolute residual is below 10−1210^{-12}. All preconditioners considered are applied inexactly. Inner solves for the augmented blocks use preconditioned conjugate gradient (PCG) with one V-cycle of an algebraic multigrid preconditioner from Trilinos ML [27] (using a degree two Chebyshev smoother, aggregation threshold set to 10−310^{-3}, maximum size of the coarsest level set to 2000, and a direct solver on the coarsest level) with a loose inner tolerance of 10−210^{-2}. For the mass matrix inversion we use PCG with point-Jacobi. In each one of the forthcoming tables, we report as last column the (average) number of PCG iterations to invert the (1,1)-block.

A classical alternative for the approximate inversion of augmented blocks in AL preconditioners is to use one or a few multigrid cycles with tailored smoothers based on patchwise relaxation [36, 21]. Crucially, designing such smoothers strongly depends on the weak form and on the finite element spaces employed; we notice that, in the mixed-dimensional case, this becomes even more challenging due to the presence of two overlapping meshes. For these reasons, we do not pursue this avenue here, and leave the development of tailored multigrid solvers to future work.

Weak imposition of boundary conditions with Lagrange multipliers

We consider the system associated with the weak imposition of boundary conditions on Γ=∂Ω\Gamma=\partial\Omega through Lagrange multipliers in Problem (34). We use a stable pair with linear Lagrangian elements for both the solution variable and the Lagrange multiplier. The resulting preconditioner is (19) with blocks

A~ij=(∇ϕi,∇ϕj)Ω+(ϕi,ϕj)Ω+γhΓ−1(ϕi,ϕj)Γ,Mkβ=(ψk,ψβ)Γ,Cki=(ϕi,ψk)Γ.(36)\begin{aligned} \widetilde{A}_{ij} &= (\nabla\phi_i,\nabla\phi_j)_{\Omega}+(\phi_i,\phi_j)_{\Omega}+\gamma h_{\Gamma}^{-1}(\phi_i,\phi_j)_{\Gamma},\\ M_{k\beta} &= (\psi_k,\psi_\beta)_{\Gamma},\\ C_{ki} &= (\phi_i,\psi_k)_{\Gamma}. \tag*{(36)} \end{aligned}

Following Remark 5.5, we have set s=12s = \frac{1}{2}, which corresponds to W~=hΓM\widetilde{W} = h_{\Gamma}M. We refer to this preconditioner as P~γBabusˇka\widetilde{P}^{\mathrm{Babuška}}_{\gamma}. We test its performance by setting γ=10\gamma= 10, with Ω=(0,1)2\Omega= (0,1)^2 and g=x+yg = x+y as a non-constant boundary datum. The results are reported in Table 3. They indicate excellent convergence properties of the AL preconditioner, which exhibits constant and very low iteration counts across mesh refinement, even with a mild value of γ=10\gamma= 10.

To stress the robustness of the preconditioner, we consider a non-trivial three-dimensional test case involving the geometry shown in Figure 4a, keeping g=x+yg = x+y as boundary datum. For such a geometry, the generation of a hexahedral mesh is a complex task, and we hence consider tetrahedral elements. Hence, P1\mathcal{P}^{1}–P1\mathcal{P}^{1} is the chosen finite element pair. The meshing procedure starts from an STL file representing the boundary of the domain7, and generates a volumetric tetrahedral mesh through the FTETWILD library [28]. The resulting mesh is shown in Figure 4a, while the computed solution is shown in Figure 4b.

Figure 4. (a)–(b): tetrahedralization of the surface mesh (clipped) and computed solution for the weak imposition of boundary conditions with g=x+yg = x + y. (c)–(d): popcorn surface Γ\Gamma (12,178 triangles) and computed solution on Ω=(−1,1)3\Omega= (-1,1)^3 (clipped in order to show mesh of Γ\Gamma) for the Poisson fictitious domain problem with boundary supported Lagrange multipliers, with f=g=1f = g = 1, s=12s = \frac{1}{2}. Iteration counts are reported in Table 5.

The results in terms of iteration counts across mesh refinement are collected in Table 4, confirming the robustness of the AL preconditioner also for a challenging geometry. The average number of inner iterations to approximately invert the augmented block mildly increases with mesh refinement, never exceeding nine PCG iterations.

Weak bcs. through multipliers (3D)
dofu_udofλ_{\lambda}FGMRES its.Inner (avg.)
5,8593,887156
37,35615,542117
264,28362,162118
1,982,981248,64289

Table 4. FGMRES(30) iteration counts for the AL preconditioner P~γBabusˇka\widetilde{P}^{\mathrm{Babuška}}_{\gamma} applied to weakly imposed boundary conditions (5.17) on the three-dimensional geometry in Figure 4, with g=x+yg = x+y, γ=10\gamma= 10, s=12s = \frac{1}{2}.

Fictitious domain with boundary supported Lagrange multipliers

We consider the saddle-point system associated with the Poisson fictitious domain problem with boundary Lagrange multipliers, which we briefly recall from [24]. Let ω\omega be a closed and bounded domain of Rd\mathbb{R}^{d}, d=2,3d = 2, 3, with Lipschitz continuous boundary Γ:=∂ω\Gamma:= \partial\omega, and Ω⊂Rd\Omega\subset\mathbb{R}^{d} a Lipschitz domain such that ω\omega is compactly contained in Ω\Omega. We consider the associated variational formulation from [24], i.e., find (u,λ)∈V×Λ′(u,\lambda) \in V \times\Lambda'

{(∇u,∇v)Ω+⟨v,λ⟩Λ×Λ′=(f,v)Ω∀v∈V=H01(Ω),⟨u,μ⟩Λ×Λ′=⟨g,μ⟩Λ×Λ′∀μ∈Λ′=H−12(Γ),(37)\left\{ \begin{aligned} (\nabla u,\nabla v)_{\Omega} + \langle v,\lambda\rangle_{\Lambda\times\Lambda'} &= (f,v)_{\Omega} && \forall v \in V = H^1_0(\Omega),\\ \langle u,\mu\rangle_{\Lambda\times\Lambda'} &= \langle g,\mu\rangle_{\Lambda\times\Lambda'} && \forall\mu\in\Lambda' = H^{-\frac{1}{2}}(\Gamma), \end{aligned} \right. \tag*{(37)}

for given data f∈L2(Ω)f \in L^2(\Omega) and g∈H12(Γ)g \in H^{\frac{1}{2}}(\Gamma). Formally, the above problem and its augmented formulation is very close to the one in the previous section. The main difference lies in the fact that Γ\Gamma is an immersed interface (a surface in the three-dimensional case) not aligned with the background domain Ω\Omega, yielding a loss of regularity for uu, which cannot be expected to be globally in H2(Ω)H^2(\Omega) [24]. Remark 5.5 gives again W‾=hΓM\overline{W} = h_{\Gamma}M, therefore the blocks of the preconditioner are defined analogously to those in (6.1). We refer to the preconditioner for this problem as P~γBLM\widetilde{P}^{\mathrm{BLM}}_{\gamma}.

We test it on a challenging three-dimensional immersed geometry. We set u∣∂Ω=0u|_{\partial\Omega} = 0, f=g=1f = g = 1, Ω=(−1,1)3\Omega= (-1,1)^3, and take Γ\Gamma to be a surface mesh representing a popcorn-like geometry. The discretization of Γ\Gamma is done by means of a surface triangular mesh consisting of 12,178 elements, and it is shown in Figure 4c. A localized refinement is performed around the interface, and the computed solution is shown in Figure 4d. Iteration counts in Table 5 remain robust under mesh refinement. Low and robust iteration counts (not reported here) are also confirmed for a simpler two-dimensional test with Ω=(0,1)2\Omega= (0,1)^2 and Γ\Gamma given by the boundary of the ball of radius 0.2 centered at (0.4,0.4)(0.4, 0.4).

FD-BLM (3D)
dofudof_udofλdof_\lambdaFGMRES its.Inner (avg.)
141,1796,0911411
577,66424,3581511
2,442,03197,4261212
10,808,121389,6981212

Table 5. FGMRES(30) iteration counts for the AL preconditioner P~γBLM\widetilde{P}^{\mathrm{BLM}}_{\gamma} applied to the Poisson fictitious domain problem with boundary supported Lagrange multipliers. We set Ω=(−1,1)3\Omega= (-1,1)^3, Γ\Gamma the pop-corn geometry, f=g=1f = g = 1, γ=10\gamma= 10, s=12s = \frac{1}{2}, and we use Q1Q^1–P1P^1 elements.

Fictitious domain with distributed Lagrange multipliers

We consider the following elliptic interface problem with a jump in the coefficients. Let Ω\Omega be a domain in Rd\mathbb{R}^d, where d∈{2,3}d \in\{2,3\}, with a bounded Lipschitz boundary ∂Ω\partial\Omega. Let Ω1\Omega_1 and Ω2\Omega_2 be two subdomains of Ω\Omega such that Ω‾=Ω‾1∪Ω‾2\overline{\Omega}=\overline{\Omega}_1\cup\overline{\Omega}_2, and let the interface Γ=Ω‾1∩Ω‾2\Gamma=\overline{\Omega}_1\cap\overline{\Omega}_2 be Lipschitz continuous. We assume Γ‾∩∂Ω=∅\overline{\Gamma}\cap\partial\Omega=\emptyset.

For i=1,2i=1,2, given forcing terms fi:Ωi→Rf_i:\Omega_i\to\mathbb{R}, and positive coefficients βi∈L∞(Ωi)\beta_i\in L^\infty(\Omega_i), find u1:Ω1→Ru_1:\Omega_1\to\mathbb{R} and u2:Ω2→Ru_2:\Omega_2\to\mathbb{R} such that:

{−div⁡(βi∇ui)=fiin Ωi,u1=u2on Γ,β1∇u1⋅n1=−β2∇u2⋅n2on Γ,u1=0on ∂Ω.(38)\begin{cases} -\operatorname{div}(\beta_i\nabla u_i)=f_i & \text{in }\Omega_i,\\ u_1=u_2 & \text{on }\Gamma,\\ \beta_1\nabla u_1\cdot\mathbf{n}_1=-\beta_2\nabla u_2\cdot\mathbf{n}_2 & \text{on }\Gamma,\\ u_1=0 & \text{on }\partial\Omega. \tag*{(38)} \end{cases}

where ni\mathbf{n}_i (i=1,2i=1,2) denotes the unit vector normal to Γ\Gamma, pointing out of Ωi\Omega_i.

Following the fictitious domain discretization developed in [3, 16], let V=H01(Ω)V=H^1_0(\Omega), V2=H1(Ω2)V_2=H^1(\Omega_2), and Λ′=[H1(Ω2)]′\Lambda'=[H^1(\Omega_2)]'. Given f∈L2(Ω)f\in L^2(\Omega), f2∈L2(Ω2)f_2\in L^2(\Omega_2) and β2>β>0\beta_2>\beta>0, let V~h=Vh×V2,h\widetilde{V}_h=V_h\times V_{2,h} denote the product space, whose elements are v~h=(vh,v2,h)\widetilde{v}_h=(v_h,v_{2,h}). The formulation requires finding (u~h,λh)=((uh,u2,h),λh)∈V~h×Λh(\widetilde{u}_h,\lambda_h)=((u_h,u_{2,h}),\lambda_h)\in\widetilde{V}_h\times\Lambda_h such that

ae(u~h,v~h)+(λh,vh∣Ω2−v2,h)Ω2=(f,vh)Ω+(f2−f,v2,h)Ω2∀v~h∈V~h,(μh,uh∣Ω2−u2,h)Ω2=0∀μh∈Λh.(39)\begin{aligned} a_e(\widetilde{u}_h,\widetilde{v}_h)+(\lambda_h,v_h|_{\Omega_2}-v_{2,h})_{\Omega_2}&=(f,v_h)_{\Omega}+(f_2-f,v_{2,h})_{\Omega_2} &&\forall\widetilde{v}_h\in\widetilde{V}_h,\\ (\mu_h,u_h|_{\Omega_2}-u_{2,h})_{\Omega_2}&=0 &&\forall\mu_h\in\Lambda_h. \tag*{(39)} \end{aligned}

where

ae((uh,u2,h),(vh,v2,h))=(β∇uh,∇vh)Ω+((β2−β)∇u2,h,∇v2,h)Ω2.a_e((u_h,u_{2,h}),(v_h,v_{2,h}))=(\beta\nabla u_h,\nabla v_h)_{\Omega}+((\beta_2-\beta)\nabla u_{2,h},\nabla v_{2,h})_{\Omega_2}.

Hence, for this problem it follows L(u,u2):=u∣Ω2−u2L(u,u_2):=u|_{\Omega_2}-u_2, which weakly enforces uu to match u2u_2 on the immersed domain Ω2\Omega_2.

We denote by hΩh_{\Omega} the characteristic mesh size of the background mesh on Ω\Omega and by h2h_2 that of the immersed mesh on Ω2\Omega_2. We assume that both meshes are shape regular and quasi-uniform and satisfy h2≃hΩh_2\simeq h_{\Omega}. Thus, the analogue of the discrete augmented formulation (9) is obtained by adding the term γh2−α(uh∣Ω2−u2,h,vh∣Ω2−v2,h)Ω2\gamma h_2^{-\alpha}(u_h|_{\Omega_2}-u_{2,h},v_h|_{\Omega_2}-v_{2,h})_{\Omega_2} to the left-hand side of the first equation. Moreover, following the recipe outlined in Remark 5.5, we set W~=h22M\widetilde{W}=h_2^2M. In this case, we consider instead the projected augmentation

γh2−2(πH(uh∣Ω2−u2,h),πH(vh∣Ω2−v2,h))Ω2,\gamma h_2^{-2}(\pi_H(u_h|_{\Omega_2}-u_{2,h}),\pi_H(v_h|_{\Omega_2}-v_{2,h}))_{\Omega_2},

as an example of the possible alternative mentioned in § 1.1. By Lemma 4.1, this term is equivalent to the algebraic augmentation and therefore does not alter the discrete solution. Using finite element spaces for which the multiplier space is discontinuous, i.e. Q1Q^1–(Q1+B)(Q^1+\mathcal{B})–Q0Q^0, where B\mathcal{B} denotes the bubble enrichment (inf-sup stability for this element has been shown in [1]), the projected term can be assembled without forming CTM−1CC^TM^{-1}C. Indeed, πH\pi_H reduces to the local projection onto piecewise constants, which is a local operation consisting of averaging the values of uhu_h over each cell of the immersed mesh Ω2\Omega_2.

Introducing basis functions {φi}i=1n\{\varphi_i\}_{i=1}^n, {ϕj}j=1l\{\phi_j\}_{j=1}^l, and {ψk}k=1m\{\psi_k\}_{k=1}^m for the finite element spaces VhV_h, V2,hV_{2,h}, and Λh\Lambda_h, respectively, the resulting matrices are defined as follows:

A~(γ)ij=(β∇φi,∇φj)Ω+γh2−2(πHφi∣Ω2,πHφj∣Ω2)Ω2,A~2(γ)ij=((β2−β)∇ϕi,∇ϕj)Ω2+γh2−2(πHϕi,πHϕj)Ω2,D(γ)ij=γh2−2(πHϕi∣Ω2,πHϕj)Ω2,Cki=(φi∣Ω2,ψk)Ω2,C2kj=(ϕj,ψk)Ω2,Mij=(ψi,ψj)Ω2.(40)\begin{aligned} \widetilde{A}(\gamma)_{ij}&=(\beta\nabla\varphi_i,\nabla\varphi_j)_{\Omega}+\gamma h_2^{-2}(\pi_H\varphi_i|_{\Omega_2},\pi_H\varphi_j|_{\Omega_2})_{\Omega_2},\\ \widetilde{A}_2(\gamma)_{ij}&=((\beta_2-\beta)\nabla\phi_i,\nabla\phi_j)_{\Omega_2}+\gamma h_2^{-2}(\pi_H\phi_i,\pi_H\phi_j)_{\Omega_2},\\ D(\gamma)_{ij}&=\gamma h_2^{-2}(\pi_H\phi_i|_{\Omega_2},\pi_H\phi_j)_{\Omega_2},\\ C_{ki}&=(\varphi_i|_{\Omega_2},\psi_k)_{\Omega_2},\\ C_{2kj}&=(\phi_j,\psi_k)_{\Omega_2},\\ M_{ij}&=(\psi_i,\psi_j)_{\Omega_2}. \tag*{(40)} \end{aligned}

Our framework gives the following candidate (ideal) preconditioner, where no triple matrix product needs to be formed:

P~γDLM:=(A~(γ)−D(γ)CT−D(γ)TA~2(γ)−C2T00−1γW~).(41)\widetilde{\mathcal{P}}_{\gamma}^{\mathrm{DLM}} := \begin{pmatrix} \widetilde{A}(\gamma) & -D(\gamma) & C^{T} \\ -D(\gamma)^{T} & \widetilde{A}_{2}(\gamma) & -C_{2}^{T} \\ 0 & 0 & -\frac{1}{\gamma}\widetilde{W} \end{pmatrix}. \tag*{(41)}

Nevertheless, approximately inverting the augmented 2×22 \times2 block remains non-trivial. To address this issue, the authors introduced in [7] a modified version with two distinct augmentation parameters, γ1\gamma_{1} and γ2\gamma_{2}. In our framework, this preconditioner takes the form

P~γ1,γ2DLM:=(A~(γ1)−D(γ1)CT0A~2(γ2)−C2T00−1γ1W~),(42)\widetilde{\mathcal{P}}_{\gamma_{1},\gamma_{2}}^{\mathrm{DLM}} := \begin{pmatrix} \widetilde{A}(\gamma_{1}) & -D(\gamma_{1}) & C^{T} \\ 0 & \widetilde{A}_{2}(\gamma_{2}) & -C_{2}^{T} \\ 0 & 0 & -\frac{1}{\gamma_{1}}\widetilde{W} \end{pmatrix}, \tag*{(42)}

and only requires the inversion of the SPD diagonal blocks. As shown in [7], the preconditioner is fairly robust with respect to the jump β2−β\beta_{2}-\beta, with an increasingly tighter spectrum when γ1→∞\gamma_{1} \to\infty and γ2→0\gamma_{2} \to0. For this reason, following [7], we set γ1=10\gamma_{1}=10 and γ2=10−2\gamma_{2}=10^{-2}.

To validate this preconditioner, we start with a classic two-dimensional experiment where Ω=(−1,1)2\Omega=(-1,1)^{2} and Ω2=B0.3(0,0)\Omega_{2}=\mathcal{B}_{0.3}(0,0), the ball of radius 0.3 centered at the origin. The number of FGMRES iterations for different values of β2\beta_{2} are collected in Table 6, showing high robustness of the preconditioner also with respect to the jump in the coefficients induced by parameter β2\beta_{2}. Inner iteration counts for the approximate inversion of the augmented (1,1)(1,1)-block when β2=103\beta_{2}=10^{3} are reported in the last column and low values are observed across mesh refinement.

FGMRES iterationsInner (avg.)
dofu_udofu2_{u_2}dofλ_\lambdaβ2=10\beta_2=10β2=103\beta_2=10^3β2=107\beta_2=10^7
4,225169801818186
16,6416573202323236
66,0492,5931,2802222227
263,16910,3055,1202222227
1,050,62541,08920,4802323237
4,198,401164,09781,9202524248

Table 6. FGMRES(30) iteration counts for the modified AL preconditioner P~γ1,γ2DLM\widetilde{\mathcal{P}}_{\gamma_{1},\gamma_{2}}^{\mathrm{DLM}} applied to the elliptic interface fictitious domain problem with distributed Lagrange multipliers. We set Ω=(−1,1)2\Omega=(-1,1)^{2}, Ω2=B0.3(0,0)\Omega_{2}=\mathcal{B}_{0.3}(0,0), Q1Q^{1}–(Q1+B)(Q^{1}+\mathbb{B})–Q0Q^{0} elements, for increasing values of β2\beta_{2}. The augmentation parameters are chosen as γ1=10\gamma_{1}=10, γ2=10−2\gamma_{2}=10^{-2}, s=1s=1.

A visualization of the solution for β2=103\beta_{2}=10^{3} is shown in Figure 5, where the contrast among subdomains results in a clear and visible separation of the two regions.

Computed solution $u_h$ for the elliptic interface fictitious domain problem

Figure 5. Computed solution uhu_h for the elliptic interface fictitious domain problem with distributed Lagrange multipliers (β2=103\beta_{2}=10^{3}) on Ω=(−1,1)2\Omega=(-1,1)^{2}, Ω2=B0.3(0,0)\Omega_{2}=\mathcal{B}_{0.3}(0,0).

For the three-dimensional case, we consider a more complex setting by extending the scalar elliptic interface problem to an immersed linear elasticity problem. We use the same finite element spaces as in the previous scalar case. Let μ,μ2\mu,\mu_{2} be the shear moduli in Ω\Omega and Ω2\Omega_{2}, respectively, and λ,λ2\lambda,\lambda_{2} the first Lamé parameters. Consistently with the assumptions for the scalar problem (38), we assume μ2>μ>0\mu_{2}>\mu>0 and λ2>λ>0\lambda_{2}>\lambda>0. We denote with δμ=μ2−μ\delta_{\mu}=\mu_{2}-\mu and δλ=λ2−λ\delta_{\lambda}=\lambda_{2}-\lambda the corresponding jumps. Vector-valued functions are indicated in boldface; thus, no ambiguity arises when λ\lambda denotes either a multiplier or a Lamé parameter. Adapting the arguments from the previous sections to the vector-valued case, the fictitious domain formulation reads as follows: find (u,u2,λ)∈V×V2×Λ′(\mathbf{u},\mathbf{u}_2,\boldsymbol{\lambda}) \in V \times V_2 \times\Lambda' such that

2μ(ε(u),ε(v))Ω+λ(div⁡u,div⁡v)Ω+⟨v∣Ω2,λ⟩Λ×Λ′=(f,v)Ω∀v∈V,2\mu(\boldsymbol{\varepsilon}(\mathbf{u}),\boldsymbol{\varepsilon}(\mathbf{v}))_{\Omega}+\lambda(\operatorname{div}\mathbf{u},\operatorname{div}\mathbf{v})_{\Omega}+\langle\mathbf{v}|_{\Omega_2},\boldsymbol{\lambda}\rangle_{\Lambda\times\Lambda'}=(\mathbf{f},\mathbf{v})_{\Omega}\qquad\forall\mathbf{v} \in V,
2δμ(ε(u2),ε(v2))Ω2+δλ(div⁡u2,div⁡v2)Ω2−⟨v2,λ⟩Λ×Λ′=0∀v2∈V2,2\delta\mu(\boldsymbol{\varepsilon}(\mathbf{u}_2),\boldsymbol{\varepsilon}(\mathbf{v}_2))_{\Omega_2}+\delta\lambda(\operatorname{div}\mathbf{u}_2,\operatorname{div}\mathbf{v}_2)_{\Omega_2}-\langle\mathbf{v}_2,\boldsymbol{\lambda}\rangle_{\Lambda\times\Lambda'}=0\qquad\forall\mathbf{v}_2 \in V_2,
⟨u∣Ω2−u2,μ⟩Λ×Λ′=0∀μ∈Λ′,\langle\mathbf{u}|_{\Omega_2}-\mathbf{u}_2,\boldsymbol{\mu}\rangle_{\Lambda\times\Lambda'}=0\qquad\forall\boldsymbol{\mu} \in\Lambda',

where ε(u)=12(∇u+∇uT)\boldsymbol{\varepsilon}(\mathbf{u})=\frac{1}{2}(\nabla\mathbf{u}+\nabla\mathbf{u}^{\mathrm{T}}) is the linearized strain tensor, f∈[L2(Ω)]3\mathbf{f} \in[L^2(\Omega)]^3, and V=[HΓD1(Ω)]3V=[H^1_{\Gamma_D}(\Omega)]^3, V2=[H1(Ω2)]3V_2=[H^1(\Omega_2)]^3, Λ′=[H1(Ω2)]3′\Lambda'=[H^1(\Omega_2)]^{3\prime} are the vector-valued analogues of the spaces defined for the scalar problem. Here, ΓD\Gamma_D denotes the portion of the boundary on which Dirichlet conditions are imposed.

We consider an elongated steel bar inside a rubber-like elastomeric mount. The background domain is the 40 mm×40 mm×80 mm40\ \mathrm{mm} \times40\ \mathrm{mm} \times80\ \mathrm{mm} rectangular box Ω=(−20,20)×(−20,20)×(−40,40)\Omega=(-20,20)\times(-20,20)\times(-40,40) (in mm), while the immersed domain is the 18 mm×18 mm×54 mm18\ \mathrm{mm} \times18\ \mathrm{mm} \times54\ \mathrm{mm} box Ω2=(−9,9)×(−9,9)×(−27,27)\Omega_2=(-9,9)\times(-9,9)\times(-27,27). Both domains are discretized with structured hexahedral meshes, with the bar mesh shown in Figure 6a.

Rectangular inclusion for $\Omega_2$Computed solution (clipped)

Figure 6. (a) Rectangular inclusion for Ω2\Omega_2. (b) Computed solution (clipped). Linear elasticity problem: bar inclusion mesh immersed in a rubber-like elastomeric mount. In gray, the displaced configuration of the inclusion, while in blue the reference configuration. The background domain is deformed and clipped in order to show the immersed geometry.

The material properties are chosen to be representative of the physical materials: the bar has Lamé constants μ2=76,923 MPa\mu_2=76{,}923\ \mathrm{MPa} and λ2=115,385 MPa\lambda_2=115{,}385\ \mathrm{MPa}, corresponding to a Young’s modulus E2=200 GPaE_2=200\ \mathrm{GPa}, while the background domain has μ=17.24 MPa\mu=17.24\ \mathrm{MPa} and λ=155.17 MPa\lambda=155.17\ \mathrm{MPa}, corresponding to a Young’s modulus E=50 MPaE=50\ \mathrm{MPa}. This implies a contrast of nearly four orders of magnitude between the immersed inclusion and the background domain, and represents a good test case to evaluate the AL preconditioner on a physically relevant scenario. On the background domain Ω\Omega, we prescribe a fixed displacement field u=(0,0,−δ)\mathbf{u}=(0,0,-\delta), with δ=5 mm\delta=5\ \mathrm{mm}, on the top face and zero displacement on the bottom face. Traction-free boundary conditions (σ⋅n=0)(\boldsymbol{\sigma}\cdot\mathbf{n}=0) are applied to the four remaining lateral faces, and body forces are neglected. The displacement magnitude (in mm) with the associated streamlines is shown in Figure 6b. The softer background domain shows a smooth gradient for the magnitude of the displacement from the clamped bottom to the fixed top face, typical of a uniaxial compression state. Due to the high contrast in material properties, the bar undergoes a translation of 2.5 mm2.5\ \mathrm{mm} in the negative zz-direction with no visible distortion, behaving as a rigid body.

We use the same inner PCG solvers as in the previous experiments, with an outer relative residual tolerance of 10−610^{-6}. We then study the behavior of P~γ1,γ2DLM\widetilde{\mathcal{P}}^{\mathrm{DLM}}_{\gamma_1,\gamma_2} with respect to simultaneous mesh refinement up to 13×10613 \times10^6 degrees of freedom. The FGMRES iterations for different cycles are reported in Table 7: also in this complex scenario, the iteration counts remain low and robust under mesh refinement. The low number of iterations, combined with a realistic setup featuring high contrast in the material coefficients, motivates the usage of the proposed preconditioner as a viable option for the solution of large-scale three-dimensional problems.

FD-DLM (3D)
dof⁡u\operatorname{dof}_udof⁡u2\operatorname{dof}_{u_2}dof⁡Λ\operatorname{dof}_{\Lambda}FGMRES its.Inner (avg.)
28,6111,551576127
212,35510,6834,608107
1,635,07579,34736,864129
12,830,211611,811294,91299

Table 7. FGMRES(30) iteration counts for the modified AL preconditioner P~γ1,γ2DLM\widetilde{P}^{\mathrm{DLM}}_{\gamma_1,\gamma_2} applied to the linear elasticity fictitious-domain problem with distributed Lagrange multipliers on the rectangular inclusion immersed in a rubber-like elastomeric mount.

Strong scaling study

We conclude with a strong scaling experiment, using the same inner and outer solvers and stopping criteria as in the previous experiment. The simulations have been run on the MareNostrum 5 cluster at Barcelona Supercomputing Center, where each compute node features 2x Intel Sapphire Rapids 8460Y+ processors at 2GHz (56 cores each, 112 cores per node) and 256GB of main memory.8

We consider the same material parameters and spaces as in the previous example, with Ω=(−1,1)3\Omega= (-1,1)^3 and Ω2=(−0.8,0.8)×(−0.3,0.3)×(−0.4,0.5)\Omega_2 = (-0.8,0.8) \times(-0.3,0.3) \times(-0.4,0.5). The discretization has 50,923,779 dof for VhV_h, 206,115 for V2,hV_{2,h}, and 98,304 for Λh\Lambda_h. We vary the number of MPI processes from 336 to 5376 (i.e., from 3 to 48 compute nodes) and report the wall-clock time as a function of the number of MPI processes for each phase: linear solver, assembly of background and immersed matrices, and coupling terms.

Results are shown in Figure 7. The annotations (in black) indicate the number of FGMRES iterations, which is independent of the number of MPI processes. The linear solver and the classical assembly phases exhibit good scaling, with a degradation when communication overhead becomes significant due to the low number of dof per MPI process. Particle detection and augmented term assembly dominate the assembly cost. The detection phase locates immersed-mesh quadrature points, treated as particles, in the background mesh and assigns them to subdomains, requiring substantial global communication between the independently partitioned meshes.

Figure 7. Strong scaling analysis for the fictitious domain method with distributed Lagrange multipliers on MareNostrum 5. The dashed line represents ideal scaling. Black numbers above the solver curve indicate FGMRES iteration counts.

Conclusions, practical guidelines and outlook

We have introduced a unified framework for the design and analysis of augmented Lagrangian preconditioners for symmetric saddle point systems arising from mixed finite element discretizations. The proposed approach is based on a continuous augmentation, which combines the spectral benefits of algebraic augmentation with the computational simplicity of a standard finite element formulation. The augmented (1,1)(1,1)-block can be explicitly assembled, preserving the sparsity pattern of the original block and avoiding sparse matrix-matrix products. Moreover, if we can prove that the stabilizing term vanishes under mesh refinement, then the solution of the discrete augmented formulation converges to that of the original problem. In addition, our analysis shows that the matrix preconditioned with the ideal preconditioner has a real, positive spectrum that is bounded away from zero and clusters around 1 as the AL parameter increases.

Numerical experiments with mixed-dimensional Lagrange multiplier formulations, different discretizations, and complex geometries validate the theoretical findings, while the abstract analysis applies to a broader class of constrained formulations. The applicability of the framework to a new problem can be assessed through four main checks: coercivity (10), the inverse inequality (27), the vanishing of the augmentation residual in (16) under mesh refinement, and compatibility of the mesh-dependent scaling with the convergence rate (Section 5.2.1). These conditions provide a practical guideline for assessing whether the framework provides an efficient alternative to algebraic augmentation while retaining its spectral advantages. The procedure is illustrated in § 5.2 for the weak imposition of boundary conditions considered.

If one of the previous checks does not hold, a possible alternative is to employ the projected counterpart of the augmentation term, as illustrated in § 6.3. This approach still avoids the explicit computation of the triple matrix product CTW−1CC^{T}W^{-1}C.

Future work will extend this approach to fluid-structure interaction problems and develop tailored multigrid solvers for the approximate inversion of the augmented blocks.

Acknowledgments

The authors are grateful to Patrick Farrell (University of Oxford) for helpful discussions.

Declarations. The implementation of this methodology is available in the authors’ maintained GitHub repository: https://github.com/fdrmrc/fictitious_domain_AL-preconditioners. The authors used ChatGPT v6.1 to improve readability and language. They reviewed and edited the material. The authors take full responsibility for all content.

References

References

  1. [1]N. Alshehri, D. Boffi, and L. Gastaldi, Unfitted mixed finite element methods for elliptic interface problems, Numerical Methods for Partial Differential Equations, 40 (2024), p. e23063, https://doi.org/10.1002/num.23063.
  2. [2]D. Arndt, W. Bangerth, D. Davydov, T. Heister, L. Heltai, M. Kronbichler, M. Maier, J.-P. Pelteret, B. Turcksin, and D. Wells, The deal.II finite element library: Design, features, and insights, Computers & Mathematics with Applications, 81 (2021), pp. 407–422.DOI
  3. [3]F. Auricchio, D. Boffi, L. Gastaldi, A. Lefieux, and A. Reali, On a fictitious domain method with distributed Lagrange multiplier for interface problems, Applied Numerical Mathematics, 95 (2015), pp. 36–50, https://doi.org/10.1016/j.apnum.2014.05.013.
  4. [4]I. Babuška, The finite element method with Lagrangian multipliers, Numerische Mathematik, 20 (1973), pp. 179–192.DOI
  5. [5]F. P. A. Beik and M. Benzi, Preconditioning techniques for the coupled Stokes-Darcy problem: spectral and field-of-values analysis, Numerische Mathematik, 150 (2022), pp. 257–298, https://doi.org/10.1007/s00211-021-01267-8.
  6. [6]M. Benzi and C. Faccio, Solving linear systems of the form $(A + \alpha UU^T) x = b$ by preconditioned iterative methods, SIAM Journal on Scientific Computing, 46 (2024), pp. S51–S70, https://doi.org/10.1137/22M1505529.
  7. [7]M. Benzi, M. Feder, L. Heltai, and F. Mungaioni, Augmented Lagrangian preconditioners for fictitious domain formulations of elliptic interface problems, arXiv:2603.12993, (2026), https://arxiv.org/abs/2603.12993.
  8. [8]M. Benzi, M. Feder, L. Heltai, and F. Mungaioni, Scalable augmented Lagrangian preconditioners for fictitious domain problems, Computer Methods in Applied Mechanics and Engineering, 450 (2026), p. 118522, https://doi.org/10.1016/j.cma.2025.118522.
  9. [9]M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numerica, 14 (2005), pp. 1–137, https://doi.org/10.1017/S0962492904000212.
  10. [10]M. Benzi and M. A. Olshanskii, An augmented Lagrangian-based approach to the Oseen problem, SIAM Journal on Scientific Computing, 28 (2006), pp. 2095–2113, https://doi.org/10.1137/050646421.
  11. [11]M. Benzi, M. A. Olshanskii, and Z. Wang, Modified augmented Lagrangian preconditioners for the incompressible Navier-Stokes equations, International Journal for Numerical Methods in Fluids, 66 (2011), pp. 486–508, https://doi.org/10.1002/fld.2267.
  12. [12]D. Boffi, F. Brezzi, and M. Fortin, Mixed Finite Element Methods and Applications, vol. 44 of Springer Series in Computational Mathematics, Springer, Berlin, Heidelberg, 2013, https://doi.org/10.1007/978-3-642-36519-5.
  13. [13]D. Boffi, A. Cangiani, M. Feder, L. Gastaldi, and L. Heltai, A comparison of non-matching techniques for the finite element approximation of interface problems, Computers & Mathematics with Applications, 151 (2023), pp. 101–115.arxiv.org/abs/2304.11908
  14. [14]D. Boffi, F. Credali, and L. Gastaldi, On the interface matrix for fluid-structure interaction problems with fictitious domain approach, Computer Methods in Applied Mechanics and Engineering, 401 (2022), p. 115650, https://doi.org/10.1016/j.cma.2022.115650.
  15. [15]D. Boffi and L. Gastaldi, A fictitious domain approach with Lagrange multiplier for fluid-structure interactions, Numer. Math., 135 (2017), pp. 711–732, https://doi.org/10.1007/s00211-016-0814-1.
  16. [16]D. Boffi, L. Gastaldi, and M. Ruggeri, Mixed formulation for interface problems with distributed Lagrange multiplier, Computers & Mathematics with Applications, 68 (2014), pp. 2151–2166, https://doi.org/10.1016/j.camwa.2014.07.020. Advances in Computational Partial Differential Equations.
  17. [17]D. Boffi and C. Lovadina, Analysis of new augmented Lagrangian formulations for mixed finite element schemes, Numerische Mathematik, 75 (1997), pp. 405–419.DOI
  18. [18]A. Budiša, X. Hu, M. Kuchta, K.-A. Mardal, and L. Zikatanov, Rational approximation preconditioners for multiphysics problems, in International Conference on Numerical Methods and Applications, Springer, 2022, pp. 100–113.
  19. [19]N. Dimola, N. Rares Franco, and P. Zunino, Numerical solution of mixed-dimensional PDEs using a neural preconditioner, Computers & Mathematics with Applications, 206 (2026), pp. 58–79, https://doi.org/10.1016/j.camwa.2025.12.013.
  20. [20]H. Elman, D. Silvester, and A. Wathen, Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics, Oxford University Press, 2014, https://doi.org/10.1093/acprof:oso/9780199678792.001.0001.
  21. [21]P. E. Farrell, M. G. Knepley, L. Mitchell, and F. Wenschung, PCPATCH: Software for the topological construction of multigrid relaxation methods, ACM Transactions on Mathematical Software, 47 (2021), https://doi.org/10.1145/3445791.
  22. [22]P. E. Farrell, L. Mitchell, and F. Wenschung, An augmented Lagrangian preconditioner for the 3D stationary incompressible Navier–Stokes equations at high Reynolds number, SIAM Journal on Scientific Computing, 41 (2019), pp. A3073–A3096, https://doi.org/10.1137/18M1219370.
  23. [23]M. Firmbach, I. Steinbrecher, A. Popp, and M. Mayr, Modified augmented Lagrangian preconditioning for mixed-dimensional beam-solid coupling, Computer Methods in Applied Mechanics and Engineering, 463 (2027), p. 119425, https://doi.org/10.1016/j.cma.2026.119425.
  24. [24]V. Girault and R. Glowinski, Error analysis of a fictitious domain method applied to a Dirichlet problem, Japan Journal of Industrial and Applied Mathematics, 12 (1995), pp. 487–514, https://doi.org/10.1007/BF03167240.
  25. [25]A. Greenbaum, V. Pták, and Z. Strakoš, Any nonincreasing convergence curve is possible for GMRES, SIAM Journal on Matrix Analysis and Applications, 17 (1996), pp. 465–469, https://doi.org/10.1137/S0895479894275030.
  26. [26]T. Heister and G. Rapin, Efficient augmented Lagrangian-type preconditioning for the Oseen problem using Grad-Div stabilization, International Journal for Numerical Methods in Fluids, 71 (2013), pp. 118–134, https://doi.org/10.1002/fld.3654.
  27. [27]M. A. Heroux, R. A. Bartlett, V. E. Howle, R. J. Hoekstra, J. J. Hu, T. G. Kolda, R. B. Lehoucq, K. R. Long, R. P. Pawlowski, E. T. Phipps, A. G. Salinger, H. K. Thornquist, R. S. Tuminaro, J. M. Willenbring, A. Williams, and K. S. Stanley, An overview of the Trilinos project, ACM Transactions on Mathematical Software, 31 (2005), pp. 397–423, https://doi.org/10.1145/1089014.1089021.
  28. [28]Y. Hu, T. Schneider, B. Wang, D. Zorin, and D. Panozzo, Fast tetrahedral meshing in the wild, ACM Trans. Graph., 39 (2020), https://doi.org/10.1145/3386569.3392385.
  29. [29]M. Kuchta, M. Nordaas, J. C. Verschaeve, M. Mortensen, and K.-A. Mardal, Preconditioners for saddle point systems with trace constraints coupling 2D and 1D domains, SIAM Journal on Scientific Computing, 38 (2016), pp. B962–B987.DOI
  30. [30]F. Laakmann, P. E. Farrell, and L. Mitchell, An augmented Lagrangian preconditioner for the magnetohydrodynamics equations at high Reynolds and coupling numbers, SIAM Journal on Scientific Computing, 44 (2022), pp. B1018–B1044, https://doi.org/10.1137/21M1416539.
  31. [31]D. Malkus, Eigenproblems associated with the discrete LBB condition for incompressible finite elements, International Journal of Engineering Science, 19 (1981), pp. 1299–1310, https://doi.org/10.1016/0020-7225(81)90013-6.
  32. [32]K.-A. Mardal and W. Winther, Preconditioning discretizations of systems of partial differential equations, Numerical Linear Algebra with Applications, 18 (2011), pp. 1–40, https://doi.org/10.1002/nla.716.
  33. [33]J. Moulin, P. Jolivet, and O. Marquet, Augmented Lagrangian preconditioner for large-scale hydrodynamic stability analysis, Computer Methods in Applied Mechanics and Engineering, 351 (2019), pp. 718–743, https://doi.org/10.1016/j.cma.2019.03.052.
  34. [34]Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM Journal on Scientific Computing, 14 (1993), pp. 461–469, https://doi.org/10.1137/0914128.
  35. [35]Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, second ed., 2003, https://doi.org/10.1137/1.9780898718003.
  36. [36]J. Schöberl, Multigrid methods for a parameter dependent problem in primal variables, Numerische Mathematik, 84 (1999), pp. 97–119, https://doi.org/10.1007/s002110050465.
  37. [37]O. Steinbach, Numerical Approximation Methods for Elliptic Boundary Value Problems: Finite and Boundary Elements, Springer, 2008.
  38. [38]J. Xia, P. E. Farrell, and F. Wenschung, Augmented Lagrangian preconditioners for the Oseen–Frank model of nematic and cholesteric liquid crystals, BIT Numerical Mathematics, 61 (2021), pp. 607–644, https://doi.org/10.1007/s10543-020-00838-9.

Paper details

vlnc:W_d3n7mbz3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT v6.1

View statement
Looking for related papers…
Contents