Projected Parallel Speedup of Dynamic Domain Decomposition

What is on this page. The dynamic domain decomposition — a prototype that carves the parameter box into regions, each with its own local snapshot basis — leaves those regions independent between the level-end split/freeze barriers: an embarrassingly-parallel work set per level. That parallelism had been implemented and instrumented but never quantified. This page is the analytical layer: a projected refinement-speedup report — critical-path time, parallel efficiency, load balance — built entirely from the per-region telemetry already in each run’s machine-readable report, treating per-region eigensolves as the unit of parallel work. It also measures the composite coverage rule π⋆ (the coverage-policy work) by reporting points-added-per-region with the rule off vs on.

Projected, not measured. At the time of this analysis, no parallel execution existed. Every speedup on this page answers “if the per-region eigensolves at each level ran concurrently and synchronised at the level-end barrier, how much wall-clock would the decomposition save?” — a property of the recorded work distribution, not of any real multiprocess run.

Now realised and measured. Real execution is no longer deferred: the per-level eigensolves run on a bounded worker pool, the parallel run is proved numerically identical to the serial one, and the measured wall-clock is confronted with this projection — see parallel-execution.md. The projected per-region speedups below are reproduced exactly by the realised driver; at laptop-safe problem sizes process overhead exceeds the per-solve compute, so raw end-to-end wall-clock favours serial — an honest finding, not a regression.

1. The model

The decomposition’s ordered level step is test (skip frozen) → flag → decide → freeze → split → bisect. Regions are mutated only at the level-end freeze/split barrier; within a level each active region tests its own edges and bisects its own flagged edges with no cross-region dependency. So the natural parallel model is a per-level barrier: regions run concurrently within a level and synchronise at the level boundary for the global split/freeze decision. Speedup accrues level by level.

Work unit — per-region eigensolve count. Wall time at 6D is dominated by the eigensolve (the §4.4 study found wall time, not memory, is the binding constraint), and wall time is recorded only globally per level, never per region. The cost proxy is therefore the number of new snapshots a region solves during a level,

w_{r,\ell} \;=\; \text{eigensolves performed in region } r \text{ during level } \ell,

reconstructed by diffing the cumulative per-region snapshot counts already in the run report — no new solve-path instrumentation. Under the per-level barrier:

Quantity	Definition
serial work	S_\ell = \sum_r w_{r,\ell}
critical path	C_\ell = \max_r w_{r,\ell}
level speedup	S_\ell / C_\ell
run speedup	\sum_\ell S_\ell \big/ \sum_\ell C_\ell
parallel efficiency	run speedup / mean active-region count
load balance	C_\ell \big/ \operatorname{mean}_r w_{r,\ell} (`1.0` = perfect; higher = more skew)

A region that solves nothing in a level (e.g. a frozen leaf) is neither on the critical path nor a processor that had to run, so it does not count toward the active-region denominator or dilute load balance.

Split-birth caveat. When a region splits, its children inherit the parent’s already-solved snapshots — those are not new eigensolves. Counting them would over-state the split level’s parallel work, so the level’s genuine new solves are taken from the level’s recorded count of newly added grid nodes (splits add no solves — the cut is an existing graph node) and the remainder is distributed across the freshly born children in proportion to their snapshot count. This makes \sum_r w_{r,\ell} equal the level’s newly-added-node count exactly (a conservation property the analyzer self-checks), at the cost of making per-region work at a split-birth level fractional — a projected estimate. Every post-split level is an exact integer snapshot diff.

2. Validation order: 1D → 2D → 6D

The analysis reads refinement-time region telemetry and never calls the region-aware ROM path, so it is dimension-neutral. It is validated bottom-up.

2.1 1D — the two-regime prototype problem

The guaranteed 1D prototype (low-rank left half certifies + freezes; right half splits). The decomposition reaches 2 subdomains; projected speedup 1.20× at efficiency 0.90. The story is necessarily thin — one split, three levels — but it confirms the pipeline end-to-end and the conservation check (the per-level work sums match the newly-added-node counts at every level).

