betaFeedback

WorksMathematics

Transform before linearizing: robust Newton methods for singular pp-Laplace and pp-Stokes equations

Abstract

For 1<p<21<p<2, the pp-Laplace equation and its pp-Stokes generalization are difficult to solve numerically. Newton's method converges rapidly only close to the solution, with iteration counts that grow under mesh refinement and deteriorate as p→1p\to1. The more robust Picard iteration converges only linearly. Rather than globalizing or preconditioning Newton's method, we modify the system to which it is applied. We lift the equation by introducing the flux ∣∇u∣p−2∇u|\nabla u|^{p-2}\nabla u as an auxiliary (or ''lifting'') variable, apply a nonlinear transformation to the resulting constitutive relation, linearize, and eliminate the auxiliary variable by static condensation. Lifting alone leaves the linearization unchanged; it is the preceding transformation that yields the new method. The elimination is algebraic and pointwise at the quadrature points, so the flux variable is never discretized, no inf-sup condition or indefinite system arises, and the cost per iteration is that of a standard Newton step. Together with a pointwise feasibility bound on the lifting variable that keeps the diffusion tensor uniformly positive definite, this yields an iteration that we prove, in finite dimensions and for the pp-Laplace equation, to converge globally and locally at a quadratic rate; a one-dimensional model problem explains why the lagged flux variable removes the zig-zag behavior of standard Newton for pp close to one. Firedrake-based experiments for pp-Laplace problems in two and three dimensions and for stationary and time-dependent pp-Stokes flows show iteration counts largely insensitive to pp and to mesh refinement, and up to an order of magnitude fewer iterations than standard Newton for pp close to one.

Introduction

For p∈(1,∞)p \in(1,\infty), the pp-Laplace equation

−∇⋅(∣∇u∣p−2∇u)=fin Ω,(1)-\nabla\cdot\left(\lvert\nabla u\rvert^{p-2}\nabla u\right) = f \quad\text{in } \Omega, \tag*{(1)}

defined over a domain Ω⊂Rd\Omega\subset\mathbb{R}^{d} is the prototypical quasilinear elliptic problem. It arises as the Euler–Lagrange equation of the pp-Dirichlet energy J(u)=1p∫Ω∣∇u∣p dx−∫Ωf u dxJ(u) = \frac{1}{p}\int_{\Omega} |\nabla u|^{p}\,dx - \int_{\Omega} f\,u\,dx. For p=2p = 2, it reduces to the linear Poisson problem; for any other exponent, it is genuinely nonlinear. Operators similar to the pp-Laplacian occur in a wide range of applications: power-law shear-thinning or thickening models for non-Newtonian fluids, ice-sheet dynamics under Glen’s flow corresponding to p=4/3p = 4/3 [8, 13], problems in geodynamics [38], and motion by curvature in the limit p→∞p \to\infty [24, 32].

Despite its seemingly simple form, (1) is notoriously difficult to solve numerically. Two features account for much of this difficulty. First, the diffusion coefficient ∣∇u∣p−2|\nabla u|^{p-2} concentrates the nonlinearity in a quantity that becomes singular for 1<p<21 < p < 2, i.e., it diverges at points where ∇u=0\nabla u = 0, and degenerate for p>2p > 2, where the linearized operator loses ellipticity. Second, solutions are not classically smooth: weak solutions are only known to be C1,αC^{1,\alpha} for some α∈(0,1)\alpha\in(0,1), and regularity properties deteriorate as pp moves away from 2. Both features have consequences at the numerical level, where the most commonly used iterative schemes to solve (1) are Newton and Picard methods.

Newton’s method linearizes the nonlinear operator on the left hand side of (1) at a current iterate uku_k. Writing the unit gradient direction wk:=∇uk/∣∇uk∣w_k := \nabla u_k / |\nabla u_k| (and, for now, assuming that the gradient does not vanish), the Newton increment u^\hat{u} solves

−∇⋅(∣∇uk∣p−2(I+(p−2)wkwk⊤)∇u^)=∇⋅(∣∇uk∣p−2∇uk)+fin Ω,(2)-\nabla\cdot\left(|\nabla u_k|^{p-2}(I + (p-2)w_k w_k^{\top})\nabla\hat{u}\right) = \nabla\cdot\left(|\nabla u_k|^{p-2}\nabla u_k\right) + f \quad\text{in }\Omega, \tag*{(2)}

followed by the update uk+1:=uk+αu^u_{k+1} := u_k + \alpha\hat{u} with step length α∈(0,1]\alpha\in(0,1].

Instead, Picard freezes the diffusion coefficient ∣∇u∣p−2|\nabla u|^{p-2} at the current iterate uku_k and computes u^\hat{u} by solving the linear problem

−∇⋅(∣∇uk∣p−2∇u^)=∇⋅(∣∇uk∣p−2∇uk)+fin Ω,(3)-\nabla\cdot\left(|\nabla u_k|^{p-2}\nabla\hat{u}\right) = \nabla\cdot\left(|\nabla u_k|^{p-2}\nabla u_k\right) + f \quad\text{in }\Omega, \tag*{(3)}

followed again by uk+1:=uk+αu^u_{k+1} := u_k + \alpha\hat{u} with α∈(0,1]\alpha\in(0,1]. A common, mathematically equivalent variant of (3) is to write it directly in terms of uk+1u_{k+1} under the assumption α=1\alpha= 1 (which is the typical choice for Picard). Comparing (2) and (3), it can be seen that the only difference is the anisotropic term (p−2)wkwk⊤(p-2)w_k w_k^{\top}, which can cause challenges for robust convergence.

The main challenges for Newton solvers based on (2) (or an appropriate regularized form) are their small basin of fast convergence and the resulting mesh-dependent iteration counts. Newton’s method converges quadratically only from initial iterates very close to the solution, with the radius of the guaranteed-convergence ball shrinking rapidly as the level of nonlinearity increases [15, 36]. This occurs when pp deviates from 2, especially in the regime 1<p<21 < p < 2, which is the primary case we consider. Damped, line-search-globalized, or semismooth Newton iterations are therefore essential in practice, but they typically require a large number of short steps before the iterate enters the quadratic regime—if it does at all. As a consequence, Newton solvers typically exhibit iteration counts that grow under mesh refinement and depend severely on pp [20, 22, 29].

A common alternative to Newton’s method is the Picard method (3), which comes with its own drawbacks. It is more robust than Newton globally, but it converges only linearly, with a contraction factor that worsens as p→1p \to1. Continuation strategies in pp [22] alleviate this issue at the price of solving a sequence of auxiliary problems.

In this paper, we propose the following strategy for singular pp-Laplace and pp-Stokes problems, i.e., 1<p<21 < p < 2. Rather than modifying Newton’s or Picard’s method by means of a preconditioner or continuation, we modify the system on which Newton’s method operates: we (1) lift the original nonlinear equation to a higher-dimensional space by introducing an auxiliary variable (here, the dual variable) that exposes the nonlinearity through a pointwise algebraic identity; (2) perform a nonlinear transformation of the lifted system that tames the offending nonlinearity; (3) linearize to derive Newton’s method in the lifted space; and (4) eliminate the auxiliary variable from the resulting linear system by static condensation. The dual variable from the underlying convex-energy formulation provides a natural choice of lifting variable. For the pp-Laplace equation (1), this is the flux λ=∣∇u∣p−2∇u\boldsymbol{\lambda} = |\nabla u|^{p-2}\nabla u, and for our generalization to pp-Stokes problems, it is the deviatoric stress tensor. Because the auxiliary unknown is eliminated before solving, the cost per iteration matches that of the standard Newton (or even Picard) method, and existing Newton solvers only require minor adjustments. As we will show, our approach exhibits a significantly larger region of rapid convergence, with iteration counts that are largely unaffected by pp or mesh refinement.

Our approach is related to several existing lines of research. The lifted Newton method proposed in [1], originally motivated by direct multiple-shooting methods for optimal control [6], likewise introduces auxiliary variables to expose nonlinearity, but does so primarily in the context of time-dependent problems. Nonlinear elimination [25] and composed nonlinear solvers [9] follow the philosophy of restructuring the nonlinear system rather than its linearization. Nonlinear preconditioning through domain decomposition [16, 18, 20, 26, 27] is complementary to our approach in that it focuses iterations on locally difficult subdomains; our lifting approach addresses the source of the difficulty directly.

In the context of nonlinear PDE solvers, related primal–dual and stress-lifting variants of Newton’s method have been proposed for other nonlinear PDEs with singular constitutive laws. For Bingham flow, whose constitutive law is singular below a yield stress and is therefore closely analogous to the pp-Laplacian with p<2p < 2, [14] employs a semismooth Newton method formulated using the dual stress. Close to our framework is the stress–velocity Newton scheme of [34, 35] for viscoplastic geodynamic Stokes flow, which treats the deviatoric stress as an independent variable prior to its elimination. The abstract form of that construction in [34], Sec 5.3 shares the steps of the strategy above and studies it for a term of L1L^1-type. It explains the degeneracy of the standard linearization with its coefficient tending to an orthogonal projector with a vanishing eigenvalue along one direction, resulting in small step sizes. Closely related, [37] proposes a primal–dual Newton–Krylov method for a viscous-plastic sea-ice model. Instead of introducing a lifted stress variable, the authors of [39] evolve a scalar lifted field that tracks ∣∇u∣2|\nabla u|^2 via a gradient-flow evolution, recovering the classical Kačanov iteration (which requires solving systems similar to (3)), as a special case. They demonstrate robustness and iteration numbers competitive with Newton’s method (which, as we argue here, is not a robust method, particularly for pp close to 1). Retaining the stress as an independent unknown is also the premise of the implicit constitutive theory of non-Newtonian fluids [10], in which the constitutive law is a relation between the stress and the symmetric velocity gradient that need not be solvable for either variable; our lifting exploits the same structural freedom, but at the level of the linearization rather than the model. Collectively, these studies indicate that reformulating the constitutive relation via an auxiliary variable is a promising approach for nonlinear PDE solvers. In this work, we develop a lifting-based method for the pp-Laplace and pp-Stokes systems and provide arguments supporting its superior convergence behavior.

Upon discretization and replacing the gradient operator with a general matrix AA, the discrete pp-Dirichlet energy associated with (1) becomes an ℓp\ell_p-regression problem of the form min⁡u∥Ax−b∥pp\min_u \|Ax-b\|_p^p. This class of problems has been widely examined in optimization and theoretical computer science. Our lifting approach is most closely related to the interior-point framework of [3], which applies Newton’s method to a coupled primal/dual feasibility system exhibiting a similar lift–linearize–condense pattern. In the limit p→1p \to1, primal–dual algorithms for total variation [12, 21] introduce a similar dual variable combined with a feasibility modification, directly paralleling the feasibility projection we employ for the lifting variable. For the discrete pp-Laplacian specifically, [29] gives an algorithm that exploits the convex variational structure of the problem to compute a solution to high accuracy in polynomial time.

Main contributions and limitations

The main contributions we make in this work are as follows: (1) Our approach is a simple modification of Newton’s method that can be implemented in standard automated finite element software. It neither requires a mixed discretization nor the solution of indefinite systems. (2) We show that the discretized iteration converges globally, with line search and pointwise diffusion tensor modification, for 1<p<21 < p < 2. It is also locally quadratically convergent; an analysis of a one-dimensional model problem explains why the lagged lifting variable suppresses the zig-zag behavior of standard Newton in flat regions. (3) Our publicly available implementations (in the finite element library Firedrake) show iteration counts largely insensitive to mesh refinement and to p→1p \to1, in two and three dimensions for pp-Laplace equations. Our generalizations to pp-Stokes and time-dependent pp-Navier–Stokes indicate an up to order-of-magnitude reduction in required linear solves compared to standard Newton for pp close to 1.

The main limitations are: (1) The lifting approach is most advantageous for problems with strong nonlinearities and potentially singular behavior, such as the power-law constitutive relation in the singular regime 1<p<21 < p < 2. The proposed method is thus less broadly applicable than, e.g., the Picard–Newton methods of [33], which do not require such structure. (2) Our convergence results are for the discretized and regularized pp-Laplace equation only, and the constants in the analysis deteriorate as p→1p \to1 at the same rate as for standard Newton. The robustness we observe numerically is thus not fully explained by the theory; we discuss it using intuitive arguments and illustrate it for a one-dimensional model problem. (3) All linear systems in our experiments are solved with direct solvers. Although we demonstrate the method on challenging two- and three-dimensional problems with linear and quadratic finite elements and on the order of 10510^5 unknowns, we do not study the use of preconditioned iterative Krylov solvers.

The pp-Laplace equation

In this section, we summarize the functional-analytic setting for the pp-Laplace equation (1) and introduce equivalent problem formulations that motivate different solution strategies. We assume a bounded Lipschitz domain Ω⊂Rd\Omega\subset\mathbb{R}^{d} (d≥1d \ge1), a source term f∈W−1,q(Ω)f \in W^{-1,q}(\Omega) (with 1/p+1/q=11/p + 1/q = 1), and given boundary data g∈W1/q,p(∂Ω)g \in W^{1/q,p}(\partial\Omega). Then the pp-Laplace problem is

−∇⋅(∣∇u∣p−2∇u)=fin Ω,u=gon ∂Ω,(4)-\nabla\cdot\left(\lvert\nabla u\rvert^{p-2}\nabla u\right) = f \quad\text{in }\Omega,\qquad u = g \quad\text{on }\partial\Omega, \tag*{(4)}

where p∈(1,∞)p \in(1,\infty) controls the degree of nonlinearity. The natural setting is the Sobolev space W1,p(Ω)W^{1,p}(\Omega): weak solutions of (4) with homogeneous boundary data (i.e., g=0g = 0) are the unique minimizers of the strictly convex energy

J(u):=1p∫Ω∣∇u∣p dx−∫Ωfu dx,u∈W01,p(Ω).(5)J(u) := \frac{1}{p}\int_{\Omega} \lvert\nabla u\rvert^{p}\,\mathrm{d}x - \int_{\Omega} fu\,\mathrm{d}x,\qquad u \in W_{0}^{1,p}(\Omega). \tag*{(5)}

Strict convexity of JJ on W01,p(Ω)W_{0}^{1,p}(\Omega) ensures the existence and uniqueness of a weak solution u∗∈W01,p(Ω)u^* \in W_{0}^{1,p}(\Omega). Since nonzero Dirichlet boundary data gg can be treated by extending gg to the whole domain Ω\Omega and then solving for a corrective term to that extension, we assume g=0g = 0 for the remainder of this section.

Applying Newton’s method directly to (4) results in the linear equation (2) that must be solved for the increment u^\hat{u}. Since this equation is only well defined if ∇u≠0\nabla u \ne0 on all of Ω\Omega, one often considers the regularized norm

∣∇u∣ε:=∣∇u∣2+ε2(6)\lvert\nabla u\rvert_{\varepsilon} := \sqrt{\lvert\nabla u\rvert^{2}+\varepsilon^{2}} \tag*{(6)}

in (4) and (5), with 0<ε≪10 < \varepsilon\ll1. This results in a well-defined Newton step of the form (2) with all norms ∣⋅∣\lvert\cdot\rvert replaced by ∣⋅∣ε\lvert\cdot\rvert_{\varepsilon}. Regularizing in this (or a similar) way to avoid the singularity is essentially the only standard remedy for the ill-posedness of (2); if the resulting Newton iteration nonetheless converges poorly (as it typically does), it is unclear how to modify it further.

To isolate the nonlinearity, we thus introduce the Rd\mathbb{R}^{d}-valued variable λ(x):=∣∇u(x)∣p−2∇u(x)\boldsymbol{\lambda}(x) := \lvert\nabla u(x)\rvert^{p-2}\nabla u(x) for all x∈Ωx \in\Omega. The resulting system in the independent variables (u,λ)(u,\boldsymbol{\lambda}) is now

−∇⋅λ=fin Ω,(7)-\nabla\cdot\boldsymbol{\lambda} = f \quad\text{in }\Omega, \tag*{(7)}
λ−∣∇u∣p−2∇u=0in Ω,(8)\lambda-\lvert\nabla u\rvert^{p-2}\nabla u=0 \quad\text{in }\Omega, \tag*{(8)}

where we emphasize that (7) is linear, and the nonlinearity is restricted to the pointwise equation (8), which can be manipulated to potentially change the nature of the nonlinearity. Before proceeding with a more detailed discussion of the solution to the lifted system (7), (8), we rigorously re-derive it below using Fenchel duality theory. We emphasize, however, that it is not necessary for the lifting variable λ\lambda to admit an interpretation as the solution of a dual problem.

Dual problem and extremality conditions

To compute the dual optimization problem corresponding to (5) following [17], we write J(u)=F(∇u)+G(u)J(u)=F(\nabla u)+G(u) with F(ξ)=1p∫Ω∣ξ∣p dxF(\xi)=\frac{1}{p}\int_{\Omega}|\xi|^p\,dx and G(u)=−∫Ωfu dxG(u)=-\int_{\Omega}fu\,dx. Fenchel duality gives the dual functions F∗(λ)=1q∫Ω∣λ∣q dxF^*(\lambda)=\frac{1}{q}\int_{\Omega}|\lambda|^q\,dx and G∗(∇⋅λ)=0G^*(\nabla\cdot\lambda)=0 if −∇⋅λ−f=0-\nabla\cdot\lambda-f=0 and G∗(∇⋅λ)=∞G^*(\nabla\cdot\lambda)=\infty otherwise. Thus, the dual problem is

