PaperlayerView exact revision on arXiv

Source-linked AI summary

Toeplitz Infinite GMRES for Parameterized Linear Systems

Weiguo Gao, Feiyang Jiang

arXiv:2610.01740v1math.NAcs.NA

TL;DR

Repeated solutions of large, sparse analytic parameterized systems can make separate factorizations expensive. The paper develops Toeplitz infinite GMRES and an implicitly rebased variant to reduce Arnoldi-construction cost; experiments report computational advantages, while a residual lower bound identifies a scaling boundary.

  • Problem

    Repeatedly factoring large, sparse analytic A(s) for many parameter values is often too expensive, despite the need to solve A(s)x(s)=z.

    Source: §1 · p. 1

  • Method

    Toeplitz infinite GMRES exploits the companion Krylov sequence to update Arnoldi recovery data incrementally, with an implicitly rebased variant for exact fixed separated representations.

    Source: §1 · p. 2, §3.1 · p. 3, §3.4 · p. 10

  • Results

    Experiments report computational advantages; on Helmholtz, IR-TiGMRES median end-to-end time was 19.96s versus 27.24s for basic Toeplitz, 30.32s for Dynamic TiGMRES, and 40.46s for full refreshed TiGMRES.

    Source: §6.2 · p. 19, §7 · p. 21

  • Takeaways & Limitations

    The methods show computational advantages for parameterized linear systems and contour-integral eigenvalue problems.

    Source: §7 · p. 21

    For square-summable Taylor coefficients, the linearized residual cannot converge to zero outside the normalized unit disk.

    Source: §7 · p. 21

Abstract

from arXiv · show

We develop Toeplitz infinite GMRES for solving large sparse analytic parameterized systems $A(s)x(s)=z$ at many parameter values. The method exploits a block upper triangular Toeplitz structure in the companion Krylov sequence to construct the Arnoldi process and recover solution approximations without storing full Arnoldi vectors. We derive incremental recurrences requiring $\mathcal{O}(np^2+p^3)$ arithmetic and $\mathcal{O}(np+p^2)$ storage for $p$ Arnoldi steps, excluding factorization setup and assuming linear-cost coefficient actions and triangular solves. A dynamic generator-refreshing strategy addresses cancellation in the basic recurrence. For matrix functions admitting a fixed separated representation, we further develop an implicitly rebased method based on a compact, contractive nilpotent matrix. Both variants preserve the Arnoldi process in exact arithmetic, with exact matrix-function actions required for the rebased method. A residual lower bound for square-summable Taylor coefficients explains a scaling obstruction outside the normalized unit disk. Theoretical analysis and numerical experiments illustrate the computational efficiency of the proposed methods.

1. Introduction.

Repeatedly solving large, sparse analytic parameterized systems makes separate factorizations expensive. The paper targets the remaining Arnoldi-construction cost by exploiting Toeplitz structure and updating only QR data needed for solution recovery.

1. Introduction.

  • Separate factorizations become expensive when solutions are needed at many parameter values, motivating methods that reuse one Arnoldi construction.The systems considered have a large, sparse, analytic matrix function A(s) and fixed right-hand side z.Source: §1 · p. 1
  • InfGMRES applies GMRES to a Taylor companion linearization, constructing one Arnoldi factorization for all parameter values and solving a small parameter-dependent least-squares problem for each s.The introduction situates this approach among inexact-preconditioned infGMRES, TOAR, tensor and infinite Arnoldi, and CORK methods.Source: §1 · p. 1
  • Direct infGMRES costs O(np^3) arithmetic and O(np^2) storage, while TOAR reduces storage to O(np + p^3) but retains O(np^3 + p^4) arithmetic.The stated comparison assumes coefficient-matrix products and triangular solves using one stored LU factorization cost O(n).Source: §1 · p. 1
  • The proposed method exploits block Toeplitz structure to update only recovery-relevant QR data, with dynamic generator refreshing for cancellation and an implicitly rebased variant for fixed separated representations.The paper assumes z is nonzero, A(0) is nonsingular, and A(s) is analytic near the origin.Source: §1 · p. 2, §2 · p. 2

2. Review of infGMRES.

The review formulates infGMRES through a Taylor companion linearization and applies GMRES to it. Its finite-step iterates can be interpreted using an infinite companion system without forming that matrix.

2. Review of infGMRES.

  • For a Taylor truncation A_q(s), solving the companion linear system yields a solution whose first n entries are x_q(s).The companion system is assembled from the Taylor coefficient matrices and identity blocks.Source: §2 · p. 2
  • GMRES is applied to the companion operator, and each parameter value uses a reduced least-squares problem to obtain the coefficient vector for recovering the approximation.The starting vector is formed from z and its norm.Source: §2 · p. 2
  • For the first p Arnoldi steps, every truncation degree q ≥ p gives identical iterates up to zero tails, so the infinite companion matrix need never be formed and omitting those tails adds no truncation error.The finite-step construction remains independent of q, including its reduced least-squares problems and recovered approximations.Source: §2 · p. 3

