PaperlayerView exact revision on arXiv

Source-linked AI summary

Acceleration of Newton's method for nonlinear algebraic systems by preflattening and elimination techniques

Ngoc Do Quyen Dang, Ibtihel Ben Gharbia, Clément Cancès, Quang Huy Tran

arXiv:2610.11912v1math.NAcs.NA

TL;DR

Newton’s method can struggle with strong or unbalanced nonlinearities, while nonlinear preconditioning lacks a scalar target that both decreases and governs iteration convergence. The paper proposes preflattening, combining it with nonlinear elimination for chemical equilibrium systems; the combined approach reduces outer iterations and complexity in the reported tests.

  • Problem

    Strong or unbalanced nonlinearities can impair Newton’s method, and nonlinear preconditioning has no scalar quantity known to both decrease under preconditioning and govern Newton-iteration convergence.

    Source: §1.1 · p. 1, §1.2 · p. 2

  • Method

    The paper reduces flatness through iteration-wise changes of variables and combines preflattening with nonlinear elimination for chemical equilibrium systems.

    Source: §5 · p. 20

  • Results

    The combined approach reduces outer iterations by up to a factor of 10 on NaCl and about 5 on Seawater, and overall complexity by up to about 3 on both test cases.

    Source: §5 · p. 21

  • Takeaways & Limitations

    For the reported chemical tests, preflattening alone is insufficient, while its combination with elimination and threshold-free bad-subset selection is an effective accelerator.

    Source: §4.5 · p. 20, §5 · p. 20

    No nonlinear scalar quantity is identified that both decreases between the original and preconditioned systems and governs Newton’s iteration convergence.

    Source: §1.2 · p. 2

Abstract

from arXiv · show

In this paper, we propose a new approach called {\em preflattening} to speed up the resolution of nonlinear algebraic systems by Newton-type methods. Preflattening is meant to be for nonlinear systems what preconditioning is for linear ones. The idea is to transform the system into an equivalent one that is more favorable to Newton's method. To this end, we introduce the notion of {\em flatness}, which is intended to play for nonlinear systems a role similar to that of the condition number for linear systems. For a physical model of interest in the geosciences, namely the chemical equilibrium problem, we combine this strategy with the nonlinear elimination technique and demonstrate the value of the resulting approach through numerical simulations.

1 Introduction

Newton’s method is effective under suitable conditions, but difficult initial guesses and strong or unbalanced nonlinearities can slow or prevent convergence. The paper proposes preflattening as a less heuristic nonlinear preconditioning strategy and combines it with nonlinear elimination for systems.

1.1 Context

  • Newton’s method can be expensive for large systems, sensitive to the initial guess, and impaired by strong or unbalanced nonlinearities.The paper notes that unsuitable starting points may cause slow convergence or divergence.Source: §1.1 · p. 1
  • Nonlinear preconditioning transforms a system into an equivalent one more favorable to Newton’s method, but lacks a scalar target that both decreases and governs Newton-iteration convergence.Existing nonlinear conditioning measures describe sensitivity to perturbations, not the second-order information used in Newton convergence analyses.Source: §1.2 · p. 2, §1.1 · p. 2

1.2 Objectives

  • Preflattening seeks a locally less nonlinear system, and the paper combines Continuous Dynamic preflattening with nonlinear elimination to recover substantial iteration gains for systems.The proposed change of variables is chosen at each iteration to reduce flatness; the new system retains the same solution after a computable variable change.Source: §1.2 · pp. 2–3

2 Notion of flatness and preflattening

The paper measures local nonlinearity with the flatness number, the spectral radius of the Jacobian of Newton’s iteration function. Preflattening uses changes of variables to reduce this measure or an upper bound, then applies a Newton step in the transformed variables.

2.1 Notion of flatness

  • The flatness number is the spectral radius of the Jacobian of Newton’s iteration function, used to measure a system’s local nonlinearity.The paper motivates this measure through the role of the iteration-function Jacobian in convergence and defines it at an arbitrary point.Source: §2.1 · p. 3
  • Flatness is affine-invariant, vanishes for affine systems, and can bound the iteration-function Jacobian norm relevant to a local contraction condition.The paper also notes that flatness is informative away from the solution, since the flatness matrix vanishes at the solution.Source: §2.1 · pp. 3–4