inf⁡λ 1q∫Ω∣λ∣q dxsubject to−∇⋅λ=f in Ω,\inf_{\lambda}\ \frac{1}{q}\int_{\Omega}|\lambda|^q\,dx \quad\text{subject to}\quad-\nabla\cdot\lambda=f\ \text{in }\Omega,

with λ\lambda in Wq(div⁡;Ω)W^{q}(\operatorname{div};\Omega). The corresponding extremality conditions connecting the primal and dual solutions are now exactly (7), (8), derived in an ad-hoc fashion before.

This nonlinear system in uu and λ\lambda can be written in several equivalent forms. For instance, recognizing that (8) implies ∣λ∣=∣∇u∣p−1|\lambda|=|\nabla u|^{p-1}, (8) is equivalent to ∇u=∣λ∣q−2λ\nabla u=|\lambda|^{q-2}\lambda. A similar, equivalent form for (8) is

∣∇u∣2−pλ−∇u=0.(9)|\nabla u|^{2-p}\lambda-\nabla u=0. \tag*{(9)}

While these forms are mathematically equivalent, they include pointwise nonlinear transformations. As a consequence, their linearizations, and thus the corresponding Newton methods, differ. We will, in the following, use (9).

Regularization and Newton methods

To avoid the singularity that occurs when ∇u=0\nabla u=0 and 1<p<21<p<2, we use the regularized norm ∣⋅∣ε|\cdot|_{\varepsilon} from (6) in the development of our Newton-type methods. Replacing ∣⋅∣|\cdot| by ∣⋅∣ε|\cdot|_{\varepsilon} in (5) results in the modified objective

Jε(u):=1p∫Ω∣∇u∣εp dx−∫Ωfu dx,(10)J_{\varepsilon}(u):=\frac{1}{p}\int_{\Omega}|\nabla u|_{\varepsilon}^{p}\,dx-\int_{\Omega}fu\,dx, \tag*{(10)}

and taking first variations yields the following functional r∈W−1,q(Ω)r\in W^{-1,q}(\Omega), i.e., the pp-Laplace equation residual:

r:=−∇⋅(∣∇u∣εp−2∇u)−f.(11)r:=-\nabla\cdot\left(|\nabla u|_{\varepsilon}^{p-2}\nabla u\right)-f. \tag*{(11)}

Integrating by parts shows that, for every v∈W01,p(Ω)v\in W^{1,p}_0(\Omega),

⟨r,v⟩=∫Ω∣∇u∣εp−2∇u⋅∇v dx−∫Ωfv dx=Jε′(u)v,(12)\langle r,v\rangle=\int_{\Omega}|\nabla u|_{\varepsilon}^{p-2}\nabla u\cdot\nabla v\,dx-\int_{\Omega}fv\,dx=J'_{\varepsilon}(u)v, \tag*{(12)}

i.e., rr is the derivative of JεJ_{\varepsilon}, regarded as an element of W−1,q(Ω)W^{-1,q}(\Omega). In the following we use whichever of the two viewpoints is more convenient: the energy derivative Jε′J'_{\varepsilon} where descent properties are at issue, and the residual rr when reporting computed quantities.

Introducing an independent variable λ\lambda as above results in the following regularized counterparts of (7), (8):

−∇⋅λ=fin Ω,(13)-\nabla\cdot\lambda=f \quad\text{in }\Omega, \tag*{(13)}
λ−∣∇u∣εp−2∇u=0in Ω.(14)\lambda-|\nabla u|_{\varepsilon}^{p-2}\nabla u=0 \quad\text{in }\Omega. \tag*{(14)}

Here, the regularized flux (14) is defined directly rather than through a dual problem; as noted above, such an interpretation is not required for the lifting. Since ∣∇u∣ε≥ε>0\lvert\nabla u\rvert_\varepsilon\ge\varepsilon> 0 for all x∈Ωx \in\Omega, (14) is equivalent to

∣∇u∣ε2−pλ−∇u=0.(15)\lvert\nabla u\rvert_\varepsilon^{2-p}\boldsymbol{\lambda}-\nabla u=0. \tag*{(15)}

We introduce the corresponding normalized directions

wε:=∇u∣∇u∣ε,wλ:=λ∣∇u∣εp−1,(16)\mathbf{w}_\varepsilon:= \frac{\nabla u}{\lvert\nabla u\rvert_\varepsilon}, \qquad\mathbf{w}_\lambda:= \frac{\boldsymbol{\lambda}}{\lvert\nabla u\rvert_\varepsilon^{p-1}}, \tag*{(16)}

and refer to wε\mathbf{w}_\varepsilon as the primal direction and to wλ\mathbf{w}_\lambda as the dual direction. The former is the regularized counterpart of the unit gradient direction wk\mathbf{w}_k used in (2); throughout this section, we suppress the iteration index. Note that wλ=wε\mathbf{w}_\lambda= \mathbf{w}_\varepsilon precisely when uu and λ\boldsymbol{\lambda} satisfy the optimality condition (14).

Treating uu and λ\boldsymbol{\lambda} as independent variables in (13) and (15), we can now derive the Newton step for this lifted system for the increments (u^,λ^)(\widehat{u},\widehat{\boldsymbol{\lambda}}):

−∇⋅λ^=f+∇⋅λ,(17)-\nabla\cdot\widehat{\boldsymbol{\lambda}}=f+\nabla\cdot\boldsymbol{\lambda}, \tag*{(17)}
[(2−p)wλwεT−I]∇u^+∣∇u∣ε2−pλ^=∇u−∣∇u∣ε2−pλ.(18)\left[(2-p)\mathbf{w}_\lambda\mathbf{w}_\varepsilon^{\mathsf{T}}-\mathbf{I}\right]\nabla\widehat{u}+\lvert\nabla u\rvert_\varepsilon^{2-p}\widehat{\boldsymbol{\lambda}}=\nabla u-\lvert\nabla u\rvert_\varepsilon^{2-p}\boldsymbol{\lambda}. \tag*{(18)}

The right hand side of (18) admits a simple interpretation in terms of the normalized directions (16), namely

∇u−∣∇u∣ε2−pλ=∣∇u∣ε(wε−wλ).\nabla u-\lvert\nabla u\rvert_\varepsilon^{2-p}\boldsymbol{\lambda}=\lvert\nabla u\rvert_\varepsilon(\mathbf{w}_\varepsilon-\mathbf{w}_\lambda).

Up to the scaling by ∣∇u∣ε\lvert\nabla u\rvert_\varepsilon, the residual of the optimality condition is thus precisely the mismatch between the primal and the dual directions, and the lifted Newton system is driven by how far the dual direction lags behind the primal one.

The system (17), (18) is formulated in terms of the lifted increments (u^,λ^)(\widehat{u},\widehat{\boldsymbol{\lambda}}) and therefore has a higher dimension than the original pp-Laplace equation. To avoid computing the Newton increment in the lifted space, we isolate the flux increment λ^\widehat{\boldsymbol{\lambda}} in equation (18) and obtain the pointwise relation

λ^=∣∇u∣εp−2(I+(p−2)wλwεT)∇u^−λ+∣∇u∣εp−2∇u.(19)\widehat{\boldsymbol{\lambda}}=\lvert\nabla u\rvert_\varepsilon^{p-2}\left(\mathbf{I}+(p-2)\mathbf{w}_\lambda\mathbf{w}_\varepsilon^{\mathsf{T}}\right)\nabla\widehat{u}-\boldsymbol{\lambda}+\lvert\nabla u\rvert_\varepsilon^{p-2}\nabla u. \tag*{(19)}

Using this in (17) and applying simple algebraic simplification results in a PDE in the Newton increment u^\widehat{u} only:

−∇⋅(∣∇u∣εp−2(I+(p−2)wλwεT)∇u^)=f+∇⋅(∣∇u∣εp−2∇u).(20)-\nabla\cdot\left(\lvert\nabla u\rvert_\varepsilon^{p-2}\left(\mathbf{I}+(p-2)\mathbf{w}_\lambda\mathbf{w}_\varepsilon^{\mathsf{T}}\right)\nabla\widehat{u}\right)=f+\nabla\cdot\left(\lvert\nabla u\rvert_\varepsilon^{p-2}\nabla u\right). \tag*{(20)}

Note that the right hand side of this equation is the negative equation residual rr defined in (11). Thus, if uu solves that equation, the increment u^\widehat{u} vanishes, as expected.

We compare this to the equation for the Newton increment for the original pp-Laplace equation without lifting, using the same regularization:

−∇⋅(∣∇u∣εp−2(I+(p−2)wεwεT)∇u^)=f+∇⋅(∣∇u∣εp−2∇u).(21)-\nabla\cdot\left(\lvert\nabla u\rvert_\varepsilon^{p-2}\left(\mathbf{I}+(p-2)\mathbf{w}_\varepsilon\mathbf{w}_\varepsilon^{\mathsf{T}}\right)\nabla\widehat{u}\right)=f+\nabla\cdot\left(\lvert\nabla u\rvert_\varepsilon^{p-2}\nabla u\right). \tag*{(21)}

Comparing (20) with (21), the two systems share the same right hand side. They only differ in one of the factors of the rank-one tensor: the lifted method uses the lagged dual direction wλ\mathbf{w}_\lambda, while standard Newton uses the primal direction wε\mathbf{w}_\varepsilon. In particular, the two linear systems coincide as soon as λ=∣∇u∣εp−2∇u\boldsymbol{\lambda}=\lvert\nabla u\rvert_\varepsilon^{p-2}\nabla u, which holds at convergence. However, as our numerical results will show, this minor change in (20) has a significant impact on the robustness of the convergence.

Note further that applying the above lift–linearize–eliminate procedure, without the transformation step, directly to (13), (14) rather than to (13), (15) results in the Newton step (21), i.e., the iteration one obtains by applying Newton’s method directly to the (regularized) pp-Laplace equation. The reason is that the lifted system is linear in λ\boldsymbol{\lambda}, and (14) can be solved explicitly for λ\boldsymbol{\lambda}.

Condensing the corresponding Newton system simply reproduces the chain rule, and one recovers the Newton step of the reduced equation. Introducing the lifting variable alone, therefore, has no effect on the iteration.

What does change the iteration is using (15) instead of (14), which multiplies the optimality condition by the factor ∣∇u∣ε2−p|\nabla u|_{\varepsilon}^{2-p}. Newton’s method is invariant under affine transformations F↦AFF \mapsto AF of the residual with a constant invertible AA [15]. Here, however, the factor depends on the current iterate, so this nonlinear rescaling falls outside the class of affine transformations and produces the genuinely different iteration (20). It is thus not the lifting itself but the nonlinear transformation performed before linearizing that yields the new method.

Modifications to ensure well-posedness

Since wεw_{\varepsilon} defined in (16) satisfies ∣wε∣≤1|w_{\varepsilon}| \le1, it can be seen that for the standard Newton linearization (21), the diffusion tensor ∣∇u∣εp−2(I+(p−2)wεwεT)∈Rd×d|\nabla u|_{\varepsilon}^{p-2}(I+(p-2)w_{\varepsilon}w_{\varepsilon}^{\mathsf{T}}) \in\mathbb{R}^{d \times d} is symmetric and positive definite for all x∈Ωx \in\Omega. As a consequence, (21), combined with appropriate boundary conditions, is a well-defined elliptic PDE. This is not automatically the case for (20). In particular, the diffusion tensor

I+(p−2)wλwεT(22)I+(p-2)w_{\lambda}w_{\varepsilon}^{\mathsf{T}} \tag*{(22)}

may fail to be positive definite, since p−2<0p-2<0 and the norm of wλw_{\lambda} is no longer bounded by one; in addition, it is not symmetric unless wλw_{\lambda} and wεw_{\varepsilon} are parallel. We address these two issues by suitably modifying the PDE operator. Note that altering the linear operator on the left-hand side of a Newton system may change the local rate of convergence. However, it does not change the underlying equation being solved, as long as its right hand side is given by the (negative) equation residual (11), as in (20).

The essential modification concerns positive definiteness. For z∈Rdz \in\mathbb{R}^{d}, the Cauchy–Schwarz inequality gives

zT(I+(p−2)wλwεT)z=∣z∣2+(p−2)(wλ⋅z)(wε⋅z)≥(1−(2−p)∣wλ∣∣wε∣)∣z∣2.(23)z^{\mathsf{T}}(I+(p-2)w_{\lambda}w_{\varepsilon}^{\mathsf{T}})z=|z|^{2}+(p-2)(w_{\lambda}\cdot z)(w_{\varepsilon}\cdot z)\geq(1-(2-p)|w_{\lambda}||w_{\varepsilon}|)|z|^{2}. \tag*{(23)}

Since ∣wε∣≤1|w_{\varepsilon}| \le1, positive definiteness is assured when (2−p)∣wλ∣<1(2-p)|w_{\lambda}|<1. We therefore enforce, for all x∈Ωx \in\Omega, the pointwise feasibility bound ∣wλ(x)∣≤β/(2−p)|w_{\lambda}(x)| \le\beta/(2-p), or equivalently

∣λ(x)∣≤β2−p∣∇u(x)∣εp−1,(24)|\lambda(x)|\leq\frac{\beta}{2-p}|\nabla u(x)|_{\varepsilon}^{p-1}, \tag*{(24)}

for a parameter β<1\beta<1, which we restrict further below. Combining (24) with (23) yields the two-sided bound

(1−β)∣z∣2≤zT(I+(p−2)wλwεT)z≤(1+β)∣z∣2,(25)(1-\beta)|z|^{2}\leq z^{\mathsf{T}}(I+(p-2)w_{\lambda}w_{\varepsilon}^{\mathsf{T}})z\leq(1+\beta)|z|^{2}, \tag*{(25)}

so that the diffusion tensor of (20) is uniformly positive definite whenever β<1\beta<1.

The parameter β\beta should not be chosen arbitrarily small. At convergence, we have wλ=wεw_{\lambda}=w_{\varepsilon} and ∣wε∣→1|w_{\varepsilon}|\to1 as ε→0\varepsilon\to0, so a value of β\beta with β/(2−p)<1\beta/(2-p)<1 would be active even at the solution of (13), (14). This would destroy the consistency wλ=wεw_{\lambda}=w_{\varepsilon} that is desirable for local fast convergence. We therefore require β/(2−p)>1\beta/(2-p)>1, which, together with β<1\beta<1, leaves the admissible, always nonempty window

2−p<β<1.(26)2-p<\beta<1. \tag*{(26)}

In practice, the feasibility bound is imposed by projecting the lifting variable; see (28).

The second modification is not needed for well-posedness, but is convenient in practice. It consists of replacing the rank-one matrix in (22) by its symmetric part, i.e., using

I+(p−2)sym⁡(wλwεT),sym⁡(B):=12(B+BT).(27)I+(p-2)\operatorname{sym}(w_{\lambda}w_{\varepsilon}^{\mathsf{T}}),\qquad\operatorname{sym}(B):=\frac{1}{2}(B+B^{\mathsf{T}}). \tag*{(27)}

This leaves the associated quadratic form—and hence the bounds (23) and (25) established above—unchanged. It does, however, render the discretized operator symmetric, allowing the use of symmetric solvers and preconditioners for the resulting linear systems. Observe that this modification has no effect at a consistent pair, where wλ=wεw_\lambda= w_\varepsilon and (22) is already symmetric.

Note that (25) is a statement about well-posedness, not about conditioning: since the lifted and the standard linearizations coincide at the solution, the two methods cannot differ in their asymptotic conditioning. What (25) does provide is a linear system that remains solvable, and an increment that remains a descent direction for JεJ_\varepsilon, no matter how far the dual direction lags behind the primal one. This is what underlies the global convergence result of the next section.

Summary of lifted Newton algorithm

Collecting the ingredients from the previous subsections yields the method we analyze and test below. We write wε,k:=∇uk/∣∇uk∣εw_{\varepsilon,k} := \nabla u_k/\lvert\nabla u_k\rvert_\varepsilon and wλ,k:=λk/∣∇uk∣εp−1w_{\lambda,k} := \lambda_k/\lvert\nabla u_k\rvert_\varepsilon^{p-1} for the directions (16) evaluated at the kk-th iterate, and recall the regularized objective (10) with corresponding (lifted) stationarity conditions (13), (14).

We assume that β\beta satisfies (26), and enforce the feasibility bound only at x∈Ωx \in\Omega where it is needed, namely in the construction of the diffusion tensor. We define

λkpr(x):=λk(x)max⁡(1,∣λk(x)∣/ρk(x)),ρk(x):=β2−p∣∇uk(x)∣εp−1,(28)\lambda_k^{\mathrm{pr}}(x) := \frac{\lambda_k(x)}{\max(1,\lvert\lambda_k(x)\rvert/\rho_k(x))}, \qquad\rho_k(x) := \frac{\beta}{2-p}\lvert\nabla u_k(x)\rvert_\varepsilon^{p-1}, \tag*{(28)}

