Efficient parallel inversion of ParaOpt preconditioners

Arne Bouillon; Corentin Bonte; Giovanni Samaey; Karl Meerbergen

REVIEW 2 major objections 4 minor 13 references

Efficient parallel inversion of ParaOpt preconditioners

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that the inner systems of the ParaOpt preconditioner can be inverted with a single modified boundary value problem solve, preserving black-box propagators and avoiding extra iterations.

desk verdict A correct and useful algebraic trick for inverting ParaOpt inner systems, with a load-bearing well-posedness gap that the authors need to close. read the letter →

arxiv 2412.02425 v1 pith:HKL3Y5WN submitted 2024-12-03 math.NA cs.NAmath.OC

Corentin Bonte , Arne Bouillon , Giovanni Samaey , Karl Meerbergen This is my paper · ORCID

classification math.NAcs.NAmath.OC MSC 65Y0565F0865L10

keywords ParaOptparallel-in-timepreconditioningalpha-circulantdiagonalizationoptimalcontrolboundaryvalueproblem

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

ParaOpt, a parallel-in-time method for optimal control, needs to invert a block-diagonal preconditioner at every quasi-Newton step; each block is a small system tying two subinterval propagators together. The paper shows these inner systems can be solved in a single boundary value problem solve with modified complex boundary conditions, instead of an extra inner GMRES iteration or specialized non-black-box shortcuts. The same direct inversion works for the nonlinear average-based preconditioner after one additional solve of the original optimality system. This lowers the number of coarse BVP solves needed per GMRES iteration and keeps the propagators black-box.

What carries the argument

The load-bearing mechanism is Lemma 1 plus the resulting symmetric phase factorization of the inner matrix. For ParaOpt's $\alpha$-circulant $C(\alpha)$, whose first column has a single nonzero entry $a=1$ on the first subdiagonal, every diagonal entry $d_\ell(\alpha)$ of the diagonalization has $|d_\ell(\alpha)|=1$. Writing $d_\ell(\alpha)=e^{i\theta}$, the inner matrix factors as $-\operatorname{diag}(e^{i\theta/2}, e^{-i\theta/2}) \tilde M \operatorname{diag}(e^{i\theta/2}, e^{-i\theta/2})$, where $\tilde M$ is a boundary-value block whose action is exactly inverted by swapping the boundary conditions in the linearized optimality system (6). This factorization moves the phase factors off the propagator derivatives and onto the identity blocks, which is what turns $M^{-1}$ into a single modified BVP solve.

What would settle it

Take a small linear problem (for instance a scalar or two-by-two constant $K$ with $L=3$ or $4$ subintervals), form the $\alpha$-circulant and the explicit matrix $M$ in (11), and compare the solution from Algorithm 1 with a direct dense solve of $M$ for several right-hand sides $(\delta p,\delta q)$. A mismatch, or a BVP failure for a right-hand side that $M$ can invert, would contradict the paper's claim. Also check the premise $|d_\ell(\alpha)|=1$ numerically for the chosen $\alpha$.

Watch

Extended reading notes

Core claim

The central discovery is that the inner system (11), whose matrix is $M$ as defined in the paper, can be inverted by solving one linearized BVP with boundary conditions $-d_\ell^*(\alpha) z(T_{\ell-1}) + z(T_\ell) = a$ and $\mu(T_{\ell-1}) - d_\ell(\alpha)\mu(T_\ell) = b$, then recovering $\delta y = -z(T_{\ell-1})/c$ and $\delta \lambda = -c\,\mu(T_\ell)$ with $c = e^{i\theta/2}$, $\theta = \angle d_\ell(\alpha)$. This works because, for the $\alpha$-circulant used in ParaOpt, $|d_\ell(\alpha)|=1$, so $d_\ell(\alpha)$ is a pure phase that can be split symmetrically around the block $M_0$ containing the propagator derivatives. The paper extends the same inversion to the nonlinear case by evaluating the preconditioner at averaged states and adjoints, and shows on a viscous Burgers optimal-control example that the new inversion lowers the total number of coarse BVP solves.

Load-bearing premise

The entire method rests on the assumption that for every right-hand side $(a,b)$, the modified linearized boundary value problem in Algorithm 1 has exactly one solution; if the coarse BVP solver cannot recover the preimage under the boundary-to-boundary map, Algorithm 1 has nothing to return.

