pith. sign in

arxiv: 2506.03947 · v4 · submitted 2025-06-04 · 🧮 math.NA · cs.NA

Block Alpha-Circulant Preconditioners for All-at-Once Diffusion-Based Covariance Operators

Jemima M. Tabeart , Selime G\"urol , John W. Pearson , Anthony T. Weaver This is my paper

Pith reviewed 2026-05-19 11:20 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords block alpha-circulant preconditionersall-at-once systemsdiffusion-based covariance operatorsChebyshev semi-iterationsaddle-point systemsdata assimilationpreconditioningnumerical linear algebra
0
0 comments X

The pith

Approximate block alpha-circulant preconditioners enable robust and efficient solves for all-at-once diffusion-based covariance operators using inner Chebyshev or saddle-point iterations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops practical ways to apply block alpha-circulant preconditioners to all-at-once systems for diffusion-based covariance operators even when the underlying diffusion matrix cannot be diagonalized by a discrete Fourier transform. Covariance operators play a central role in data assimilation and statistical inverse problems, and the all-at-once formulation exploits parallelism across the system. Prior approaches depended on exact Fourier diagonalization, which is not always available, so the authors replace exact application of the preconditioner with approximate inner solves on the resulting block diagonal problems. One route uses Chebyshev semi-iteration on a complex-shifted positive definite matrix, with extended convergence bounds; the other recasts each subproblem as a real saddle-point system. If these approximations preserve outer convergence, the methods would allow scalable parallel computation of covariance actions in large statistical estimation tasks without requiring special matrix structure.

Core claim

We provide practical methods to apply block alpha-circulant preconditioners to the all-at-once system for the case where the main diffusion operation matrix cannot be readily diagonalized using a discrete Fourier transform. Our new framework applies the block alpha-circulant preconditioner approximately by solving an inner block diagonal problem via a choice of inner iterative approaches. Our first method applies Chebyshev semi-iteration to a symmetric positive definite matrix, shifted by a complex scaling of the identity, and we extend theoretical results to obtain computable bounds on the asymptotic convergence factor for each of the complex sub-problems. The second approach transforms the

What carries the argument

Approximate application of the block alpha-circulant preconditioner through inner iterative solution of complex-shifted block diagonal or saddle-point subproblems.

If this is right

  • With unlimited computational resources both inner methods achieve outer iteration counts matching those of the exact best-case block alpha-circulant preconditioner.
  • A nested adaptation of the Chebyshev approach reduces work under a limited computational budget while retaining robustness.
  • Suitable choices of the parameter alpha make the overall scheme robust when measured by outer iterations and total matrix-vector products.
  • The framework extends all-at-once diffusion representations to matrices that lack Fourier diagonalizability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same inner-solver strategy for approximate circulant preconditioners could transfer to other all-at-once or time-parallel formulations of evolution equations.
  • Convergence bounds for the complex subproblems may guide parameter tuning in related iterative methods for statistical estimation beyond the diffusion case.
  • Hybrid combinations of these alpha-circulant approximations with other parallel preconditioners might further improve scalability in large data-assimilation pipelines.

Load-bearing premise

The inner block diagonal problems arising from the approximate block alpha-circulant preconditioner can be solved to sufficient accuracy by Chebyshev semi-iteration or saddle-point methods without degrading outer iteration convergence in practice.

What would settle it

A marked increase in outer iteration count or total matrix-vector products when the inner Chebyshev or saddle-point solves are used instead of exact preconditioner application would show that the approximations fail to preserve efficiency.

Figures

Figures reproduced from arXiv: 2506.03947 by Anthony T. Weaver, Jemima M. Tabeart, John W. Pearson, Selime G\"urol.

