pith. sign in

arxiv: 2509.22156 · v2 · submitted 2025-09-26 · 🧮 math.NA · cs.NA

A Parallel-in-Time Combination Method for Parabolic Problems

Michael Griebel , Marc Alexander Schweitzer , Lukas Troska This is my paper

Pith reviewed 2026-05-18 12:54 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords parallel-in-timeMGRITsparse gridsspace-filling curvesdomain decompositionparabolic PDEsheat equationhigh-dimensional problems
0
0 comments X

The pith

A combination of parallel-in-time multigrid, sparse-grid discretization, and space-filling-curve decomposition produces an embarrassingly parallel solver for parabolic problems up to six dimensions.

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

The paper develops a discretization and solution approach for parabolic problems that integrates three existing techniques into one framework. It applies the multigrid reduction-in-time algorithm to advance the solution in parallel across time steps, uses the sparse-grid combination method to discretize the elliptic problems that arise in space, and adds a space-filling-curve domain decomposition to distribute each subproblem. The resulting method is described as extremely fast with excellent speedup and scale-up properties. A sympathetic reader would care because many applications in physics, chemistry, and stochastic modeling require solutions in four to six space dimensions, where conventional time-marching and full-grid approaches quickly become prohibitive on even large parallel machines.

Core claim

The authors present a parallel discretization and solution method for parabolic problems with a higher number of space dimensions. It consists of a parallel-in-time approach using the multigrid reduction-in-time algorithm MGRIT with its implementation in the library XBraid, the sparse grid combination method for discretizing the resulting elliptic problems in space, and a domain decomposition method for each of the subproblems in the combination method based on the space-filling curve approach. As a result, they obtain an extremely fast and embarrassingly parallel solver with excellent speedup and scale-up qualities, which is perfectly suited for parabolic problems with up to six space 1.5 2

What carries the argument

The integrated parallel solver formed by combining MGRIT for time-parallel integration, the sparse-grid combination technique for spatial discretization, and space-filling-curve domain decomposition for each subproblem.

Load-bearing premise

The three component techniques can be integrated without destroying stability, accuracy, or parallel efficiency for the parabolic problems tested.

What would settle it

Solve a six-dimensional heat equation with the combined method on a large parallel machine and check whether measured wall-clock time continues to drop linearly with added processors while the computed solution remains within a fixed error tolerance of a reference solution obtained by a standard sequential method.

Figures

Figures reproduced from arXiv: 2509.22156 by Lukas Troska, Marc Alexander Schweitzer, Michael Griebel.