Editorial extensions

If this is right

In the linear case, every inner system (11) of the ParaOpt preconditioner can be inverted with one BVP solve, eliminating the extra inner GMRES iteration described in [2].
In the nonlinear case, the same inversion applies to the averaged preconditioner (12) after one additional solve of (3), so the preconditioner is no longer restricted to linear problems.
For both final-value and tracking objectives, the number of coarse BVP solves per GMRES iteration in the Burgers example drops to one derivative BVP plus one preconditioner inversion BVP, tracking the reduction in GMRES iterations.
Black-box propagators are retained: the BVP solver is only required to solve linearized systems (6), not to expose internal structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the phase-factor factorization is generic for circulant preconditioners whose diagonal entries are pure phases, the same one-BVP inversion should apply to other ParaDiag-type block-circulant preconditioners beyond ParaOpt, a testable extension.
The paper's numerical results rely on the modified BVP being well-posed; a direct verification on small linear problems with explicitly formed $M$ would separate the method's claim from the solver's behavior.
Because the derivation only uses locality of the BVP, the inversion may remain valid for nonuniform time grids if the diagonalization is replaced by another transform that diagonalizes the coupling matrix and preserves the phase property.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Corentin and colleagues have found a genuinely new algebraic trick, and they have left one unproven assumption that needs to be fixed. The new piece is Section 4: the factorization (16)-(17) moves the d_l factors from the propagator blocks onto the identity, so the inner system (11) becomes a single linear BVP with modified, complex boundary conditions (19). That is a real advance over [2], which required either an inner iteration or a non-black-box solver. The algebra is exact, Lemma 1 is fine, and the nonlinear averaging generalisation in Section 3.2 is the standard ParaDiag trick applied sensibly. The Burgers experiments are honest, show the expected reduction in coarse BVP solves, and the code is released.

The soft spot is real and load-bearing. Algorithm 1 is only valid if the modified BVP in step 2 is well-posed, and the paper does not prove or even state that as an assumption. It is not implied by invertibility of M0. For g(y)=0 and alpha=1, the alpha-circulant has an eigenvalue d=1, and the propagator block is Py=I, Plambda=-(DeltaT/gamma)I, Qy=0, Qlambda=I. Then the matrix in (18) is [[0,-(DeltaT/gamma)I],[0,0]], which is singular; the homogeneous version of the modified BVP has nonzero solutions (z constant, mu=0). So the direct inversion fails for that simple linear problem. The Burgers example dodges the issue, but the paper needs either a proof of well-posedness under reasonable assumptions (for instance, choosing alpha so that no d_l hits a problematic value, or a spectral condition on the propagator) or an explicit assumption plus numerical checks. This is a gap, not a fatal flaw: the method is correct when the modified BVP is well-posed, and those are likely the cases of interest.

Minor points: only one test problem, and the comparison counts BVP solves rather than wall-clock time, so the practical benefit is plausible but not fully demonstrated. The 'black-box' claim should be qualified: the BVP solver must accept complex boundary conditions.

Who should read this: researchers in parallel-in-time methods, especially those working on optimal control and preconditioning. I would send it to peer review; with a well-posedness statement and a little more testing, it is publishable.

Referee Report

2 major / 4 minor

Summary. The paper proposes a direct inversion procedure for the small inner systems that arise when applying the diagonalization-based ParaOpt preconditioner. It generalizes the linear preconditioner to nonlinear problems by evaluating the derivative blocks at averaged state/adjoint values, and it derives an algebraic factorization (Eqs. (16)-(17)) that reduces the inner system (11) to a single complex-valued BVP with modified boundary conditions (Eq. (19)). Algorithm 1 implements this inversion using an abstract coarse BVP solver. Numerical experiments on viscous Burgers equation report reductions in the number of coarse BVP solves relative to the inner-iteration approach.

Significance. If the proposed inversion is valid, it is a useful contribution: it avoids an inner Krylov iteration for the ParaOpt preconditioner and preserves the black-box view of the coarse propagators. The algebraic factorization leading to (19) is exact, Lemma 1 is proved cleanly, and the paper ships reproducible code with a numerical demonstration. No free parameters are fitted, and the claimed reduction in BVP counts is achieved in the Burgers examples. However, the central algorithmic claim is not established in general: the modified BVP in Algorithm 1 is only useful if it is well-posed, and the paper neither proves this nor states a condition under which it holds; in fact it fails for a simple linear problem with α=1. The numerical tests use a dissipative example, which likely satisfies the needed property, so they do not test the general claim.