2.2 2D — the diffusion problem with the §3.3.3 coefficient

The region-aware refinement loop runs clean at d_param = 2 and the split criterion fires (the not-yet-implemented part of the region machinery is confined to the ROM evaluation side; the refinement path is dimension-neutral). The decomposition reaches 3 subdomains with max per-region POD rank 12 vs the single-store rank 15 (the decomposition’s rank-reduction payoff). Projected speedup 1.09× at efficiency 0.65.

2.3 6D — the §4.4 L-shape elasticity problem

One memory-bounded run on the laptop (the only host): a target of n_dof ≈ 4500 (realised 4522, within the reference §4.4 problem’s n_dof ≈ 6028 regime), first-k mode with 4 eigenpairs, a recompute cold tier, store capped at 2 GB, four levels. Peak RSS ≈ 101 MB, wall ≈ 1.9 s — no overflow. The speedup analysis is mode-agnostic (it reads per-region snapshot counts, not the spectrum), so the cheap first-k path is used instead of the §4.4 window mode whose cold-tier saturation is the memory wall documented elsewhere — that wall is irrelevant to this analytical layer.

A question the decomposition design left open — whether the split criterion fires at all in six parameter dimensions, or the box stalls at one subdomain — is resolved positively. The decomposition does not stall at one subdomain at 6D: it reaches 8 leaf subdomains through 7 splits, with real per-level parallelism in the deeper levels (up to 6 active regions at level 3). Projected speedup 1.42× at efficiency 0.44, mean 3.2 active regions per working level; max per-region POD rank 8 vs single-store 11.

Case	Peak subdomains	Run speedup (projected)	Efficiency	Mean active regions	Max region POD rank / single-store
1D two-regime prototype	2	1.20×	0.90	1.33	6 / 7
2D diffusion §3.3.3	3	1.09×	0.65	1.67	12 / 15
6D L-shape elasticity	8	1.42×	0.44	3.20	8 / 11

The per-level barrier shows where parallelism actually lives: speedup is 1.0 at level 0 (the seed lattice is one region) and climbs as the box splits — the 6D run reaches a level speedup of 3.7× at level 4, where 4–5 subdomains refine concurrently. Efficiency falls with dimension because the early levels (few regions) and the imperfect load balance (the split criterion is density-ranked, not balance-ranked) drag the harmonic-style aggregate down — an honest read, not a tuned one.

2.4 6D measured at campaign scale (DIR-113, faithful operator)

The projection above is confronted with measured 6D numbers at n_dof = 1846 on the DIR-112-corrected operator (tests/artifacts/dir_113/; see the §4.4 campaign page). These supersede the earlier DIR-110 numbers, which were measured on a fake-soft operator whose ~380-mode window made every solve artificially heavy:

DIR-055B harness at campaign n_dof (FirstK config, 14 workers): serial ≡ parallel exact (nodes, verdicts, eigenvalue rel-diff 0.0); measured per-region barrier-model speedup 1.82× vs the equal-cost projection’s 1.08× on the same run. But the raw end-to-end wall-clock is 0.76× — the pool loses to serial.
Raw end-to-end wall-clock on the real §4.4 Window campaign config (Stage A serial 1.6 s vs Stage B1 --regions --parallel-workers 14 2.3 s, identical 32-node trajectory): 0.70× — again overhead-bound.

The lesson inverts the pre-fix page: at the faithful window a §4.4 solve returns ~10 modes and costs milliseconds, so it sits below the DIR-055C crossover — fork/pickle/barrier overhead dominates the 14 workers and the pool buys nothing in wall-clock. The barrier-model projection still exceeds 1× (it counts solves, not overhead), but the honest wall-clock conclusion at the true §4.4 scale is that parallelism does not pay. The pre-fix 2.43× was real but was an artifact of the fake window’s heavy solves. (One faithful bonus: the pre-fix 2-of-124k band-verdict BLAS-order flip is gone — the sparse window has almost no near-threshold bands, so serial and parallel are verdict-identical.)