3. Toeplitz infinite GMRES.

This section presents Toeplitz infGMRES methods that recover Arnoldi approximations from compact QR data and address instability in the Toeplitz Arnoldi recurrence. It describes dynamic generator refreshing and an implicitly rebased variant for matrix functions with an exact separated representation.

3. Toeplitz infinite GMRES.

  • The Toeplitz structure reduces infGMRES to QR factorization of the structured matrix, but near-aligned generators can make direct QR numerically unstable.The method therefore derives compact QR updates for solution recovery rather than storing full Arnoldi vectors.Source: §3.1 · p. 4

3.2. Incremental recurrences.

  • At step m, incremental recurrences update the required QR and recovery data in O(nm + m^2) operations and reproduce p-step Arnoldi in exact arithmetic.The overall arithmetic cost is factorization and triangular-solve setup plus O(np^2 + p^3); the additional storage is O(np + p^2).Source: §3.2 · pp. 6–7

3.3. Cancellation in the recovery recurrence.

  • Cancellation in the recovery update can amplify errors that the unmodified Toeplitz method then propagates; the computable indicator η_m estimates prospective cancellation.When consecutive recovery-vector norms are comparable, η_m tracks prospective cancellation up to their norm ratio.Source: §3.3 · pp. 7–8

3.4. Dynamic stabilization.

  • Dynamic Toeplitz infGMRES uses the cancellation indicator to trigger refreshes, reconstructing selected Arnoldi vectors and replacing generators to avoid subtraction while preserving the process in exact arithmetic.After refreshing, the structured QR update produces the same Q and S factors, and the basic recurrence can continue unchanged.Source: §3.4 · p. 9

3.4. Dynamic stabilization

  • Dynamic TiGMRES refreshes at every step during the first half, then when η_m ≥ τ, because early-step precision affects later steps.The stated cost for refreshing the first half is approximately 1/12 np^3, about one-eighth of refreshing every step.Source: §3.4 · p. 9
  • With τ = 0, Dynamic TiGMRES refreshes every step and matches TOAR infGMRES’s O(np^3 + p^4) arithmetic and O(np + p^3) storage complexities.The passage also states that their leading-order flop counts are the same.Source: §3.4 · p. 10
  • TOAR infGMRES incurs O(3np^3 + O(np^2 + p^4)) total basis-construction cost, which Toeplitz infGMRES avoids; Dynamic TiGMRES adds recurrence and selected-vector reconstruction costs.For each method, solving reduced problems and forming N approximations adds O(N(p^2 + np)) arithmetic.Source: §3.4 · p. 10

Implicitly rebased Toeplitz infGMRES

  • Under Theorem 4.5’s assumptions, IR-TiGMRES constructs a p-step basis in O(np^2 + p^3) arithmetic and O(np + p^2) storage.It computes each recovery vector from a compact Arnoldi-basis representation and updates that representation using incremental QR.Source: §3.4 · p. 10

4. Implicitly rebased Toeplitz infGMRES.

IR-TiGMRES uses a compact representation of the Arnoldi basis for systems with an exact fixed separated representation of A(s). Under the stated assumptions, it preserves the Arnoldi process while reducing basis-construction cost and storage.

4.1. Exact separated representation.

  • Hypothesis 4.1 requires an exact separated representation with fixed d, analytic scalar functions, and sparse fixed matrices; it covers polynomial, exponential, trigonometric, rational, and affine square-root dependence.The number d is independent of n, p, and q, and each M_l has O(n) nonzeros.Source: §4.1 · pp. 10–11

4.2. A compact representation of the Arnoldi basis.

  • The Arnoldi basis is stored through G_m and a strictly upper triangular K_m, requiring O(nm+m^2) scalars instead of storing all its block rows.The first block row is G_m; each later block row is the preceding row multiplied by K_m.Source: §4.2 · p. 11

4.3. Computing the recovery vector.

  • The next recovery vector can be computed from the compact pair using G_m and the vectors ϕ_l(K_m)e_m, without reconstructing the full basis.The section then constructs G_m and K_m recursively to preserve the same basis representation.Source: §4.3 · pp. 11–12

4.4. Recursive construction of the compact representation.

  • With exact arithmetic and exact matrix-function actions, the recursive compact-state updates produce the same H_p and infGMRES approximation as p Arnoldi steps.The recurrence preserves the compact representation of Q_m as it updates the QR data.Source: §4.4 · pp. 12–13

4.5. Incremental evaluation of matrix-function actions.

  • For the treated function classes, nested matrix states allow incremental matrix-function actions to be updated in O(m^2) cost for fixed parameters and degrees.Fixed-degree polynomials and fixed-degree rational functions are among the described cases; the rational evaluation uses a triangular solve.Source: §4.5 · pp. 13–14