major comments (2)

[Section 4, Eqs. (18)-(19), Algorithm 1] The central claim is that solving the inner system (11) reduces to solving the BVP with boundary conditions (19), but this is only valid if that modified BVP is well-posed for every right-hand side. The paper asserts this implicitly and gives no proof, and the property is not a consequence of M0 being invertible. A concrete counterexample is the linear case g(y)=0. Then the coarse propagators are Py=I, Pλ=-(ΔT/γ)I, Qy=0, Qλ=I. For α=1 and L≥2, one eigenvalue is dℓ=1, so the matrix M in (11) becomes [[0, (ΔT/γ)I],[0,0]], which is singular and not surjective; for a right-hand side with δq≠0 there is no solution. Correspondingly, the homogeneous form of (19) admits the nonzero solution z≡const, μ≡0, so Algorithm 1, Step 2 is not well-posed. This is not an exotic edge case: the numerical examples use α=1. The authors need to add an explicit well-posedness/invertibility condition (e.g., that no dℓ belongs to the spectrum of the monodromy map, or a choice of α that excludes such values), prove or state it as an assumption, and verify it in the numerical experiments.
[Section 4, Eq. (13)] The preliminary inversion of M0 by 'changing the BCs' has the same missing well-posedness hypothesis. To obtain the inverse of M0 by solving (6) with boundary conditions z(Tℓ)=δp and μ(Tℓ-1)=δq, one must know that this boundary value problem has a unique solution for every such pair. This is not automatic for a generic coarse BVP solver, and the later construction inherits the requirement. The paper should state this as an explicit hypothesis on the coarse solver and on the linearized BVP, rather than treating the BVP solve as a black box that accepts arbitrary two-point boundary conditions.

minor comments (4)

[Section 3.2, Eq. (12)] The notation C1(α) is used in Eq. (12) but is not defined; it should presumably be C(α), the alpha-circulant matrix introduced in Section 3.1.
[Section 2] There are typos in the text: 'method of Langrage multipliers' should be 'method of Lagrange multipliers', and 'first-order order optimality conditions' should be 'first-order optimality conditions'.
[Section 4, Algorithm 1] The phrase 'maintains the black-box property' should be qualified: the abstract BVP solver must now accept complex coefficients and coupled two-point boundary conditions of the form (19), which is a stronger interface than the separated boundary conditions y(Tℓ-1)=Yℓ-1, λ(Tℓ)=Λℓ used by the original propagators P and Q.
[Section 5] The numerical experiments report BVP counts but not wall-clock time; since the new method solves a complex-valued BVP with coupled conditions, a timing comparison would strengthen the claim of practical efficiency.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: Algorithm 1 is an exact algebraic inversion of (11); the unproved well-posedness of (19) is a correctness gap, not a circular reduction.

full rationale

The derivation chain in Sections 3 and 4 is algebraic and self-contained given the published ParaOpt diagonalization framework. The new inversion method contains no fitted parameters and no quantity that is defined in terms of the target output: Eqs. (17)-(19) transform the inner system (11) by the unitary scaling c = e^{iθ/2} and identify the resulting operator with a two-point BVP of the same form as the derivative system (6). Algorithm 1's recovery formulas δy = -z(T_{ℓ-1})/c and δλ = -c μ(T_ℓ) are the exact inverse of that transformation, not a renamed fit or a statistically forced prediction. The numerical example is a demonstration of BVP counts, not a validation of fitted constants. Self-citations to [2] and [7] supply the α-circulant preconditioner and simultaneous diagonalization framework, but these are published, parameter-free mathematical results and are not used to justify the new inversion solely by authority. The one legitimate concern is that Section 4 and Algorithm 1 assume without proof that the modified BVP (19) is well-posed for every right-hand side; for instance, with g(y)=0, α=1 and d_ℓ=1 the homogeneous BCs admit the nontrivial pair z ≡ const, μ ≡ 0, so the algorithm's success depends on an unstated spectral assumption. This is a correctness risk, not circularity, and does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The method introduces no free parameters. The derivation relies on three background assumptions: the well-posedness of the modified BVP (the key enabling assumption), the adequacy of the averaging heuristic for nonlinear problems, and the standard inexact-Newton convergence of ParaOpt. No new entities are postulated.

