Source-linked AI summary
Deflation techniques for finding distinct solutions of nonlinear partial differential equations
Patrick E. Farrell, Ásgeir Birkisson, Simon W. Funke
TL;DR
Finding distinct nonlinear PDE solutions is difficult when initial guesses converge to the same solution. The paper introduces deflation, enabling repeated Newton solves from one initial guess and demonstrating usefulness across several nonlinear PDEs.
Problem
Computing distinct solutions can be challenging because almost all convergent initial guesses may reach the same solution.
Method
The paper extends deflation to infinite-dimensional Banach spaces, modifies residuals to eliminate known solutions, and preconditions the resulting dense Jacobians.
Results
Deflation finds three Allen–Cahn solutions from the same zero initial guess and finds both benchmark solutions in approximately one second.
Takeaways & Limitations
Deflation is useful across nonlinear PDEs from special functions, phase separation, differential geometry, and fluid mechanics, while complementing continuation methods.
Takeaways & Limitations
Deflation does not guarantee that all solutions will be found, and some deflation operators can cause erroneous convergence from small residuals away from solutions.
Abstract
from arXiv · showhide
Nonlinear systems of partial differential equations (PDEs) may permit several distinct solutions. The typical current approach to finding distinct solutions is to start Newton's method with many different initial guesses, hoping to find starting points that lie in different basins of attraction. In this paper, we present an infinite-dimensional deflation algorithm for systematically modifying the residual of a nonlinear PDE problem to eliminate known solutions from consideration. This enables the Newton--Kantorovitch iteration to converge to several different solutions, even starting from the same initial guess. The deflated Jacobian is dense, but an efficient preconditioning strategy is devised, and the number of Krylov iterations is observed not to grow as solutions are deflated. The power of the approach is demonstrated on several problems from special functions, phase separation, differential geometry and fluid mechanics that permit distinct solutions.
1. Introduction.
The paper develops deflation for finding distinct solutions of nonlinear PDEs by modifying the residual to exclude known solutions. It extends prior algebraic ideas to infinite-dimensional spaces, addresses implementation challenges, and contrasts deflation with continuation-based approaches.
- Deflation: Deflation modifies a nonlinear problem’s residual so iterative rootfinding will not converge to an already-identified solution.For norm deflation, the modified residual is G(x) = F(x) ||x − r||, with r a known solution.
- Contributions: The paper extends deflation from nonlinear algebraic systems to infinite-dimensional Banach spaces, enabling its use for systems of partial differential equations.It also introduces new deflation operators and discusses practical implementation details.
- Implementation: Deflation produces a dense Jacobian even when the original discretised residual Jacobian is sparse, motivating an efficient Sherman–Morrison preconditioner.The dense deflated Jacobian is described as a rank-one perturbation of the sparse original Jacobian.
- Numerical continuation: Continuation traces solution curves in augmented solution space and requires arclength-type parameterisations when the solution parameterisation by λ becomes singular.These curves produce bifurcation diagrams.
- Numerical continuation: For fixed λ below the Bratu–Gelfand critical value, deflation finds the second solution directly, whereas continuation traces the solution curve around a turning point.For λ < λcrit ≈ 3.51383, the ODE has two solutions; at λ = λcrit it has one, and above it none.
- Related techniques: The paper distinguishes its approach from deflation methods for multiple roots and from numerical algebraic geometry techniques for polynomial PDE nonlinearities.It presents comparison with numerical algebraic geometry separately and notes that the algorithm targets distinct solutions rather than singular multiple solutions.
2. Deflation for PDEs.
The paper extends deflation from finite-dimensional systems to Banach spaces, establishing conditions that exclude known solutions while preserving other roots. It develops norm-based variants, shifted deflation, and practical safeguards for numerical difficulties and large-scale PDE discretizations.
- Infinite-dimensional extension: Deflation is extended from algebraic systems to infinite-dimensional Banach spaces, providing the theoretical basis for applying it to PDEs.The extension is identified as the essential theoretical step for PDE applications.
- Deflation properties: A deflation operator excludes a known solution while preserving other solutions and avoiding spurious zeros of the modified residual.The procedure can be iterated after each newly found solution until the rootfinding method diverges.
- Deflation operators: Squared-norm deflation succeeds on the second Painlevé solution where norm deflation fails for the globalised Newton algorithm.The reported successful variant uses p = 2.
- Numerical difficulties: Exponentiated norm deflation can cause false convergence when small deflated residuals occur far from any solution.In the sigmoid example, p = 2 produces a residual of order 10^-13 at x ≈ −1.2×10^8.
- Shifted deflation: Shifted deflation adds αI so the deflated residual does not artificially approach zero far from previously found roots.For α > 0, the deflated residual approaches αF(u) away from deflated roots; α = 1 is suggested as a natural default.
- Large-scale implementation: Applying deflation to large discretized PDEs requires addressing the loss of Jacobian sparsity in the Newton linear system.The paper turns to implementation details for making deflation computationally viable at scale.
3. Implementation: sparsity and preconditioning.
Deflation makes the discretized Jacobian dense, even when the original Jacobian is sparse. The implementation therefore uses matrix-free Jacobian actions and a preconditioner based on the undeflated system, with Krylov iterations observed not to increase as solutions are deflated.
- Implementation: The deflated Jacobian action is obtained from the Fréchet derivative of the deflated residual in a direction δu.The scalar factor η(u) depends on the deflation operator and may incorporate multiple deflations.
- Sparsity: The deflated Jacobian is dense because it is a rank-one perturbation of the sparse undeflated Jacobian.This holds after discretization, even when the original Jacobian is sparse.
- Implementation: The discretized deflated Jacobian should be applied matrix-free rather than stored explicitly.Preconditioning also requires care for Newton–Krylov linear systems involving the dense Jacobian.
- Preconditioning: A preconditioner for the deflated system is constructed from an available left preconditioner for the undeflated Jacobian.The analysis examines this construction away from previously deflated roots, where η may be large when α is small.
- Preconditioning: For large η, the deflated and undeflated preconditioned operators are expected to differ little when the original preconditioner is effective.This scaling motivates using the undeflated preconditioner as the basis for the deflated system.
- Results: The number of Krylov iterations required is observed not to grow as more solutions are deflated.This is reported from computational experience with the preconditioned Newton–Krylov method.
4. Examples.
The examples apply deflation to distinct-solution problems in special functions, phase separation, differential geometry, and fluid mechanics. Across these cases, deflation finds multiple solutions from shared initial guesses, while preconditioning keeps Krylov costs approximately stable; continuation combined with reflection recovers an overlooked Navier–Stokes branch.
- 4.1. Special functions: Painlevé: Exactly two Painlevé solutions satisfy the boundary conditions, but most convergent initial guesses reach only u+; deflation computes u− from the same initial guess.Deflation with p = 2 and α = 0 required globalised damped Newton iteration, while p = 1 failed to converge.
- 4.3. Phase separation: Allen–Cahn: The Allen–Cahn experiment finds three solutions from an initial guess of zero: one unstable and two stable solutions.The stable solutions provide initialisation for the string method, whose minimum energy pathway passes through the unstable solution.
- 4.3. Phase separation: Allen–Cahn: The average number of Krylov iterations stays approximately constant as solutions are deflated in the Allen–Cahn and Yamabe experiments.The authors interpret this as evidence that the proposed preconditioning strategy remains effective despite dense deflated Jacobians.
- 4.3. Phase separation: Allen–Cahn: For every tested deflation-parameter family, the Allen–Cahn procedure finds more than one solution, although predicting parameters that find all solutions is difficult.The reported results include parameter choices finding two or three solutions, while performance varies with p and α.
- 4.5. Flow bifurcation: Navier–Stokes: In the Navier–Stokes continuation experiment, six solutions are found by Re = 100, while reflection identifies an additional solution and enables all seven by Re = 82.5.Reflection generates initial guesses from known asymmetric solutions and recovers the branch missed by deflation-only continuation.
- Conclusion: The paper concludes that deflation is useful across nonlinear PDE examples but does not guarantee that all solutions will be found.It is presented as a complement to continuation methods rather than a complete enumeration procedure.
5. Conclusion.
A possible future application of deflation is finding multiple local optima in PDE-constrained optimization by computing distinct solutions of the associated Karush–Kuhn–Tucker equations.
- Deflation could support computation of multiple local optima in PDE-constrained optimization through distinct solutions of associated Karush–Kuhn–Tucker equations.