3. Coverage rule off vs on (π⋆ surplus)

The motivation for caring about parallelism now is the composite refinement rule π⋆ (see the coverage-policy validation), which re-admits certified-but-inaccurate cells and so is expected to add points. The question this section answers with measurement rather than assertion: are those extra points absorbed by the decomposition — distributed across independent subdomains — or do they pile onto one region?

Each case was run twice — coverage rule off (the baseline predicate, byte-identical to the shipped behaviour) and on (the surplus indicator with its self-calibrating threshold) — with regions on in both.

Case	Eigensolves off → on	Δ	Projected speedup off → on
2D diffusion	13 → 24	+11 (+85%)	1.088 → 1.105
6D L-shape	36 → 39	+3 (+8%)	1.415 → 1.484

2D. π⋆ adds 11 eigensolves, and the points-added-per-region table shows they land in the active (un-frozen) subdomains — region 3 (+9) and region 4 (+2) — while the three frozen/certified regions (0, 1, 2) take none. The extra cost is spent where the eigensurface is genuinely under-resolved, not smeared uniformly; the projected speedup is essentially unchanged. The honest nuance: the spread is not even — one subdomain (region 3) absorbs most of the re-admitted refinement.

6D. π⋆ adds only 3 eigensolves on this run (region 7 +1, region 12 +1), again in active leaves; projected speedup ticks up 1.42× → 1.48×. The coverage rule is conservative here because the §4.4 spectrum is already heavily refined by the matching verdict before coverage gets a vote.

The claim “the new rule adds more points but distributes them across independent subdomains” is therefore partly confirmed, partly qualified: the extra points do land in active subdomains rather than frozen ones (so the decomposition does absorb them), but they concentrate in the busiest leaf rather than balancing the load. This is the measured statement the program asked for.

4. Honest framing and the deferred follow-up

Every number here is projected, derived from the recorded work distribution under an idealised per-level barrier with zero communication, zero scheduling overhead, and instantaneous synchronisation. A real implementation pays interface-exchange and process-startup costs that this model omits; the interface-budget series (the recorded fraction of grid nodes on a region boundary) is the instrument the real-execution follow-up must hold down.
The speedups are modest (1.1×–1.5×) because these are small, fast runs chosen to be laptop-safe and reproducible in seconds — not because the ceiling is 1.5×. The per-level barrier shows the mechanism scaling with subdomain count (level speedup 3.7× where 4–5 regions are concurrent); the run aggregate is dragged down by the unavoidably serial early levels. A larger box that splits earlier and deeper would raise the aggregate.
No measured wall-clock speedup is claimed on this page. The follow-up that realises it is the real multiprocess executor: run the per-region refinement on separate workers, synchronise at the barrier, and measure. Only then does “projected N-way” become “measured N-way” — and that measured confrontation is parallel-execution.md.

5. Provenance

The run reports, projected-speedup tables, and coverage off-vs-on deltas were produced by an instrumented driver in the project repository, which also persists per-case artifacts.

Related. The realisation + measured-vs-projected confrontation of this projection: parallel-execution.md. The decomposition design and the freeze/split criterion are set out in the domain-decomposition design note, not yet published. The composite coverage rule and its cost-accuracy validation: coverage-policy-validation.md. The interface-scalability frontier the real-execution follow-up inherits — whether the region boundary, a (d−1)-dimensional surface of never-compressed full-fidelity snapshots, stays cheap as the parameter dimension grows — belongs to a companion catalogue of open scalability problems, not yet published.