2.2 Preflattening

  • Preflattening changes variables to reduce the flatness number or an upper bound, making the system less nonlinear while leaving affine systems unchanged.The paper proposes flatness as the nonlinear target analogous to the linear condition number.Source: §2.2 · p. 4
  • At each iteration, the prototype selects a parametrization by minimizing flatness, updates the transformed variable, and maps back to the variable of interest.The parametrization family includes the identity; the transformed variable is an intermediate value used in the next iteration.Source: §2.2 · pp. 4–5

3 Preflattening a scalar equation

The scalar model compares alternative formulations and parametrizations for Newton’s method, including methods that switch or interpolate between formulations. Across the tested cases, the methods’ iteration counts vary, while CD shows higher asymptotic convergence order than BC.

3.1 Model

  • The model’s f formulation has a derivative that blows up near x = 0, while the transformed g formulation has a derivative that blows up as |y| grows, motivating a unified formulation.The paper states that neither formulation is robust on its own.Source: §3.1 · p. 5

3.2 Methods

  • BS switches between two formulations, BC embeds the switch in a parametrization to remain a Newton method, and CD continuously interpolates between the two extreme choices.CD chooses its interpolation parameter at each iterate to minimize and cancel the flatness number.Source: §3.2 · p. 6

3.3 Numerical results

  • Across the four cases, BS matches the better of Newton’s methods when both converge and can converge when Newton on f fails; BC and CD never require more iterations than BS.CD is faster than BC in Cases 1 and 4, BC is better in Case 2, and they are nearly indistinguishable in Case 3.Source: §3.3 · p. 8, Table 2 · p. 8, Table 4 · p. 8
  • In all four cases, CD has the steepest residual curves in the final iterations and converges cubically, compared with quadratic convergence for BC.The cubic regime is reached only close enough to the solution, so CD’s higher asymptotic order does not always mean fewer iterations.Source: §3.3 · p. 9, Figure 1 · p. 9

4 Preflattening a chemical system

This section develops parametrized preflattening and nonlinear elimination to address difficulties in Newton’s method for chemical-equilibrium systems. It describes threshold-free selection of variables for elimination and evaluates the combined approach on H₂O, NaCl, and Seawater.

4.1 Model

  • Material-balance equations are affine and mass-action equations are affine in log fractions; the x formulation can blow up near zero, while the log-trick transfers nonlinearity to balances.The balance Jacobian can then blow up as log variables grow, motivating intermediate formulations that generalize right-preconditioning.Source: §4.1 · pp. 10–11
  • Theorem 4.1 gives a closed-form flatness matrix for the parametrized system, whose columns include their corresponding normalized residuals as factors.Consequently, a zero normalized residual makes its corresponding flatness-matrix column vanish.Source: §4.1 · pp. 11–12

4.2 Methods

  • CD tunes species-specific parametrization weights using a computable flatness upper bound; Hybrid chooses BC when the estimate exceeds 0.5, otherwise CD, with BC as a domain safeguard.The exact flatness number is impractical to minimize at reasonable cost, so the method uses the upper bound’s explicit minimizer.Source: §4.2 · p. 13
  • Hybrid improved on BC by at most three iterations for NaCl and Seawater, but more than halved BC’s count at five of six H2O starts for ν = 10^-7.For NaCl and Seawater, the gain was zero at some starting points.Source: §4.2 · p. 13

4.3 Elimination as a preconditioner

  • Eliminating badly scaled unknowns yields a two-step Newton process that avoids forming a costly Schur complement and acts as a right-preconditioner.The method retains global monotone convergence, including for semismooth systems when the generalized Jacobian is an M-matrix [10].Source: §4.3 · pp. 13–14
  • A frozen normalized-residual projection cancels the nonlinear normalized residuals, and the subsequent outer Newton step leaves the projected bad variables unchanged.The inner problem uses Hybrid, which was consistently the best inner solver in the reported tests.Source: §4.3 · p. 14

4.4 Choice of the bad subset

  • AANC selects above-average Γ_j columns as bad, needs no sorting, and selects none when all contributions are equal, avoiding fixed-threshold sensitivity.Fixed ε can overlook bad components when too large or over-select them when too small, with no universally good choice.Source: §4.4 · pp. 16–17
  • Double AANC applies a second selection round to remaining components because single-pass AANC can miss bad components and sometimes increase flatness after projection.Preliminary tests found AANC usually improved complexity, but it could also incur higher cost.Source: §4.4 · p. 17

