pith. sign in

arxiv: 2110.11211 · v3 · submitted 2021-10-21 · 🧮 math.NA · cs.NA

A dimension-oblivious domain decomposition method based on space-filling curves

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

Pith reviewed 2026-05-24 13:21 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords domain decompositionspace-filling curvestwo-level preconditionerdimension-oblivious solverelliptic partial differential equationsparallel scalabilitysparse grid combination
0
0 comments X

The pith

Space-filling curves create subdomains and overlaps for a two-level domain decomposition solver that stays optimal in any dimension with any processor count.

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

The paper develops an algebraic two-level domain decomposition solver for elliptic partial differential equations that partitions the problem using space-filling curves. This partitioning works directly on the assembled matrix from any discretization and produces subdomains with large overlaps. A sympathetic reader would care because the method remains independent of the underlying dimension and supports arbitrary numbers of processors while keeping optimal convergence rates. The construction supplies the data redundancy needed for fault tolerance and serves as a building block for extreme-scale sparse grid computations.

Core claim

The paper claims that space-filling curve partitioning generates subdomains and overlaps such that the resulting two-level domain decomposition preconditioner retains optimal convergence rates independent of the dimension of the partial differential equation and for arbitrary processor counts. The approach operates algebraically on assembled matrix equations and therefore applies to any discretization. This dimension-oblivious property is presented as the requirement for attaining extreme scalability in sparse grid combination techniques and for constructing fault-tolerant solvers through the built-in data redundancy of large overlaps.

What carries the argument

Space-filling curve partitioning that directly produces subdomains and large overlaps from the assembled matrix to support the two-level domain decomposition preconditioner.

If this is right

  • Arbitrary processor counts become usable without regard to the dimension of the underlying partial differential equation.
  • Optimal convergence rates are retained across all dimensions when the solver is applied to the assembled matrix equations.
  • The same partitioning supplies the data redundancy required for fault-tolerant operation on high-dimensional problems.
  • The construction directly enables a sparse grid combination technique that scales to exascale processor counts.

Where Pith is reading between the lines

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

  • The algebraic nature of the partitioning may allow the same subdomains to be reused across different right-hand sides or time steps without recomputation.
  • Large overlaps constructed this way could reduce communication volume in distributed-memory settings beyond what standard graph partitioners achieve.
  • Because the method never refers to the mesh geometry, it could be applied unchanged to problems whose spatial dimension changes during the computation.

Load-bearing premise

The overlaps and subdomains created by the space-filling curve must preserve the theoretical properties that let the two-level preconditioner keep optimal convergence rates no matter the dimension.

What would settle it

A set of numerical runs in dimension four or higher in which the iteration count of the solver grows with the number of processors or with increasing dimension.

Figures

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

