WorksMathematics
Transform before linearizing: robust Newton methods for singular -Laplace and -Stokes equations
Abstract
For , the -Laplace equation and its -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 . 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 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 -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 close to one. Firedrake-based experiments for -Laplace problems in two and three dimensions and for stationary and time-dependent -Stokes flows show iteration counts largely insensitive to and to mesh refinement, and up to an order of magnitude fewer iterations than standard Newton for close to one.
Introduction
For , the -Laplace equation
defined over a domain is the prototypical quasilinear elliptic problem. It arises as the Euler–Lagrange equation of the -Dirichlet energy . For , it reduces to the linear Poisson problem; for any other exponent, it is genuinely nonlinear. Operators similar to the -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 [8, 13], problems in geodynamics [38], and motion by curvature in the limit [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 concentrates the nonlinearity in a quantity that becomes singular for , i.e., it diverges at points where , and degenerate for , where the linearized operator loses ellipticity. Second, solutions are not classically smooth: weak solutions are only known to be for some , and regularity properties deteriorate as 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 . Writing the unit gradient direction (and, for now, assuming that the gradient does not vanish), the Newton increment solves
followed by the update with step length .
Instead, Picard freezes the diffusion coefficient at the current iterate and computes by solving the linear problem
followed again by with . A common, mathematically equivalent variant of (3) is to write it directly in terms of under the assumption (which is the typical choice for Picard). Comparing (2) and (3), it can be seen that the only difference is the anisotropic term , 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 deviates from 2, especially in the regime , 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 [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 . Continuation strategies in [22] alleviate this issue at the price of solving a sequence of auxiliary problems.
Approach and related literature
In this paper, we propose the following strategy for singular -Laplace and -Stokes problems, i.e., . 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 -Laplace equation (1), this is the flux , and for our generalization to -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 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 -Laplacian with , [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 -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 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 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 -Laplace and -Stokes systems and provide arguments supporting its superior convergence behavior.
Upon discretization and replacing the gradient operator with a general matrix , the discrete -Dirichlet energy associated with (1) becomes an -regression problem of the form . 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 , 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 -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 . 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 , in two and three dimensions for -Laplace equations. Our generalizations to -Stokes and time-dependent -Navier–Stokes indicate an up to order-of-magnitude reduction in required linear solves compared to standard Newton for 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 . 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 -Laplace equation only, and the constants in the analysis deteriorate as 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 unknowns, we do not study the use of preconditioned iterative Krylov solvers.
The -Laplace equation
In this section, we summarize the functional-analytic setting for the -Laplace equation (1) and introduce equivalent problem formulations that motivate different solution strategies. We assume a bounded Lipschitz domain (), a source term (with ), and given boundary data . Then the -Laplace problem is
where controls the degree of nonlinearity. The natural setting is the Sobolev space : weak solutions of (4) with homogeneous boundary data (i.e., ) are the unique minimizers of the strictly convex energy
Strict convexity of on ensures the existence and uniqueness of a weak solution . Since nonzero Dirichlet boundary data can be treated by extending to the whole domain and then solving for a corrective term to that extension, we assume 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 . Since this equation is only well defined if on all of , one often considers the regularized norm
in (4) and (5), with . This results in a well-defined Newton step of the form (2) with all norms replaced by . 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 -valued variable for all . The resulting system in the independent variables is now
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 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 with and . Fenchel duality gives the dual functions and if and otherwise. Thus, the dual problem is
with in . 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 and can be written in several equivalent forms. For instance, recognizing that (8) implies , (8) is equivalent to . A similar, equivalent form for (8) is
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 and , we use the regularized norm from (6) in the development of our Newton-type methods. Replacing by in (5) results in the modified objective
and taking first variations yields the following functional , i.e., the -Laplace equation residual:
Integrating by parts shows that, for every ,
i.e., is the derivative of , regarded as an element of . In the following we use whichever of the two viewpoints is more convenient: the energy derivative where descent properties are at issue, and the residual when reporting computed quantities.
Introducing an independent variable as above results in the following regularized counterparts of (7), (8):
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 for all , (14) is equivalent to
We introduce the corresponding normalized directions
and refer to as the primal direction and to as the dual direction. The former is the regularized counterpart of the unit gradient direction used in (2); throughout this section, we suppress the iteration index. Note that precisely when and satisfy the optimality condition (14).
Treating and as independent variables in (13) and (15), we can now derive the Newton step for this lifted system for the increments :
The right hand side of (18) admits a simple interpretation in terms of the normalized directions (16), namely
Up to the scaling by , 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 and therefore has a higher dimension than the original -Laplace equation. To avoid computing the Newton increment in the lifted space, we isolate the flux increment in equation (18) and obtain the pointwise relation
Using this in (17) and applying simple algebraic simplification results in a PDE in the Newton increment only:
Note that the right hand side of this equation is the negative equation residual defined in (11). Thus, if solves that equation, the increment vanishes, as expected.
We compare this to the equation for the Newton increment for the original -Laplace equation without lifting, using the same regularization:
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 , while standard Newton uses the primal direction . In particular, the two linear systems coincide as soon as , 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) -Laplace equation. The reason is that the lifted system is linear in , and (14) can be solved explicitly for .
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 . Newton’s method is invariant under affine transformations of the residual with a constant invertible [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 defined in (16) satisfies , it can be seen that for the standard Newton linearization (21), the diffusion tensor is symmetric and positive definite for all . 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
may fail to be positive definite, since and the norm of is no longer bounded by one; in addition, it is not symmetric unless and 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 , the Cauchy–Schwarz inequality gives
Since , positive definiteness is assured when . We therefore enforce, for all , the pointwise feasibility bound , or equivalently
for a parameter , which we restrict further below. Combining (24) with (23) yields the two-sided bound
so that the diffusion tensor of (20) is uniformly positive definite whenever .
The parameter should not be chosen arbitrarily small. At convergence, we have and as , so a value of with would be active even at the solution of (13), (14). This would destroy the consistency that is desirable for local fast convergence. We therefore require , which, together with , leaves the admissible, always nonempty window
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
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 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 , 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 and for the directions (16) evaluated at the -th iterate, and recall the regularized objective (10) with corresponding (lifted) stationarity conditions (13), (14).
We assume that satisfies (26), and enforce the feasibility bound only at where it is needed, namely in the construction of the diffusion tensor. We define
so that pointwise. The associated direction is thus the projection of onto the ball of radius , so that (24) holds at every iterate and for every . The method then proceeds as follows.
(i) Initialize: set , initialize such that it satisfies the desired nonhomogeneous Dirichlet boundary conditions as in (4), initialize , and choose the Armijo parameter .
(ii) Assemble and solve: use the symmetrized diffusion tensor (27) with the projected direction,
to assemble and solve the system for the primal increment , i.e., solve (20) with diffusion tensor and homogeneous Dirichlet boundary conditions.
(iii) Recover: compute the lifting variable increment pointwise from (19),
(iv) Line search: choose as the largest number in with
(v) Update and advance: set and . Set and return to step (ii), until a stopping criterion is met.
Several things should be pointed out. First, eliminating from the lifted system cancels from the right-hand side of the system solved in step (ii), so the lifting variable influences the primal iterate only through . Projecting it there is therefore enough, and no constraint needs to be placed on itself. One may also project after each update; this variant of the algorithm is briefly discussed in Appendix A. Second, is symmetric and, by (25), uniformly positive definite for every and every initial guess . Since , the projection (28) is inactive whenever 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 makes the rank-one term vanish, so that 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 and , 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 -Laplace equation with . 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 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 -Laplace equation in infinite dimensions is very challenging due to the lack of Hilbert space structure. One remedy, followed in [36] for the -Stokes system, is to use Hilbert space regularization. That is, in addition to the regularization , a term with is added to the energy, which places the problem in . We take a different approach and establish global convergence for the discretized problem, that is, in a finite-dimensional setting: after fixing , compactness of the discrete energy sublevel set provides the coercivity constant that the 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 be a fixed conforming finite element space and let . We equip with the seminorm . We use to denote the dual space of , and denote its norm by . We study the lifted Newton iteration of section 2.4, discretized in . We consider an extension of the Dirichlet data to the domain and an iteration with a lifting variable . Then, the increment of step (ii) is determined by solving the finite element approximation of (20) with the diffusion tensor as in (29); the remaining steps (iii)–(v) are carried out unchanged. We denote by the discrete residual at the iterate , i.e., the restriction to of the functional (11). By (12) it satisfies for all . Since , the dual norm used below is the 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 satisfy (26) and assume arbitrary initializations and . Then the (discrete) iterates produced by the iteration of section 2.4 converge globally, in the sense that the discrete residual in , and
where is the unique minimizer of over .
Proof. Consider the sublevel set , which is bounded because as . Since is finite-dimensional, is compact, and therefore . We prove the uniform boundedness and coercivity of the linearization resulting from the lifting approach on the sublevel set. To this end, suppose that . We first derive pointwise spectral bounds for defined in (29). For any , (25) gives
where and . Denoting
we thus have
The pointwise bounds (33) imply that defines an inner product on , so the primal increment is uniquely defined by for all . Choosing gives
If , then on , and strict convexity shows that . We may therefore assume below that .
Next, we bound the energy along the search direction. Since , the map is concave and thus lies below its tangent line at any . Applying this pointwise with and , whose difference is , then dividing by , integrating, and adding the linear load term to both sides gives
for all , , and . Note that the last term in (35) is the bilinear form of the Picard iteration (3), which majorizes the curvature of because . The estimate (35) holds globally in and involves no remainder term.
We now take and . The lower bound in (25) gives
so that (35) and (34) yield, for every ,
By (34), the Armijo condition (31) requires a decrease of at least . Comparing with (36), it is therefore satisfied as soon as the bracket is at least , that is, whenever . Since the line search halves the trial step starting from , it terminates with an accepted step size . Since (31) and (34) give , starting from , induction therefore proves that the iteration is well defined and that every remains in . Using (34), (31), and the lower bound on , we obtain
Since is bounded below, summation over shows that . Cauchy–Schwarz in the -inner product and the upper bound in (33) give, for every ,
so that in by [12]. Compactness of and strict convexity of then prove in .
Next, we prove the convergence of the discretized lifting variable . The discretized lifting variable is defined at the quadrature points by , and it is thus an element of . We denote 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 , we define .
Corollary 2 (Pointwise convergence of the lifting variable) Under the assumptions of theorem 1, for every ,
Proof. For a fixed , let , and . Since cell-local gradient evaluation is continuous on the fixed finite-dimensional space , and is continuous, the convergence gives , and thus
At the same quadrature point, (30) and step (v) of section 2.4 give
By the upper bound in (32), for every , we have . Moreover, the proof of theorem 1 showed that . Thus, with
we have
Here by the convergence statements above. Since in addition , this gives , and the pointwise convergence now follows from .
Note that the coercivity constant depends on the bound , which comes from the compactness of the fixed finite element sublevel set. In the continuous space, an energy sublevel set gives an -bound but not an -bound on . Therefore, the same argument does not yield a mesh-independent coercivity constant for on unless one adds an additional uniformly elliptic term as in [36] or assumes a priori an 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 . 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 in (14),
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 of the pair , and the observation that the lifting variable update reduces this inconsistency quadratically.
Below, all pointwise quantities are evaluated at the quadrature points , and is the maximum over these points; we write for the second term in (39). Since is finite-dimensional, there is a constant with for all . Since , the map of corollary 2 is smooth, with
which is the diffusion tensor of standard Newton (21), and and for all . We write for the standard Newton tensor at the -th iterate. All constants below depend only on , , , and .
Lemma 3 (Jacobian error) For every ,
Proof. Comparing (29) and (40), . Since by (26), the projection (28) leaves fixed and is 1-Lipschitz, so that . Using and gives (41). □
The second ingredient concerns the lifting variable. Suppose that a unit step is taken, . Then (30) and step (v) of section 2.4 give , whereas Taylor expansion of gives with . Subtracting the two identities, the first-order terms cancel, and we obtain
This cancellation makes the method second order: the lifting variable update (30) adds to exactly the first-order change of , up to the Jacobian error. Together with (41) and the inverse estimate, (42) yields
Theorem 4 (Local quadratic convergence) Let the assumptions of theorem 1 hold and let the Armijo parameter satisfy . Then there exist and , independent of , such that implies and
In particular, since by theorem 1 and corollary 2, the iteration eventually takes unit steps and converges quadratically.
Proof. Consider the discrete residual on the finite-dimensional space with norm . Its Jacobian at is the operator induced by the bilinear form ; it is Lipschitz continuous by the bound on and the inverse estimate, and is invertible since is uniformly positive definite. The primal increment satisfies , where is the operator induced by , so the primal iteration is a Newton method with the perturbed Jacobian , with by lemma 3. Moreover, by (34), (33), and ,
Since and is a descent direction by [34], the sufficient decrease condition (31) holds at as soon as and the relative Jacobian perturbation are small enough; see the proof of [31], Theorem 3.6, which only uses the Armijo condition. Both quantities are bounded by , so there is such that implies . With , the perturbed-Jacobian estimate of [23], Theorem 5.4.1 gives, for (after decreasing if necessary),
By (42) and (44), . Adding the two estimates gives (43). □
The constant degrades in the two limits that make the problem hard: through the factor in (40) and the factor in (41) as , and through , which carries by (26), as . The same dependence on and 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 near 1, where solving (4) is particularly difficult.
Prevalence of -flat regions. First, note that solutions of the -Laplace equation exhibit largely flat regions, especially when is close to 1. This is evident from the energy formulation (5), which converges to the -norm of the gradient as . Such objectives promote sparsity, meaning the gradient vanishes over large parts of the domain and variation concentrates on small sets. In the -regularized problem, the relevant notion of flatness corresponds to values of of an order of magnitude of 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 , which is common to all methods considered here and thus cannot account for differences between them. The second is through the direction entering the rank-one term. Where , this direction is influential but well determined and varies smoothly. In deeply flat regions, , it is poorly determined and highly sensitive to changes in , but it is also of little influence since suppresses the rank-one term and the Newton methods reduce to the Picard operator. It is when that is simultaneously influential and highly sensitive to small changes in . The two methods respond differently to this sensitivity. In the standard Newton method, the rank-one term is and both of its factors are recomputed from the current iterate. The Newton direction 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, is updated only through (30), so the factor lags behind . This matters quantitatively: in the direction of , the standard Newton tensor has eigenvalue , i.e., it is times more compliant than the Picard operator exactly where the residual points in flat regions, whereas with a small lagged 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 -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 shows that, on the plateau, standard and lifted Newton compute the same increment of the flux , namely the one that drives it to zero. They differ in how this flux increment is converted into an increment of (note that here ): standard Newton divides by the tangent slope of the nearly flat constitutive function, so that every gradient on the plateau changes sign and grows by a factor , whereas lifted Newton with a small lagged divides by the secant slope and sets the plateau gradients to zero up to in one step. The update of the lifting variable then yields on the plateau from the first iteration on. Figure 1 shows both iterations for and a random initialization within an interval of length 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 , 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 -Laplace problem introduced in appendix B with . Each panel shows the projection of iterates onto the two-dimensional subspace given by two nodal values.
Numerical results: -Laplace
Implementation and comparisons
We implement the lifted Newton method for the -Laplace (and for the -Stokes problem in section 5 below) with the finite element (FE) library Firedrake [19]. The FE method represents the discrete solution in a finite element space and solves a weak formulation of the associated PDE. For the lifted Newton method, given the discrete variables and , we seek an increment , where denotes the subspace of that incorporates homogeneous Dirichlet boundary conditions. The increment solves the linear system (20) with the symmetrized diffusion tensor (27). Writing and for the discrete counterparts of the directions (16), its weak form reads
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 is represented. Note that the computation of is purely algebraic, in the sense that (30) does not involve derivatives of . Moreover, the linear system (46) only requires the values of at quadrature points. For these reasons, we do not introduce 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 . 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 and 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 -Laplace problem (4) for different values of with , 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 -Laplace equation, and some of these approaches are later applied to the -Stokes problems in section 6.
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 . 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 and . We use a slight modification of the Armijo line search and use
where at the order of machine precision (we use ). 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 may not change, even though the residual can still be decreased by accepting a full update step.
In our numerical experiments we set in (47). While this line-search variant does not enforce a prescribed fraction of the predicted decrease, the coercivity of ensures that 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 yields the same number of iterations. Iterations are terminated when the relative norm -norm of the residual reaches , or after 500 iterations, indicating that the method takes too long to converge.
Two-dimensional -Laplace equation example
In this subsection, we use a two-dimensional example for the -Laplace equation (4) taken from [29]. Let , , and we enforce a Dirichlet condition given by the characteristic function , where
We initialize the primal solution by and impose the Dirichlet boundary condition strongly. The lifting variable is initialized as , 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 regular grids with and crossed diagonals. Each square of the Cartesian partition is split into four triangles, so the three meshes contain , 10,000, and 40,000 triangles, respectively.
In Figure 2, we show the solutions for several values of together with the performance of the different solvers on the grid. One observes that, as 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 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 , so it fails to achieve the prescribed relative tolerance for on all three grids. The hybrid PN offers a substantial improvement over both P and SN, but for 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 , SN spends a long initial phase accepting strongly damped steps; many accepted steps are approximately . On the other hand, LN takes only a few damped steps before accepting full steps, which accelerates the convergence.

Figure 2. Solutions and convergence behavior for the two-dimensional -Laplace example on the grid (10,000 triangles). The top row shows the solutions for , , and . The middle row shows the relative -norm of the residual, i.e., , with a shared vertical scale. Normalization is performed separately for each ; 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.
| Method | |||||
| SN | 15/18/22 | 23/29/33 | 34/40/57 | 79/87/105 | 283/329/358 |
| LN | 9/11/11 | 10/10/10 | 18/15/16 | 18/19/20 | 23/21/24 |
| P | 15/15/15 | 38/38/38 | 112/119/123 | 203/218/232 | n.c./n.c./n.c. |
| PN | 8/8/8 | 12/14/18 | 24/28/30 | 32/38/46 | 62/80/92 |
Table 2. Number of iterations needed for convergence by different methods applied to the two-dimensional -Laplace problem. Each table entry gives the iteration counts for the , , and 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 values; each entry lists the counts for , 50, and 100. For , the spread of required iterations is modest on every grid, whereas the discrepancies between them increase markedly as 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 . For , a smaller makes the problem more singular and generally increases the number of iterations required for convergence. In particular, for and , 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 -regularization for solver robustness.
| Method | ||||||
| SN | 19 | 27 | 38 | 65 | 206 | |
| SN | 18 | 29 | 40 | 87 | 329 | |
| SN | 18 | 21 | 41 | 112 | 443 | |
| SN | 17 | 22 | 42 | 127 | n.c.† | |
| LN | 8 | 11 | 12 | 15 | 18 | |
| LN | 11 | 10 | 15 | 19 | 21 | |
| LN | 9 | 11 | 19 | 21 | 31 | |
| LN | 9 | 11 | 21 | 23 | 30† |
Table 3. Comparison of the number of iterations required by SN and LN for various regularization parameters in the two-dimensional -Laplace example for . As done throughout, the iteration is terminated when the relative residual reaches ; the entries marked with † correspond to a relative residual of . For these tests, the residual does not decrease to , likely due to rounding errors due to extreme values of and .
Three-dimensional -Laplace equation example
In this subsection, we consider a three-dimensional -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 , again set and use the Dirichlet boundary data , where
Similar to the previous two-dimensional example, this corner-cutting problem produces a sharp transition close to , especially for . To properly refine this transition zone, we use a locally refined finite element mesh. We start from a uniform Cartesian partition of the cube 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 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 since the slab is very thin. The resulting mesh used in the computations contains tetrahedra, of which 3,612 intersect . Plane-intersecting cells have a diameter of . 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.

Figure 3. Solution and convergence behavior for the three-dimensional -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 (with the mesh visualized), , and . The middle row compares the relative -norm of the residual 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 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 approaches 1.
| Discretization | Method | |||
| CG1 | SN | 10 | 43 | 257 |
| CG1 | LN | 7 | 15 | 21 |
| CG1 | P | 15 | 102 | n.c. |
| CG1 | PN | 8 | 30 | 50 |
| CG2 | SN | 14 | 47 | 242 |
| CG2 | LN | 7 | 15 | 24 |
| CG2 | P | 15 | 105 | n.c. |
| CG2 | PN | 8 | 26 | 44 |
Table 4. Iterations required for convergence of the various methods on the locally refined mesh with tetrahedra, using linear (CG1) and quadratic (CG2) finite elements. The “n.c.” means that the prescribed tolerance was not reached within 500 iterations.
| Cells | Method | ||||
| SN | 19 | 49 | 59 | 228 | |
| LN | 4 | 12 | 15 | 18 | |
| SN | 29 | 51 | 67 | 263 | |
| LN | 5 | 12 | 18 | 21 | |
| SN | 47 | 50 | 69 | 285 | |
| LN | 5 | 12 | 15 | 22 |
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 , 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 -Stokes problem, a generalization of the -Laplacian of section 2 obtained by coupling the same type of power-law nonlinearity to an incompressibility constraint [10, 13]. The -Stokes system describes the slow, creeping flow of a generalized Newtonian (power-law) fluid. It differs from the -Laplace problem in that the unknown is a divergence-free vector field. For , 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 gets close to 1 [30, 36]. We next specify the -Stokes problem and then follow the same lift–transform–linearize–eliminate procedure as in section 2.2.
Let , , be a bounded Lipschitz domain with boundary . In the -Stokes problem, we seek a velocity field and a pressure satisfying
where is the symmetric velocity gradient (strain rate tensor) and , are prescribed data. Clearly, more complicated boundary conditions are possible, but we restrict ourselves to Dirichlet conditions for simplicity. The deviatoric extra-stress tensor is given by a power-law constitutive relation
with and is the second invariant of the strain rate tensor.
As in section 2, we introduce a small parameter to regularize the second invariant of the strain-rate tensor, thereby avoiding the singularity for . Specifically, we set , and define the associated regularized stress by \Lambda(x) := S_{\varepsilon}(Du)(x) and consider the following regularized, lifted, and transformed system for (\boldsymbol{u},\pi,\Lambda)$:
together with boundary conditions as in (47). Following the same procedure as in section 2.2, we linearize (48) around in the direction . Then, by isolating the increment and eliminating it from the system, we arrive at the following linearized system for the velocity/pressure increment :
where and , and where a rank-one fourth-order tensor acts on a second-order tensor as . Note the direct analogy with (20): for , the terms , and in the -Laplace problem play the role of , and , respectively. The matrix–vector product is replaced by its tensorial counterpart.
Writing
for the resulting fourth-order diffusion tensor, where is the identity on symmetric second-order tensors, the increment of the lifting variable is recovered pointwise from
in analogy with (30). Substituting (57) into the linearized momentum equation cancels from the right-hand side, which is why only appears in eq:49; as in section 2.4, the lifting variable influences the velocity increment only through .
The two modifications of section 2.3 that guarantee the well-posedness of eq:49 also carry over. The symmetrization used in (56) leaves the quadratic form unchanged, but makes self-adjoint, so that the velocity block of the saddle-point system eq:49 is symmetric. The feasibility bound is imposed on as in (24), but scaled by the viscosity constant: with as in (26), we enforce
by replacing in (56) by its pointwise projection onto the ball of radius , as in (28). The iterate itself remains unchanged. Since , this yields the bounds
for every symmetric , the direct counterpart of (25). The velocity block is therefore uniformly elliptic for every choice of , 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 -Stokes problem in section 6.1 and for a time-dependent problem modeling the -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 -Laplace implementation. Analogously to before, the lifting variable 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 , , . 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 -Stokes flow problem. We consider eq:47 on , with and , and with the (smoothed) driving lid Dirichlet data on the top boundary and the Dirichlet condition on the remaining boundaries. In these computations, we set the solution to the lid-driven cavity problem with as our initial guess in both the standard and lifted Newton methods. This avoids the failure of the nonlinear solvers for small values.
The flow field and the solver performance for different meshes and values of 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 . Furthermore, as the table indicates, the lifted method requires only moderately more iterations as decreases, and its iteration counts are largely insensitive to the mesh: for 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 approaches 1; on the finest mesh, it requires 285 iterations for , compared with 22 for LN, a factor of more than 13. Both methods show a mild mesh dependence at , but at levels that differ by more than an order of magnitude.

Figure 4. Solutions and convergence behavior for the lid-driven cavity -Stokes problem. We consider different values of in and meshes with increasing numbers of cells . The top row shows the velocity magnitude and streamlines for and on the most refined mesh, with a shared color scale for . The bottom row shows the relative 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 and various mesh sizes.
Flow around a cylinder for the -Navier–Stokes equations
As a second numerical example, we solve the time-dependent -Navier–Stokes (-NS) equations:
together with the divergence-free condition . Unlike the steady -Stokes problem, the -NS equations are time-dependent, and the convection term introduces an additional nonlinearity. For the -NS equation, we build a LN method exactly as for the -Stokes equation, i.e., by introducing a lifting variable that represents the deviatoric stress tensor . 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 . The domain is of length and height , with the cylinder of radius centered at . We enforce the velocity boundary conditions
Figure 5. In the top left figures above, each row presents the velocity magnitude field at . The top right figure shows the number of iterations per time step for three different values. In the table, for each we indicate the maximum and mean number of Newton iterations in time for SN and LN.
on the left boundary, with for and for . On the top and lower boundaries, we set , and on the right boundary, . As initial condition, we set the fluid velocity to zero. We run the simulation up to time for 3,392 time steps on a mesh of 4,961 cells. To be able to observe vortex shedding, we set , which results, for , in a nominal Reynolds number of about 100. These computations are challenging for two reasons: (1) For values of 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 norm of the discrete residual. For both SN and LN, the time steps that require the largest number of Newton iterations are those for , 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 approaches 1. Conversely, for LN, this increase is mild. For , both Newton methods require a similar number of iterations.
The advantage of LN is therefore concentrated in the stiff regime. At , the two methods are essentially indistinguishable in cost, whereas at , 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 , 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 -dependence of Newton’s and Picard’s methods is continuation in [22], and sometimes in . One solves a sequence of auxiliary problems, starting from (or a large ) 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 and , 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 is spectrally equivalent to the Picard operator , with constants and that are independent of the mesh and of . 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 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 for every , 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 . 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 , with iteration counts that differ by at most one or two. More substantial differences are seen as . For example, for the two-dimensional -Laplace problem with and , 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 . For the coefficient vanishes rather than blows up where , so no regularization is needed to define the residual, and the standard Newton tensor is uniformly positive definite. The difficulties for large are of a different kind: the diffusion coefficient degenerates in flat regions, its dynamic range grows like and leads to ill-conditioned systems and round-off sensitivity, and the energy becomes increasingly non-quadratic in steep regions. The transformation [9] is also the wrong one for : multiplying the constitutive relation by introduces a singularity at 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 with , i.e., one applies the approach of this paper to the dual problem of section 2.1, in which the exponent now lies in the range where the transformation is beneficial. A systematic study of lifting for is left for future work.
Open questions. Since , the coercivity constant guaranteed by (25) satisfies , so our bounds degrade as 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 , remains open. Equally open is a convergence result in the infinite-dimensional setting or with ; 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 itself is evolved unconstrained. An alternative is to project the iterate as well, i.e., to replace step (v) by
with as in (28) evaluated at , and to use itself in (29). As in (28), the last relation is understood pointwise and gives . Since the feasibility bound then holds for the iterate itself, the projection in the definition of 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 untouched, since implies
pointwise. Since the scaling in (58) is the pointwise projection onto the ball of radius 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.
| Method | |||||
| Lifted Newton from section eq:2.4 | 11 | 10 | 15 | 19 | 21 |
| Lifted Newton variant | 11 | 10 | 15 | 18 | 21 |
Table 5. Comparison of iterations required by lifted Newton method from section 2.4 and the variant discussed here for the two-dimensional -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 close to one. To make this explanation more concrete, this appendix analyzes the standard and lifted Newton steps for a one-dimensional -Laplace problem discretized with finite differences. The key observation is that both methods compute the same increment of the flux , 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 , and hence overshoots by a factor of , whereas lifted Newton uses a secant slope and gets close to the solution quickly.
Consider the -Laplace equation (4) on with homogeneous Dirichlet boundary conditions. We partition using uniformly distributed nodes with spacing and denote by the interior degrees of freedom, with . The finite difference gradient is , for . The discrete problem is the minimization of
Let denote the scalar constitutive function (the flux as a function of the gradient) and the vector with components . The residual is , with components .
To obtain a problem with a plateau in the solution, we choose such that the discrete solution is , i.e., , and for . From and we obtain and for , 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 from a linear system of the form
and differ only in the diagonal coefficients. For standard Newton, is the Hessian of , with
For lifted Newton with lifting variable , the one-dimensional counterpart of the diffusion tensor (27) is
where denotes the feasibility projection of , cf. (24). Note that if , 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
and we initialize with .
Expansions for small values of
We introduce and assume . Although determines which regions are flat, we assume for simplicity that for all , so that ; we found this to be accurate for the iterates in Figure 1, where . Since for bounded away from zero and infinity, to leading order in ,
where we used . The constitutive function is thus nearly the sign function: its tangent slope is of order , while the secant slope through the origin is of order one. Lifted Newton with uses this secant slope; with it recovers the tangent slope.
We introduce the linearized flux increment , so that for . In terms of , the Newton system (53) reads , i.e., for , and therefore
In one dimension, the flux increment is thus determined by the residual up to a single constant . This constant is fixed by the homogeneous boundary conditions, which imply that , and therefore
that is, is a convex combination of the values . Equations (62)-(63) are therefore an explicit solution formula for (59), valid for any positive diagonal .
The flux increment is the same for both methods
By the expressions for the residual and the forcing , the sums in (62) telescope,
and . Close to the solution, and , so that by (61) and . Thus,
To estimate the constant in (63), let denote the distance of the iterate from the solution and assume . For both methods, in the interior by (61), while at the two boundary intervals for standard Newton and for lifted Newton with , , and for the first lifted Newton step. Using (64) and , the convex combination (63) evaluates to
with . In all cases, , which is small compared to the unit-size values in (64). Inserting into (62) yields, in the flat region,
for both methods, i.e., they compute the same flux increment. As desired, the linearized flux 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 of the flux increment into a gradient increment. Combining (61) and (65), we find for
With a unit step, standard Newton replaces by : every gradient in the flat region changes sign and grows in magnitude by a factor of approximately . Since the residual is dominated by , 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 would be needed in the flat region to make the step useful, while the steep boundary intervals, where is well approximated by its tangent, allow for . The Armijo line search must compromise between the two, which explains the slow convergence of standard Newton on this problem. Lifted Newton with instead gives , so that a unit step sets the gradients in the flat region to zero up to .
The lifting variable in the flat region
It remains to justify that for and all . By the definition of , the update (60) of the lifting variable can be written as
that is, the new lifting variable is exactly the linearized flux after the step. Hence, by (61) and (65), the components , , of in the flat region are of order . This holds for all values of , since (65) does not depend on . In particular, for the first step, gives , so that the first lifted Newton step coincides with a Picard step and equals times the first standard Newton step. After the step, in the flat region, (61) gives again, and the argument repeats. On the two boundary intervals, in contrast, and after the first step, so that there 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 of the nearly flat function and hence overshoots by , whereas lifted Newton uses the secant slope and lands on the flat solution, up to , 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 in regions where the gradient is small.
References
- [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]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]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]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]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]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]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]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]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]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]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]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]Cuffey, K.M., Paterson, W.S.B.: The Physics of Glaciers, 4th edn. Butterworth-Heinemann/Elsevier, Burlington, MA (2010)
- [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]Deuflhard, P.: Newton Methods for Nonlinear Problems. Springer Series in Computational Mathematics, vol. 35. Springer, Berlin (2004)
- [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]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]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]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]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]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]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]Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. Frontiers in Applied Mathematics, vol. 16. SIAM, Philadelphia (1995)
- [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]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]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]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]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]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]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]Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006)
- [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]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]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]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]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]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]Turcotte, D.L., Schubert, G.: Geodynamics, 2nd edn. Cambridge University Press, Cambridge (2002). https://doi.org/10.1017/CBO9780511807442
- [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