4.5 Numerical results

  • Across all tested starting points, CDe needs fewer outer iterations and has lower complexity than BC and Hybrid, with only marginal complexity gains over Hybrid at two NaCl starts.On H2O, CDe outperforms BCe at ν = 10^-1 and matches it at ν = 10^-7.Source: Table 6 · p. 18, Table 7 · p. 19, Table 8 · p. 20
  • At ν = 10^-1, CDe needs 2 outer iterations and has complexity 30 versus BCe’s 4 iterations and 48, because its x1 parametrization makes the material balance affine.The methods use the same elimination procedure, bad subset, and inner solver; CDe’s outer step is in x1, whereas BCe’s is in ln x1.Source: Table 6 · p. 18, §4.5 · p. 19, Table 7 · p. 19
  • At ν = 10^-7, BCe and CDe need 1–2 outer iterations versus BC’s 9–25, while elimination cuts BC complexity by a factor of 1.8–6.8.Elimination brings the outer problem close to its solution; BCe and CDe coincide because one or two outer steps suffice for both parametrizations.Source: Table 6 · p. 18, §4.5 · p. 19, Table 7 · p. 19
  • For NaCl, CDe with double AANC reduces BC’s outer iterations from 30 to 3 and complexity from 2430 to 729 in the hardest case.Its complexity gain over Hybrid is marginal at two starting points and ranges from 1.2 to 3 at the others.Source: §4.5 · pp. 19–20, Table 8 · p. 20
  • For Seawater, CDe uses 5–9 outer iterations versus BC’s 16–29; at n0_j ≠ 1 = 10^-4, complexity is 13743 versus 38988, and projection lowers flatness on every run.CDe’s complexity is 1.4–1.7 times lower than BC’s and 1.2–1.6 times lower than Hybrid’s at the other starting points.Source: §4.5 · p. 20, Table 9 · p. 20

5 Conclusion

The conclusion introduces flatness as a measure of local nonlinearity and preflattening as an iteration-wise change of variables intended to reduce it. The combined approach with nonlinear elimination improves iteration counts and overall complexity on the reported chemical-equilibrium tests.

5 Conclusion

  • Flatness is the spectral radius of Newton’s iteration-function Jacobian, an affine-invariant measure of local nonlinearity that vanishes for affine systems.Preflattening is a right change of variables, chosen anew at each iteration, to reduce flatness or an upper bound on it.Source: §5 · p. 20
  • On the scalar model, Continuous Dynamic cancels flatness at each iterate and converges cubically.For chemical-equilibrium systems, preflattening alone brings only modest gains.Source: §5 · p. 20
  • Up to 10 fewer outer iterations on NaCl and about 5 on Seawater, with overall complexity reduced by up to about 3 on both test cases versus traditional BC.The approach combines nonlinear elimination with a threshold-free double AANC rule derived from the flatness estimate.Source: §5 · pp. 20–21
  • The authors leave extensions to non-ideal mixtures and nonlinear systems from PDE discretizations for future work.Source: §5 · p. 21

A Proofs of Section 2

The appendix proves a column-wise formula for the flatness matrix, affine invariance of the flatness number, and an upper bound based on a matrix norm.

A.1 Column-wise expression of the flatness matrix

  • Differentiating Newton’s iteration function yields the column-wise flatness-matrix expression cited as formula (2.8).Source: §A.1 · p. 23

A.2 Affine invariance of the flatness number

  • Under an affine change of variables, the flatness Jacobian transforms by similarity, preserving the flatness number.Source: §A.2 · p. 24

A.3 Upper bound for the flatness number

  • The flatness number is bounded above by a matrix norm of the appropriately transformed flatness Jacobian.The proof uses the spectral-radius bound ρ(M) ≤ ∥M∥.Source: §A.3 · p. 24

B.1 Smaller flatness number

The appendix compares flatness for two scalar formulations and establishes a condition under which one has a smaller flatness number. It also derives an admissible weight for the scalar CD parametrization.

B.1 Smaller flatness number

  • The transformed scalar formulation g has smaller flatness than f exactly when pm|y|^(m−1) < q.Source: §B.1 · p. 24

B.2 Optimal weight for the scalar equation

  • For the scalar CD parametrization, the derived weight α lies in [0, 1].The proof establishes this using the nonzero, same-sign values of x and y.Source: §B.2 · p. 25

C Proofs of Section 4

The proofs connect the abstract system to ideal-mixture chemical equilibrium, derive flatness matrices for separated and chemical forms, and establish the weight-minimization and residual-equivalence results used in Section 4.