assumptions (4)

domain assumption The linearized BVP (6) with boundary conditions -d*_ell z(T_{ell-1}) + z(T_ell) = a and mu(T_{ell-1}) - d_ell mu(T_ell) = b (Eq.
This is the load-bearing assumption for the new inversion method. The paper states the boundary conditions 'naturally define' a BVP but provides no existence or uniqueness proof. If the BVP is not well-posed for some d_ell, Algorithm 1 fails.
domain assumption The averaged derivatives P_G_y(Y_av, Lambda_av), etc. (Eq. 12) form a preconditioner that reduces GMRES iterations for the nonlinear ParaOpt system.
Borrowed from nonlinear ParaDiag techniques [8-11]; no convergence analysis is given for ParaOpt. The numerical example shows a benefit, but the generality is unproven.
domain assumption The coarse-propagator Jacobian tilde f' is a sufficient approximation for inexact Newton iteration (5) to converge; the fine solver is exact enough that the matching conditions (4) have a well-defined solution.
This is the standard ParaOpt assumption from [1] and is not new to this paper, but the numerical results depend on it.
standard math The alpha-circulant matrix C(alpha) is diagonalized by C(alpha) = Gamma^{-1} F^* D(alpha) F Gamma, and for |alpha|=1, C(alpha) and C(alpha)^* can be diagonalized simultaneously (Eq. 9 and surrounding text).
Known result from [7]; used in the construction of the preconditioner and in Lemma 1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient parallel inversion of ParaOpt preconditioners." pith.science (2026). https://pith.science/paper/HKL3Y5WN

@misc{pith2026241202425,
  author       = {Pith},
  title        = {Pith review of: Efficient parallel inversion of ParaOpt preconditioners},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HKL3Y5WN}},
  note         = {Machine review of arXiv:2412.02425}
}

read the original abstract

Recently, the ParaOpt algorithm was proposed as an extension of the time-parallel Parareal method to optimal control. ParaOpt uses quasi-Newton steps that each require solving a system of matching conditions iteratively. The state-of-the-art parallel preconditioner for linear problems leads to a set of independent smaller systems that are currently hard to solve. We generalize the preconditioner to the nonlinear case and propose a new, fast inversion method for these smaller systems, avoiding disadvantages of the current options with adjusted boundary conditions in the subproblems.

Figures

Figures reproduced from arXiv: 2412.02425 by the authors.

