Source-linked AI summary
Composing Scalable Nonlinear Algebraic Solvers
Peter R. Brune, Matthew G. Knepley, Barry F. Smith, Xuemin Tu
TL;DR
The paper addresses whether composable algorithmic ideas from linear solvers can improve nonlinear algebraic solves. It develops nonlinear composition and preconditioning methods in a software framework, and reports substantial efficiency and robustness gains across nonlinear PDE problems, while noting important method-specific limitations.
Problem
Nonlinear PDE solvers need a systematic way to combine solver components analogous to the composable components used in efficient linear solvers.
Method
The paper composes nonlinear solvers and applies nonlinear preconditioning through a software framework that supports combinations of outer and inner methods.
Results
The experiments show that nonlinear composition and preconditioning can provide efficiency and robustness gains for nonlinear PDE solves, including difficult nonlinearities.
Takeaways & Limitations
Composed nonlinear solvers provide a practical framework for exploring solver combinations across nonlinear elasticity, buoyant driven cavity flow, and the p-Laplacian.
Takeaways & Limitations
Backtracking line search is used only with Newton’s method because its assumptions may fail for other methods and ill-conditioned Jacobians can cause stagnation.
Abstract
from arXiv · showhide
Most efficient linear solvers use composable algorithmic components, with the most common model being the combination of a Krylov accelerator and one or more preconditioners. A similar set of concepts may be used for nonlinear algebraic systems, where nonlinear composition of different nonlinear solvers may significantly improve the time to solution. We describe the basic concepts of nonlinear composition and preconditioning and present a number of solvers applicable to nonlinear partial differential equations. We have developed a software framework in order to easily explore the possible combinations of solvers. We show that the performance gains from using composed solvers can be substantial compared with gains from standard Newton-Krylov methods.
1. Introduction.
The paper develops a systematic framework for composing nonlinear solvers, adapting ideas from composable linear solvers to nonlinear equations and implementing them in software.
- The paper combines a small number of nonlinear solver building blocks to create many solvers with different convergence and performance properties.It focuses on nonlinear composition and preconditioning as the two related construction techniques.
- Its contributions are a mathematical and software framework for combining nonlinear solvers and efficient solver constructions for several problems.The implementations are available in the PETSc library for use on relevant applications.
- The paper formulates its subject as solving nonlinear equations, with the nonlinear residual defined for a discretized function F and right-hand side b.
2. Background.
The background contrasts standard linear preconditioning and solver composition with the nonlinear setting, where approximate solutions and residuals must both be handled explicitly.
- Linear stationary solvers repeatedly apply an operator approximating the inverse of the system matrix to reduce error.Jacobi, Gauss-Seidel, and multigrid are examples of linear stationary solvers.
- Linear preconditioners can be composed additively or multiplicatively, allowing different components to address different portions of the error space.This composition strategy underlies domain decomposition methods.
- Linear left- and right-preconditioning are commonly combined with Krylov methods for parallel linear-system solution.
- Linear left-preconditioning modifies the residual, whereas right-preconditioning solves for a preconditioned variable and transforms it back to the original solution.The right-preconditioned formulation uses P^-1 to transform the intermediate solution y.
- In the nonlinear case, composition and preconditioning must define both the approximate solution and residual for the outer solver and preconditioner.The paper transfers these ideas systematically from the linear setting to nonlinear solvers.
3. Nonlinear Composed Solvers.
Nonlinear composition chains solver updates, while nonlinear preconditioning modifies the residual through an inner solver before an outer solver acts; these constructions support multiple solver combinations and trade-offs.
- Nonlinear composition sequences two or more solution methods, whereas nonlinear preconditioning modifies the residual using an inner method before applying an outer solver.
- Additive nonlinear composition combines updates from two solvers using weights, while sequential composition applies one solver and then updates with the next solver’s result.
- Nonlinear left-preconditioning recasts the problem through a fixed-point residual and can improve conditioning or reduce nonlinear severity under suitable circumstances.Examples include nonlinear SOR and additive Schwarz-preconditioned inexact Newton.
- Nonlinear right-preconditioning treats the inner solver as a transformation before outer evaluation, but combining the inner solve with function evaluation can be significantly more expensive.For Newton-Krylov outer solvers, the paper states that this formulation is equivalent to another nonlinear right-preconditioning form.
- Nonlinear right-preconditioning is a misnomer because it does not reduce to right linear preconditioning in the linear case.The name refers instead to applying the inner solver before function evaluation, as in linear right-preconditioning.
- The framework distinguishes outer and inner methods and records their combinations in a notation table for systematic implementation and composition.
4. Solvers.
The paper presents line searches, nonlinear Richardson iteration, Anderson mixing, Newton-Krylov methods, and quasi-Newton methods as composable tools for solving nonlinear systems. Their applicability depends on problem structure, descent behavior, Jacobian properties, and the cost of residual or Jacobian evaluations.
- 4.1. Line Searches: Line searches globalize nonlinear solvers by scaling search directions, with full-step defaults appropriate near solutions and shortening or lengthening used when scaling must be determined.Backtracking is designed for Newton steps, whereas other methods may require alternatives because their directions can be ill-scaled or Jacobian assembly can be expensive.
- 4.1. Line Searches: Critical-point and L2 line searches offer alternatives: CP can converge faster for some solvers, while converged L2 provides optimal damping along the residual direction and helps prevent divergence.L2 typically uses one inner iteration and requires two additional residual evaluations per application.
- 4.2. Nonlinear Richardson (NRICH): Nonlinear Richardson iteration steps along the negative residual and can be substantially improved by nonlinear preconditioning, although unmodified NRICH often converges slowly or stagnates.Left preconditioning replaces the residual equation with x−M(r,x), and the line search may minimize either the original or preconditioned residual.
- 4.3. Anderson Mixing (ANDERSON): Anderson mixing combines previous approximate solutions and a new trial, determining weights through a residual-based least-squares formulation that can be solved with SVD-based LAPACK routines.The framework also applies residual-minimizing weights to additive compositions of multiple nonlinear solvers.
- 4.4. Newton-Krylov Methods (NEWT\K).: Newton-Krylov methods determine search directions by approximately inverting the Jacobian with a preconditioned Krylov method, while quasi-Newton methods approximate the inverse Jacobian using low-rank updates.The paper restricts L-BFGS and nonlinear conjugate gradients to symmetric-Jacobian problems; limited-memory Broyden methods are recommended when L-BFGS is inapplicable.
5. Decomposition Solvers.
Decomposition solvers partition nonlinear problems across blocks, subdomains, or coarse grids, trading communication and convergence behavior against parallelism and arithmetic intensity.
- Decomposition Solvers: Decomposition solvers do not guarantee convergence, so they may be combined with global solvers as nonlinear preconditioners or accelerators.Their use also requires information about local problems, a decomposition, or a discretization hierarchy.
- Block Decomposition: Gauss-Seidel-Newton applies Newton’s method multiplicatively across small block subproblems and can provide an efficient nonlinear solver kernel.It has high arithmetic intensity, typically exceeding twice the work per degree of freedom of NRICH for scalar problems.
- Block Decomposition: GSN is typically used as a preconditioner because stationary nonlinear solvers do not converge robustly for large problems.As a preconditioner, it avoids global convergence monitoring within GSN iterations and can use additive updates in parallel.
- Subdomain Decomposition: Nonlinear Additive Schwarz solves overlapping subdomain problems with general methods and sums their corrections into a global search direction.NASM uses overlapping injection, while restricted additive Schwarz uses non-overlapping injection; subdomain solvers are typically Newton-Krylov.
- Coarse-Grid Decomposition: FAS advances nonlinear solutions on coarse rediscretizations, with multiplicative cycles improving per-iteration convergence and additive cycles enabling parallel coarse corrections.FAS differs from linear multigrid through its coarse right-hand-side construction and can use nonlinear solution methods as smoothers.
- Framework and Applications: The framework combines these solver classes through nonlinear composition and preconditioning, then tests composed solvers on nonlinear elasticity, buoyant lid-driven cavity flow, and the p-Laplacian.The software is designed to explore flexible combinations of composed nonlinear solvers.
6. Experiments.
Experiments across nonlinear elasticity and p-Laplacian problems show that carefully composed or preconditioned nonlinear solvers can substantially improve convergence, iteration counts, and runtime over standard approaches.
- Nonlinear Elasticity: For the elasticity baseline, NEWT\K−MG required 27 nonlinear iterations and 1,618 multigrid V-cycles, while NCG required 8,991 function evaluations.NEWT\K−MG nearly stagnated before suddenly entering its basin of attraction; NCG decreased at a roughly constant rate after an initial jump.
- Nonlinear Elasticity: Additive and multiplicative elasticity compositions avoided stagnation and reached quadratic convergence after entering Newton\K’s basin of attraction.Both methods followed the initial NCG convergence pace before exhibiting the expected Newton\K behavior.
- Nonlinear Elasticity: In nonlinear elasticity, left-preconditioning NCG and ANDERSON with NEWT\K−MG nearly halved iterations while maintaining rapid, mostly constant convergence.The preconditioned methods used only slightly more linear preconditioner applications than composition cases.
- Tuning the Solvers to Obtain Convergence: On a higher-Grashof-number problem, Newton’s method stagnated and standard coarse-mesh continuation also failed, motivating nonlinear multigrid and solver composition.These experiments tested whether composed methods could recover convergence in a more difficult regime.
- Overall Findings: Composed solvers converted nonconvergent behavior into convergence with few iterations, while RAS-based nonlinear preconditioning produced especially strong improvements.The authors emphasize that hierarchical and multilevel inner solvers can support high arithmetic intensity and low communication at extreme scale.
- p-Laplacian: Multiplicative composition reduced p-Laplacian outer iterations fivefold and runtime by about fourfold compared with Newton’s method.Additive composition also reduced outer iterations, but multiplicative composition was more effective.
7. Conclusion.
Nonlinear composition and preconditioning can improve solver efficiency and robustness, but effective combinations and parameter settings vary by problem. The paper explores a deliberately limited combination space while enabling users to construct deeper, problem-specific solver hierarchies.
- The best solver configuration varies by problem, from simple NCG to multilevel combinations such as FAS*(NEWT\K−MG).Nonlinear composition introduces additional parameters at multiple hierarchy levels that require tuning.
- The study restricts most combinations to globalized and decomposition methods because unrestricted nesting would create a combinatorial explosion.Users may still experiment with deeper arbitrary combinations for particular problems.
- Nonlinear preconditioning and composition can provide both efficiency and robustness gains for difficult nonlinear problems.The authors argue that broader adoption could benefit computational science.