# Projected Parallel Speedup of Dynamic Domain Decomposition > **What is on this page.** The dynamic domain decomposition — a prototype > that carves the parameter box into regions, each with its own local snapshot > basis — leaves those regions independent *between* the level-end split/freeze > barriers: an embarrassingly-parallel work set per level. That parallelism had > been implemented and instrumented but never **quantified**. This page is the > analytical layer: a *projected* refinement-speedup report — critical-path > time, parallel efficiency, load balance — built entirely from the per-region > telemetry already in each run's machine-readable report, treating per-region > eigensolves as the unit of parallel work. It also measures the composite > coverage rule π⋆ (the coverage-policy work) by reporting > points-added-per-region with the rule **off vs on**. > > **Projected, not measured.** At the time of this analysis, no parallel > execution existed. Every speedup on this page answers *"if the per-region > eigensolves at each level ran concurrently and synchronised at the level-end > barrier, how much wall-clock would the decomposition save?"* — a property of > the recorded work distribution, **not** of any real multiprocess run. > > **Now realised and measured.** Real execution is no longer deferred: > the per-level eigensolves run on a bounded worker pool, the parallel run is > proved numerically identical to the serial one, and the measured wall-clock is > confronted with this projection — see > [parallel-execution.md](parallel-execution.md). The projected per-region > speedups below are reproduced exactly by the realised driver; at laptop-safe > problem sizes process overhead exceeds the per-solve compute, so raw > end-to-end wall-clock favours serial — an honest finding, not a regression. --- ## 1. The model The decomposition's ordered level step is *test (skip frozen) → flag → decide → freeze → split → bisect*. Regions are mutated **only** at the level-end freeze/split barrier; *within* a level each active region tests its own edges and bisects its own flagged edges with no cross-region dependency. So the natural parallel model is a **per-level barrier**: regions run concurrently within a level and synchronise at the level boundary for the global split/freeze decision. Speedup accrues level by level. **Work unit — per-region eigensolve count.** Wall time at 6D is dominated by the eigensolve (the §4.4 study found wall time, not memory, is the binding constraint), and wall time is recorded only *globally* per level, never per region. The cost proxy is therefore the number of new snapshots a region solves during a level, $$ w_{r,\ell} \;=\; \text{eigensolves performed in region } r \text{ during level } \ell, $$ reconstructed by diffing the cumulative per-region snapshot counts already in the run report — **no new solve-path instrumentation**. Under the per-level barrier: | Quantity | Definition | |---|---| | serial work | $S_\ell = \sum_r w_{r,\ell}$ | | critical path | $C_\ell = \max_r w_{r,\ell}$ | | level speedup | $S_\ell / C_\ell$ | | run speedup | $\sum_\ell S_\ell \big/ \sum_\ell C_\ell$ | | parallel efficiency | run speedup / mean active-region count | | load balance | $C_\ell \big/ \operatorname{mean}_r w_{r,\ell}$ (`1.0` = perfect; higher = more skew) | A region that solves nothing in a level (e.g. a frozen leaf) is neither on the critical path nor a processor that had to run, so it does not count toward the active-region denominator or dilute load balance. **Split-birth caveat.** When a region splits, its children *inherit* the parent's already-solved snapshots — those are not new eigensolves. Counting them would over-state the split level's parallel work, so the level's genuine new solves are taken from the level's recorded count of newly added grid nodes (splits add no solves — the cut is an existing graph node) and the remainder is distributed across the freshly born children in proportion to their snapshot count. This makes $\sum_r w_{r,\ell}$ equal the level's newly-added-node count exactly (a conservation property the analyzer self-checks), at the cost of making per-region work *at a split-birth level* fractional — a projected estimate. Every *post-split* level is an exact integer snapshot diff. --- ## 2. Validation order: 1D → 2D → 6D The analysis reads refinement-time region telemetry and never calls the region-aware ROM path, so it is dimension-neutral. It is validated bottom-up. ### 2.1 1D — the two-regime prototype problem The guaranteed 1D prototype (low-rank left half certifies + freezes; right half splits). The decomposition reaches **2 subdomains**; projected speedup **1.20×** at efficiency **0.90**. The story is necessarily thin — one split, three levels — but it confirms the pipeline end-to-end and the conservation check (the per-level work sums match the newly-added-node counts at every level). ### 2.2 2D — the diffusion problem with the §3.3.3 coefficient The region-aware refinement loop runs clean at `d_param = 2` and the split criterion fires (the not-yet-implemented part of the region machinery is confined to the *ROM evaluation* side; the *refinement* path is dimension-neutral). The decomposition reaches **3 subdomains** with max per-region POD rank **12** vs the single-store rank **15** (the decomposition's rank-reduction payoff). Projected speedup **1.09×** at efficiency **0.65**. ### 2.3 6D — the §4.4 L-shape elasticity problem One memory-bounded run on the laptop (the only host): a target of `n_dof ≈ 4500` (realised 4522, within the reference §4.4 problem's `n_dof ≈ 6028` regime), first-k mode with 4 eigenpairs, a recompute cold tier, store capped at 2 GB, four levels. **Peak RSS ≈ 101 MB, wall ≈ 1.9 s** — no overflow. The speedup analysis is **mode-agnostic** (it reads per-region snapshot counts, not the spectrum), so the cheap first-k path is used instead of the §4.4 window mode whose cold-tier saturation is the memory wall documented elsewhere — that wall is irrelevant to this analytical layer. **A question the decomposition design left open — whether the split criterion fires at all in six parameter dimensions, or the box stalls at one subdomain — is resolved positively.** The decomposition does *not* stall at one subdomain at 6D: it reaches **8 leaf subdomains** through **7 splits**, with real per-level parallelism in the deeper levels (up to 6 active regions at level 3). Projected speedup **1.42×** at efficiency **0.44**, mean **3.2** active regions per working level; max per-region POD rank **8** vs single-store **11**. | Case | Peak subdomains | Run speedup (projected) | Efficiency | Mean active regions | Max region POD rank / single-store | |---|---|---|---|---|---| | 1D two-regime prototype | 2 | **1.20×** | 0.90 | 1.33 | 6 / 7 | | 2D diffusion §3.3.3 | 3 | **1.09×** | 0.65 | 1.67 | 12 / 15 | | 6D L-shape elasticity | 8 | **1.42×** | 0.44 | 3.20 | 8 / 11 | The per-level barrier shows where parallelism actually lives: speedup is `1.0` at level 0 (the seed lattice is one region) and climbs as the box splits — the 6D run reaches a **level speedup of 3.7×** at level 4, where 4–5 subdomains refine concurrently. Efficiency falls with dimension because the early levels (few regions) and the imperfect load balance (the split criterion is density-ranked, not balance-ranked) drag the harmonic-style aggregate down — an honest read, not a tuned one. ### 2.4 6D measured at campaign scale (DIR-113, faithful operator) The projection above is confronted with **measured** 6D numbers at `n_dof = 1846` on the DIR-112-corrected operator (`tests/artifacts/dir_113/`; see the [§4.4 campaign page](examples/elasticity-4-4-campaign.qmd)). These supersede the earlier DIR-110 numbers, which were measured on a fake-soft operator whose ~380-mode window made every solve artificially heavy: - **DIR-055B harness at campaign n_dof** (FirstK config, 14 workers): serial ≡ parallel **exact** (nodes, verdicts, eigenvalue rel-diff 0.0); measured per-region barrier-model speedup **1.82×** vs the equal-cost projection's 1.08× on the same run. But the **raw end-to-end wall-clock is 0.76×** — the pool loses to serial. - **Raw end-to-end wall-clock on the real §4.4 Window campaign config** (Stage A serial 1.6 s vs Stage B1 `--regions --parallel-workers 14` 2.3 s, identical 32-node trajectory): **0.70×** — again overhead-bound. The lesson inverts the pre-fix page: at the **faithful** window a §4.4 solve returns ~10 modes and costs milliseconds, so it sits **below** the DIR-055C crossover — fork/pickle/barrier overhead dominates the 14 workers and the pool buys nothing in wall-clock. The barrier-model *projection* still exceeds 1× (it counts solves, not overhead), but the honest wall-clock conclusion at the true §4.4 scale is that parallelism does not pay. The pre-fix 2.43× was real but was an artifact of the fake window's heavy solves. (One faithful bonus: the pre-fix 2-of-124k band-verdict BLAS-order flip is gone — the sparse window has almost no near-threshold bands, so serial and parallel are verdict-identical.) --- ## 3. Coverage rule off vs on (π⋆ surplus) The motivation for caring about parallelism now is the composite refinement rule π⋆ (see [the coverage-policy validation](coverage-policy-validation.md)), which re-admits certified-but-inaccurate cells and so is *expected to add points*. The question this section answers with measurement rather than assertion: **are those extra points absorbed by the decomposition — distributed across independent subdomains — or do they pile onto one region?** Each case was run twice — coverage rule **off** (the baseline predicate, byte-identical to the shipped behaviour) and **on** (the surplus indicator with its self-calibrating threshold) — with regions on in both. | Case | Eigensolves off → on | Δ | Projected speedup off → on | |---|---|---|---| | 2D diffusion | 13 → 24 | **+11 (+85%)** | 1.088 → 1.105 | | 6D L-shape | 36 → 39 | **+3 (+8%)** | 1.415 → 1.484 | **2D.** π⋆ adds 11 eigensolves, and the points-added-per-region table shows they land in the **active (un-frozen) subdomains** — region 3 (+9) and region 4 (+2) — while the three frozen/certified regions (0, 1, 2) take none. The extra cost is spent where the eigensurface is genuinely under-resolved, not smeared uniformly; the projected speedup is essentially unchanged. The honest nuance: the spread is *not* even — one subdomain (region 3) absorbs most of the re-admitted refinement. **6D.** π⋆ adds only 3 eigensolves on this run (region 7 +1, region 12 +1), again in active leaves; projected speedup ticks up `1.42× → 1.48×`. The coverage rule is conservative here because the §4.4 spectrum is already heavily refined by the matching verdict before coverage gets a vote. The claim *"the new rule adds more points but distributes them across independent subdomains"* is therefore **partly confirmed, partly qualified**: the extra points do land in active subdomains rather than frozen ones (so the decomposition does absorb them), but they concentrate in the busiest leaf rather than balancing the load. This is the measured statement the program asked for. --- ## 4. Honest framing and the deferred follow-up - Every number here is **projected**, derived from the recorded work distribution under an idealised per-level barrier with zero communication, zero scheduling overhead, and instantaneous synchronisation. A real implementation pays interface-exchange and process-startup costs that this model omits; the interface-budget series (the recorded fraction of grid nodes on a region boundary) is the instrument the real-execution follow-up must hold down. - The speedups are **modest** (1.1×–1.5×) because these are small, fast runs chosen to be laptop-safe and reproducible in seconds — not because the ceiling is 1.5×. The per-level barrier shows the mechanism scaling with subdomain count (level speedup 3.7× where 4–5 regions are concurrent); the run aggregate is dragged down by the unavoidably serial early levels. A larger box that splits earlier and deeper would raise the aggregate. - **No measured wall-clock speedup is claimed on this page.** The follow-up that realises it is the real multiprocess executor: run the per-region refinement on separate workers, synchronise at the barrier, and measure. Only then does "projected N-way" become "measured N-way" — and that measured confrontation is [parallel-execution.md](parallel-execution.md). --- ## 5. Provenance The run reports, projected-speedup tables, and coverage off-vs-on deltas were produced by an instrumented driver in the project repository, which also persists per-case artifacts. --- **Related.** The realisation + measured-vs-projected confrontation of this projection: [parallel-execution.md](parallel-execution.md). The decomposition design and the freeze/split criterion are set out in the domain-decomposition design note, not yet published. The composite coverage rule and its cost-accuracy validation: [coverage-policy-validation.md](coverage-policy-validation.md). The interface-scalability frontier the real-execution follow-up inherits — whether the region boundary, a `(d−1)`-dimensional surface of never-compressed full-fidelity snapshots, stays cheap as the parameter dimension grows — belongs to a companion catalogue of open scalability problems, not yet published.