Figure 1
Figure 1. Figure 1: The combination method, two-dimensional case with [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Decomposition of an isotropic grid with l = (3, 3) by the Hilbert curve approach (left) and corresponding disjoint subdomains (middle). Construction of two overlapping subdomains (square/blue and triangle/green) by enlargement using the Hilbert space-filling curve (right) [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Decomposition of an anisotropic grid with [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Weak scaling: Number of iterations versus number of subdomains for the linear/Richardson [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Weak scaling: Number of iterations versus number of subdomains for the unweighted [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Weak scaling: Number of iterations versus number of subdomains for the unweighted [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Weak scaling: Number of iterations versus number of subdomains for the [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Weak scaling: Number of iterations versus number of subdomains for the [PITH_FULL_IMAGE:figures/full_fig_p021_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Strong scaling: Number of iterations versus number of subdomains for the [PITH_FULL_IMAGE:figures/full_fig_p023_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Approximate number of degrees of freedom for the combination technique and full grid [PITH_FULL_IMAGE:figures/full_fig_p024_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Absolute error of the solution for the full grid and combination technique (top) and [PITH_FULL_IMAGE:figures/full_fig_p026_11.png] view at source ↗
read the original abstract

In this paper we present an algebraic dimension-oblivious two-level domain decomposition solver for discretizations of elliptic partial differential equations. The proposed parallel solver is based on a space-filling curve partitioning approach that is applicable to any discretization, i.e. it directly operates on the assembled matrix equations. Moreover, it allows for the effective use of arbitrary processor numbers independent of the dimension of the underlying partial differential equation while maintaining optimal convergence behavior. This is the core property required to attain a sparse grid based combination method with extreme scalability which can utilize exascale parallel systems efficiently. Moreover, this approach provides a basis for the development of a fault-tolerant solver for the numerical treatment of high-dimensional problems. To achieve the required data redundancy we are therefore concerned with large overlaps of our domain decomposition which we construct via space-filling curves. In this paper, we propose our space-filling curve based domain decomposition solver and present its convergence properties and scaling behavior. The results of numerical experiments clearly show that our approach provides optimal convergence and scaling behavior in arbitrary dimension utilizing arbitrary processor numbers.

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 manuscript proposes an algebraic two-level domain decomposition preconditioner for elliptic PDE discretizations. It uses space-filling curve (SFC) partitioning to generate subdomains with large overlaps directly from the assembled matrix, claims to be dimension-oblivious (allowing arbitrary processor counts independent of PDE dimension d), and asserts that optimal convergence rates are retained. The approach is motivated by enabling extreme scalability for sparse-grid combination techniques and fault tolerance via redundant overlaps; numerical experiments are stated to confirm optimal convergence and scaling in arbitrary dimensions.

Significance. If the geometric properties of the SFC subdomains are shown to preserve the standard two-level additive Schwarz assumptions, the method would offer a practical algebraic route to dimension-independent parallel solvers for high-dimensional problems, directly supporting exascale sparse-grid computations and fault-tolerant schemes.

major comments (2)
  1. [Sections 3–4 (method construction and convergence properties)] The central claim that SFC partitioning produces subdomains and overlaps whose multiplicity and partition-of-unity constants remain bounded independently of dimension (required for the two-level DD condition-number bound to be independent of both h and d) lacks an analytic verification or lemma. No estimate of overlap width or multiplicity as a function of d is supplied, so the optimality assertion for d ≫ 3 rests entirely on the numerical section.
  2. [Numerical experiments section (and abstract)] The abstract states that numerical experiments demonstrate optimal convergence and scaling, yet provides no information on the test problems, dimensions d tested, processor counts, iteration counts versus h and d, or comparison baselines. Without these details the load-bearing claim of dimension-oblivious optimality cannot be assessed from the given evidence.
minor comments (2)
  1. Clarify the precise definition of the large overlap constructed via SFC (e.g., how the overlap width is chosen relative to the SFC traversal) at its first appearance.
  2. Add a short table summarizing the dimensions, mesh sizes, and processor counts used in the reported experiments.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the two major comments point by point below. Where the comments identify gaps in analysis or presentation, we agree to make revisions.

read point-by-point responses

  1. Referee: [Sections 3–4 (method construction and convergence properties)] The central claim that SFC partitioning produces subdomains and overlaps whose multiplicity and partition-of-unity constants remain bounded independently of dimension (required for the two-level DD condition-number bound to be independent of both h and d) lacks an analytic verification or lemma. No estimate of overlap width or multiplicity as a function of d is supplied, so the optimality assertion for d ≫ 3 rests entirely on the numerical section.

    Authors: We agree that Sections 3–4 contain no analytic lemma or explicit estimate proving that the overlap multiplicity and partition-of-unity constants remain bounded independently of dimension d. The manuscript invokes the standard two-level additive Schwarz theory and asserts optimality on that basis, but the dimension-independent boundedness is supported only by the numerical results. In revision we will add a short remark in Section 4 discussing the locality properties of space-filling curves that heuristically suggest dimension-independent overlap width; we will also expand the numerical section with additional high-d data. A complete rigorous proof of the constants’ independence of d lies beyond the present scope and would require separate analysis. revision: partial

  2. Referee: [Numerical experiments section (and abstract)] The abstract states that numerical experiments demonstrate optimal convergence and scaling, yet provides no information on the test problems, dimensions d tested, processor counts, iteration counts versus h and d, or comparison baselines. Without these details the load-bearing claim of dimension-oblivious optimality cannot be assessed from the given evidence.

    Authors: We acknowledge that the abstract is too terse and omits concrete information on the test problems, dimensions, processor counts, and iteration counts. Although the numerical experiments section describes the Poisson problem, the dimensions examined, and the observed scaling, the abstract does not. We will revise the abstract to include a concise summary of the experimental setup (e.g., Poisson equation, dimensions d = 2 … 6, processor counts independent of d, and bounded iteration counts) and will ensure the numerical section explicitly tabulates iteration counts versus h and d together with baseline comparisons. revision: yes

Circularity Check

0 steps flagged

No significant circularity; claims rest on numerical verification of standard DD theory

full rationale

The paper's derivation chain presents an algebraic two-level DD solver constructed via SFC partitioning that operates directly on assembled matrices. Optimal convergence independent of dimension is asserted as a property verified by numerical experiments rather than derived from fitted parameters, self-definitions, or load-bearing self-citations. The text references standard DD assumptions and SFC properties without reducing the central claim (dimension-oblivious optimality) to an input by construction. No equations or steps exhibit the enumerated circular patterns; the approach is positioned as building on external theory with experimental confirmation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract relies on standard assumptions for elliptic PDEs and domain decomposition theory plus properties of space-filling curves; no free parameters, new entities, or ad-hoc axioms are introduced at the abstract level.

axioms (2)
  • domain assumption The underlying problem is a discretization of an elliptic partial differential equation
    Stated directly in the abstract as the target class of problems.
  • domain assumption Space-filling curve partitions can be constructed to produce sufficient overlaps for both convergence and data redundancy
    Invoked for the fault-tolerant solver application.

pith-pipeline@v0.9.0 · 5721 in / 1245 out tokens · 22159 ms · 2026-05-24T13:21:40.230855+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking contradicts
    ?
    contradicts

    CONTRADICTS: the theorem conflicts with this paper passage, or marks a claim that would need revision before publication.

    it allows for the effective use of arbitrary processor numbers independent of the dimension of the underlying partial differential equation while maintaining optimal convergence behavior... in arbitrary dimension utilizing arbitrary processor numbers.

  • IndisputableMonolith/Foundation/AlexanderDuality.lean SphereAdmitsCircleLinking D ↔ D = 3 contradicts
    ?
    contradicts

    CONTRADICTS: the theorem conflicts with this paper passage, or marks a claim that would need revision before publication.

    our domain decomposition approach must be dimension-oblivous and directly applicable to anisotropic meshes... we utilize a space-filling curve method... independent of the dimension d.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    M. Ali, P. Strazdins, B. Harding, and M. Hegland. Complex scientific applications made fault-tolerant with the sparse grid combination technique. The International Journal of High Performance Computing Applications 30:335--359, 2016

    work page 2016

  2. [2]

    M. Bader. Space-Filling Curves: An Introduction with Applications in Scientific Computing, Texts in Computations Science and Engineering, Volume 9, Springer-Verlag, 2013

    work page 2013

  3. [3]

    Bank and M

    R. Bank and M. Holst. A new paradigm for parallel adaptive meshing algorithms. SIAM Review 45(2):291--323, 2003

    work page 2003

  4. [4]

    Bouwmeester, A

    H. Bouwmeester, A. Dougherty, and A. Knyazev. Nonsymmetric preconditioning for conjugate gradient and steepest descent methods. Procedia Computer Science 51:276--285, 2015

    work page 2015

  5. [5]

    S. Brenner. Lower bounds for two-level additive Schwarz preconditioners with small overlap. SIAM J. Sci. Comput. 21(5):1657--1669, 2000

    work page 2000

  6. [6]

    Bungartz and M

    H.-J. Bungartz and M. Griebel. Sparse grids. Acta Numerica 13:147--269, 2004

    work page 2004

  7. [7]

    A. Butz. Alternative algorithm for Hilbert's space-filling curve, IEEE Transactions on Computers 20(4):424-426, 1971

    work page 1971

  8. [8]

    Chernoch

    P. Chernoch. //github.com/paulchernoch/HilbertTransformation, retrieved 06.10.2020

    work page 2020

  9. [9]

    Dryja and O

    M. Dryja and O. Widlund. An additive variant of the Schwarz alternating method for the case of many subregions. Ultracomputer Note 131, Department of Computer Science, Courant Institute, New York, 1987

    work page 1987

  10. [10]

    Dryja and O

    M. Dryja and O. Widlund. Domain decomposition algorithms with small overlap. SIAM J. Sci. Comput. 15(3):604--620, 1994

    work page 1994

  11. [11]

    Dolean, P

    V. Dolean, P. Jolivet, and F. Nataf. An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation, SIAM, 2015

    work page 2015

  12. [12]

    Griebel, M

    M. Griebel, M. Schneider, and C. Zenger. A combination technique for the solution of sparse grid problems. In: P. de Groen and R. Beauwens, editors, Iterative Methods in Linear Algebra , IMACS, Elsevier, North Holland, 263--281, 1992

    work page 1992

  13. [13]

    Griebel and H

    M. Griebel and H. Harbrecht. On the convergence of the combination technique. In: Sparse grids and Applications . Volume 97 of Lecture Notes in Computational Science and Engineering , Springer, 55--74, 2014

    work page 2014

  14. [14]

    Griebel, S

    M. Griebel, S. Knapek, and G. Zumbusch. Numerical Simulation in Molecular Dynamics. Springer, Berlin, Heidelberg, 2007

    work page 2007

  15. [15]

    Griebel and P

    M. Griebel and P. Oswald. On the abstract theory of additive and multiplicative S chwarz algorithms. Numer. Math. 70:163--180, 1995

    work page 1995

  16. [16]

    Griebel and P

    M. Griebel and P. Oswald. Stochastic subspace correction methods and fault tolerance. Math. Comp. 89(321):279--312, 2020

    work page 2020

  17. [17]

    Griebel and M

    M. Griebel and M. Schweitzer and L. Troska. A fault-tolerant domain decomposition method based on space-filling curves. arXiv:2103.03315, 2021

    work page arXiv 2021

  18. [18]

    Griebel and G

    M. Griebel and G. Zumbusch. Parallel adaptive subspace correction schemes with applications to elasticity. Computer Methods in Applied Mechanics and Engineering 184:303--332, 2000

    work page 2000

  19. [19]

    Griebel and G

    M. Griebel and G. Zumbusch. Hash based adaptive parallel multilevel methods with space-filling curves. In: H. Rollnik and D. Wolf, editors, NIC Symposium 2001 , Volume 9 of NIC Series , Forschungszentrum J\"ulich, Germany, 479--492, 2002

    work page 2001

  20. [20]

    Harding, M

    B. Harding, M. Hegland, J. Larson, and J. Southern. Fault tolerant computation with the sparse grid combination technique. SIAM J. Sci. Comput. 37(03):C331--C353, 2014

    work page 2014

  21. [21]

    R. Lago, M. Obersteiner, T. Pollinger, J. Rentrop, H.-J. Bungartz, T. Dannert, M. Griebel, F. Jenko, and D. Pfl\"uger. EXAHD -- A massively parallel fault-tolerant sparse grid approach for high-dimensional turbulent plasma simulations. In: H.-J. Bungartz, S. Reiz, B. Uekermann, P. Neumann, and W. Nagel, editors, Software for Exascale Computing - SPPEXA 20...

    work page 2016

  22. [22]

    J. Mandel. Balancing domain decomposition. Comm. Numer. Methods Engrg. 9:233-241, 1993

    work page 1993

  23. [23]

    D. Moore. Fast Hilbert curve generation, sorting, and range queries. http://www.tiac.net/\- sw/2008/10/Hilbert/moore/, retrieved 01.04.2017

    work page 2008

  24. [24]

    Nicolaides

    R. Nicolaides. Deflation of conjugate gradients with applications to boundary value problems. SIAM J. Numer. Anal. 24:355-365, 1987

    work page 1987

  25. [25]

    Pfl\"uger, H.-J

    D. Pfl\"uger, H.-J. Bungartz, M. Griebel, F. Jenko, T. Dannert, M. Heene, C. Kowitz, A. Hinojosa, and P. Zaspel. EXAHD : An exa-scalable two-level sparse grid approach for higher-dimensional problems in plasma physics and beyond. In: L. Lopes et al, editors, Euro-Par 2014: Parallel Processing Workshops , Volume 8806 of Lecture Notes in Computer Science , ...

    work page 2014

  26. [26]

    Quarteroni and A

    A. Quarteroni and A. Valli. Domain Decomposition Methods for Partial Differential Equations, Oxford Science Publications, 1999

    work page 1999

  27. [27]

    Cai and Y

    X.-C. Cai and Y. Saad. Overlapping Domain Decomposition Algorithms for General Sparse Matrices. Numerical Linear Algebra with Applications 3: 221--237, 1996

    work page 1996

  28. [28]

    Uber einen Grenz\

    H. Schwarz. \"Uber einen Grenz\"ubergang durch alternierendes Verfahren. Vierteljahrsschrift der Naturforschenden Gesellschaft in Z\"urich 15:272--286, 1870

    work page

  29. [29]

    A. Shavit. //github.com/adishavit/hilbert/blob/master/hilbert.c\#L529, retrieved 06.10.2020

    work page 2020

  30. [30]

    Skilling

    J. Skilling. Programming the Hilbert curve, AIP Conference Proceedings 707:381-387, 2004

    work page 2004

  31. [31]

    Smith, P

    B. Smith, P. Bjorstad, and W. Gropp. Domain Decomposition, Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 1996

    work page 1996

  32. [32]

    Toselli and O

    A. Toselli and O. Widlund. Domain Decomposition Methods - Algorithms and Theory. Springer Series in Computational Mathematics , Volume 34, Springer, Berlin, Heidelberg, 2004

    work page 2004

  33. [33]

    Vuik and R

    C. Vuik and R. Nabben. A comparison of deflation and the balancing preconditioner. SIAM J. Sci. Comput. 27(5):1742--1759, 2006

    work page 2006

  34. [34]

    C. Zenger. Sparse grids. In: Parallel algorithms for partial differential equations , Proceedings of the 6th GAMM-Seminar, Kiel/Germany, 1990, Volume 31 of Notes Numer. Fluid Mech. , Vieweg, Braunschweig, 241--251, 1991

    work page 1990

  35. [35]

    Zumbusch

    G. Zumbusch. Parallel Multilevel Methods. Adaptive Mesh Refinement and Loadbalancing, Teubner, 2003

    work page 2003

  36. [36]

    Cai and Y

    X.-C. Cai and Y. Saad. Overlapping domain decomposition algorithms for general sparse matrices. Numerical Linear Algebra with Applications 3: 221--237, 1996

    work page 1996