Figure 1
Figure 1. Figure 1: Visualization of scaled 10-th roots of unity on [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Left panel: Number of iterations to reach convergence fo [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Relative error at each iteration of CI applied to [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Number of iterations to reach convergence using [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Comparison of the norm of the relative residual [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of wallclock times required for the pre-comput [PITH_FULL_IMAGE:figures/full_fig_p021_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Comparison of the relative residual norm [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Wallclock times for increasing problem dimension when using th [PITH_FULL_IMAGE:figures/full_fig_p023_8.png] view at source ↗
read the original abstract

Covariance matrices are central to data assimilation and inverse methods derived from statistical estimation theory. Previous work has considered the application of an all-at-once diffusion-based representation of a covariance matrix operator in order to exploit inherent parallelism in the underlying problem. In this paper, we provide practical methods to apply block $\alpha$-circulant preconditioners to the all-at-once system for the case where the main diffusion operation matrix cannot be readily diagonalized using a discrete Fourier transform. Our new framework applies the block $\alpha$-circulant preconditioner approximately by solving an inner block diagonal problem via a choice of inner iterative approaches. Our first method applies Chebyshev semi-iteration to a symmetric positive definite matrix, shifted by a complex scaling of the identity. We extend theoretical results for Chebyshev semi-iteration in the symmetric positive definite setting, to obtain computable bounds on the asymptotic convergence factor for each of the complex sub-problems. The second approach transforms the complex sub-problem into a (generalized) saddle point system with real coefficients. Numerical experiments reveal that in the case of unlimited computational resources, both methods can match the iteration counts of the `best-case' block $\alpha$-circulant preconditioner. We also provide a practical adaptation to the nested Chebyshev approach, which improves performance in the case of a limited computational budget. Using an appropriate choice of $\alpha$ our new approaches are robust and efficient in terms of outer iterations and matrix--vector products.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops practical approximate application methods for block α-circulant preconditioners applied to all-at-once linear systems arising from diffusion-based covariance operators, specifically when the underlying diffusion matrix cannot be diagonalized via the discrete Fourier transform. The preconditioner is applied by solving inner block-diagonal complex-shifted problems either via an extension of Chebyshev semi-iteration (with new bounds on the asymptotic convergence factor) or via a real-coefficient generalized saddle-point reformulation. Numerical experiments are presented claiming that, for suitable choices of α, both inner approaches can match the outer GMRES iteration counts of the exact best-case block α-circulant preconditioner under unlimited resources, together with a practical nested-Chebyshev adaptation for limited budgets.

Significance. If the central claims hold, the work supplies usable techniques for deploying α-circulant preconditioners in settings where exact block-diagonal solves are unavailable, which is relevant to parallel-in-time data assimilation and inverse problems. The extension of Chebyshev convergence theory to complex shifts and the saddle-point reformulation constitute concrete technical contributions. The reported numerical matching of outer iteration counts and matvec efficiency for chosen α, if reproducible with explicit inner tolerances, would strengthen the case for these preconditioners in practice.

major comments (2)
  1. [§3] §3 (theoretical extension): the new bounds on the asymptotic convergence factor for Chebyshev semi-iteration applied to the complex-shifted SPD blocks are derived, but the manuscript does not provide a quantitative link showing how these inner factors control the spectrum of the overall preconditioned operator or the outer GMRES convergence rate; without this transfer result the claim that inner solves preserve best-case outer iteration counts remains unproven.
  2. [Numerical experiments] Numerical experiments section, Tables 1–3: the reported outer iteration counts and total matvecs for the approximate inner methods are stated to match the exact block α-circulant case, yet the inner iteration tolerances, maximum inner iterations, and resulting effective preconditioner quality are not tabulated or analyzed; this omission makes it impossible to verify that the inner solves do not degrade the outer convergence enough to offset the claimed robustness.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'matrix--vector products' uses a double hyphen; replace with a single hyphen or en-dash for consistency with journal style.
  2. [§2] Notation: the parameter α is introduced as a free choice, but its admissible range and any constraints arising from the complex shift in the Chebyshev analysis should be stated explicitly in the first section where the preconditioner is defined.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments provided. Below we respond to each major comment in turn, indicating the changes we intend to make to the paper.

read point-by-point responses

  1. Referee: [§3] §3 (theoretical extension): the new bounds on the asymptotic convergence factor for Chebyshev semi-iteration applied to the complex-shifted SPD blocks are derived, but the manuscript does not provide a quantitative link showing how these inner factors control the spectrum of the overall preconditioned operator or the outer GMRES convergence rate; without this transfer result the claim that inner solves preserve best-case outer iteration counts remains unproven.

    Authors: We appreciate this observation. The bounds we derive control the rate at which the inner Chebyshev iterations converge to the exact solution of the complex-shifted systems. When computational resources are unlimited, one can perform a sufficient number of inner iterations to achieve machine precision accuracy, rendering the approximate preconditioner application identical to the exact block α-circulant preconditioner. Consequently, the outer GMRES iteration counts match those of the best-case scenario by construction, without requiring an additional transfer theorem for this limiting case. For the practical nested-Chebyshev variant with limited budgets, the matching is demonstrated numerically. In the revision, we will clarify this distinction in §3 and the numerical experiments section to make the claims more precise. revision: partial

  2. Referee: [Numerical experiments] Numerical experiments section, Tables 1–3: the reported outer iteration counts and total matvecs for the approximate inner methods are stated to match the exact block α-circulant case, yet the inner iteration tolerances, maximum inner iterations, and resulting effective preconditioner quality are not tabulated or analyzed; this omission makes it impossible to verify that the inner solves do not degrade the outer convergence enough to offset the claimed robustness.

    Authors: We agree that providing details on the inner solver parameters would enhance reproducibility and allow better assessment of the preconditioner quality. In the revised manuscript, we will include additional information, such as a new table or expanded discussion in the numerical experiments section, specifying the inner iteration tolerances, maximum number of inner iterations employed for each method, and any analysis of the resulting effective preconditioner accuracy relative to the exact case. This will substantiate that the inner solves maintain sufficient quality to preserve the reported outer iteration robustness. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via standard theory and explicit extensions.

full rationale

The paper extends known Chebyshev semi-iteration bounds to complex-shifted SPD matrices and reformulates subproblems as real saddle-point systems using standard algebraic manipulations. These steps are derived directly from the block α-circulant structure and inner solver theory without reducing any central claim (robustness for chosen α, outer iteration counts) to a fitted parameter or self-citation chain. Numerical experiments compare against the exact best-case preconditioner, providing external falsifiability. No load-bearing uniqueness theorem or ansatz is imported from the authors' prior work; the framework remains independent of its own outputs.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

Limited information available from abstract; relies on standard assumptions of symmetric positive definiteness for Chebyshev applicability and existence of suitable inner solvers for the block diagonal subproblems.

free parameters (1)
  • alpha
    Parameter controlling the circulant approximation; chosen appropriately for robustness but no specific fitting procedure described.
axioms (1)
  • domain assumption The shifted matrix remains suitable for Chebyshev semi-iteration bounds after complex scaling.
    Invoked when extending theoretical results to complex sub-problems.

pith-pipeline@v0.9.0 · 5813 in / 1278 out tokens · 47530 ms · 2026-05-19T11:20:17.077302+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Iterative Solution Methods

    Owe Axelsson. Iterative Solution Methods . Cambridge University Press, Cambridge, UK, 1996

    work page 1996

  2. [2]

    Joseph Bak and Donald J. Newman. Complex Analysis . Springer New York, NY, 2010

    work page 2010

  3. [3]

    Daniele Bertaccini and Michael K. Ng. Block {ω }-circulant preconditioners for the systems of differential equations. Calcolo, 40(2):71–90, 2003

    work page 2003

  4. [4]

    HSL MI20: an efficient AMG precon- ditioner for finite element problems in 3D

    Jonathan Boyle, Milan Mihajlovi´ c, and Jennifer Scott. HSL MI20: an efficient AMG precon- ditioner for finite element problems in 3D. International Journal for Numerical Methods in Engineering, 82(1):64–98, 2010

    work page 2010

  5. [5]

    A computational framework for infinite-dimensional Bayesian inverse problems

    Tan Bui-Thanh, Omar Ghattas, James Martin, and Georg Stadler . A computational framework for infinite-dimensional Bayesian inverse problems. Part I: The linea rized case, with application to global seismic inversion. SIAM Journal on Scientific Computing , 35(6):A2494–A2523, 2013

    work page 2013

  6. [6]

    Weaver, Philip Browne, Hao Zuo, and M agdalena A

    Marcin Chrust, Anthony T. Weaver, Philip Browne, Hao Zuo, and M agdalena A. Balmaseda. Impact of ensemble-based hybrid background-error covariance s in ECMWF’s next generation ocean reanalysis system. Quarterly Journal of the Royal Meteorological Society , 151(767):e4914, 2025

    work page 2025

  7. [7]

    On a class of Chebyshe v approximation problems which arise in connection with a conjugate gradient type method

    Roland Freund and Stephan Ruscheweyh. On a class of Chebyshe v approximation problems which arise in connection with a conjugate gradient type method. Numerische Mathematik , 48(5):525–542, 1986

    work page 1986

  8. [8]

    Gander and Davide Palitta

    Martin J. Gander and Davide Palitta. A new ParaDiag time-parallel t ime integration method. SIAM Journal on Scientific Computing , 46(2):A697–A718, 2024

    work page 2024

  9. [9]

    Composite convergence bounds based on Chebyshev polyno- mials and finite precision conjugate gradient computations

    Tom´ aˇ s Gergelits and Zdenˇ ek Strakoˇ s. Composite convergence bounds based on Chebyshev polyno- mials and finite precision conjugate gradient computations. Numerical Algorithms, 65(4):759–782, 2014

    work page 2014

  10. [10]

    Weaver, Youssef Diouane , and Oliver Guillet

    Olivier Goux, Selime G¨ urol, Anthony T. Weaver, Youssef Diouane , and Oliver Guillet. Impact of correlated observation errors on the conditioning of variationa l data assimilation problems. Numerical Linear Algebra with Applications , 31(1):e2529, 2024. 25

    work page 2024

  11. [11]

    Weaver, Xavier Vasseur, Yann Michel, S erge Gratton, and Selime G¨ urol

    Oliver Guillet, Anthony T. Weaver, Xavier Vasseur, Yann Michel, S erge Gratton, and Selime G¨ urol. Modelling spatially correlated observation errors in variation al data assimilation using a diffusion operator on an unstructured mesh. Quarterly Journal of the Royal Meteorological Society, 145(722):1947–1967, 2019

    work page 1947

  12. [12]

    Gutknecht and Stefan R¨ ollin

    Martin H. Gutknecht and Stefan R¨ ollin. The Chebyshev iteratio n revisited. Parallel Computing , 28(2):263–283, 2002

    work page 2002

  13. [13]

    Studies in the history of pro bability and statistics XLIX: On the Mat´ ern correlation family

    Peter Guttorp and Tilmann Gneiting. Studies in the history of pro bability and statistics XLIX: On the Mat´ ern correlation family. Biometrika, 93(4):989–995, 2006

    work page 2006

  14. [14]

    Hestenes and Eduard Stiefel

    Magnus R. Hestenes and Eduard Stiefel. Methods of conjugat e gradients for solving linear sys- tems. Journal of Research of the National Bureau of Standards , 49(6):409–436, 1952

    work page 1952

  15. [15]

    A sine transform based preconditioned MINRES method for all-at-once systems from cons tant and variable-coefficient evolutionary partial differential equations

    Sean Hon, Po Yin Fun, Jiamei Dong, and Stefano Serra-Capizza no. A sine transform based preconditioned MINRES method for all-at-once systems from cons tant and variable-coefficient evolutionary partial differential equations. Numerical Algorithms, 95(4):1769–1799, 2024

    work page 2024

  16. [16]

    A First Course in the Numerical Analysis of Differential Equa tions

    Arieh Iserles. A First Course in the Numerical Analysis of Differential Equa tions. Cambridge University Press, Cambridge, UK, 2008

    work page 2008

  17. [17]

    A preconditio ned MINRES method for block lower triangular Toeplitz systems

    Congcong Li, Xuelei Lin, Sean Hon, and Shu-Lin Wu. A preconditio ned MINRES method for block lower triangular Toeplitz systems. Journal of Scientific Computing , 100(3):Art. 63, 2024

    work page 2024

  18. [18]

    An all-at-once preconditioner for ev olutionary partial differential equations

    Xue-lei Lin and Michael Ng. An all-at-once preconditioner for ev olutionary partial differential equations. SIAM Journal on Scientific Computing , 43(4):A2766–A2784, 2021

    work page 2021

  19. [19]

    An explicit link between Gaussian fields and Gaussian Markov random fields: the stochastic partial differential equation approach

    Finn Lindgren, H ˚ avard Rue, and Johan Lindstr¨ om. An explicit link between Gaussian fields and Gaussian Markov random fields: the stochastic partial differential equation approach. Journal of the Royal Statistical Society, Series B (Statistical Metho dology), 73(4):423–498, 2011

    work page 2011

  20. [20]

    A fast block α -circulant preconditioner for all-at-once systems from wave equations

    Jun Liu and Shu-Lin Wu. A fast block α -circulant preconditioner for all-at-once systems from wave equations. SIAM Journal on Matrix Analysis and Applications , 41(4):1912–1943, 2020

    work page 1912

  21. [21]

    Manteuffel

    Thomas A. Manteuffel. The Tchebychev iteration for nonsymme tric linear systems. Numerische Mathematik, 28(3):307–327, 1977

    work page 1977

  22. [22]

    Manteuffel

    Thomas A. Manteuffel. Adaptive procedure for estimating para meters for the nonsymmetric Tchebychev iteration. Numerische Mathematik , 31(2):183–208, 1978

    work page 1978

  23. [23]

    Preco nditioning and iterative solution of all-at-once systems for evolutionary partial differential equat ions

    Eleanor McDonald, Jennifer Pestana, and Andy Wathen. Preco nditioning and iterative solution of all-at-once systems for evolutionary partial differential equat ions. SIAM Journal on Scientific Computing, 40(2):A1012–A1033, 2018

    work page 2018

  24. [24]

    Richardson’s iteration for n onsymmetric matrices

    Gerhard Opfer and Glenn Schober. Richardson’s iteration for n onsymmetric matrices. Linear Algebra and its Applications , 58:343–361, 1984

    work page 1984

  25. [25]

    Paige and Michael A

    Christopher C. Paige and Michael A. Saunders. Solution of spar se indefinite systems of linear squations. SIAM Journal on Numerical Analysis , 12(4):617–629, 1975

    work page 1975

  26. [26]

    Pearson and Andrew J

    John W. Pearson and Andrew J. Wathen. A new approximation of the Schur complement in preconditioners for PDE-constrained optimization. Numerical Linear Algebra with Applications , 19(5):816–829, 2012

    work page 2012

  27. [27]

    Ruge and Klaus St¨ uben

    John W. Ruge and Klaus St¨ uben. Algebraic multigrid. In Stephen F. McCormick, editor, Multi- grid Methods, pages 73–130. SIAM, 1987. 26

    work page 1987

  28. [28]

    In order to ma ke spatial statistics computa- tionally feasible, we need to forget about the covariance function

    Daniel Simpson, Finn Lindgren, and H ˚ avard Rue. In order to ma ke spatial statistics computa- tionally feasible, we need to forget about the covariance function. Environmetrics, 23(1):65–74, 2012

    work page 2012

  29. [29]

    One-shot solution of a time-dependent time-period ic PDE-constrained optimization problem

    Martin Stoll. One-shot solution of a time-dependent time-period ic PDE-constrained optimization problem. IMA Journal of Numerical Analysis , 34(4):1554–1577, 2014

    work page 2014

  30. [30]

    Inverse Problem Theory and Methods for Model Parameter Esti mation

    Albert Tarantola. Inverse Problem Theory and Methods for Model Parameter Esti mation. SIAM, Philadelphia, PA, 2005

    work page 2005

  31. [31]

    Weaver, Selime G¨ urol, Jean Tshimanga, Marcin Chru st, and Andrea Piacentini

    Anthony T. Weaver, Selime G¨ urol, Jean Tshimanga, Marcin Chru st, and Andrea Piacentini. “Time”-Parallel diffusion-based correlation operators. Quarterly Journal of the Royal Meteoro- logical Society, 144(716):2067–2088, 2018

    work page 2067

  32. [32]

    Weaver and Isabelle Mirouze

    Anthony T. Weaver and Isabelle Mirouze. On the diffusion equatio n and its application to isotropic and anisotropic correlation modelling in variational assimilatio n. Quarterly Journal of the Royal Meteorological Society , 139(670):242–260, 2013

    work page 2013

  33. [33]

    Weaver, Jean Tshimanga, and Andrea Piacentini

    Anthony T. Weaver, Jean Tshimanga, and Andrea Piacentini. Co rrelation operators based on an implicitly formulated diffusion equation solved with the Chebyshev itera tion. Quarterly Journal of the Royal Meteorological Society , 142(694):455–471, 2016

    work page 2016

  34. [34]

    Nonstandard norms and robust estimates fo r saddle point problems

    Walter Zulehner. Nonstandard norms and robust estimates fo r saddle point problems. SIAM Journal on Matrix Analysis and Applications , 32(2):536–560, 2011. 27

    work page 2011