so that ∣λkpr∣=min⁡(∣λk∣,ρk)\lvert\lambda_k^{\mathrm{pr}}\rvert= \min(\lvert\lambda_k\rvert,\rho_k) pointwise. The associated direction wλ,kpr:=λkpr/∣∇uk∣εp−1w_{\lambda,k}^{\mathrm{pr}} := \lambda_k^{\mathrm{pr}}/\lvert\nabla u_k\rvert_\varepsilon^{p-1} is thus the projection of wλ,kw_{\lambda,k} onto the ball of radius β/(2−p)\beta/(2-p), so that (24) holds at every iterate and for every λk\lambda_k. The method then proceeds as follows.

(i) Initialize: set k=0k = 0, initialize u0u_0 such that it satisfies the desired nonhomogeneous Dirichlet boundary conditions as in (4), initialize λ0\lambda_0, and choose the Armijo parameter γ∈(0,1)\gamma\in(0,1).

(ii) Assemble and solve: use the symmetrized diffusion tensor (27) with the projected direction,

Mk:=∣∇uk∣εp−2(I+(p−2)sym⁡(wλ,kprwε,kT)),(29)M_k := \lvert\nabla u_k\rvert_\varepsilon^{p-2}\left(I + (p-2)\operatorname{sym}(w_{\lambda,k}^{\mathrm{pr}}w_{\varepsilon,k}^{\mathsf T})\right), \tag*{(29)}

to assemble and solve the system for the primal increment u^k\hat{u}_k, i.e., solve (20) with diffusion tensor MkM_k and homogeneous Dirichlet boundary conditions.

(iii) Recover: compute the lifting variable increment pointwise from (19),

λ^k:=Mk∇u^k−λk+∣∇uk∣εp−2∇uk.(30)\hat{\lambda}_k := M_k\nabla\hat{u}_k-\lambda_k+\lvert\nabla u_k\rvert_\varepsilon^{p-2}\nabla u_k. \tag*{(30)}

(iv) Line search: choose αk\alpha_k as the largest number in {1,1/2,1/22,…}\{1,1/2,1/2^2,\ldots\} with

Jε(uk+αku^k)≤Jε(uk)+γαkJε′(uk)u^k.(31)J_\varepsilon(u_k+\alpha_k\hat{u}_k)\leq J_\varepsilon(u_k)+\gamma\alpha_k J_\varepsilon'(u_k)\hat{u}_k. \tag*{(31)}

(v) Update and advance: set uk+1:=uk+αku^ku_{k+1}:=u_k+\alpha_k\hat{u}_k and λk+1:=λk+αkλ^k\lambda_{k+1}:=\lambda_k+\alpha_k\hat{\lambda}_k. Set k←k+1k\leftarrow k+1 and return to step (ii), until a stopping criterion is met.

Several things should be pointed out. First, eliminating λ^\hat{\lambda} from the lifted system cancels λk\lambda_k from the right-hand side of the system solved in step (ii), so the lifting variable influences the primal iterate only through MkM_k. Projecting it there is therefore enough, and no constraint needs to be placed on λk\lambda_k itself. One may also project λk\lambda_k after each update; this variant of the algorithm is briefly discussed in Appendix A. Second, MkM_k is symmetric and, by (25), uniformly positive definite for every kk and every initial guess λ0\lambda_0. Since β>2−p\beta> 2-p, the projection (28) is inactive whenever λk\lambda_k is close to satisfying (14), and in particular in a neighborhood of the solution; it acts only during the initial phase of the iteration. Third, initializing the lifting variable by λ0=0\lambda_0 = 0 makes the rank-one term vanish, so that M0=∣∇u0∣p−2IM_0 = |\nabla u_0|^{p-2}I and the first iterate is a Picard step (3), known to be a robust choice. Note finally that only step (ii) requires a linear solve; steps (iii) and (v) are pointwise algebraic operations on ∇uk\nabla u_k and λk\boldsymbol{\lambda}_k, so the cost of one lifted Newton iteration is essentially that of one standard Newton (or Picard) iteration.

Analysis of the lifted method

In this section, we analyze the lifted Newton iteration of section 2.4 for the pp-Laplace equation with 1<p<21 < p < 2. We work in the discretized setting to show global convergence with line search and fast local convergence in sections 3.1 and 3.2. Both results also hold for the standard Newton method. The greater robustness of lifted Newton away from the solution and for p→1p \to1 is not captured by these results. In section 3.3, we discuss the mechanism behind this difference, which we make precise for a one-dimensional model problem in Appendix B.

Global convergence for discretized method

Proving global convergence of Newton’s methods to solve nonlinear PDEs such as the pp-Laplace equation in infinite dimensions is very challenging due to the lack of Hilbert space structure. One remedy, followed in [36] for the pp-Stokes system, is to use Hilbert space regularization. That is, in addition to the regularization ∣∇u∣ε|\nabla u|_\varepsilon, a term μ0∥∇u∥L22\mu_0\|\nabla u\|_{L^2}^2 with μ0>0\mu_0 > 0 is added to the energy, which places the problem in H1H^1. We take a different approach and establish global convergence for the discretized problem, that is, in a finite-dimensional setting: after fixing VhV_h, compactness of the discrete energy sublevel set provides the coercivity constant that the H1H^1 term provides in [36]. The proof follows the same Armijo framework. Although this avoids the need for extra regularization, it comes with the drawback that the constants may depend on the discretization.

Let Vh⊂W1,∞(Ω)V_h \subset W^{1,\infty}(\Omega) be a fixed conforming finite element space and let V˚h:=Vh∩W01,2(Ω)\mathring{V}_h := V_h \cap W_0^{1,2}(\Omega). We equip V˚h\mathring{V}_h with the H1H^1 seminorm ∥uh∥h:=∥∇uh∥L2(Ω)\|u_h\|_h := \|\nabla u_h\|_{L^2(\Omega)}. We use V˚h⋆\mathring{V}_h^\star to denote the dual space of V˚h\mathring{V}_h, and denote its norm by ∥⋅∥h,⋆\|\cdot\|_{h,\star}. We study the lifted Newton iteration of section 2.4, discretized in V˚h\mathring{V}_h. We consider an extension of the Dirichlet data gg to the domain Ω\Omega and an iteration uk∈g+V˚hu_k \in g + \mathring{V}_h with a lifting variable λk\boldsymbol{\lambda}_k. Then, the increment u^k∈V˚h\widehat{u}_k \in\mathring{V}_h of step (ii) is determined by solving the finite element approximation of (20) with the diffusion tensor MkM_k as in (29); the remaining steps (iii)–(v) are carried out unchanged. We denote by rh,k∈V˚h⋆r_{h,k} \in\mathring{V}_h^\star the discrete residual at the iterate uh,ku_{h,k}, i.e., the restriction to V˚h\mathring{V}_h of the functional (11). By (12) it satisfies ⟨rh,k,vh⟩=Jε′(uh,k)vh\langle r_{h,k},v_h\rangle= J_\varepsilon'(u_{h,k})v_h for all vh∈V˚hv_h \in\mathring{V}_h. Since ∥vh∥h=∥∇vh∥L2(Ω)\|v_h\|_h = \|\nabla v_h\|_{L^2(\Omega)}, the dual norm ∥⋅∥h,⋆\|\cdot\|_{h,\star} used below is the H−1H^{-1} norm reported in the numerical experiments of section 4. A global convergence result in finite dimensions, similar as presented below, also applies to the standard Newton method. Thus, the main point of the following theorem is that a global convergence analysis also holds for the lifted Newton method from section 2.4.

Theorem 1 (Global convergence of the lifted method) Let β\beta satisfy (26) and assume arbitrary initializations uh,0∈g+V˚hu_{h,0} \in g + \mathring{V}_h and λh,0\boldsymbol{\lambda}_{h,0}. Then the (discrete) iterates produced by the iteration of section 2.4 converge globally, in the sense that the discrete residual rh,k→0r_{h,k} \to0 in V˚h⋆\mathring{V}_h^\star, and

uh,k→uh⋆in Vh,u_{h,k} \to u_h^\star\quad\text{in } V_h,

where uh⋆∈g+V˚hu_h^\star\in g + \mathring{V}_h is the unique minimizer of JεJ_\varepsilon over g+V˚hg + \mathring{V}_h.

Proof. Consider the sublevel set Lh:={uh∈g+V˚h:Jε(uh)≤Jε(u0)}\mathcal{L}_h := \{u_h \in g + \mathring{V}_h : J_\varepsilon(u_h) \leq J_\varepsilon(u_0)\}, which is bounded because Jε(uh)→∞J_\varepsilon(u_h) \to\infty as ∥uh∥h→∞\|u_h\|_h \to\infty. Since VhV_h is finite-dimensional, Lh\mathcal{L}_h is compact, and therefore Ch:=max⁡uh∈Lh∥∇uh∥L∞(Ω)<∞C_h := \max_{u_h \in\mathcal{L}_h} \|\nabla u_h\|_{L^\infty(\Omega)} < \infty. We prove the uniform boundedness and coercivity of the linearization resulting from the lifting approach on the sublevel set. To this end, suppose that uh,k∈Lhu_{h,k} \in\mathcal{L}_h. We first derive pointwise spectral bounds for MkM_k defined in (29). For any z∈Rdz \in\mathbb{R}^d, (25) gives

z⊤Mkz≥(1−β)∣∇uh,k∣εp−2∣z∣2≥mh∣z∣2,(32)z^{\top}M_kz \ge(1-\beta)|\nabla u_{h,k}|_{\varepsilon}^{p-2}|z|^2 \ge m_h|z|^2, \tag*{(32)}
z⊤Mkz≤(1+β)∣∇uh,k∣εp−2∣z∣2≤m‾h∣z∣2,z^{\top}M_kz \le(1+\beta)|\nabla u_{h,k}|_{\varepsilon}^{p-2}|z|^2 \le\overline{m}_h|z|^2,

where mh:=(1−β)(Ch2+ε2)(p−2)/2m_h := (1-\beta)(C_h^2+\varepsilon^2)^{(p-2)/2} and m‾h:=(1+β)εp−2\overline{m}_h := (1+\beta)\varepsilon^{p-2}. Denoting

ak(vh,wh):=∫ΩMk∇vh⋅∇wh dx,a_k(v_h,w_h) := \int_{\Omega} M_k\nabla v_h\cdot\nabla w_h\,\mathrm{d}x,

we thus have

ak(vh,vh)≥mh∥vh∥h2,∣ak(vh,wh)∣≤m‾h∥vh∥h∥wh∥hfor all vh,wh∈V˚h.(33)a_k(v_h,v_h)\ge m_h\lVert v_h\rVert_h^2,\qquad|a_k(v_h,w_h)|\le\overline{m}_h\lVert v_h\rVert_h\lVert w_h\rVert_h\quad\text{for all }v_h,w_h\in\mathring{V}_h. \tag*{(33)}

The pointwise bounds (33) imply that aka_k defines an inner product on V˚h\mathring{V}_h, so the primal increment is uniquely defined by ak(u^h,k,vh)=−Jε′(uh,k)vha_k(\hat{u}_{h,k},v_h)=-J_{\varepsilon}'(u_{h,k})v_h for all vh∈V˚hv_h\in\mathring{V}_h. Choosing vh=u^h,kv_h=\hat{u}_{h,k} gives

Jε′(uh,k)u^h,k=−ak(u^h,k,u^h,k).(34)J_{\varepsilon}'(u_{h,k})\hat{u}_{h,k}=-a_k(\hat{u}_{h,k},\hat{u}_{h,k}). \tag*{(34)}

If u^h,k=0\hat{u}_{h,k}=0, then Jε′(uh,k)=0J_{\varepsilon}'(u_{h,k})=0 on V˚h\mathring{V}_h, and strict convexity shows that uh,k=uh∗u_{h,k}=u_h^*. We may therefore assume below that u^h,k≠0\hat{u}_{h,k}\ne0.

Next, we bound the energy along the search direction. Since p<2p<2, the map t↦tp/2t\mapsto t^{p/2} is concave and thus lies below its tangent line at any t0>0t_0>0. Applying this pointwise with t0=∣∇uh∣ε2t_0=|\nabla u_h|_{\varepsilon}^2 and t=∣∇uh+α∇vh∣ε2t=|\nabla u_h+\alpha\nabla v_h|_{\varepsilon}^2, whose difference is 2α∇uh⋅∇vh+α2∣∇vh∣22\alpha\nabla u_h\cdot\nabla v_h+\alpha^2|\nabla v_h|^2, then dividing by pp, integrating, and adding the linear load term to both sides gives

Jε(uh+αvh)≤Jε(uh)+αJε′(uh)vh+α22∫Ω∣∇uh∣εp−2∣∇vh∣2 dx(35)J_{\varepsilon}(u_h+\alpha v_h)\le J_{\varepsilon}(u_h)+\alpha J_{\varepsilon}'(u_h)v_h+\frac{\alpha^2}{2}\int_{\Omega}|\nabla u_h|_{\varepsilon}^{p-2}|\nabla v_h|^2\,\mathrm{d}x \tag*{(35)}

for all uh∈g+V˚hu_h\in g+\mathring{V}_h, vh∈V˚hv_h\in\mathring{V}_h, and α≥0\alpha\ge0. Note that the last term in (35) is the bilinear form of the Picard iteration (3), which majorizes the curvature of JεJ_{\varepsilon} because p<2p<2. The estimate (35) holds globally in α\alpha and involves no remainder term.

We now take uh=uh,ku_h=u_{h,k} and vh=u^h,kv_h=\hat{u}_{h,k}. The lower bound in (25) gives

∫Ω∣∇uh,k∣εp−2∣∇u^h,k∣2 dx≤11−βak(u^h,k,u^h,k),\int_{\Omega}|\nabla u_{h,k}|_{\varepsilon}^{p-2}|\nabla\hat{u}_{h,k}|^2\,\mathrm{d}x\le\frac{1}{1-\beta}a_k(\hat{u}_{h,k},\hat{u}_{h,k}),

so that (35) and (34) yield, for every α≥0\alpha\ge0,

Jε(uh,k+αu^h,k)≤Jε(uh,k)−α(1−α2(1−β))ak(u^h,k,u^h,k).(36)J_{\varepsilon}(u_{h,k}+\alpha\hat{u}_{h,k})\le J_{\varepsilon}(u_{h,k})-\alpha\left(1-\frac{\alpha}{2(1-\beta)}\right)a_k(\hat{u}_{h,k},\hat{u}_{h,k}). \tag*{(36)}

By (34), the Armijo condition (31) requires a decrease of at least γαak(u^h,k,u^h,k)\gamma\alpha a_k(\hat{u}_{h,k},\hat{u}_{h,k}). Comparing with (36), it is therefore satisfied as soon as the bracket is at least γ\gamma, that is, whenever 0<α≤2(1−γ)(1−β)0<\alpha\le2(1-\gamma)(1-\beta). Since the line search halves the trial step starting from α=1\alpha=1, it terminates with an accepted step size αk≥α‾:=(1−γ)(1−β)>0\alpha_k\ge\underline{\alpha}:=(1-\gamma)(1-\beta)>0. Since (31) and (34) give Jε(uh,k+1)≤Jε(uh,k)J_{\varepsilon}(u_{h,k+1})\le J_{\varepsilon}(u_{h,k}), starting from uh,0∈Lhu_{h,0}\in\mathcal{L}_h, induction therefore proves that the iteration is well defined and that every uh,ku_{h,k} remains in Lh\mathcal{L}_h. Using (34), (31), and the lower bound on α\alpha, we obtain

Jε(uh,k)−Jε(uh,k+1)≥γα‾ak(u^h,k,u^h,k).J_{\varepsilon}(u_{h,k})-J_{\varepsilon}(u_{h,k+1})\ge\gamma\underline{\alpha}a_k(\hat{u}_{h,k},\hat{u}_{h,k}).

Since JεJ_{\varepsilon} is bounded below, summation over kk shows that ak(u^h,k,u^h,k)→0a_k(\hat{u}_{h,k},\hat{u}_{h,k})\to0. Cauchy–Schwarz in the aka_k-inner product and the upper bound in (33) give, for every vh∈V˚hv_h\in\mathring{V}_h,

∣Jε′(uh,k)vh∣2=∣ak(u^h,k,vh)∣2≤m‾hak(u^h,k,u^h,k)∥vh∥h2,(37)|J_{\varepsilon}'(u_{h,k})v_h|^2=|a_k(\hat{u}_{h,k},v_h)|^2\le\overline{m}_h a_k(\hat{u}_{h,k},\hat{u}_{h,k})\lVert v_h\rVert_h^2, \tag*{(37)}

so that rh,k→0r_{h,k} \to0 in V˚h⋆\mathring{V}_h^\star by [12]. Compactness of Lh\mathcal{L}_h and strict convexity of JεJ_\varepsilon then prove uh,k→uh⋆u_{h,k} \to u_h^\star in VhV_h.

