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

Tom Werner, Ning Wan, Agnieszka Międlar · 2025

Read nlKrylov : A Unified Framework for Nonlinear GCR-type Krylov Subspace Methods by Tom Werner, Ning Wan, Agnieszka Międlar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14713.txt.

Introduction

Tom Werner, Ning Wan, and Agnieszka Miedlar unite a family of solvers for systems of nonlinear equations under one framework called nlKrylov. Fast linear solvers of Krylov type, such as GMRESR, build answers inside growing search spaces. Extending that power to nonlinear problems has produced many separate methods with separate proofs.

The nlKrylov framework recasts the GCR-style linear methods as nested algorithms that work directly on nonlinear systems. Convergence is proved under relaxed conditions that avoid costly exact line searches. The same ideas extend to matrix-valued root finding through global variants. Numerical tests back the theory, showing the unified solvers stay robust and efficient across problems.

Catalog record

CREATORTom Werner, Ning Wan, Agnieszka Międlar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14713

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

nlKrylov : A Unified Framework for Nonlinear GCR-type Krylov Subspace Methods Thanks: Tom Werner, Ning Wan, Agnieszka Międlar Abstract In this paper, we introduce a unified framework for nonlinear Krylov subspace methods (nlKrylov) to solve systems of nonlinear equations. Building on classical GCR-like/type linear Krylov solvers such as GMRESR, we generalize these approaches to nonlinear problems via nested algorithmic structures. We present rigorous convergence results for problems, relying on relaxed assumptions that avoid the need for exact line searches. The framework is further extended to matrix-valued rootfinding problems using global nonlinear Krylov approaches. Extensive numerical experiments validate the theoretical insights and demonstrate the robustness and efficiency of our proposed algorithms. keywords nonlinear Krylov, quasi-Newton, nonlinear acceleration, Anderson Acceleration Funding. Work of N. Wan and A. Międlar has been supported by the NSF awards DMS #2144181 and #2324958. † † runningheads: nlKrylov / T. Werner, N. Wan, and A. Międlar MSC 39B42, 65B99, 65F08, 65F10, 65H10, 65N22, 68W25, 90C53 1 Introduction A classical problem in numerical analysis, with increasing popularity in recent data science and machine learning applications, is the root finding problem \text{Find }x\in\mathbb{R}^{n}\ \text{ that satisfies }\ f(x)=0, (1) where f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n} is continuously differentiable and possibly nonlinear. Nonlinear equations like ( 1 ) can appear in a variety of problems such as the numerical solution of nonlinear ordinary differential equations \dot{x}(t)=F(t,x),\ F:\mathbb{R}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}, using implicit integrators, the numerical solution of discretized nonlinear partial differential equations \Delta u(x)=F(x,u),\ u:\Omega\rightarrow\mathbb{R},\ F:\Omega\times\mathbb{R}\rightarrow\mathbb{R}, or when solving unconstrained optimization problems \min_{x\in\mathbb{R}^{n}}\phi(x),\ \phi:\mathbb{R}^{n}\rightarrow\mathbb{R}\ \text{ twice continuously differentiable,} (2) using the optimality condition \nabla\phi(x)=:f(x)=0 . Since ( 1 ) frequently arises in practical applications, numerous methods have been developed and refined since the mid-20th century, most of which are based on fixed-point iteration x_{j+1}=g(x_{j}),\ g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}. (3) Clearly, if we choose g(x):=x+\beta f(x) , for some \beta\neq 0 , then x=g(x)~\Longleftrightarrow~\beta f(x)=0~\Longleftrightarrow~f(x)=0, i.e., any fixed point of g is a solution to the root finding problem ( 1 ) and vice versa. However, convergence of the fixed-point scheme ( 3 ) is generally not guaranteed and can be very slow in many applications. To improve or ensure convergence of ( 3 ), considerable effort has focused on acceleration schemes such as Anderson Acceleration (AA) [ 4 , 5 ] and the related Pulay mixing method [ 70 , 71 ] , owing to their simplicity and effectiveness across a wide range of applications. Both methods rely on effectively sampling the next iterate from two sets of vectors, namely, the differences of consecutive function values \Delta f_{j}:=f(x_{j+1})-f(x_{j}) , and of consecutive iterates \Delta x_{j}:=x_{j+1}-x_{j} . Lately, the use of Krylov subspace techniques for nonlinear acceleration has been discovered and explored in the form of nonlinear versions of GMRES [ 25 , 67 , 93 ] and GCR [ 50 ] . In [ 91 ] , the equivalence of AA, GMRES and GCR on linear problems has been established. The same study also formalizes the connection between Anderson Acceleration (AA) and multi-secant methods, a relation first identified in [ 39 ] and subsequently extended in [ 40 ] . A second family of fixed-point schemes ( 3 ) for ( 1 ) is the family of Newton-type methods, which can be characterized by x_{j+1}=x_{j}+\Delta x_{j},\ \ \text{where}\ \ B_{j}\Delta x_{j}=-f(x_{j})+t_{j}. The classical Newton method [ 60 ] uses B_{j}=J_{f}(x_{j}) and t_{j}=0 , resulting in the fixed-point scheme ( 3 ) with g(x)=x-J_{f}(x)^{-1}f(x). In practice, the update equation is usually solved approximately, introducing an error term t_{j}\neq 0 . This inexactness leads to the class of inexact Newton methods [ 32 ] . Among those, Newton-Krylov methods have attracted significant attention across various research fields owing to their efficiency and scalability for large-scale and parallel computations [ 60 ] . When the exact Jacobian J_{f}(x_{j}) is unavailable or too expensive to compute, an approximation B_{j}\approx J_{f}(x_{j}) is employed and iteratively updated using information from previous steps, giving rise to quasi-Newton methods [ 34 ] . Contributions and Outline In [ 50 ] , the nonlinear truncated Generalized Conjugate Residual (nlTGCR) method was introduced and placed within the broader context of acceleration and multi-secant techniques. The authors extended the classical Generalized Conjugate Residual (GCR) method of [ 37 ] -itself a generalization of the Conjugate Residual and Conjugate Gradient methods [ 52 ] -from unsymmetric linear systems to nonlinear equations. Since the development of GCR, numerous refinements have been proposed, resulting in algorithms such as the recursive GMRES (GMRESR) method of van der Vorst and Vuik [ 87 ] , the GCR variant with inner orthogonalization by de Sturler [ 26 ] , later refined to incorporate optimal basis truncation in GCRO and GCROT [ 27 ] , and the Loose GMRES (LGMRES) method of Baker, Jessup, and Manteuffel [ 12 ] . Our objective in this paper is to develop a unified framework for extending nested GCR-type algorithms to nonlinear equations. Building on the ideas of [ 50 ] , the proposed approach preserves the essential structure of its linear counterparts while enabling a systematic treatment of nonlinear nested GCR methods within the subspace projected Newton framework of [ 82 ] . This perspective facilitates a more refined convergence analysis for nonlinear Krylov methods without relying on exact line-search assumptions. In addition, we compare nlTGCR with nlOrthomin and motivate an interpretation of nonlinear nested GCR algorithms as preconditioned variants of nlOrthomin. Finally, we demonstrate how the proposed framework extends naturally to matrix-valued root-finding problems F(X)=0,~F:\mathbb{R}^{n,p}\rightarrow\mathbb{R}^{n,p}, which have gained increasing relevance in recent years, particularly in large-scale data analysis and manifold-constrained optimization problems that require solving ( 2 ) of the form \phi:\mathbb{R}^{n,p}\rightarrow\mathbb{R},~X\mapsto\phi(X) , e.g. under orthogonality constraint X^{T}X=I_{p} [ 1 , 55 , 96 ] . The theoretical developments are illustrated through practical and representative numerical examples. The remainder of this paper is organized as follows. This section concludes with a brief overview of the notation adopted throughout the paper. Section 2 provides an introduction to the theoretical background of Krylov subspace methods and nonlinear Newton-type methods, which serve as the basis for the developments in the subsequent sections. It also revisits the concept of the nonlinear GCR method proposed in [ 50 ] , establishing the foundation for the general nonlinear Krylov framework developed in Section 3 . This framework enables an interpretation of nonlinear nested GCR algorithms within the context of quasi-Newton and subspace-projected Newton methods, as discussed in Section 4 . The connection to preconditioned nlOrthomin method is also elaborated in this section. The main convergence results are presented in Section 5 , addressing problems with both regular ( Theorem 1 ) and singular Jacobians ( Theorem 5 ). Section 6 details the practical implementation aspects, followed by Section 7 , which outlines the extension of the proposed algorithms to matrix-valued problems. Numerical experiments that demonstrate the performance of the newly developed algorithms for vector- and matrix-valued problems are presented in Section 8 . The paper concludes with a brief summary and an outlook on open research directions. Notation Throughout the paper, real scalars are denoted by Greek letters, vectors by lowercase Roman letters, and matrices by uppercase Roman letters, unless stated otherwise. For a (nonlinear) function f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n} , J_{f}(x)\in\mathbb{R}^{n,n} denotes its Jacobian evaluated at a point

Read the complete text