Figure 6
Figure 6. Figure 6: C tl,0 Tl,0 Φl,0 Φcoarse,l,0 F tl,1 Φl,1 F tl,2 Φl,2 C tl,3 Tl,1 Φl,3 Φcoarse,l,1 F tl,4 Φl,4 F tl,5 Φl,5 C tl,6 Tl,2 Φl,6 Φcoarse,l,2 F tl,7 Φl,7 F tl,8 Φl,8 C tl,9 Tl,3 Φl,9 Φcoarse,l,3 F tl,10 Φl,10 F tl,11 Φl,11 C tl,12 Tl,4 1 [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
read the original abstract

In this article, we present a parallel discretization and solution method for parabolic problems with a higher number of space dimensions. It consists of a parallel-in-time approach using the multigrid reduction-in-time algorithm MGRIT with its implementation in the library XBraid, the sparse grid combination method for discretizing the resulting elliptic problems in space, and a domain decomposition method for each of the subproblems in the combination method based on the space-filling curve approach. As a result, we obtain an extremely fast and embarrassingly parallel solver with excellent speedup and scale-up qualities, which is perfectly suited for parabolic problems with up to six space dimensions. We describe our new parallel approach and show its superior parallelization properties for the heat equation, the chemical master equation and some exemplary stochastic differential equations.

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 / 3 minor

Summary. The manuscript presents a parallel discretization and solution method for high-dimensional parabolic problems. It combines the multigrid reduction-in-time (MGRIT) algorithm implemented in XBraid for time-parallelism, the sparse-grid combination technique for spatial discretization of the resulting elliptic problems, and a space-filling-curve domain decomposition approach for each subproblem. Numerical experiments on the heat equation, the chemical master equation, and selected stochastic differential equations are used to demonstrate the method's parallel performance, with claims of excellent speedup, scale-up, and suitability for problems with up to six space dimensions.

Significance. If the reported numerical results hold under the combined scheme, the work offers a practical route to solving parabolic problems in up to six dimensions with an embarrassingly parallel approach that leverages existing libraries. The integration of established components (MGRIT, sparse grids, SFC partitioning) is a strength for immediate applicability, and the focus on real-world examples such as the chemical master equation adds relevance. However, the absence of any convergence or stability analysis for the composite scheme limits the long-term significance beyond the specific test cases shown.

major comments (2)
  1. [Section 4] Section 4 (Numerical Results), heat-equation experiments: the reported L2 errors and speedup factors for d=6 are presented without a dedicated study isolating the effect of applying MGRIT coarse-grid corrections to the anisotropic operators produced by the sparse-grid combination; this interaction is load-bearing for the central claim that the three techniques integrate without loss of accuracy or stability.
  2. [Section 3] Section 3 (Method Description), combination step: no estimate is given for how the spectrum of the spatial operators changes when MGRIT is applied to the individual sparse-grid subproblems, nor for the additional communication introduced by SFC partitioning; this is central to the assertion of preserved parallel efficiency up to six dimensions.
minor comments (3)
  1. [Introduction] Introduction: the claim of an 'extremely fast and embarrassingly parallel solver' should be qualified by reference to the specific hardware and problem sizes used in the experiments.
  2. [Figure 2] Figure 2: axis labels and legends are too small to read the different combination levels clearly.
  3. [References] References: the original sparse-grid combination paper by Griebel et al. is cited, but a more recent review on high-dimensional parabolic solvers would help contextualize the contribution.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address the two major comments point by point below, proposing revisions that strengthen the presentation while remaining faithful to the numerical focus of the work.

read point-by-point responses

  1. Referee: [Section 4] Section 4 (Numerical Results), heat-equation experiments: the reported L2 errors and speedup factors for d=6 are presented without a dedicated study isolating the effect of applying MGRIT coarse-grid corrections to the anisotropic operators produced by the sparse-grid combination; this interaction is load-bearing for the central claim that the three techniques integrate without loss of accuracy or stability.

    Authors: We agree that a more explicit isolation of the MGRIT–anisotropic-operator interaction would clarify the results. The L2 errors reported for d=6 remain consistent with the known accuracy of the sparse-grid combination technique applied to the heat equation, and the observed speedups track the expected parallel scaling of XBraid on the individual subproblems. To address the concern directly, we will add a short comparative study in the revised Section 4 that recomputes selected d=6 cases both with and without MGRIT coarse-grid corrections on the anisotropic sparse-grid operators, thereby isolating any effect on accuracy and stability. revision: yes

  2. Referee: [Section 3] Section 3 (Method Description), combination step: no estimate is given for how the spectrum of the spatial operators changes when MGRIT is applied to the individual sparse-grid subproblems, nor for the additional communication introduced by SFC partitioning; this is central to the assertion of preserved parallel efficiency up to six dimensions.

    Authors: The sparse-grid combination technique yields a fixed set of anisotropic but still elliptic spatial operators whose spectra are already documented in the sparse-grid literature; MGRIT acts only on the temporal direction and inherits the spatial spectrum of each subproblem. We therefore do not expect a qualitative change in the spatial spectrum. For communication, the space-filling-curve partitioning is selected to maintain spatial locality, and the scale-up results up to six dimensions already demonstrate that parallel efficiency is preserved. In the revision we will insert a concise paragraph in Section 3 that recalls the spectral properties of the anisotropic operators and provides a first-order estimate of the additional communication volume induced by the SFC-based domain decomposition across the combination levels. revision: partial

Circularity Check

0 steps flagged

No circularity detected in method composition for high-dimensional parabolic solvers

full rationale

The paper presents a composition of three established techniques—MGRIT for parallel-in-time integration, the sparse-grid combination method for spatial discretization, and space-filling-curve domain decomposition—for parabolic problems up to six dimensions. Claims of excellent speedup, scale-up, and suitability rest on numerical tests for the heat equation, chemical master equation, and stochastic differential equations rather than any first-principles derivation, fitted parameters renamed as predictions, or load-bearing self-citations that reduce the result to its inputs by construction. No equations or theoretical steps are shown that would make the performance claims equivalent to the method definition itself; the work is self-contained as an empirical demonstration of integrated existing components.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract describes an assembly of standard numerical components; no new free parameters, axioms, or invented entities are introduced beyond those already present in MGRIT, sparse grids, and domain decomposition.

pith-pipeline@v0.9.0 · 5659 in / 1067 out tokens · 32400 ms · 2026-05-18T12:54:08.117586+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

28 extracted references · 28 canonical work pages

  1. [1]

    http://llnl.gov/casc/xbraid

    XB raid: Parallel Multigrid in Time . http://llnl.gov/casc/xbraid

    work page

  2. [2]

    Anderson, J

    P. Amestoy, A. Buttari, J.-Y. L'Excellent, and T. Mary , Performance and Scalability of the Block Low-Rank Multifrontal Factorization on Multicore Architectures , ACM Transactions on Mathematical Software, 45 (2019), pp. 2:1--2:26, https://doi.org/10.1145/3242094

    work page doi:10.1145/3242094 2019

  3. [3]

    Amestoy, I

    P. Amestoy, I. S. Duff, J. Koster, and J.-Y. L'Excellent , A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling , SIAM Journal on Matrix Analysis and Applications, 23 (2001), pp. 15--41, https://doi.org/10.1137/s0895479899358194

    work page doi:10.1137/s0895479899358194 2001

  4. [4]

    Balay, S

    S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, S. Zampini, and H. Zhang , PETS c Users Manual , Tech. Report ANL-95/11 - Revision 3.6, 2015, http://www.mcs.anl.gov/petsc

    work page 2015

  5. [5]

    Balay, S

    S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, S. Zampini, and H. Zhang , PETS c W eb Page . http://www.mcs.anl.gov/petsc, 2015, http://www.mcs.anl.gov/petsc

    work page 2015

  6. [6]

    Balay, W

    S. Balay, W. D. Gropp, L. C. McInnes, and B. F. Smith , Efficient Management of Parallelism in Object Oriented Numerical Software Libraries , in Modern Software Tools in Scientific Computing, E. Arge, A. M. Bruaset, and H. P. Langtangen, eds., Birkh \" a user Press, 1997, pp. 163--202, https://doi.org/10.1007/978-1-4612-1986-6_8

    work page doi:10.1007/978-1-4612-1986-6_8 1997

  7. [7]

    Bungartz and M

    H.-J. Bungartz and M. Griebel , Sparse Grids , Acta Numerica, 13 (2004), pp. 147--269, https://doi.org/10.1017/cbo9780511569975.003

    work page doi:10.1017/cbo9780511569975.003 2004

  8. [8]

    Deuflhard, W

    P. Deuflhard, W. Huisinga, T. Jahnke, and M. Wulkow , Adaptive Discrete Galerkin Methods Applied to the Chemical Master Equation , SIAM Journal on Scientific Computing, 30 (2008), pp. 2990--3011, https://doi.org/10.1137/070689759

    work page doi:10.1137/070689759 2008

  9. [9]

    Falgout, S

    R. Falgout, S. Friedhoff, T. Kolev, S. MacLachlan, and J. Schroder , Parallel Time Integration with Multigrid , SIAM Journal on Scientific Computing, 36 (2014), pp. C635--C661, https://doi.org/10.1002/pamm.201410456

    work page doi:10.1002/pamm.201410456 2014

  10. [10]

    Ganter and T

    M. Ganter and T. Lunet , Time Parallel Time Integration , vol. 99 of CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, 2024, https://doi.org/10.1137/1.9781611978025

    work page doi:10.1137/1.9781611978025 2024

  11. [11]

    Garcke , Sparse Grids in a Nutshell , in Sparse grids and applications, J

    J. Garcke , Sparse Grids in a Nutshell , in Sparse grids and applications, J. Garcke and M. Griebel, eds., vol. 88 of Lecture Notes in Computational Science and Engineering, Springer, 2013, pp. 57--80

    work page 2013

  12. [12]

    T. S. Gardner, C. R. Cantor, and J. J. Collins , Construction of a Genetic Toggle Switch in Escherichia Coli , Nature, 403 (2000), pp. 339--342, https://doi.org/10.1038/35002131

    work page doi:10.1038/35002131 2000

  13. [13]

    The Journal of Physical Chemistry , volume =

    D. Gillespie , Exact Stochastic Simulation of Coupled Chemical Reactions , The Journal of Physical Chemistry, 81 (1977), pp. 2340--2361, https://doi.org/10.1021/j100540a008

    work page doi:10.1021/j100540a008 1977

  14. [14]

    Griebel , Adaptive Sparse Grid Multilevel Methods for Elliptic PDE s Based on Finite Differences , Computing, 61 (1998), pp

    M. Griebel , Adaptive Sparse Grid Multilevel Methods for Elliptic PDE s Based on Finite Differences , Computing, 61 (1998), pp. 151--179, https://doi.org/10.1007/bf02684411

    work page doi:10.1007/bf02684411 1998

  15. [15]

    Griebel and H

    M. Griebel and H. Harbrecht , On the Convergence of the Combination Technique , in Sparse grids and Applications, vol. 97 of Lecture Notes in Computational Science and Engineering, Springer, 2014, pp. 55--74, https://doi.org/10.1007/978-3-319-04537-5_3

    work page doi:10.1007/978-3-319-04537-5_3 2014

  16. [16]

    Griebel and P

    M. Griebel and P. Oswald , Tensor Product Type Subspace Splitting and Multilevel Iterative Methods for Anisotropic Problems , Adv. Comput. Math., 4 (1995), pp. 171--206, https://doi.org/10.1007/bf02123478

    work page doi:10.1007/bf02123478 1995

  17. [17]

    Griebel, M

    M. Griebel, M. Schneider, and C. Zenger , A Combination Technique for the Solution of Sparse Grid Problems , in Iterative Methods in Linear Algebra , P. de Groen and R. Beauwens, eds., IMACS, Elsevier, North Holland, 1992, pp. 263--281

    work page 1992

  18. [18]

    Griebel, M

    M. Griebel, M. Schweitzer, and L. Troska , A Dimension-Oblivious Domain Decomposition Method Based on Space-Filling Curves , SIAM Journal on Scientific Computing, 45 (2023), pp. A369--A396, https://doi.org/10.1137/21m1454481

    work page doi:10.1137/21m1454481 2023

  19. [19]

    Jette, C

    M. Jette, C. Dunlap, J. Garlick, and M. Grondona , Slurm: Simple Linux Utility for Resource Management , (2002), https://doi.org/10.1007/10968987_3, https://www.osti.gov/biblio/15002962

    work page doi:10.1007/10968987_3 2002

  20. [20]

    Kryven, S

    I. Kryven, S. Röblitz, and C. Schütte , Solution of the Chemical Master Equation by Radial Basis Functions Approximation with Interface Tracking , BMC Systems Biology, 9 (2015), https://doi.org/10.1186/s12918-015-0210-y

    work page doi:10.1186/s12918-015-0210-y 2015

  21. [21]

    R. Lago, M. Obersteiner, T. Pollinger, J. Rentrop, H.-J. Bungartz, T. Dannert, M. Griebel, F. Jenko, and D. Pfl \"u ger , EXAHD : A Massively Parallel Fault Tolerant Sparse Grid Approach for High-Dimensional Turbulent Plasma Simulations , in Software for Exascale Computing - SPPEXA 2016-2019, H.-J. Bungartz, S. Reiz, B. Uekermann, P. Neumann, and W. Nagel...

    work page doi:10.1007/978-3-030-47956-5_11 2016

  22. [22]

    parareal

    J.-L. Lions, Y. Maday, and G. Turinici , A "parareal" in Time Discretization of Pde's , Comptes Rendus de l’Académie des Sciences. Série I. Mathématique, 332 (2001)

    work page 2001

  23. [23]

    D. Lunz, G. Batt, J. Ruess, and J. F. Bonnans , Beyond the Chemical Master Equation: Stochastic Chemical Kinetics Coupled with Auxiliary Processes , PLOS Computational Biology, 17 (2021), p. e1009214, https://doi.org/10.1371/journal.pcbi.1009214

    work page doi:10.1371/journal.pcbi.1009214 2021

  24. [24]

    Neumüller and I

    M. Neumüller and I. Smears , Time-Parallel Iterative Solvers for Parabolic Evolution Equations , SIAM Journal on Scientific Computing, 41 (2019), pp. C28--C51, https://doi.org/10.1137/18m1172466

    work page doi:10.1137/18m1172466 2019

  25. [25]

    Pollinger, J

    R. Pollinger, J. Rentrop, D. Pfl\"uger, and K. Kormann , A Stable and Mass-Conserving Sparse Grid Combination Technique with Biorthogonal Hierarchical Basis Functions for Kinetic Simulations , Journal of Computational Physics, 491 (2023), p. 112338, https://doi.org/10.1016/j.jcp.2023.112338

    work page doi:10.1016/j.jcp.2023.112338 2023

  26. [26]

    Sjöberg, P

    P. Sjöberg, P. Lötstedt, and J. Elf , Fokker–Planck Approximation of the Master Equation in Molecular Biology , Computing and Visualization in Science, 12 (2007), pp. 37--50, https://doi.org/10.1007/s00791-006-0045-6

    work page doi:10.1007/s00791-006-0045-6 2007

  27. [27]

    Spencer and L

    B. Spencer and L. Bergman , On the Numerical Solution of the Fokker-Planck Equation for Nonlinear Stochastic Systems , Nonlinear Dynamics, 4 (1993), pp. 357--372, https://doi.org/10.1007/bf00120671

    work page doi:10.1007/bf00120671 1993

  28. [28]

    Wojtkiewicz, L

    S. Wojtkiewicz, L. Bergman, B. Spencer, and E. Johnson , Numerical Solution of the Four-Dimensional Nonstationary Fokker-Planck Equation , Springer Netherlands, 2001, pp. 271--287, https://doi.org/10.1007/978-94-010-0886-0_22

    work page doi:10.1007/978-94-010-0886-0_22 2001