**Figure 1.** Total GMRES iterations and coarse BVP solves in one subinterval in tracking ParaOpt (without and with the proposed improvements) [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

**Figure 2.** Total GMRES iterations and coarse BVP solves in one subinterval in final value ParaOpt (without and with the proposed improvements) [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 12 canonical work pages

[2]

Bouillon, G

A. Bouillon, G. Samaey, K. Meerbergen, Diagonalization-Based Preconditioners and Generalized Convergence Bounds for ParaOpt, SIAM Journal on Scientific Computing (2024) S317–S345

work page 2024
[1]

M. J. Gander, F. Kwok, J. Salomon, PARAOPT: A Parareal Algorithm for Optimality Systems, SIAM Journal on Scientific Computing 42 (5) (2020) A2773–A2802

work page 2020
[3]

M. J. Gander, F. Kwok, G. Wanner, Constrained Optimization: From Lagrangian Mechanics to Optimal Control and PDE Constraints, in: R. Hoppe (Ed.), Optimization with PDE Constraints, Springer International Publishing, Cham, 2014, pp. 151–202

work page 2014
[4]

pararéel

J.-l. Lions, Y . Maday, G. Turinici, Résolution d’EDP par un schéma en temps "pararéel", Comptes Rendus de l’Académie des Sciences - Series I - Mathematics, 332 (7) (2001) 661–668

work page 2001
[5]

McDonald, J

E. McDonald, J. Pestana, A. Wathen, Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Di fferential Equations, SIAM Journal on Scientific Computing 40 (2) (2018) A1012–A1033

work page 2018
[6]

M. J. Gander, J. Liu, S.-L. Wu, X. Yue, T. Zhou, ParaDiag: Parallel-in-time algorithms based on the diagonalization technique, arXiv:2005.09158 [cs, math] (Apr. 2021). arXiv:2005.09158

arXiv 2005
[7]

Bouillon, G

A. Bouillon, G. Samaey, K. Meerbergen, On Generalized Preconditioners for Time-Parallel Parabolic Optimal Control, SIAM Journal on Scientific Computing 46 (4) (2024) A2298–A2323

work page 2024
[8]

M. J. Gander, L. Halpern, Time Parallelization for Nonlinear Problems Based on Diagonalization, in: C.-O. Lee, X.-C. Cai, D. E. Keyes, H. H. Kim, A. Klawonn, E.-J. Park, O. B. Widlund (Eds.), Domain Decomposition Methods in Science and Engineering XXIII, V ol. 116, Springer International Publishing, Cham, 2017, pp. 163–170

work page 2017

Show all 13 references

[9]

Liu, S.-L

J. Liu, S.-L. Wu, A Fast Block α-Circulant Preconditoner for All-at-Once Systems From Wave Equations, SIAM Journal on Matrix Analysis and Applications 41 (4) (2020) 1912–1943

2020
[10]

S.-L. Wu, T. Zhou, Z. Zhou, A Uniform Spectral Analysis for a Preconditioned All-at-Once System from First-Order and Second-Order Evolutionary Problems, SIAM Journal on Matrix Analysis and Applications 43 (3) (2022) 1331–1353

2022
[11]

S. Wu, Z. Zhou, A Parallel-in-Time Algorithm for High-Order BDF Methods for Di ffusion and Subdiffusion Equations, SIAM Journal on Scientific Computing 43 (6) (2021) A3627–A3656

2021
[12]

Fornberg, A Practical Guide to Pseudospectral Methods, 1st Edition, Cambridge University Press, 1996

B. Fornberg, A Practical Guide to Pseudospectral Methods, 1st Edition, Cambridge University Press, 1996

1996
[13]

Sabeh, M

Z. Sabeh, M. Shamsi, M. Dehghan, Distributed optimal control of the viscous Burgers equation via a Legendre pseudo-spectral approach, Mathematical Methods in the Applied Sciences 39 (12) (2016) 3350–3360. 6

2016

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [2]

Bouillon, G

A. Bouillon, G. Samaey, K. Meerbergen, Diagonalization-Based Preconditioners and Generalized Convergence Bounds for ParaOpt, SIAM Journal on Scientific Computing (2024) S317–S345

work page 2024

[2] [1]

M. J. Gander, F. Kwok, J. Salomon, PARAOPT: A Parareal Algorithm for Optimality Systems, SIAM Journal on Scientific Computing 42 (5) (2020) A2773–A2802

work page 2020

[3] [3]

M. J. Gander, F. Kwok, G. Wanner, Constrained Optimization: From Lagrangian Mechanics to Optimal Control and PDE Constraints, in: R. Hoppe (Ed.), Optimization with PDE Constraints, Springer International Publishing, Cham, 2014, pp. 151–202

work page 2014

[4] [4]

pararéel

J.-l. Lions, Y . Maday, G. Turinici, Résolution d’EDP par un schéma en temps "pararéel", Comptes Rendus de l’Académie des Sciences - Series I - Mathematics, 332 (7) (2001) 661–668

work page 2001

[5] [5]

McDonald, J

E. McDonald, J. Pestana, A. Wathen, Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Di fferential Equations, SIAM Journal on Scientific Computing 40 (2) (2018) A1012–A1033

work page 2018

[6] [6]

M. J. Gander, J. Liu, S.-L. Wu, X. Yue, T. Zhou, ParaDiag: Parallel-in-time algorithms based on the diagonalization technique, arXiv:2005.09158 [cs, math] (Apr. 2021). arXiv:2005.09158

arXiv 2005

[7] [7]

Bouillon, G

A. Bouillon, G. Samaey, K. Meerbergen, On Generalized Preconditioners for Time-Parallel Parabolic Optimal Control, SIAM Journal on Scientific Computing 46 (4) (2024) A2298–A2323

work page 2024

[8] [8]

M. J. Gander, L. Halpern, Time Parallelization for Nonlinear Problems Based on Diagonalization, in: C.-O. Lee, X.-C. Cai, D. E. Keyes, H. H. Kim, A. Klawonn, E.-J. Park, O. B. Widlund (Eds.), Domain Decomposition Methods in Science and Engineering XXIII, V ol. 116, Springer International Publishing, Cham, 2017, pp. 163–170

work page 2017