Next, we prove the convergence of the discretized lifting variable λh,k\lambda_{h,k}. The discretized lifting variable is defined at the quadrature points by xq\boldsymbol{x}_q, q=1,…,NQq = 1,\ldots,N_Q and it is thus an element of (Rd)NQ(\mathbb{R}^d)^{N_Q}. We denote λh,k;q:=λh,k(xq)\lambda_{h,k;q} := \lambda_{h,k}(\boldsymbol{x}_q) and more details on the practical implementation are provided in section 4.1. Convergence in a finite-dimensional space is equivalent to componentwise convergence, which is what we show below. For ξ∈Rd\xi\in\mathbb{R}^d, we define S(ξ):=∣ξ∣εp−2ξS(\xi) := |\xi|_\varepsilon^{p-2}\xi.

Corollary 2 (Pointwise convergence of the lifting variable) Under the assumptions of theorem 1, for every q=1,…,NQq = 1,\ldots,N_Q,

λh,k;q⟶S(∇uh⋆(xq))in Rd.\lambda_{h,k;q} \longrightarrow S\left(\nabla u_h^\star(\boldsymbol{x}_q)\right) \quad\text{in } \mathbb{R}^d.

Proof. For a fixed qq, let Sk:=S(∇uh,k(xq))S_k := S(\nabla u_{h,k}(\boldsymbol{x}_q)), and S⋆:=S(∇uh⋆(xq))S^\star:= S(\nabla u_h^\star(\boldsymbol{x}_q)). Since cell-local gradient evaluation is continuous on the fixed finite-dimensional space VhV_h, and SS is continuous, the convergence uh,k→uh⋆u_{h,k} \to u_h^\star gives ∇uh,k(xq)→∇uh⋆(xq)\nabla u_{h,k}(\boldsymbol{x}_q) \to\nabla u_h^\star(\boldsymbol{x}_q), and thus

Sk→S⋆,∇(uh,k+1−uh,k)(xq)→0.S_k \to S^\star,\qquad\nabla(u_{h,k+1}-u_{h,k})(\boldsymbol{x}_q) \to0.

At the same quadrature point, (30) and step (v) of section 2.4 give

λh,k+1;q−Sk+1=(1−αk)(λh,k;q−Sk)+(Sk−Sk+1)+Mk(xq)∇(uh,k+1−uh,k)(xq).\lambda_{h,k+1;q}-S_{k+1}=(1-\alpha_k)(\lambda_{h,k;q}-S_k)+(S_k-S_{k+1})+M_k(\boldsymbol{x}_q)\nabla(u_{h,k+1}-u_{h,k})(\boldsymbol{x}_q).

By the upper bound in (32), for every z∈Rdz \in\mathbb{R}^d, we have ∣Mk(xq)z∣≤m‾h∣z∣|M_k(\boldsymbol{x}_q)z| \le\overline{m}_h|z|. Moreover, the proof of theorem 1 showed that αk≥α>0\alpha_k \ge\alpha> 0. Thus, with

ek:=∣λh,k;q−Sk∣,bk:=∣Sk+1−Sk∣+m‾h∣∇(uh,k+1−uh,k)(xq)∣e_k := |\lambda_{h,k;q}-S_k|,\qquad b_k := |S_{k+1}-S_k|+\overline{m}_h|\nabla(u_{h,k+1}-u_{h,k})(\boldsymbol{x}_q)|

we have

ek+1≤(1−α)ek+bk.(38)e_{k+1} \le(1-\alpha)e_k+b_k. \tag*{(38)}

Here bk→0b_k \to0 by the convergence statements above. Since in addition 1−α<11-\alpha< 1, this gives ek→0e_k \to0, and the pointwise convergence now follows from Sk→S⋆S_k \to S^\star.

Note that the coercivity constant mhm_h depends on the bound ChC_h, which comes from the compactness of the fixed finite element sublevel set. In the continuous space, an energy sublevel set gives an LpL^p-bound but not an L∞L^\infty-bound on ∇u\nabla u. Therefore, the same argument does not yield a mesh-independent coercivity constant for MkM_k on H01(Ω)H_0^1(\Omega) unless one adds an additional uniformly elliptic term as in [36] or assumes a priori an L∞L^\infty bound on the gradients.

Local convergence for discretized problem

Recall that the lifted method was derived as a Newton method in lifted space, and that the resulting Newton method coincides with the standard Newton method at the solution, where wλ=wεw_\lambda= w_\varepsilon. For these reasons, one can expect the lifted method to inherit the fast local convergence of the standard Newton method. However, it must be shown that the linear operator arising in the lifted Newton method approaches the exact one fast enough. Measuring the primal error together with the inconsistency of the pair (uh,k,λh,k)(u_{h,k},\lambda_{h,k}) in (14),

Ek:=∥uh,k−uh⋆∥h+∥λh,k−S(∇uh,k)∥∞,(39)\mathcal{E}_k := \lVert u_{h,k}-u_h^\star\rVert_h+\lVert\lambda_{h,k}-S(\nabla u_{h,k})\rVert_\infty, \tag*{(39)}

we show below that the rate is quadratic. We will refer to standard arguments from the literature and use two ingredients specific to the lifted method. The standard ingredients are the local convergence of Newton’s method with a perturbed Jacobian [23] and the acceptance of unit steps by the Armijo line search [31]. The specific ingredients are a bound on the perturbation of the Jacobian in terms of the inconsistency δk\delta_k of the pair (uh,k,λh,k)(u_{h,k},\lambda_{h,k}), and the observation that the lifting variable update reduces this inconsistency quadratically.

Below, all pointwise quantities (λh,k,Mk,∇uh,k)(\lambda_{h,k}, M_k, \nabla u_{h,k}) are evaluated at the quadrature points xqx_q, and ∥⋅∥∞\|\cdot\|_\infty is the maximum over these points; we write δk\delta_k for the second term in (39). Since VhV_h is finite-dimensional, there is a constant CinvC_{\mathrm{inv}} with ∥∇vh∥∞≤Cinv∥vh∥h\|\nabla v_h\|_\infty\le C_{\mathrm{inv}}\|v_h\|_h for all vh∈Vhv_h \in V_h. Since ε>0\varepsilon> 0, the map SS of corollary 2 is smooth, with

S′(ξ)=∣ξ∣εp−2(I+(p−2)wwT),w:=ξ∣ξ∣ε,(40)S'(\xi) = |\xi|_\varepsilon^{p-2}\left(I + (p-2)ww^\mathsf{T}\right), \qquad w := \frac{\xi}{|\xi|_\varepsilon}, \tag*{(40)}

which is the diffusion tensor of standard Newton (21), and ∥S′(ξ)∥≤εp−2\|S'(\xi)\| \le\varepsilon^{p-2} and ∥S′′(ξ)∥≤Cpεp−3\|S''(\xi)\| \le C_p\varepsilon^{p-3} for all ξ∈Rd\xi\in\mathbb{R}^d. We write Hk:=S′(∇uh,k)H_k := S'(\nabla u_{h,k}) for the standard Newton tensor at the kk-th iterate. All constants below depend only on hh, ε\varepsilon, pp, β\beta and γ\gamma.

Lemma 3 (Jacobian error) For every kk,

∥Mk−Hk∥∞≤2−pεδk.(41)\|M_k-H_k\|_\infty\le\frac{2-p}{\varepsilon}\delta_k. \tag*{(41)}

Proof. Comparing (29) and (40), Mk−Hk=(p−2)∣∇uh,k∣εp−2sym⁡((wλ,kpr−wε,k)wε,kT)M_k-H_k=(p-2)|\nabla u_{h,k}|_\varepsilon^{p-2}\operatorname{sym}\left((w_{\lambda,k}^{\mathrm{pr}}-w_{\varepsilon,k})w_{\varepsilon,k}^{\mathsf{T}}\right). Since ∣wε,k∣<1<β/(2−p)|w_{\varepsilon,k}|<1<\beta/(2-p) by (26), the projection (28) leaves wε,kw_{\varepsilon,k} fixed and is 1-Lipschitz, so that ∣wλ,kpr−wε,k∣≤∣wλ,k−wε,k∣=∣λh,k−S(∇uh,k)∣/∣∇uh,k∣εp−1|w_{\lambda,k}^{\mathrm{pr}}-w_{\varepsilon,k}|\le|w_{\lambda,k}-w_{\varepsilon,k}|=|\lambda_{h,k}-S(\nabla u_{h,k})|/|\nabla u_{h,k}|_\varepsilon^{p-1}. Using ∥sym⁡(abT)∥≤∣a∣∣b∣\|\operatorname{sym}(ab^\mathsf{T})\|\le|a||b| and ∣∇uh,k∣ε≥ε|\nabla u_{h,k}|_\varepsilon\ge\varepsilon gives (41). □

The second ingredient concerns the lifting variable. Suppose that a unit step is taken, αk=1\alpha_k=1. Then (30) and step (v) of section 2.4 give λh,k+1=λh,k+λ^h,k=S(∇uh,k)+Mk∇u^h,k\lambda_{h,k+1}=\lambda_{h,k}+\widehat{\lambda}_{h,k}=S(\nabla u_{h,k})+M_k\nabla\widehat{u}_{h,k}, whereas Taylor expansion of SS gives S(∇uh,k+1)=S(∇uh,k)+Hk∇u^h,k+RkS(\nabla u_{h,k+1})=S(\nabla u_{h,k})+H_k\nabla\widehat{u}_{h,k}+R_k with ∥Rk∥∞≤Cpεp−3∥∇u^h,k∥∞2\|R_k\|_\infty\le C_p\varepsilon^{p-3}\|\nabla\widehat{u}_{h,k}\|_\infty^2. Subtracting the two identities, the first-order terms cancel, and we obtain

λh,k+1−S(∇uh,k+1)=(Mk−Hk)∇u^h,k+Rk.(42)\lambda_{h,k+1}-S(\nabla u_{h,k+1})=(M_k-H_k)\nabla\widehat{u}_{h,k}+R_k. \tag*{(42)}

This cancellation makes the method second order: the lifting variable update (30) adds to λh,k\lambda_{h,k} exactly the first-order change of S(∇uh,k)S(\nabla u_{h,k}), up to the Jacobian error. Together with (41) and the inverse estimate, (42) yields

δk+1≤C(δk+∥u^h,k∥h)∥u^h,k∥h.(43)\delta_{k+1}\le C\left(\delta_k+\|\widehat{u}_{h,k}\|_h\right)\|\widehat{u}_{h,k}\|_h. \tag*{(43)}

Theorem 4 (Local quadratic convergence) Let the assumptions of theorem 1 hold and let the Armijo parameter satisfy γ<12\gamma<\frac{1}{2}. Then there exist ρ>0\rho>0 and C⋆>0C^\star>0, independent of kk, such that Ek≤ρ\mathcal{E}_k\le\rho implies αk=1\alpha_k=1 and

Ek+1≤C⋆Ek2.(44)\mathcal{E}_{k+1}\le C^\star\mathcal{E}_k^2. \tag*{(44)}

In particular, since Ek→0\mathcal{E}_k\to0 by theorem 1 and corollary 2, the iteration eventually takes unit steps and converges quadratically.

Proof. Consider the discrete residual Fh(uh):=J′(uh)∣V˚hF_h(u_h):=J'(u_h)|_{\mathring{V}_h} on the finite-dimensional space g+V˚hg+\mathring{V}_h with norm ∥⋅∥h\|\cdot\|_h. Its Jacobian at uh,ku_{h,k} is the operator induced by the bilinear form ∫ΩHk∇vh⋅∇wh dx\int_\Omega H_k\nabla v_h\cdot\nabla w_h\,dx; it is Lipschitz continuous by the bound on S′′S'' and the inverse estimate, and Fh′(uh⋆)F'_h(u_h^\star) is invertible since HkH_k is uniformly positive definite. The primal increment satisfies u^h,k=−Bk−1Fh′(uh,k)\widehat{u}_{h,k}=-B_k^{-1}F'_h(u_{h,k}), where BkB_k is the operator induced by aka_k, so the primal iteration is a Newton method with the perturbed Jacobian Bk=Fh′(uh,k)+ΔkB_k=F'_h(u_{h,k})+\Delta_k, with ∥Δk∥≤∥Mk−Hk∥∞≤2−pεδk\|\Delta_k\|\le\|M_k-H_k\|_\infty\le\frac{2-p}{\varepsilon}\delta_k by lemma 3. Moreover, by (34), (33), Fh(uh⋆)=0F_h(u_h^\star)=0 and ∥S′∥≤εp−2\|S'\|\le\varepsilon^{p-2},

∥u^h,k∥h≤εp−2mh∥uh,k−uh⋆∥h.(45)\|\widehat{u}_{h,k}\|_h\le\frac{\varepsilon^{p-2}}{m_h}\|u_{h,k}-u_h^\star\|_h. \tag*{(45)}

Since γ<12\gamma< \frac{1}{2} and u^h,k\hat{u}_{h,k} is a descent direction by [34], the sufficient decrease condition (31) holds at α=1\alpha= 1 as soon as ∥uh,k−uh∗∥h\|u_{h,k} - u_h^*\|_h and the relative Jacobian perturbation ∥Δku^h,k∥h,⋆/∥u^h,k∥h≤∥Δk∥\|\Delta_k\hat{u}_{h,k}\|_{h,\star}/\|\hat{u}_{h,k}\|_h \leq\|\Delta_k\| are small enough; see the proof of [31], Theorem 3.6, which only uses the Armijo condition. Both quantities are bounded by CEkC\mathcal{E}_k, so there is ρ>0\rho> 0 such that Ek≤ρ\mathcal{E}_k \leq\rho implies αk=1\alpha_k = 1. With αk=1\alpha_k = 1, the perturbed-Jacobian estimate of [23], Theorem 5.4.1 gives, for Ek≤ρ\mathcal{E}_k \leq\rho (after decreasing ρ\rho if necessary),

∥uh,k+1−uh∗∥h≤K(∥uh,k−uh∗∥h2+∥Δk∥∥uh,k−uh∗∥h)≤CEk2.\|u_{h,k+1} - u_h^*\|_h \leq K\left(\|u_{h,k} - u_h^*\|_h^2 + \|\Delta_k\|\|u_{h,k} - u_h^*\|_h\right) \leq C\mathcal{E}_k^2.

By (42) and (44), δk+1≤C(δk+∥uh,k−uh∗∥h)∥uh,k−uh∗∥h≤CEk2\delta_{k+1} \leq C(\delta_k + \|u_{h,k} - u_h^*\|_h)\|u_{h,k} - u_h^*\|_h \leq C\mathcal{E}_k^2. Adding the two estimates gives (43). □

The constant C⋆C_\star degrades in the two limits that make the problem hard: through the factor (2−p)/ε(2-p)/\varepsilon in (40) and the factor εp−3\varepsilon^{p-3} in (41) as ε→0\varepsilon\to0, and through mhm_h, which carries 1−β<p−11-\beta< p-1 by (26), as p→1p \to1. The same dependence on ε\varepsilon and pp is present in the corresponding constants for the standard Newton method.

Robustness away from the solution

Since the results of sections 3.1 and 3.2 apply equally to standard Newton, the difference between the two methods observed in practice must arise away from the solution. We next discuss the properties of the two linearizations, focusing on values of pp near 1, where solving (4) is particularly difficult.

Prevalence of ε\varepsilon-flat regions. First, note that solutions of the pp-Laplace equation exhibit largely flat regions, especially when pp is close to 1. This is evident from the energy formulation (5), which converges to the L1L^1-norm of the gradient as p→1p \to1. Such objectives promote sparsity, meaning the gradient vanishes over large parts of the domain and variation concentrates on small sets. In the ε\varepsilon-regularized problem, the relevant notion of flatness corresponds to values of ∣∇u∣|\nabla u| of an order of magnitude of ε\varepsilon or smaller. This is the threshold used in the discussion below.

Instability of standard Newton. Next, it is useful to separate the two distinct ways in which flat regions affect the linearizations. The first is through the scalar prefactor ∣∇u∣εp−2|\nabla u|_\varepsilon^{p-2}, which is common to all methods considered here and thus cannot account for differences between them. The second is through the direction wε=∇u/∣∇u∣εw_\varepsilon= \nabla u/|\nabla u|_\varepsilon entering the rank-one term. Where ∣∇u∣≫ε|\nabla u| \gg\varepsilon, this direction is influential but well determined and varies smoothly. In deeply flat regions, ∣∇u∣≪ε|\nabla u| \ll\varepsilon, it is poorly determined and highly sensitive to changes in uu, but it is also of little influence since ∣wε∣≤∣∇u∣/ε|w_\varepsilon| \leq|\nabla u|/\varepsilon suppresses the rank-one term and the Newton methods reduce to the Picard operator. It is when ∣∇u∣∼ε|\nabla u| \sim\varepsilon that wεw_\varepsilon is simultaneously influential and highly sensitive to small changes in uu. The two methods respond differently to this sensitivity. In the standard Newton method, the rank-one term is wεwεTw_\varepsilon w_\varepsilon^{\mathsf{T}} and both of its factors are recomputed from the current iterate. The Newton direction u^\hat{u} may then vary strongly from one iteration to the next, a phenomenon known as zig-zag behavior, which typically makes substantial damping of the step size necessary for convergence. In the lifted method, λ\lambda is updated only through (30), so the factor wεw_\varepsilon lags behind wεw_\varepsilon. This matters quantitatively: in the direction of ∇u\nabla u, the standard Newton tensor has eigenvalue (p−1)∣∇u∣εp−2(p-1)|\nabla u|_\varepsilon^{p-2}, i.e., it is 1/(p−1)1/(p-1) times more compliant than the Picard operator exactly where the residual points in flat regions, whereas with a small lagged λ\lambda the lifted tensor stays close to the Picard operator. The linearization in lifted Newton thus filters these fluctuations, an effect that decays as the iterates approach consistency and is therefore confined to the phase of the iteration before the Newton convergence basin is reached.