4.6. Algorithm and complexity.

  • Under Hypothesis 4.1, IR-TiGMRES constructs the Arnoldi basis in O(np^2+p^3) arithmetic and O(np+p^2) storage, excluding the common factorization and solve costs.The bounds assume the stated separated representation and incremental function-action schemes.Source: §4.6 · p. 15
  • Under the same separated representation, G-TOAR infGMRES has O(np^2+p^4) arithmetic and O(np+p^3) storage, and is included only in the theoretical comparison, not the experiments.Table 2 compares basis-construction complexities; its IR-TiGMRES bounds additionally require Theorem 4.5 assumptions.Source: §4.6 · p. 16, Table 2 · p. 16

5. A residual lower bound and parameter scaling.

The section establishes a positive infGMRES residual lower bound outside the normalized unit disk under square-summability of Taylor coefficients. It also explains how parameter scaling can weaken this bound.

5. A residual lower bound and parameter scaling.

  • At s=0, the minimized residual is zero.The proof obtains this by choosing y=βe_1 in the reduced problem.Source: §5 · p. 16
  • For |s|>1, infGMRES has a positive residual lower bound independent of m and q when the Taylor coefficients are square-summable; analyticity on a disk of radius greater than one suffices.The bound uses C_m, which may be replaced by C_∞ under the stated summability condition.Source: §5 · pp. 16–17
  • When t>1, increasing the scaling weight weakens the residual lower bound and can alleviate the scaling obstruction, especially when higher Taylor coefficients are small.For fixed center and target, the scaling changes t and the coefficient norm in directions that weaken the bound.Source: §5 · p. 17

6. Numerical experiments.

The experiments compare the methods on time-delay, parameterized Helmholtz, and contour-integral eigenvalue problems. IR-TiGMRES is fastest across six NLEVP problems, while residual behavior differs across the parameterized systems.

6. Numerical experiments.

  • Reported runtimes are medians of seven timed runs following one untimed run, with method order rotated across runs.NLEVP methods share each problem’s contour, expansion node, scaling factor, Taylor degree, probing matrix, Beyn postprocessing, and random seed.Source: §6 · p. 17, §6.3.1 · p. 21

6.1. Time-delay system.

  • At s = 0.4, Toeplitz infGMRES stalls at 3.55 × 10^-4, while full refreshed, Dynamic, and IR-TiGMRES reach residuals near 10^-14.At s = 0.1, all four methods first reach 10^-8 at iteration 14; Figure 1 shows the residual histories.Source: Figure 1 · p. 18, §6.1 · p. 18

6.2. Parameterized Helmholtz equation.

  • Coefficient grouping was not implemented for Toeplitz infGMRES or Dynamic TiGMRES, although it can be applied under Hypothesis 4.1.The authors treated those methods as general-purpose rather than specialized for separated representations.Source: §6.2 · p. 19
  • For the Helmholtz problem, all four methods reach 10^-8 at iteration 34 and finish near 1.47 × 10^-11; IR-TiGMRES takes 19.96s, versus 27.24s for Toeplitz infGMRES.The four-term separated action requires 196 sparse matrix-vector products at p = 50, compared with 1225 for Taylor convolution.Source: Figure 2 · p. 19, §6.2 · p. 19

6.3. Contour-integral nonlinear eigensolvers.

  • The NLEVP experiments use the contour’s geometric center as the sole expansion node, avoiding problem-dependent node selection and allowing one Arnoldi run.Fewer expansion nodes may require a larger Taylor degree and Arnoldi length to reduce truncation error and improve accuracy.Source: §6.3 · p. 20

6.3.1. Benchmarks.

  • IR-TiGMRES is fastest in all six NLEVP problems, with geometric-mean speedups of 3.77 over full refreshed TiGMRES and 1.33 for Dynamic TiGMRES.The smallest speedups occur for railtrack2 rep, where LU factorization dominates runtime.Source: Table 3 · p. 21, §6.3.1 · p. 21
  • For the six NLEVP problems, each method returns the requested eigenvalues, and the largest reported eigenpair residuals range from 5.41 × 10^-14 to 1.14 × 10^-10.Table 4 reports the largest residual for each method, evaluated from eigenpairs returned by the last timed run.Source: §6.3.1 · p. 20, Table 4 · p. 21

7. Conclusions.

The paper presents compact Toeplitz infinite GMRES methods and reports computational advantages in its experiments. It also establishes a scaling limitation for the companion formulation.

7. Conclusions.

  • For fixed separated representations, IR-TiGMRES avoids basis reconstruction and preserves Toeplitz infGMRES complexity bounds under the stated function-evaluation assumptions.Experiments demonstrate computational advantages for parameterized linear systems and contour-integral eigenvalue problems.Source: §7 · p. 21
  • For square-summable Taylor coefficients, the linearized residual cannot converge to zero outside the normalized unit disk.The paper identifies this as a limitation of the companion formulation and relates it to parameter scaling.Source: §7 · p. 21
Loading 2610.01740v1…