nlKrylov: A Unified Framework for Nonlinear GCR-type Krylov Subspace Methods

Technical Summary: NLKRYLOV – A Unified Framework for Nonlinear GCR-Type Krylov Subspace Methods

Problem Statement
The paper addresses the numerical solution of systems of nonlinear equations $f(x) = 0$, where $f: \mathbb{R}^n \to \mathbb{R}^n$ is continuously differentiable. This class of problems is fundamental in scientific computing, arising in ODE/PDE solvers and unconstrained optimization (via optimality conditions $\nabla \phi(x) = 0$). While fixed-point iterations and Newton-type methods are standard, fixed-point schemes often suffer from slow convergence or lack of guaranteed convergence, and Newton methods require expensive Jacobian computations or approximations. Existing acceleration techniques, such as Anderson Acceleration (AA) and Quasi-Newton methods, sample iterate differences but may not fully exploit the structure of Krylov subspaces for nonlinear problems.

Methodology
The authors propose nlKrylov, a unified framework that generalizes classical linear nested Krylov solvers (specifically GCR-type methods) to nonlinear systems. The framework is built upon the Nonlinear Truncated Generalized Conjugate Residual (nlTGCR) method but introduces a modular structure centered on a subroutine $SR_j$.

1. Unified Framework Structure:
   The core algorithm (Algorithm 3) maintains a set of search directions $P_j$ and Jacobian-related vectors $V_j$. At each iteration $j$, the update $x_{j+1} = x_j + P_j y_j$ is computed by minimizing the residual norm within the subspace spanned by $P_j$.

   • The Subroutine $SR_j$: The distinguishing feature of the framework is the subroutine $SR_j(r_j, J_f(x_j))$, which solves the linear subproblem $J_f(x_j) b_p = r_j$ approximately. This allows the construction of the search direction $b_p$ (and subsequently $P_j$) using any suitable linear solver.
   • Nested Algorithms: By selecting specific inner solvers for $SR_j$, the framework generates nonlinear extensions of established linear methods:
     • nlGMRESR: Uses $m$ steps of GMRES as the inner solver.
     • nlGCRO: Uses a deflated GMRES that projects out the outer basis $V_j$ to reuse information.
     • nlLGMRES: Uses an augmented GMRES that includes the outer basis $P_j$ in the inner Krylov subspace.

2. Connections to Existing Methods:
   The paper establishes that nlKrylov methods can be viewed as:

   • Quasi-Newton Methods: They perform updates of the form $x_{j+1} = x_j - P_j V_j^T f(x_j)$, effectively using a rank-$n_j$ approximation $G_j \approx P_j V_j^T$ for the inverse Jacobian.
   • Inexact Newton Methods: The framework fits within the inexact Newton theory, where the inner solver controls the forcing term.
   • Subspace Projected Newton: The methods are linked to preconditioned subspace projection approaches (PAA), where the subspace is constructed dynamically.

3. Implementation Details:

   • Adaptive Linearization: To reduce computational cost, the algorithm can switch between nonlinear residual updates and linearized updates based on an angle condition between the nonlinear and linearized residuals.
   • Restarting: An automatic restart strategy is employed to manage ill-conditioning of the basis matrices $P_j$ and $V_j$ caused by the changing Jacobian in nonlinear settings.
   • Matrix-Valued Extension: The framework is extended to solve matrix-valued equations $F(X)=0$ by utilizing global Krylov subspace techniques and Frobenius inner products.

Key Contributions

• Unified Framework: The paper provides a general theoretical structure that encompasses and extends linear nested solvers (GMRESR, GCRO, LGMRES) to the nonlinear domain, clarifying their relationships to nlTGCR and nlOrthomin.
• Convergence Theory:
  • For problems with nonsingular Jacobians, the authors prove local convergence under relaxed assumptions. Specifically, they do not require exact line searches or uniform bounds on the error matrix; instead, they rely on a condition $\mu_j + \eta_j \leq c < 1$, where $\mu_j$ and $\eta_j$ measure the quality of the subspace approximation and the residual reduction, respectively.
  • For problems with singular Jacobians (specifically those with a one-dimensional null space), convergence results are derived showing linear convergence with a rate of $1/2$ along the null space direction, provided the forcing sequence satisfies specific quadratic bounds.
• Algorithmic Variants: The derivation of specific algorithms (nlGMRESR, nlGCRO, nlLGMRES) and a comparative analysis of their computational costs (function evaluations and inner products) are presented.

Results
Extensive numerical experiments were conducted on four benchmark problems:

1. Lennard-Jones Problem: A molecular optimization problem.
2. Chandrasekhar H-Equation: An integral equation with both nonsingular and singular Jacobian cases.
3. Symmetric Bratu Problem: A nonlinear PDE discretization.
4. Nonlinear Algebraic Riccati Equation (NARE): A matrix-valued root-finding problem.

Findings:

• Performance: nlGMRESR consistently demonstrated the most robust performance across various problems and parameter choices.
• Subspace Recycling: nlGCRO and nlLGMRES showed significant advantages over standard nlGCR in problems with slowly varying Jacobians (e.g., the Bratu problem), where reusing the outer basis improved convergence. However, their performance was more problem-dependent.
• Comparison with Baselines:
  • nlKrylov methods generally required fewer outer iterations than nlGCR and nlOrthomin.
  • In terms of total function evaluations, nlKrylov methods were competitive with Jacobian-free Newton-Krylov (JFNK) and Anderson Acceleration (AA).
  • nlOrthomin, while having comparable iteration counts to nlGCR, incurred significantly higher function evaluation costs due to its exact line search requirements.
  • AA was often the fastest in runtime for specific cases (e.g., the singular H-equation) but required careful tuning.
• Singular Problems: The adaptive variants (e.g., nlGCR-A) successfully overcame stagnation in singular cases where the pure nonlinear methods failed, validating the utility of the linear-update switching mechanism.

Significance
The paper claims that the nlKrylov framework offers a systematic way to generalize linear Krylov recycling strategies to nonlinear problems. It provides a theoretical bridge between Krylov subspace methods, Quasi-Newton updates, and inexact Newton schemes. The authors emphasize that these methods are not a uniform replacement for Newton-Krylov but serve as a complementary class of solvers. Their primary advantage lies in scenarios where the Jacobian varies slowly, allowing for effective subspace recycling, and in providing a flexible structure for matrix-valued problems. The work clarifies the theoretical underpinnings of nonlinear acceleration and offers practical algorithms that balance local linear model accuracy with computational overhead.