An illustrative 1D pp-Laplace problem. Appendix B analyses a one-dimensional problem, discretized with finite differences, whose solution is constructed to have a plateau. Expanding both linearizations in the small parameter p−1p-1 shows that, on the plateau, standard and lifted Newton compute the same increment of the flux ∣∇u∣εp−2∇u|\nabla u|_\varepsilon^{p-2}\nabla u, namely the one that drives it to zero. They differ in how this flux increment is converted into an increment of ∇u\nabla u (note that here ∇u=u′\nabla u = u'): standard Newton divides by the tangent slope (p−1)/∣∇u∣(p-1)/|\nabla u| of the nearly flat constitutive function, so that every gradient on the plateau changes sign and grows by a factor 1/(p−1)1/(p-1), whereas lifted Newton with a small lagged λ\boldsymbol{\lambda} divides by the secant slope 1/∣∇u∣1/\lvert\nabla u\rvert and sets the plateau gradients to zero up to O(p−1)O(p-1) in one step. The update of the lifting variable then yields λ=O(p−1)\boldsymbol{\lambda}=O(p-1) on the plateau from the first iteration on. Figure 1 shows both iterations for p=1.01p=1.01 and a random initialization within an interval of length 0.10.1 around the solution: standard Newton exhibits the predicted zig-zag and needs 27 iterations, while lifted Newton converges in 4. The first lifted step, for which λ0=0\boldsymbol{\lambda}_0=0, is a Picard step and points in the same direction as the first standard Newton step.

Figure 1. Lifted and standard Newton iterations for a finite difference discretization of the one-dimensional pp-Laplace problem introduced in appendix B with p=1.01p=1.01. Each panel shows the projection of iterates onto the two-dimensional subspace given by two nodal values.

Numerical results: pp-Laplace

Implementation and comparisons

We implement the lifted Newton method for the pp-Laplace (and for the pp-Stokes problem in section 5 below) with the finite element (FE) library Firedrake [19]. The FE method represents the discrete solution uhu_h in a finite element space VhV_h and solves a weak formulation of the associated PDE. For the lifted Newton method, given the discrete variables uhu_h and λh\boldsymbol{\lambda}_h, we seek an increment u^h∈V˚h\hat{u}_h \in\mathring{V}_h, where V˚h\mathring{V}_h denotes the subspace of VhV_h that incorporates homogeneous Dirichlet boundary conditions. The increment u^h\hat{u}_h solves the linear system (20) with the symmetrized diffusion tensor (27). Writing wε,h\boldsymbol{w}_{\varepsilon,h} and wλ,h\boldsymbol{w}_{\lambda,h} for the discrete counterparts of the directions (16), its weak form reads

∫Ω∣∇uh∣εp−2(I+(p−2)sym⁡(wλ,hwε,hT))∇u^h⋅∇vh dx=∫Ωfvh dx−∫Ω∣∇uh∣εp−2∇uh⋅∇vh dx∀vh∈V˚h.(46)\int_{\Omega} \lvert\nabla u_h\rvert_{\varepsilon}^{p-2}\left(I+(p-2)\operatorname{sym}\left(\boldsymbol{w}_{\lambda,h}\boldsymbol{w}_{\varepsilon,h}^{\mathsf{T}}\right)\right)\nabla\hat{u}_h\cdot\nabla v_h\,\mathrm{d}x = \int_{\Omega} f v_h\,\mathrm{d}x-\int_{\Omega}\lvert\nabla u_h\rvert_{\varepsilon}^{p-2}\nabla u_h\cdot\nabla v_h\,\mathrm{d}x\quad\forall v_h\in\mathring{V}_h. \tag*{(46)}

Equation (46) can be implemented with a few lines of code, thanks to Firedrake’s use of unified form language [2], a purely symbolic language for writing variational forms of PDEs, and PETSc [5], a numerical linear algebra library.

It remains to specify how the discrete lifting variable λh\boldsymbol{\lambda}_h is represented. Note that the computation of λh\boldsymbol{\lambda}_h is purely algebraic, in the sense that (30) does not involve derivatives of λh\boldsymbol{\lambda}_h. Moreover, the linear system (46) only requires the values of λh\boldsymbol{\lambda}_h at quadrature points. For these reasons, we do not introduce λh\boldsymbol{\lambda}_h as a FE function but simply store and update its values at quadrature points. In Firedrake, this is made possible with the so-called “quadrature element” functionality, as illustrated in the open-source implementation we provide.1 Quadrature elements are special function spaces in Firedrake defined only on the points of a numerical quadrature rule. This contrasts with standard FE functions, characterized in terms of degrees of freedom (i.e. linear forms defined on the FE space) and defined for all x∈Ω\boldsymbol{x}\in\Omega. Quadrature elements are a standard feature in many FE libraries; they are also available in FEniCS [28], and an equivalent functionality can be found in MFEM [4]. We point out that the relationship between the variables uu and λ\lambda differs from that found in mixed FE problems [7]. There, FE spaces are introduced for both variables, and these spaces

must satisfy so-called inf-sup conditions to ensure the stability of the discrete problem. The explicit and purely algebraic nature of (30) dispenses with the need for such conditions, simplifying the construction of discrete lifted Newton schemes considerably. In the following, we report numerical comparisons of iterative schemes for solving the pp-Laplace problem (4) for different values of pp with 1<p<21 < p < 2, for a problem in two and one in three dimensions. We study the influence of uniform and local mesh refinement and use linear and quadratic elements. We present results for the Picard method (3), the classical Newton method (21), and the lifted Newton iteration (20). Additionally, we compare the recently proposed Picard–Newton method [33], which alternates between Picard and Newton steps to improve the robustness of Newton’s method. The method has been shown to be particularly useful for significantly nonlinear stationary Navier–Stokes problems. Table 1 summarizes the methods compared in this section for solving the pp-Laplace equation, and some of these approaches are later applied to the pp-Stokes problems in section 6.

NameMethodIteration
SNStandard Newton(21)
LNLifted Newton(20), section 2.4
PPicard(3)
PNPicard–Newton[33]

Table 1. Abbreviations used for the iterative methods compared in the numerical experiments.

In all examples, we report the iteration counts, which are equivalent to the number of linear solves. This is justified since all methods require the solution of a symmetric, positive definite system for the degrees of freedom corresponding to the discretization of uu. One step of the Picard–Newton method requires solving two linear systems, and this is counted as two iterations. Our implementation uses a direct solver for the symmetric linear systems arising in each iteration. Unless otherwise specified, we use the parameters ε=10−6\varepsilon= 10^{-6} and β=1−10−4\beta= 1 - 10^{-4}. We use a slight modification of the Armijo line search and use

Jε(uh,k+αku^h,k)≤Jε(uh,k)+γαkJε′(uh,k)u^h,k+τls,(47)J_{\varepsilon}(u_{h,k} + \alpha_k \widehat{u}_{h,k}) \leq J_{\varepsilon}(u_{h,k}) + \gamma\alpha_k J_{\varepsilon}'(u_{h,k})\widehat{u}_{h,k} + \tau_{\mathrm{ls}}, \tag*{(47)}

where τls\tau_{\mathrm{ls}} at the order of machine precision (we use τls=10−15\tau_{\mathrm{ls}} = 10^{-15}). Including this tolerance prevents the line search from failing because of rounding errors when the iterate is extremely close to the solution. This typically occurs in the final step, where the finite-precision value of Jε(uh,k)J_{\varepsilon}(u_{h,k}) may not change, even though the residual can still be decreased by accepting a full update step.

In our numerical experiments we set γ=0\gamma= 0 in (47). While this line-search variant does not enforce a prescribed fraction of the predicted decrease, the coercivity of MkM_k ensures that u^h,k\widehat{u}_{h,k} is a descent direction at each iteration, so the backtracking procedure is well defined. For several of the tests reported below, we also confirmed that taking γ=10−4\gamma= 10^{-4} yields the same number of iterations. Iterations are terminated when the relative norm H−1H^{-1}-norm of the residual reaches 10−610^{-6}, or after 500 iterations, indicating that the method takes too long to converge.

Two-dimensional pp-Laplace equation example

In this subsection, we use a two-dimensional example for the pp-Laplace equation (4) taken from [29]. Let Ω=(0,1)2\Omega= (0,1)^2, f=0f = 0, and we enforce a Dirichlet condition given by the characteristic function g=1Xg = 1_X, where

X=({0}×[0.25,0.75])∪([0.6,1]×[0.25,1]).X = (\{0\} \times[0.25, 0.75]) \cup([0.6,1] \times[0.25,1]).

We initialize the primal solution by u0=0u_0 = 0 and impose the Dirichlet boundary condition strongly. The lifting variable is initialized as λ0=0\lambda_0 = 0, resulting in the first iteration being a Picard step as discussed at the end of section 2.4. Other initialization strategies we tried resulted in the same, or nearly the same, convergence behavior. We use continuous piecewise-linear elements on uniform N×NN \times N regular grids with N∈{25,50,100}N \in\{25, 50, 100\} and crossed diagonals. Each square of the Cartesian partition is split into four triangles, so the three meshes contain 4N2=2,5004N^2 = 2{,}500, 10,000, and 40,000 triangles, respectively.

In Figure 2, we show the solutions for several values of pp together with the performance of the different solvers on the N=50N = 50 grid. One observes that, as pp tends to 1, the transition layer becomes increasingly sharp, which makes the problem more difficult to solve. The iteration counts on all three grids are reported in Table 2. When pp approaches 1, the iteration counts rise steeply for all methods, with the exception of LN, whose counts grow only mildly on every grid. The linear convergence of P degrades as p→1p \to1, so it fails to achieve the prescribed relative tolerance for p=1.01p = 1.01 on all three grids. The hybrid PN offers a substantial improvement over both P and SN, but for p≈1p \approx1 it is still less efficient than LN. The line search step lengths in Figure 2 explain the different convergence behaviors between SN and LN. For p=1.01p = 1.01, SN spends a long initial phase accepting strongly damped steps; many accepted steps are approximately 1/321/32. On the other hand, LN takes only a few damped steps before accepting full steps, which accelerates the convergence.

Solutions and convergence behavior for the two-dimensional $p$-Laplace example

Figure 2. Solutions and convergence behavior for the two-dimensional pp-Laplace example on the N=50N = 50 grid (10,000 triangles). The top row shows the solutions for p=1.6p = 1.6, p=1.1p = 1.1, and p=1.01p = 1.01. The middle row shows the relative H−1H^{-1}-norm of the residual, i.e., ∥rh,k∥H−1/∥rh,0∥H−1\lVert r_{h,k}\rVert_{H^{-1}}/\lVert r_{h,0}\rVert_{H^{-1}}, with a shared vertical scale. Normalization is performed separately for each pp; all methods share the same initial iterate within a column, so every curve starts at one. The bottom row shows the accepted line-search step sizes on a shared base-2 vertical scale. Picard is omitted from the bottom row because it does not use line search; for Picard–Newton, the step size of the Newton substep is shown. Histories extending beyond a panel’s horizontal range are truncated; complete iteration counts are given in Table 2.

Methodp=1.6p = 1.6p=1.3p = 1.3p=1.1p = 1.1p=1.05p = 1.05p=1.01p = 1.01
SN15/18/2223/29/3334/40/5779/87/105283/329/358
LN9/11/1110/10/1018/15/1618/19/2023/21/24
P15/15/1538/38/38112/119/123203/218/232n.c./n.c./n.c.
PN8/8/812/14/1824/28/3032/38/4662/80/92

Table 2. Number of iterations needed for convergence by different methods applied to the two-dimensional pp-Laplace problem. Each table entry gives the iteration counts for the N=25N = 25, N=50N = 50, and N=100N = 100 grids, reported as X/X/X; the corresponding meshes have 2,500, 10,000, and 40,000 triangles. The label “n.c.” indicates that the specified tolerance was not achieved within 500 iterations.

In table 2 we summarize the performance of the different methods over a range of pp values; each entry lists the counts for N=25N = 25, 50, and 100. For p=1.6p = 1.6, the spread of required iterations is modest on every grid, whereas the discrepancies between them increase markedly as pp approaches 1. It can also be seen that LN is substantially less sensitive to mesh refinement.

Finally, in Table 3, we show the number of iterations required for different choices of regularization parameters ε\varepsilon. For p≈1p \approx1, a smaller ε\varepsilon makes the problem more singular and generally increases the number of iterations required for convergence. In particular, for ε=10−10\varepsilon= 10^{-10} and p=1.01p = 1.01, the residuals of both methods fail to reach the prescribed tolerance, likely due to roundoff errors for these extreme parameter values. This shows the necessity of the ε\varepsilon-regularization for solver robustness.

Methodε\varepsilonp=1.6p = 1.6p=1.3p = 1.3p=1.1p = 1.1p=1.05p = 1.05p=1.01p = 1.01
SN10−410^{-4}19273865206
SN10−610^{-6}18294087329
SN10−810^{-8}182141112443
SN10−1010^{-10}172242127n.c.†
LN10−410^{-4}811121518
LN10−610^{-6}1110151921
LN10−810^{-8}911192131
LN10−1010^{-10}911212330†

Table 3. Comparison of the number of iterations required by SN and LN for various regularization parameters ε\varepsilon in the two-dimensional pp-Laplace example for N=50N = 50. As done throughout, the iteration is terminated when the relative residual reaches 10−610^{-6}; the entries marked with † correspond to a relative residual of 10−510^{-5}. For these tests, the residual does not decrease to 10−610^{-6}, likely due to rounding errors due to extreme values of pp and ε\varepsilon.

Three-dimensional pp-Laplace equation example

In this subsection, we consider a three-dimensional pp-Laplace test problem and compare some of the solution methods from table 1 for two finite element spaces with different polynomial orders on a locally refined mesh. We use Ω=(0,1)3\Omega= (0,1)^3, again set f=0f = 0 and use the Dirichlet boundary data g=1Xg = 1_X, where

X={(x,y,z)∈[0,1]3:x+y+z≥52}.X = \left\{(x,y,z) \in[0,1]^3 : x + y + z \ge\frac{5}{2}\right\}.

Similar to the previous two-dimensional example, this corner-cutting problem produces a sharp transition close to Γ:={(x,y,z)∈[0,1]3:x+y+z=52}\Gamma:= \left\{(x,y,z) \in[0,1]^3 : x + y + z = \frac{5}{2}\right\}, especially for p≈1p \approx1. To properly refine this transition zone, we use a locally refined finite element mesh. We start from a uniform 5×5×55 \times5 \times5 Cartesian partition of the cube Ω\Omega and divide each cube into 6 tetrahedral cells, resulting in a coarse mesh with 750 cells. We then perform three successive local refinement passes. At each pass, a tetrahedron is marked when the range of x+y+zx+y+z over its vertices intersects the plane-centered slab of perpendicular half-width 0.01; in other words, we only refine every cell that is cut by Γ\Gamma since the slab is very thin. The resulting mesh used in the computations contains N=16,848N = 16{,}848 tetrahedra, of which 3,612 intersect Γ\Gamma. Plane-intersecting cells have a diameter of hK=3/40≈0.0433h_K = \sqrt{3}/40 \approx0.0433. On this locally refined mesh, we use both continuous piecewise-linear (CG1) and piecewise-quadratic (CG2) finite element spaces, whose degrees of freedom are 3,352 and 24,406, respectively. The mesh is visualized in the top left of Figure 3.

Solution fields and convergence behavior for the three-dimensional $p$-Laplace example

Figure 3. Solution and convergence behavior for the three-dimensional pp-Laplace example using CG2 elements on the locally refined mesh with 16,848 tetrahedra. The top row shows part of the solution fields computed with lifted Newton for p=1.6p = 1.6 (with the mesh visualized), p=1.1p = 1.1, and p=1.01p = 1.01. The middle row compares the relative H−1H^{-1}-norm of the residual ∥rh,k∥H−1/∥rh,0∥H−1\lVert r_{h,k}\rVert_{H^{-1}}/\lVert r_{h,0}\rVert_{H^{-1}} for all four methods on a shared vertical scale. The bottom row shows the accepted line-search step sizes on a shared base-2 vertical scale. Picard is omitted from the bottom row because it does not use line search; for PN, the step size of the Newton substep is shown. Histories extending beyond a panel’s horizontal range are truncated; complete iteration counts are given in Table 4.

We use the same initializations as in section 4.2. The CG2 solutions and the convergence behavior for p∈{1.6,1.1,1.01}p \in\{1.6, 1.1, 1.01\} are shown in Figure 3, while Table 4 reports the iteration counts of all methods for both CG1 and CG2. As in the two-dimensional example, LN converges in substantially fewer iterations than SN, and the difference becomes more significant as pp approaches 1.

DiscretizationMethodp=1.6p = 1.6p=1.1p = 1.1p=1.01p = 1.01
CG1SN1043257
CG1LN71521
CG1P15102n.c.
CG1PN83050
CG2SN1447242
CG2LN71524
CG2P15105n.c.
CG2PN82644

Table 4. Iterations required for convergence of the various methods on the locally refined mesh with N=16,848N = 16{,}848 tetrahedra, using linear (CG1) and quadratic (CG2) finite elements. The “n.c.” means that the prescribed tolerance was not reached within 500 iterations.

CellsMethodp=1.5p=1.5p=1.1p=1.1p=1.05p=1.05p=1.01p=1.01
N=2.5×103N=2.5\times10^{3}SN194959228
LN4121518
N=104N=10^{4}SN295167263
LN5121821
N=4×104N=4\times10^{4}SN475069285
LN5121522

Table 4.

The results in Table 4 also show that LN is robust to the polynomial degree: its CG1 and CG2 iteration counts differ by at most three. For p=1.01p = 1.01, lifted Newton requires 21 linear solves with CG1 and 24 with CG2, compared to 257 and 242, respectively, for SN. P does not reach the prescribed tolerance within 500 iterations for either discretization, whereas PN converges in 50 linear solves with CG1 and 44 with CG2.

Generalization to p-Stokes problems

We now turn to the pp-Stokes problem, a generalization of the pp-Laplacian of section 2 obtained by coupling the same type of power-law nonlinearity to an incompressibility constraint [10, 13]. The pp-Stokes system describes the slow, creeping flow of a generalized Newtonian (power-law) fluid. It differs from the pp-Laplace problem in that the unknown is a divergence-free vector field. For 1<p<21 < p < 2, such fluids are said to be shear-thinning. The resulting near-singular viscosity makes Newton’s method slow and fragile, with iteration counts that grow with mesh refinement and as pp gets close to 1 [30, 36]. We next specify the pp-Stokes problem and then follow the same lift–transform–linearize–eliminate procedure as in section 2.2.

Let Ω⊂Rd\Omega\subset\mathbb{R}^{d}, d∈{2,3}d \in\{2,3\}, be a bounded Lipschitz domain with boundary ∂Ω\partial\Omega. In the pp-Stokes problem, we seek a velocity field u:Ω→Rd\boldsymbol{u} : \Omega\to\mathbb{R}^{d} and a pressure π:Ω→R\pi: \Omega\to\mathbb{R} satisfying

−∇⋅S(Du)+∇π=fin Ω,(48)-\nabla\cdot S(Du) + \nabla\pi= f \quad\text{in } \Omega, \tag*{(48)}
∇⋅u=0in Ω,(49)\nabla\cdot\boldsymbol{u} = 0 \quad\text{in } \Omega, \tag*{(49)}
u=uDon ∂Ω,(50)\boldsymbol{u} = \boldsymbol{u}_{D} \quad\text{on } \partial\Omega, \tag*{(50)}

where Du:=12(∇u+∇uT)Du := \frac{1}{2}(\nabla\boldsymbol{u} + \nabla\boldsymbol{u}^{\mathsf{T}}) is the symmetric velocity gradient (strain rate tensor) and ff, uD\boldsymbol{u}_{D} are prescribed data. Clearly, more complicated boundary conditions are possible, but we restrict ourselves to Dirichlet conditions for simplicity. The deviatoric extra-stress tensor SS is given by a power-law constitutive relation

S(Du)=2ν0∣Du∣p−2Du,p∈(1,∞),S(Du) = 2\nu_{0}|Du|^{p-2}Du, \qquad p \in(1,\infty),

with ν0>0\nu_{0} > 0 and ∣Du∣2:=Du:Du|Du|^{2} := Du : Du is the second invariant of the strain rate tensor.

As in section 2, we introduce a small parameter ε>0\varepsilon> 0 to regularize the second invariant of the strain-rate tensor, thereby avoiding the singularity for p<2p < 2. Specifically, we set ∣Du∣ε:=∣Du∣2+ε2|Du|_{\varepsilon} := \sqrt{|Du|^{2} + \varepsilon^{2}}, and define the associated regularized stress by Sε(Du):=2ν0∣Du∣εp−2Du.Analogously,weintroducethetensor−valuedvariableS_{\varepsilon}(Du) := 2\nu_{0}|Du|_{\varepsilon}^{p-2}Du. Analogously, we introduce the tensor-valued variable\Lambda(x) := S_{\varepsilon}(Du)(x) and consider the following regularized, lifted, and transformed system for (\boldsymbol{u},\pi,\Lambda)$:

−∇⋅Λ+∇π=fin Ω,(51)-\nabla\cdot\Lambda+ \nabla\pi= f \quad\text{in } \Omega, \tag*{(51)}
∇⋅u=0in Ω,(52)\nabla\cdot\boldsymbol{u} = 0 \quad\text{in } \Omega, \tag*{(52)}
Λ∣Du∣ε2−p−2ν0Du=0in Ω,(53)\Lambda|Du|_{\varepsilon}^{2-p} - 2\nu_{0}Du = 0 \quad\text{in } \Omega, \tag*{(53)}

together with boundary conditions as in (47). Following the same procedure as in section 2.2, we linearize (48) around (u,π,Λ)(\boldsymbol{u},\pi,\Lambda) in the direction (u^,π^,Λ^)(\widehat{\boldsymbol{u}},\widehat{\pi},\widehat{\Lambda}). Then, by isolating the increment Λ^\widehat{\Lambda} and eliminating it from the system, we arrive at the following linearized system for the velocity/pressure increment (u^,π^)(\hat{u},\hat{\pi}):

−∇⋅(∣Du∣εp−2(2ν0Du^+(p−2)(WΛ⊗Wε):Du^))+∇π^=f+∇⋅Sε(Du)−∇π,(54)-\nabla\cdot\left(|D u|_{\varepsilon}^{p-2}\left(2\nu_0 D\hat{u}+(p-2)(W_{\Lambda}\otimes W_{\varepsilon}):D\hat{u}\right)\right)+\nabla\hat{\pi}=f+\nabla\cdot S_{\varepsilon}(D u)-\nabla\pi, \tag*{(54)}
∇⋅u^=0(55)\nabla\cdot\hat{u}=0 \tag*{(55)}

where Wε:=Du/∣Du∣εW_{\varepsilon}:=D u/|D u|_{\varepsilon} and WΛ:=Λ/∣Du∣εp−1W_{\Lambda}:=\Lambda/|D u|_{\varepsilon}^{p-1}, and where a rank-one fourth-order tensor acts on a second-order tensor as (A⊗B):C:=A(B:C)(A\otimes B):C:=A(B:C). Note the direct analogy with (20): for 2ν0=12\nu_0=1, the terms ∇u\nabla u, wεw_{\varepsilon} and wΛw_{\Lambda} in the pp-Laplace problem play the role of DuD u, WεW_{\varepsilon} and WΛW_{\Lambda}, respectively. The matrix–vector product (wΛwΛT)∇u^(w_{\Lambda}w_{\Lambda}^{\mathsf{T}})\nabla\hat{u} is replaced by its tensorial counterpart.

Writing

M:=∣Du∣εp−2(2ν0I+(p−2)sym⁡(WΛ⊗Wε))(56)\mathbb{M}:=|D u|_{\varepsilon}^{p-2}\left(2\nu_0\mathbb{I}+(p-2)\operatorname{sym}(W_{\Lambda}\otimes W_{\varepsilon})\right) \tag*{(56)}

for the resulting fourth-order diffusion tensor, where I\mathbb{I} is the identity on symmetric second-order tensors, the increment of the lifting variable is recovered pointwise from

Λ^:=M:Du^−Λ+Sε(Du),(57)\hat{\Lambda}:=\mathbb{M}:D\hat{u}-\Lambda+S_{\varepsilon}(D u), \tag*{(57)}

in analogy with (30). Substituting (57) into the linearized momentum equation cancels Λ\Lambda from the right-hand side, which is why only Sε(Du)S_{\varepsilon}(D u) appears in eq:49; as in section 2.4, the lifting variable influences the velocity increment only through M\mathbb{M}.

The two modifications of section 2.3 that guarantee the well-posedness of eq:49 also carry over. The symmetrization sym⁡(WΛ⊗Wε):=12(WΛ⊗Wε+Wε⊗WΛ)\operatorname{sym}(W_{\Lambda}\otimes W_{\varepsilon}):=\frac{1}{2}(W_{\Lambda}\otimes W_{\varepsilon}+W_{\varepsilon}\otimes W_{\Lambda}) used in (56) leaves the quadratic form E:M:EE:\mathbb{M}:E unchanged, but makes M\mathbb{M} self-adjoint, so that the velocity block of the saddle-point system eq:49 is symmetric. The feasibility bound is imposed on WΛW_{\Lambda} as in (24), but scaled by the viscosity constant: with 2−p<β<12-p<\beta<1 as in (26), we enforce

∣WΛ(x)∣≤2ν0β2−pfor x∈Ω\lvert W_{\Lambda}(x)\rvert\leq\frac{2\nu_0\beta}{2-p}\qquad\text{for }x\in\Omega

by replacing Λ\Lambda in (56) by its pointwise projection onto the ball of radius ρ(x):=2ν0β2−p∣Du(x)∣εp−1\rho(x):=\frac{2\nu_0\beta}{2-p}|D u(x)|_{\varepsilon}^{p-1}, as in (28). The iterate Λ\Lambda itself remains unchanged. Since ∣Wε∣≤1\lvert W_{\varepsilon}\rvert\leq1, this yields the bounds

2ν0(1−β)∣Du∣εp−2∣E∣2≤E:M:E≤2ν0(1+β)∣Du∣εp−2∣E∣22\nu_0(1-\beta)|D u|_{\varepsilon}^{p-2}|E|^2\leq E:\mathbb{M}:E\leq2\nu_0(1+\beta)|D u|_{\varepsilon}^{p-2}|E|^2

for every symmetric EE, the direct counterpart of (25). The velocity block is therefore uniformly elliptic for every choice of Λ\Lambda, and standard Stokes solvers and preconditioners can be applied.

Numerical results: p-Stokes

We discretize the incompressible Stokes equations using Taylor–Hood finite elements, i.e., we represent the velocity as a continuous piecewise quadratic vector field and the pressure as a continuous linear scalar field. In this section, we present results for a stationary lid-driven cavity pp-Stokes problem in section 6.1 and for a time-dependent problem modeling the pp-Navier–Stokes flow around a cylinder in section 6.2. For brevity, we limit our comparison to the standard Newton (SN) and lifted Newton (LN) methods and examine how these methods behave under mesh refinement, as well as in a time-dependent setting where good initializations for the iterative solvers are available at each time step.

Our implementation again uses the Firedrake finite element library and is available from the same repository as the pp-Laplace implementation. Analogously to before, the lifting variable Λ\Lambda is not implemented as a finite element function. Instead, it is treated purely algebraically at the quadrature points. As before, we use the numerical parameters ε=10−6\varepsilon=10^{-6}, β=1−10−4\beta=1-10^{-4}, γ=0\gamma=0. In each iteration of both methods, the resulting linear Stokes subproblems are again solved with a direct solver. Because these are standard symmetric saddle-point systems stemming from a stable Stokes finite element discretization, they are also amenable to existing iterative saddle-point preconditioners and solvers.

Lid-driven cavity flow

First, we consider an incompressible lid-driven cavity pp-Stokes flow problem. We consider eq:47 on Ω=(0,1)2\Omega= (0,1)^2, with f=0\boldsymbol{f} = 0 and ν0=1/2\nu_0 = 1/2, and with the (smoothed) driving lid Dirichlet data uD=[12(1−cos⁡(2πx)),0]T\boldsymbol{u}_D = [\frac{1}{2}(1-\cos(2\pi x)),0]^{\mathsf{T}} on the top boundary and the Dirichlet condition uD=0\boldsymbol{u}_D = \boldsymbol{0} on the remaining boundaries. In these computations, we set the solution to the lid-driven cavity problem with p=2p = 2 as our initial guess in both the standard and lifted Newton methods. This avoids the failure of the nonlinear solvers for small pp values.

The flow field and the solver performance for different meshes and values of pp are shown in Figure 4. First, we observe that the driven flow close to the top boundary localizes in a very narrow boundary layer for p=1.01p = 1.01. Furthermore, as the table indicates, the lifted method requires only moderately more iterations as pp decreases, and its iteration counts are largely insensitive to the mesh: for p=1.5p = 1.5 it converges in four or five iterations on all three meshes, whereas SN grows from 19 to 47 iterations under the same refinement. The number of SN iterations rises steeply as pp approaches 1; on the finest mesh, it requires 285 iterations for p=1.01p = 1.01, compared with 22 for LN, a factor of more than 13. Both methods show a mild mesh dependence at p=1.01p = 1.01, but at levels that differ by more than an order of magnitude.

Solutions and convergence behavior for the lid-driven cavity $p$-Stokes problem

Figure 4. Solutions and convergence behavior for the lid-driven cavity pp-Stokes problem. We consider different values of pp in (1,2)(1,2) and meshes with increasing numbers of cells NN. The top row shows the velocity magnitude and streamlines for p=1.5p=1.5 and p=1.01p=1.01 on the most refined mesh, with a shared color scale for ∣u∣\lvert u\rvert. The bottom row shows the relative H−1H^{-1} norm of the equation residual for SN and LN on the same mesh, using a shared vertical scale. The table reports the number of iterations for all values of pp and various mesh sizes.

Flow around a cylinder for the pp-Navier–Stokes equations

As a second numerical example, we solve the time-dependent pp-Navier–Stokes (pp-NS) equations:

∂u∂t+(u⋅∇)u−∇⋅S(Du)+∇π=fon Ω,\frac{\partial\boldsymbol{u}}{\partial t} + (\boldsymbol{u}\cdot\nabla)\boldsymbol{u} - \nabla\cdot\boldsymbol{S}(D\boldsymbol{u}) + \nabla\pi= \boldsymbol{f} \quad\text{on } \Omega,

together with the divergence-free condition ∇⋅u=0\nabla\cdot\boldsymbol{u} = 0. Unlike the steady pp-Stokes problem, the pp-NS equations are time-dependent, and the convection term (u⋅∇)u(\boldsymbol{u}\cdot\nabla)\boldsymbol{u} introduces an additional nonlinearity. For the pp-NS equation, we build a LN method exactly as for the pp-Stokes equation, i.e., by introducing a lifting variable that represents the deviatoric stress tensor S(Du)\boldsymbol{S}(D\boldsymbol{u}). We discretize in time using the implicit Euler scheme. Following [30], we compute the two-dimensional flow around a cylinder, see the left panels in Figure 5, for p=1.25,1.1,1.01p = 1.25, 1.1, 1.01. The domain is of length L=2.2L = 2.2 and height H=0.41H = 0.41, with the cylinder of radius 0.050.05 centered at (0.2,0.2)(0.2,0.2). We enforce the velocity boundary conditions

Figure 5. In the top left figures above, each row presents the velocity magnitude field ∣u∣|u| at t=8t = 8. The top right figure shows the number of iterations per time step for three different pp values. In the table, for each pp we indicate the maximum and mean number of Newton iterations in time for SN and LN.

u(x,y)=ω(t)(1−(1−2yH)20)\boldsymbol{u}(x,y) = \omega(t)\begin{pmatrix} 1-\left(1-\frac{2y}{H}\right)^2 \\ 0 \end{pmatrix}

on the left boundary, with ω(t)=12(1−cos⁡(πt))\omega(t) = \frac{1}{2}(1-\cos(\pi t)) for t<1t < 1 and ω(t)=1\omega(t) = 1 for t>1t > 1. On the top and lower boundaries, we set u=0\boldsymbol{u} = \boldsymbol{0}, and on the right boundary, S(Du)n−πn=0\boldsymbol{S}(D\boldsymbol{u})\boldsymbol{n} - \pi\boldsymbol{n} = 0. As initial condition, we set the fluid velocity to zero. We run the simulation up to time t=8t = 8 for 3,392 time steps on a mesh of 4,961 cells. To be able to observe vortex shedding, we set ν0=0.001\nu_0 = 0.001, which results, for p=2p = 2, in a nominal Reynolds number of about 100. These computations are challenging for two reasons: (1) For values of pp close to 1, enforcing the incoming velocity boundary condition (a parabolic profile) makes the problem stiff. (2) The nonlinear convection term is a potential source of numerical instabilities. We solve these issues as done in [30]: for (1), we enforce boundary conditions using Nitsche’s method. For (2), we stabilize our discretization with the so-called continuous interior penalty (CIP) method [11]. This method penalizes discontinuities in the velocity gradients.

Information on the iterations at each time step can be found in Figure 5. For these computations, convergence of the Newton methods is measured in terms of the relative L2L^2 norm of the discrete residual. For both SN and LN, the time steps that require the largest number of Newton iterations are those for t<4t<4, when the solution experiences the biggest changes at each time step. In these initial time steps, the number of iterations required by SN increases substantially as pp approaches 1. Conversely, for LN, this increase is mild. For t>4t>4, both Newton methods require a similar number of iterations.

The advantage of LN is therefore concentrated in the stiff regime. At p=1.25p=1.25, the two methods are essentially indistinguishable in cost, whereas at p=1.01p=1.01, the mean drops from 9.86 to 4.12. Accumulated over the 3,392 time steps, this amounts to roughly 33,400 linear solves for SN compared to 14,000 for LN, a reduction by a factor of about 2.4. The peak cost per time step is affected far more strongly. At p=1.01p=1.01, the maximum number of iterations in a single step falls from 140 to 24, which makes the cost of the lifted iteration substantially more predictable in a time-stepping context.

Discussion and extension

We finish with a discussion of the main findings and possible extensions.

Continuation. The standard remedy for the pp-dependence of Newton’s and Picard’s methods is continuation in pp [22], and sometimes in ε\varepsilon. One solves a sequence of auxiliary problems, starting from p=2p=2 (or a large ε\varepsilon) and moving the parameters towards the target, using each solution to initialize the next problem. This is a globalization by proximity to the solution, and its cost is the

sum of all intermediate solves. None of the results presented here use continuation; since the lifted iteration counts are largely insensitive to pp and hh, there is no need for it.

Krylov solvers. All linear systems reported here are solved directly. For larger problems in three dimensions, the structure of the lifted tangent is favorable for iterative solvers. By [25], the tensor MkM_k is spectrally equivalent to the Picard operator ∣∇uk∣p−2I|\nabla u_k|^{p-2}I, with constants 1−β1-\beta and 1+β1+\beta that are independent of the mesh and of ε\varepsilon. Any preconditioner that is spectrally equivalent to the discretized Picard operator is therefore a good candidate. Following standard Newton–CG arguments, if the linear system in step (ii) of section 2.4 is solved by CG initialized by zero, every CG iterate u~\tilde{u} is a descent direction, and the Armijo search [31] remains well defined.

Symmetrized versus non-symmetrized lifted Newton operator. The symmetrization [27] of the rank-one term was introduced in section 2.3 for convenience only. Since zTBz=zTsym⁡(B)zz^{\mathsf{T}}Bz = z^{\mathsf{T}}\operatorname{sym}(B)z for every B∈Rd×dB \in\mathbb{R}^{d \times d}, the quadratic form, along with the coercivity bounds [25], the descent property of the increment, and the global convergence proof are identical for the symmetrized and the nonsymmetric tensor I+(p−2)wεwεTI+(p-2)w_\varepsilon w_\varepsilon^{\mathsf{T}}. We have compared both variants on the examples of section [4] and found the iteration histories to be nearly indistinguishable for most cases with moderate pp, with iteration counts that differ by at most one or two. More substantial differences are seen as p→1p \to1. For example, for the two-dimensional pp-Laplace problem with p=1.01p = 1.01 and N=25N = 25, we obtain 23 iterations with and 40 iterations without symmetrization. The symmetrized form is preferable in practice for other reasons as well. It allows us to use symmetric direct and iterative solvers, and it is the form for which the descent property of inexact CG steps discussed above holds.

The case p>2p > 2. For p>2p > 2 the coefficient ∣∇u∣p−2|\nabla u|^{p-2} vanishes rather than blows up where ∇u=0\nabla u = 0, so no regularization is needed to define the residual, and the standard Newton tensor is uniformly positive definite. The difficulties for large pp are of a different kind: the diffusion coefficient degenerates in flat regions, its dynamic range grows like ∣∇u∣p−2|\nabla u|^{p-2} and leads to ill-conditioned systems and round-off sensitivity, and the energy JJ becomes increasingly non-quadratic in steep regions. The transformation [9] is also the wrong one for p>2p > 2: multiplying the constitutive relation by ∣∇u∣2−p|\nabla u|^{2-p} introduces a singularity at ∇u=0\nabla u = 0 where the original relation is perfectly smooth. The natural counterpart exchanges the roles of the primal and dual variables and lifts the dual constitutive relation ∇u=∣λ∣q−2λ\nabla u = |\lambda|^{q-2}\lambda with q=p/(p−1)∈(1,2)q = p/(p-1) \in(1,2), i.e., one applies the approach of this paper to the dual problem of section 2.1, in which the exponent qq now lies in the range where the transformation is beneficial. A systematic study of lifting for p>2p > 2 is left for future work.

Open questions. Since β>2−p\beta> 2-p, the coercivity constant guaranteed by (25) satisfies 1−β<p−11-\beta< p-1, so our bounds degrade as p→1p \to1 at the same rate as those for standard Newton. The observed iteration counts do not, and a local convergence analysis that quantifies this gap, ideally with constants independent of pp, remains open. Equally open is a convergence result in the infinite-dimensional setting or with ε→0\varepsilon\to0; however, this is a challenge that the lifted method shares with the standard variant.

Acknowledgements

This work was supported in part by the US National Science Foundation (NSF) under awards #2343866, #2411229 and #2411349.

Alternative projection of the lifting variable

In the method of section 2.4, the projection (28) is applied only where the lifting variable enters the diffusion tensor, while the iterate λk\lambda_k itself is evolved unconstrained. An alternative is to project the iterate as well, i.e., to replace step (v) by

uk+1:=uk+αku^k,λ~k+1:=λk+αkλ^k,λk+1:=λ~k+1max⁡(1,∣λ~k+1∣/ρk+1)(58)u_{k+1} := u_k + \alpha_k \widehat{u}_k,\qquad\widetilde{\lambda}_{k+1} := \lambda_k + \alpha_k \widehat{\lambda}_k,\qquad\lambda_{k+1} := \frac{\widetilde{\lambda}_{k+1}}{\max\left(1,\lvert\widetilde{\lambda}_{k+1}\rvert/\rho_{k+1}\right)} \tag*{(58)}

with ρk+1\rho_{k+1} as in (28) evaluated at uk+1u_{k+1}, and to use λk\lambda_k itself in (29). As in (28), the last relation is understood pointwise and gives ∣λk+1∣=min⁡{∣λ~k+1∣,ρk+1}\lvert\lambda_{k+1}\rvert= \min\{\lvert\widetilde{\lambda}_{k+1}\rvert,\rho_{k+1}\}. Since the feasibility bound then holds for the iterate itself, the projection in the definition of MkM_k becomes unnecessary.

The two variants are not equivalent in the initial phase, but the analysis of section 3.1 covers both. The primal statements of theorem 1 use the projection only through the spectral bounds (32), which hold for either variant. For the flux convergence of corollary 2 one notes in addition that the projection in (58) leaves Sk+1:=∣∇uk+1∣εp−2∇uk+1S_{k+1} := \lvert\nabla u_{k+1}\rvert_{\varepsilon}^{p-2}\nabla u_{k+1} untouched, since β>2−p\beta> 2-p implies

∣Sk+1∣=∣∇uk+1∣εp−2∣∇uk+1∣≤∣∇uk+1∣εp−1≤β2−p∣∇uk+1∣εp−1=ρk+1\lvert S_{k+1}\rvert= \lvert\nabla u_{k+1}\rvert_{\varepsilon}^{p-2}\lvert\nabla u_{k+1}\rvert\le\lvert\nabla u_{k+1}\rvert_{\varepsilon}^{p-1} \le\frac{\beta}{2-p}\lvert\nabla u_{k+1}\rvert_{\varepsilon}^{p-1} = \rho_{k+1}

pointwise. Since the scaling in (58) is the pointwise projection onto the ball of radius ρk+1\rho_{k+1} and hence nonexpansive, the recursion (38) is preserved, and the conclusion is unchanged. In practice, the two methods yield almost identical behavior in terms of iteration numbers, as shown in Table 5.

Methodp=1.6p = 1.6p=1.3p = 1.3p=1.1p = 1.1p=1.05p = 1.05p=1.01p = 1.01
Lifted Newton from section eq:2.41110151921
Lifted Newton variant1110151821

Table 5. Comparison of iterations required by lifted Newton method from section 2.4 and the variant discussed here for the two-dimensional pp-Laplace example of section 4.2, using a mesh with 10,000 triangles.

One-dimensional finite difference example

In section 3.3, we give a qualitative explanation of the mechanisms behind the improved convergence of the lifted Newton method for pp close to one. To make this explanation more concrete, this appendix analyzes the standard and lifted Newton steps for a one-dimensional pp-Laplace problem discretized with finite differences. The key observation is that both methods compute the same increment of the flux ∣∇u∣εp−2∇u|\nabla u|_{\varepsilon}^{p-2}\nabla u, and differ only in how this flux increment is converted into an increment of the gradient: standard Newton uses the tangent slope of the constitutive function, which is nearly flat for p≈1p \approx1, and hence overshoots by a factor of 1/(p−1)1/(p-1), whereas lifted Newton uses a secant slope and gets close to the solution quickly.

Consider the pp-Laplace equation (4) on Ω=(0,1)\Omega= (0,1) with homogeneous Dirichlet boundary conditions. We partition Ω\Omega using n+2n+2 uniformly distributed nodes with spacing h=1/(n+1)h = 1/(n+1) and denote by u=(u1,…,un)⊤u = (u_1,\ldots,u_n)^{\top} the interior degrees of freedom, with u0=un+1=0u_0 = u_{n+1} = 0. The finite difference gradient is y=Bu∈Rn+1y = Bu \in\mathbb{R}^{n+1}, yi=(ui−ui−1)/hy_i = (u_i-u_{i-1})/h for i=1,…,n+1i = 1,\ldots,n+1. The discrete problem is the minimization of

J(u):=1p∑i=1n+1∣yi(u)∣εp−f⊤u,∣y∣ε:=(y2+ε2)1/2.J(u) := \frac{1}{p}\sum_{i=1}^{n+1}|y_i(u)|_{\varepsilon}^{p} - f^{\top}u,\qquad|y|_{\varepsilon} := (y^2+\varepsilon^2)^{1/2}.

Let g(t):=∣t∣εp−2tg(t) := |t|_{\varepsilon}^{p-2}t denote the scalar constitutive function (the flux as a function of the gradient) and g(y)g(y) the vector with components g(yi)g(y_i). The residual is r(u)=B⊤g(Bu)−fr(u) = B^{\top}g(Bu)-f, with components ri=(g(yi)−g(yi+1))/h−fir_i = (g(y_i)-g(y_{i+1}))/h-f_i.

To obtain a problem with a plateau in the solution, we choose ff such that the discrete solution is u∗=1n:=(1,…,1)⊤u^{*} = \mathbf{1}_n := (1,\ldots,1)^{\top}, i.e., y1∗=1/hy_1^{*} = 1/h, yn+1∗=−1/hy_{n+1}^{*} = -1/h and yi∗=0y_i^{*} = 0 for i=2,…,ni = 2,\ldots,n. From r(u∗)=0r(u^{*}) = 0 and g(0)=0g(0) = 0 we obtain f1=fn=g(1/h)/hf_1 = f_n = g(1/h)/h and fi=0f_i = 0 for i=2,…,n−1i = 2,\ldots,n-1, so that the solution is flat in the sense of section 3.3 on all but the two boundary intervals.

Both Newton methods compute an increment u^\hat{u} from a linear system of the form

B⊤DBu^=−r(u),D=diag⁡(d1,…,dn+1)∈R(n+1)×(n+1),(59)B^{\top}DB\hat{u} = -r(u),\qquad D = \operatorname{diag}(d_1,\ldots,d_{n+1}) \in\mathbb{R}^{(n+1)\times(n+1)}, \tag*{(59)}

and differ only in the diagonal coefficients. For standard Newton, B⊤DSBB^{\top}D^{S}B is the Hessian of JJ, with

diS:=g′(yi)=∣yi∣εp−2[1+(p−2)yi2∣yi∣ε2].d_i^{S} := g'(y_i) = |y_i|_{\varepsilon}^{p-2}\left[1+(p-2)\frac{y_i^2}{|y_i|_{\varepsilon}^{2}}\right].

For lifted Newton with lifting variable λ∈Rn+1\lambda\in\mathbb{R}^{n+1}, the one-dimensional counterpart of the diffusion tensor (27) is

diL:=∣yi∣εp−2[1+(p−2)πi(λi)yi∣yi∣εp].d_i^{L} := |y_i|_{\varepsilon}^{p-2}\left[1+(p-2)\frac{\pi_i(\lambda_i)y_i}{|y_i|_{\varepsilon}^{p}}\right].

where πi(λi)\pi_i(\lambda_i) denotes the feasibility projection of λi\lambda_i, cf. (24). Note that diL=diSd_i^{L} = d_i^{S} if λi=g(yi)\lambda_i = g(y_i), in accordance with section 2.2. The lifting variable is updated according to step (iii) of section 2.4, which, for a unit step, reads

λk+1=g(yk)+DLy^k,y^k:=Bu^k,(60)\lambda_{k+1} = g(y_k) + D^{L}\hat{y}_k,\qquad\hat{y}_k := B\hat{u}_k, \tag*{(60)}

and we initialize with λ0=0\lambda_0 = 0.

Expansions for small values of p−1p - 1

We introduce τ:=p−1\tau:= p - 1 and assume τ≪1\tau\ll1. Although ε\varepsilon determines which regions are flat, we assume for simplicity that ∣yi∣≫ε|y_i| \gg\varepsilon for all ii, so that ∣yi∣ε≈∣yi∣|y_i|_\varepsilon\approx|y_i|; we found this to be accurate for the iterates in Figure 1, where ε=10−6\varepsilon= 10^{-6}. Since ∣y∣p−2=∣y∣−1∣y∣τ=∣y∣−1(1+O(τ))|y|^{p-2} = |y|^{-1}|y|^\tau= |y|^{-1}(1 + O(\tau)) for ∣y∣|y| bounded away from zero and infinity, to leading order in τ\tau,

g(y)≈sign⁡(y),dS≈τ∣y∣,dL≈1−πu(λ)sign⁡(y)∣y∣(61)g(y) \approx\operatorname{sign}(y), \qquad d^S \approx\frac{\tau}{|y|}, \qquad d^L \approx\frac{1-\pi_u(\lambda)\operatorname{sign}(y)}{|y|} \tag*{(61)}

where we used p−2=τ−1p - 2 = \tau- 1. The constitutive function is thus nearly the sign function: its tangent slope dSd^S is of order τ\tau, while the secant slope g(y)/y≈1/∣y∣g(y)/y \approx1/|y| through the origin is of order one. Lifted Newton with πu(λ)=O(τ)\pi_u(\lambda) = O(\tau) uses this secant slope; with λ=g(y)\lambda= g(y) it recovers the tangent slope.

We introduce the linearized flux increment z^:=DBu^∈Rn+1\hat{z} := D B \hat{u} \in\mathbb{R}^{n+1}, so that y^i=z^i/di\hat{y}_i = \hat{z}_i/d_i for i=1,…,n+1i = 1,\ldots,n+1. In terms of z^\hat{z}, the Newton system (53) reads BTz^=−rB^\mathsf{T}\hat{z} = -r, i.e., (z^i−z^i+1)/h=−ri(\hat{z}_i - \hat{z}_{i+1})/h = -r_i for i=1,…,ni = 1,\ldots,n, and therefore

z^i=z^1+hρi,ρi:=∑j=1i−1rj,i=1,…,n+1.(62)\hat{z}_i = \hat{z}_1 + h\rho_i, \qquad\rho_i := \sum_{j=1}^{i-1} r_j, \qquad i = 1,\ldots,n+1. \tag*{(62)}

In one dimension, the flux increment is thus determined by the residual up to a single constant z^1\hat{z}_1. This constant is fixed by the homogeneous boundary conditions, which imply that u^n+1−u^0=h∑i=1n+1y^i=0\hat{u}_{n+1} - \hat{u}_0 = h\sum_{i=1}^{n+1}\hat{y}_i = 0, and therefore

z^1=−∑i=1n+1wihρi,wi:=di−1∑ℓ=1n+1dℓ−1.(63)\hat{z}_1 = -\sum_{i=1}^{n+1}w_i h\rho_i, \qquad w_i := \frac{d_i^{-1}}{\sum_{\ell=1}^{n+1}d_\ell^{-1}}. \tag*{(63)}

that is, −z^1-\hat{z}_1 is a convex combination of the values hρih\rho_i. Equations (62)-(63) are therefore an explicit solution formula for (59), valid for any positive diagonal DD.

The flux increment is the same for both methods

By the expressions for the residual rr and the forcing ff, the sums in (62) telescope,

hρi=g(y1)−g(yi)−hf1=g(y1)−g(1/h)−g(yi),i=2,…,n,h\rho_i = g(y_1) - g(y_i) - h f_1 = g(y_1) - g(1/h) - g(y_i), \qquad i = 2,\ldots,n,

and hρn+1=g(y1)−g(yn+1)−2g(1/h)h\rho_{n+1} = g(y_1) - g(y_{n+1}) - 2g(1/h). Close to the solution, y1>0y_1 > 0 and yn+1<0y_{n+1} < 0, so that by (61) g(y1)−g(1/h)=O(τ)g(y_1) - g(1/h) = O(\tau) and g(yn+1)+g(1/h)=O(τ)g(y_{n+1}) + g(1/h) = O(\tau). Thus,

hρ1=0,hρi≈−g(yi)≈−sign⁡(yi)for i=2,…,n,hρn+1=O(τ).(64)h\rho_1 = 0, \qquad h\rho_i \approx-g(y_i) \approx-\operatorname{sign}(y_i) \quad\text{for } i = 2,\ldots,n, \qquad h\rho_{n+1} = O(\tau). \tag*{(64)}

To estimate the constant z^1\hat{z}_1 in (63), let δ:=max⁡i∣ui−1∣\delta:= \max_i|u_i - 1| denote the distance of the iterate from the solution and assume δ≪1\delta\ll1. For both methods, di−1∝∣yi∣d_i^{-1} \propto|y_i| in the interior by (61), while at the two boundary intervals d1−1≈dn+1−1≈1/(τh)d_1^{-1} \approx d_{n+1}^{-1} \approx1/(\tau h) for standard Newton and for lifted Newton with λ1≈g(y1)\lambda_1 \approx g(y_1), λn+1≈g(yn+1)\lambda_{n+1} \approx g(y_{n+1}), and d1−1≈dn+1−1≈1/hd_1^{-1} \approx d_{n+1}^{-1} \approx1/h for the first lifted Newton step. Using (64) and h∑i=2n∣yi∣sign⁡(yi)=un−u1h\sum_{i=2}^n |y_i|\operatorname{sign}(y_i) = u_n-u_1, the convex combination (63) evaluates to

z^1≈un−u12+TV⁡(u)+O(τ)(standard Newton, first lifted Newton step),\hat{z}_1 \approx\frac{u_n-u_1}{2+\operatorname{TV}(u)} + O(\tau) \qquad\text{(standard Newton, first lifted Newton step),}
z^1≈τ(un−u1)2+τTV⁡(u)+O(τ)(later lifted Newton steps),\hat{z}_1 \approx\frac{\tau(u_n-u_1)}{2+\tau\operatorname{TV}(u)} + O(\tau) \qquad\text{(later lifted Newton steps),}

with TV⁡(u):=h∑i=2n∣yi∣\operatorname{TV}(u) := h \sum_{i=2}^{n} |y_i|. In all cases, ∣z^1∣≲δ+O(τ)|\hat{z}_1| \lesssim\delta+ O(\tau), which is small compared to the unit-size values in (64). Inserting into (62) yields, in the flat region,

z^i≈−g(yi)≈−sign⁡(yi),i=2,…,n,(65)\hat{z}_i \approx-g(y_i) \approx-\operatorname{sign}(y_i), \qquad i=2,\ldots,n, \tag*{(65)}

for both methods, i.e., they compute the same flux increment. As desired, the linearized flux g(yi)+z^ig(y_i) + \hat{z}_i after the step vanishes to leading order, which is the target value of the flux in the flat region.

Comparison of the primal increments

The two methods differ only in the conversion y^i=z^i/di\hat{y}_i = \hat{z}_i/d_i of the flux increment into a gradient increment. Combining (61) and (65), we find for i=2,…,ni=2,\ldots,n

y^iS≈−∣yi∣τsign⁡(yi)=−yiτ,y^iL≈−∣yi∣sign⁡(yi)1−πu(λi)sign⁡(yi)=−yi1−πu(λi)sign⁡(yi).\hat{y}^{S}_i \approx-\frac{|y_i|}{\tau}\operatorname{sign}(y_i) = -\frac{y_i}{\tau}, \qquad\hat{y}^{L}_i \approx-\frac{|y_i|\operatorname{sign}(y_i)}{1-\pi_u(\lambda_i)\operatorname{sign}(y_i)} = -\frac{y_i}{1-\pi_u(\lambda_i)\operatorname{sign}(y_i)}.

With a unit step, standard Newton replaces yiy_i by yi(1−1/τ)y_i(1-1/\tau): every gradient in the flat region changes sign and grows in magnitude by a factor of approximately 1/τ1/\tau. Since the residual r\boldsymbol{r} is dominated by sign⁡(yi)−sign⁡(yi+1)\operatorname{sign}(y_i)-\operatorname{sign}(y_{i+1}), the residual changes sign as well, and the next step reverses the motion. This is the zig-zag behavior described in section 3.3 and visible in Figure 1. A damping parameter α≈τ\alpha\approx\tau would be needed in the flat region to make the step useful, while the steep boundary intervals, where gg is well approximated by its tangent, allow for α≈1\alpha\approx1. The Armijo line search must compromise between the two, which explains the slow convergence of standard Newton on this problem. Lifted Newton with πu(λi)=O(τ)\pi_u(\lambda_i)=O(\tau) instead gives y^iL≈−yi\hat{y}^{L}_i \approx-y_i, so that a unit step sets the gradients in the flat region to zero up to O(τ)O(\tau).

The lifting variable in the flat region

It remains to justify that λi=O(τ)\lambda_i=O(\tau) for i=2,…,ni=2,\ldots,n and all k≥1k \ge1. By the definition of z^\hat{z}, the update (60) of the lifting variable can be written as

λk+1=g(yk)+z^k,\boldsymbol{\lambda}_{k+1} = \boldsymbol{g}(\boldsymbol{y}_k) + \hat{\boldsymbol{z}}_k,

that is, the new lifting variable is exactly the linearized flux after the step. Hence, by (61) and (65), the components λk+1,i\lambda_{k+1,i}, i=2,…,ni=2,\ldots,n, of λk+1\lambda_{k+1} in the flat region are of order τ\tau. This holds for all values of λk\lambda_k, since (65) does not depend on DD. In particular, for the first step, λ0=0\lambda_0=0 gives diL=∣yi∣p−2≈1/∣yi∣d_i^L=|y_i|^{p-2}\approx1/|y_i|, so that the first lifted Newton step coincides with a Picard step and equals τ\tau times the first standard Newton step. After the step, λi=O(τ)\lambda_i=O(\tau) in the flat region, (61) gives diL≈1/∣yi∣d_i^L\approx1/|y_i| again, and the argument repeats. On the two boundary intervals, in contrast, λ1≈g(y1)≈1\lambda_1\approx g(y_1)\approx1 and λn+1≈−1\lambda_{n+1}\approx-1 after the first step, so that there dL≈dSd^L\approx d^S and lifted Newton reduces to standard Newton, which converges quadratically in the steep region.

To summarize, the two linearizations agree on what the flux should do. Standard Newton converts the flux increment into a primal increment using the tangent slope τ/∣y∣\tau/|y| of the nearly flat function gg and hence overshoots by 1/τ1/\tau, whereas lifted Newton uses the secant slope 1/∣y∣1/|y| and lands on the flat solution, up to O(τ)O(\tau), in one step. This is the one-dimensional instance of the mechanism described in section 3.3: the dual direction lags behind the primal direction and filters out the extreme sensitivity of wε\boldsymbol{w}_{\varepsilon} in regions where the gradient is small.

References

  1. [1]Albersmeyer, J., Diehl, M.: The lifted Newton method and its application in optimization. SIAM J. Optim. 20(3), 1655–1684 (2010) https://doi.org/10.1137/080724885
  2. [2]Alnæs, M.S., Logg, A., Ølgaard, K.B., Rognes, M.E., Wells, G.N.: Unified form language: A domain-specific language for weak formulations of partial differential equations. ACM Trans. Math. Softw. 40(2), 9–1937 (2014) https://doi.org/10.1145/2566630
  3. [3]Andersen, K.D., Christiansen, E., Conn, A.R., Overton, M.L.: An efficient primal-dual interior-point method for minimizing a sum of Euclidean norms. SIAM J. Sci. Comput. 22(1), 243–262 (2000) https://doi.org/10.1137/S1064827598343954
  4. [4]Anderson, R., Andrej, J., Barker, A., Bramwell, T., Camier, J.-S., Cerveny, J., Dobrev, V., Dudouit, Y., Fisher, A., Knupp, P., Kolev, T., Medina, C., Moon, S.-J., Pazner, W., Petersson, T., Phillips, D., Rieben, R., Severino, G., Tomov, V., Vaughan, G., Wilcox, C., Woodward, C.: MFEM: A modular finite element methods library. Computers & Mathematics with Applications 81, 42–74 (2021) https://doi.org/10.1016/j.camwa.2020.06.009
  5. [5]Balay, S., Abhyankar, S., Adams, M.F., Benson, S., Brown, J., Brune, P., Buschelman, K., Constantinescu, E., Dalcin, L., Dener, A., Eijkhout, V., Faibussowitsch, J., Gropp, W.D., Hapla, V., Isaac, T., Jolivet, P., Karpiev, D., Karpeev, D., Kaushik, D., Knepley, M.G., Kong, F., Kruger, S., May, D.A., McInnes, L.C., Mills, R.T., Mitchell, L., Munson, T., Roman, J.E., Rupp, K., Sanan, P., Sarich, J., Smith, B.F., Suh, H., Zampini, S., Zhang, H., Zhang, H., Zhang, J.: PETSc/TAO users manual. Technical Report ANL-21/39 - Revision 3.22, Argonne National Laboratory (2024) https://doi.org/10.2172/2205494
  6. [6]Bock, H.G., Plitt, K.J.: A multi-phase shooting algorithm for direct solution of optimal control problems. IFAC Proc. Vol. 17(2), 1603–1608 (1984) https://doi.org/10.1016/S1474-6670(17)61205-9
  7. [7]Brezzi, F., Fortin, M.: Mixed and Hybrid Finite Element Methods. Springer Series in Computational Mathematics, vol. 15, p. 350. Springer, New York (1991). https://doi.org/10.1007/978-1-4612-3172-1
  8. [8]Brown, J., Smith, B., Ahmadia, A.: Achieving textbook multigrid efficiency for hydrostatic ice sheet flow. SIAM J. Sci. Comput. 35(2), 359–375 (2013) https://doi.org/10.1137/110834512
  9. [9]Brune, P.R., Knepley, M.G., Smith, B.F., Tu, X.: Composing scalable nonlinear algebraic solvers. SIAM Rev. 57(4), 535–565 (2015) https://doi.org/10.1137/130936725
  10. [10]Buliček, M., Gwiazda, P., Málek, J., Świerczewska-Gwiazda, A.: On unsteady flows of implicitly constituted incompressible fluids. SIAM J. Math. Anal. 44(4), 2756–2801 (2012) https://doi.org/10.1137/110830289
  11. [11]Burman, E., Ern, A.: Continuous interior penalty hp-finite element methods for advection and advection-diffusion equations. Math. Comput. 76(259), 1119–1140 (2007) https://doi.org/10.1090/S0025-5718-07-01951-5
  12. [12]Chan, T.F., Golub, G.H., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20(6), 1964–1977 (1999) https://doi.org/10.1137/S1064827596299767
  13. [13]Cuffey, K.M., Paterson, W.S.B.: The Physics of Glaciers, 4th edn. Butterworth-Heinemann/Elsevier, Burlington, MA (2010)
  14. [14]De los Reyes, J.C., González Andrade, S.: Path following methods for steady laminar Bingham flow in cylindrical pipes. ESAIM Math. Model. Numer. Anal. 43(1), 81–117 (2009) https://doi.org/10.1051/m2an/2008039
  15. [15]Deuflhard, P.: Newton Methods for Nonlinear Problems. Springer Series in Computational Mathematics, vol. 35. Springer, Berlin (2004)
  16. [16]Dolean, V., Gander, M.J., Kheriji, W., Kwok, F., Masson, R.: Nonlinear preconditioning: How to use a nonlinear Schwarz method to precondition Newton’s method. SIAM J. Sci. Comput. 38(6), 3357–3380 (2016) https://doi.org/10.1137/15M102887X
  17. [17]Ekeland, I., Temam, R.: Convex Analysis and Variational Problems. Classics in Applied Mathematics, Vol. 28. SIAM, Philadelphia (1999). https://doi.org/10.1137/1.9781611971088
  18. [18]Gander, M.J.: On the origins of linear and non-linear preconditioning. In: Domain Decomposition Methods in Science and Engineering XXIII. Lecture Notes in Computational Science and Engineering, pp. 153–161. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-52389-7_14
  19. [19]Ham, D.A., Kelly, P.H.J., Mitchell, L., Cotter, C.J., Kirby, R.C., Sagiyama, K., Bouziani, N., Vorderwuelbecke, S., Gregory, T.J., Betteridge, J., Shapero, D.R., Nixon-Hill, R.W., Ward, C.J., Farrell, P.E., Brubeck, P.D., Marsden, I., Gibson, T.H., Homolya, M., Sun, T., McRae, A.T.T., Luporini, F., Gregory, A., Lange, M., Funke, S.W., Rathgeber, F., Bercea, G.-T., Markall, G.R.: Firedrake User Manual, First edition edn. Imperial College London and University of Oxford and Baylor University and University of Washington, (2023). https://doi.org/10.25561/104839 . Imperial College London and University of Oxford and Baylor University and University of Washington
  20. [20]Heinlein, A., Klawonn, A., Lanser, M.: Adaptive nonlinear domain decomposition methods with an application to the p-Laplacian. SIAM J. Sci. Comput. 45(3), 152–172 (2022) https://doi.org/10.1137/21M1433605
  21. [21]Hintermüller, M., Stadler, G.: An infeasible primal-dual algorithm for total variation-based inf-convolution-type image restoration. SIAM J. Sci. Comput. 28(1), 1–23 (2006) https://doi.org/10.1137/040613263
  22. [22]Huang, Y., Li, R., Liu, W.: Preconditioned descent algorithms for p-Laplacian. J. Sci. Comput. 32(2), 343–371 (2007) https://doi.org/10.1007/s10915-007-9134-z
  23. [23]Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. Frontiers in Applied Mathematics, vol. 16. SIAM, Philadelphia (1995)
  24. [24]Kohn, R., Serfaty, S.: A deterministic-control-based approach to motion by curvature. Commun. Pure Appl. Math. 59(3), 344–407 (2006) https://doi.org/10.1002/cpa.20101
  25. [25]Lanzkron, P.J., Rose, D.J., Wilkes, J.T.: An analysis of approximate nonlinear elimination. SIAM J. Sci. Comput. 17(2), 583–559 (1996) https://doi.org/10.1137/S106482759325154X
  26. [26]Liu, L., Keyes, D.E.: Convergence analysis for the multiplicative Schwarz preconditioned inexact Newton algorithm. SIAM J. Numer. Anal. 54(5), 3145–3166 (2016)
  27. [27]Liu, L., Hwang, F.-N., Luo, L., Cai, X.-C., Keyes, D.E.: A nonlinear elimination preconditioned inexact Newton algorithm. SIAM J. Sci. Comput. 44(3), 1579–1605 (2022) https://doi.org/10.1137/21M1416138
  28. [28]Logg, A., Mardal, K.-A., Wells, G.: Automated Solution of Differential Equations by the Finite Element Method: The FEniCS Book. Springer, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-23099-8
  29. [29]Loisel, S.: Efficient algorithms for solving the p-Laplacian in polynomial time. Numer. Math. 146(2), 369–400 (2020) https://doi.org/10.1007/s00211-020-01141-z
  30. [30]Margen̈berg, N., Mehlmann, C.: A scalable monolithic modified Newton multigrid framework for time-dependent p-Navier–Stokes flow. Preprint (2026). https://doi.org/10.48550/arXiv.2603.28706
  31. [31]Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006)
  32. [32]Oberman, A.M.: Finite difference methods for the infinity Laplace and p-Laplace equations. J. Comput. Appl. Math. 254, 65–80 (2013) https://doi.org/10.1016/j.cam.2012.11.023
  33. [33]Pollock, S., Rebholz, L.G., Tu, X., Xiao, M.: Analysis of the Picard–Newton iteration for the Navier–Stokes equations: global stability and quadratic convergence. J. Sci. Comput. 104(1), 25 (2025) https://doi.org/10.1007/s10915-025-02946-6
  34. [34]Rudi, J.: Global convection in Earth’s mantle: Advanced numerical methods and extreme-scale simulations. PhD thesis, The University of Texas at Austin (2018)
  35. [35]Rudi, J., Shih, Y.-H., Stadler, G.: Advanced Newton methods for geodynamical models of Stokes flow with viscoplastic rheologies. Geochem. Geophys. Geosyst. 21(9), 2020–009059 (2020) https://doi.org/10.1029/2020GC000959
  36. [36]Schmidt, N.: Global convergence of Newton’s method for the regularized p-Stokes equations. Numer. Algorithms 99(4), 2011–2038 (2025) https://doi.org/10.1007/s11075-024-01941-6
  37. [37]Shih, Y.-h., Mehlmann, C., Losch, M., Stadler, G.: Robust and efficient primal-dual Newton–Krylov solvers for viscous-plastic sea-ice models. J. Comput. Phys. 474, 111802 (2023) https://doi.org/10.1016/j.jcp.2022.111802
  38. [38]Turcotte, D.L., Schubert, G.: Geodynamics, 2nd edn. Cambridge University Press, Cambridge (2002). https://doi.org/10.1017/CBO9780511807442
  39. [39]Zampini, S., Boffi, D., Dovletov, G., Markowich, P.A.: Auxiliary gradient-flow solvers for generalized Newtonian models. Preprint (2026). https://doi.org/10.48550/arXiv.2606.05926

Paper details

vlnc:W_k4wfjpha
Version
v1 · latest
Published
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

Not recorded for this paper

View statement
Looking for related papers…
Contents