C.1 Physical origin

  • Chemical equilibrium is formulated through element conservation and reaction-equilibrium equations; this work restricts its model to ideal mixtures.The paper also describes an equivalent formulation using species mole fractions and reciprocal total moles as unknowns.Source: §C.1 · p. 26

C.2 Flatness matrix for a separated form

  • For a separated system, the flatness matrix is assembled from component second derivatives and the scaled residual vector η.Source: §C.2 · p. 27

C.3 Flatness matrix for the chemical system

  • The chemical-system flatness-matrix expression follows by inserting the system derivatives and normalized residuals into the separated-form formula.Source: §C.3 · pp. 28–29

C.4 Minimizing the upper bound of the flatness number

  • Minimizing the flatness upper bound over the CD weights separates into a sum-of-squares problem, with a unique minimizer when every δ_i is nonzero.Source: §C.4 · p. 29

C.5 Simultaneous vanishing of the two normalized residuals

  • The proof establishes equivalence between simultaneous vanishing of the bad nonlinear and linear normalized residuals through an invertible change of basis.Source: §C.5 · pp. 29–30

C.6 Bad subset for AANC

The subsection establishes how the index maximizing the partial-sum criterion is selected, including the case where all Γj values are equal.

C.6 Bad subset for AANC

  • Multiplying the objective function by a positive constant leaves the maximizer unchanged.Source: §C.6 · p. 30
  • The partial sums increase while Γ(j) exceeds ρH/n and do not increase after that threshold.The argument uses that the sequence Γ(ℓ) − ρH/n is nonincreasing and goes from nonnegative to nonpositive values.Source: §C.6 · p. 30
  • The maximum is attained at the index j* given by (4.40), which is the smallest maximizer.When all Γj values are equal, the set in (4.40) is empty; the convention max ∅ = 0 again gives the smallest maximizer.Source: §C.6 · p. 31

C.7.1 H2O test case

The H2O test case transforms a four-unknown system to expose the dimensionless charge-imbalance parameter ν and focus on a ν-dependent three-variable subsystem. Experiments use two values of ν.

C.7.1 H2O test case

  • The water-dissociation model has 3 species, 2 elements, 1 reaction, and 3 unknowns (x1, x2, x3).Source: §C.7.1 · p. 31
  • Replacing the second equation with a linear combination highlights ν, a dimensionless parameter representing charge imbalance between H+ and OH− that affects the desired molar fractions.Source: §C.7.1 · p. 31
  • The transformed formulation focuses on a ν-dependent 3×3 subsystem because ω appears only in a linear equation and can be deduced from (x1, x2, x3).Source: §C.7.1 · p. 31
  • Experiments use ν = 10^-1 and ν = 10^-7, with t = 40.2406556362.The reference potentials are specified at P = 1 bar and T = 298.15 K.Source: §C.7.1 · p. 31

C.7.2 NaCl test case

The NaCl test case is a larger chemical system with prescribed feeds and reference chemical potentials; the enlarged system is used without the reduction described for H2O.

C.7.2 NaCl test case

  • NaCl comprises 8 species, 4 elements, and 4 reactions.The reactions include NaCl, NaOH, OH−, and HCl equilibria.Source: §C.7.2 · p. 32
  • The prescribed feeds are fH = 111.0174, fO = 55.5087, fNa = 0.1, and fCl = 0.1.Source: §C.7.2 · p. 32
  • The reference chemical potentials are evaluated at T = 298.15 K, and the enlarged system (C.6) is used as it stands.Source: §C.7.2 · p. 32

C.7.3 Seawater test case

The Seawater test case extends the chemical system to 37 species, 10 elements, and 27 reactions, using prescribed feeds and the enlarged system (C.6).

C.7.3 Seawater test case

  • Seawater comprises 37 species, 10 elements, and 27 reactions.Table 10 lists the set of 27 reactions.Source: §C.7.3 · p. 32, Table 10
  • The prescribed feeds include fH = 110.78054, fO = 55.5087, fNa = 0.469, and fMg = 0.0528.Additional listed feeds are fS = 0.0282, fCa = 0.0103, fK = 0.0102, fC = 0.00206, fSr = 10^-5, and fCl = 0.546.Source: §C.7.3 · p. 32
  • The enlarged system (C.6) is used as it stands, and initial guesses are built in the same way as for NaCl.The reference chemical potentials are given in Table 11.Source: §C.7.3 · p. 32, Table 11 · p. 33
Loading 2610.11912v1…