Analysis and Detection of Stagnation in Floating-Point Summation

1 Introduction

• Partial stagnation occurs in M additions when 0 < ui ≤ t, where t limits the most significant bits used in each qualifying addition.The qualifying additions may appear anywhere in the n − 1 operations, rather than necessarily being consecutive.Source: §1 · pp. 2–3
• Total stagnation occurs when ui = 0 and the rounded sum equals either addend; it represents complete loss of information from those addends.The paper focuses on total stagnation as the most severe type.Source: §1 · pp. 2–3
• Near-total stagnation occurs when ui = 0 but the rounded sum is neither addend, so the larger addend changes only through rounding.The paper describes it as an indication that the changes contain very little useful information.Source: §1 · p. 2
• The paper calls a single operand rounded off in an addition absorption; total stagnation consists of M absorptions.For |x| > |y| under round-to-nearest, total absorption occurs when |y| < |ulp(x)|/2.Source: §1 · p. 3
• The average level of stagnation summarizes bits used across additions and can identify code regions where extra precision, another summation algorithm, or stochastic rounding may be considered.The measure can provide information without a reference solution.Source: §1 · p. 3

2 Previous work

• Dynamic cancellation tools report cancellation severity at runtime, while stagnation tracks information erased by absorption across additions.FPDebug uses high-precision shadow values [7], and Lam et al. measure cancellation from operand and result exponents.Source: §2 · p. 4
• Static analysis by Lopes et al. reports possible cancellation and absorption using propagated input ranges, unlike the paper’s stagnation definition over a series of additions.The range-based approach does not require running the program, but may report absorption pessimistically when range extremes do not occur at runtime.Source: §2 · p. 4
• For the Taylor-series example, descending ordering reduces stagnation, but the paper cautions that stagnation is inappropriate for an example whose error culprit is catastrophic cancellation.In that case, ascending ordering reports no stagnation despite having the greatest relative error.Source: §2 · p. 5
• Sakr et al. [11] define partial and total swamping for individual dot-product operations, whereas the paper defines stagnation over multiple additions.Their analysis also models product-term variance and uses the variance retention ratio to assess swamping severity.Source: §2 · p. 5
• Prior stochastic-rounding studies report reduced or prevented stagnation in selected ODE/PDE settings, while exact stochastic rounding is described as immune to stagnation for nonzero additions.The cited ODE examples report stagnation under round-to-nearest below a timestep threshold and prevention with stochastic rounding.Source: §2 · pp. 5–6

3.1 Defining stagnation

• Stagnation of length M counts absorptions of the corresponding total, near-total, or partial type anywhere in a recursive summation.The authors report no evidence that restricting the definition to consecutive absorptions is superior.Source: §3.1 · p. 6

3.2 Reducing or eliminating stagnation

• Stochastic rounding, compensated summation, and higher precision are proposed as ways to reduce stagnation or its effects.Compensated summation computes rounding errors for use in later additions, while higher precision can increase average u.Source: §3.2 · pp. 6–7
• Reordering can reduce stagnation when data is available, with the suggested aim of adding values of similar exponents.For positive numbers, summing in decreasing rather than increasing order is noted as reducing the error bound, though not necessarily the actual error.Source: §3.2 · p. 7

3.3.1 Stagnation and ordering of the addends

• For nonnegative addends, total stagnation of length 1 to n − 1 can occur when the sequence after the first addend is decreasing or constant, and it can also occur when that sequence is increasing.The harmonic series illustrates decreasing addends eventually absorbed by a growing finite-precision sum; increasing sequences can instead absorb the accumulator.Source: §3.3.1 · pp. 7–8
• A decreasing positive sequence cannot totally stagnate if each x_k exceeds x_1/2 and 2^(p−1)x_1 is below Nmax.Here p is the format precision and Nmax the greatest normalized floating-point number.Source: §3.3.1 · p. 8
• The bound based on x_1 is overconservative and limits the number of terms; falling below it means the theorem no longer guarantees prevention, not that stagnation must occur.The authors characterize the bound as a sufficient condition for preventing total stagnation.Source: §3.3.1 · pp. 8–9
• For a decreasing sequence, total stagnation cannot occur when each subsequent x_(k+1) exceeds k ulp(x_1)/2.This condition depends on both the initial value and the number of terms.Source: §3.3.1 · p. 9

3.4 Implementing stagnation detection in MATLAB

• The MATLAB prototype overloads plus to detect total or near-total absorption during single-precision additions.Global variables track the detection data as each addition occurs.Source: §3.4 · p. 9
• The accumulated u records smaller-addend significand bits that contribute to additions, while total absorptions count cases where all those bits are shifted off.The stagnation level is u/additions; total absorptions record stagnation length.Source: §3.4 · p. 9
• After recursive summation, users can inspect the recorded values to identify how stagnation affected the sum.Source: §3.4 · p. 9

3.5.1 Design of the Julia tool

• StagnationDetection.jl provides Float64SD, Float32SD, and Float16SD types that automatically detect stagnation during arithmetic.The types share the FloatSD abstract type, and the tool can measure total, near-total, or partial stagnation.Source: §3.5.1 · p. 10
• For each addition, the tool tracks preserved bits and absorption direction; report functions summarize counts and stagnation data.reportall() can summarize local-scope values and arrays, but the authors could not make it work within a function.Source: §3.5.1 · pp. 10–11

3.5.2 Harmonic series with stagnation detection

• The harmonic-series example detects total stagnation in 1,902,848 of 4,000,000 additions with Float32SD.The report gives an average of 0.524715 preserved bits per addition.Source: §3.5.2 · p. 12

3.5.3 Matrix multiplication with stagnation detection

• For the 5×5 product matrix C, reportall() gives a mean stagnation range of 0.011%.The example uses Float32SD inputs; reportall() uses diff absorptions to summarize C's range.Source: §3.5.3 · pp. 13–14

4.1 MATLAB stagnation detection

• P has the lowest average u, H the second lowest, and R2 uses approximately all 23 bits because its accumulator resets at 1.IH and R1 average around five bits per addition.Source: Table 1 · p. 14, §4.1 · p. 15
• With t = 2, H is classified as partially stagnating after i = 106 steps, while P stagnates very early.IH and R1 show decreasing average u, whereas R2's average remains stable.Source: Table 1 · p. 14, §4.1 · p. 15
• For H and P, stochastic rounding recovers errors observed with round-to-nearest, and both have over 50% of additions in total or near-total stagnation.For IH and R2, which have no stagnation, stochastic rounding reduces error; for R1, it does not appear to reduce error.Source: Table 2 · p. 14, §4.1 · p. 15
• Decreasing addends contribute to stagnation in H and P; the ascending-order IH sum does not meet the theorem's magnitude-difference condition.The paper's theory does not concern the randomly sorted R1 and R2 sums.Source: §4.1 · p. 15

4.2.1 Verification of conditions for stagnation

• Tests with StagnationDetection.jl found no total stagnation for the tested positive sequence spanning the greatest possible value range in single and half precision.The sequence starts with x > 0 and descends by consecutive floating-point values to nextfloat(x/2), as specified in the theorem verification setup.Source: §4.2.1 · pp. 15–16

4.2.2 Summation of random numbers

• Ascending order consistently has the least stagnation in binary32 and binary16 vector sums, while descending-order stagnation eventually surpasses random ordering.The transition occurs earlier in descending order than ascending order; after it begins, descending-order stagnation grows faster than in the other orderings.Source: Figure 1 · p. 16, §4.2.2 · p. 17
• Near 1, relative error plateaus after n ≈6.4 × 107 in single precision and n ≈104 in half precision, mostly where stagnation exceeds 50%.Ascending order has lower stagnation, but the absorbed values are larger, causing the greatest possible error per absorption.Source: Figure 1 · p. 16, §4.2.2 · p. 17
• Below n ≈6.4 × 107 in single precision, stagnation’s usefulness as an error indicator is unclear, and other error sources may matter.For this range, random ordering has the best or tied-best relative error despite being the only ordering reporting some stagnation.Source: §4.2.2 · p. 17

4.2.3 Inner products

• For dot products, overall stagnation and relative-error trends resemble vector sums, but descending-order stagnation is greater in both precisions.Single-precision random-order relative error follows a visible linear progression.Source: Figure 2 · p. 18, §4.2.3 · pp. 18–19

4.2.4 Matrix-matrix multiplication

• For 5×n by n×5 matrix products, stagnation grows less than linearly, and its rate depends on summation length relative to precision.The results cover single and half precision; each product computes 5×5 dot products of length n.Source: §4.2.4 · p. 19, Table 3 · p. 19, Table 4 · p. 19

4.3.1 Implementation choice and approach

• The experiment used ShallowWaters.jl for a 200-day shallow-fluid simulation, measuring Float32SD and Float16SD stagnation and comparing layer-height η RMSE with an all-Float64 computation.Other prognostic variables were monitored, but significant stagnation was not observed in them in these tests.Source: §4.3.1 · p. 20

4.3.2 Configuration of the shallow water model

• For the Float16 tests, stagnation detection covered all prognostic variables on the default 100 × 50 grid, with scaling disabled; the measured η had no direct scaling.The authors report no observed difference in error depending on whether scaling was active.Source: §4.3.2 · pp. 20–21

4.3.3 Stagnation and error in the time integration

• The default fourth-order Runge-Kutta scheme records four detected additions per integration step; timestep size was varied through the CFL number while grid resolution remained fixed.The Float64 results were checked for consistency across timestep values and converged as dt decreased.Source: §4.3.3 · p. 21, Figure 3 · p. 21
• At dt=176, Float16 stagnation affected over 70% of additions in some domain regions; at dt=11, each solution entry involved more than 6 × 10^6 additions.Figure 4 depicts layer height η at dt=176 for nx=100 and nx=200; the default timesteps are 5656 and 2828, respectively.Source: Figure 4 · p. 22, §4.3.3 · pp. 22–23
• For Float16, RMSE and stagnation generally grew as dt decreased, but below dt=100 stagnation fell without accuracy improving; compensated summation reduced RMSE and prevented solution divergence.The RMSE plateaued for dt ≤353; Figure 5 compares ordinary and compensated summation, and Figure 6 shows the Float16 solution diverging from the Float64 reference as dt decreases.Source: Figure 5 · p. 22, §4.3.3 · pp. 23–24, Figure 6 · p. 23

4.4 Benchmarking performance of stagnation detection

• The benchmarks replaced Julia's sum, dot, and matrix-multiplication functions with custom implementations; without detection, these were already much slower than Julia's counterparts.The implementations were designed to retain the same algorithms with and without stagnation detection, and had the expected time complexity.Source: §4.4 · p. 24, §4.4.1 · p. 24

4.4.1 Sums and vector inner products

• Benchmark sample counts decreased as tests became more expensive, so stagnation-detection measurements may be noisy.Random floating-point inputs were generated by reinterpreting random unsigned integers.Source: §4.4.1 · pp. 24–25
• Stagnation detection produced roughly similar performance for vector sums and dot products, with dot products slowed by approximately 9×; matrix multiplication incurred a greater slowdown.The dot product uses three-argument muladd, whereas the summation algorithm uses two-argument addition.Source: §4.4.1 · p. 25, Table 6 · p. 25, Table 7 · p. 25

4.4.2 Comparison to MPFR

• Stagnation-detected double-precision vector summation was approximately 10× faster than p=128 MPFR summation, while still adding significant overhead versus regular floating-point arithmetic.Figure 7 compares the same unoptimized recursive summation algorithm across regular double precision, stagnation detection, and MPFR.Source: §4.4.2 · p. 25, Figure 7 · p. 26

4.4.3 Storage cost

• FloatSD types have six fields and yield an expected 6× size increase for scalars, but the increase grows for vectors and matrices.The authors note that FloatSD types occupy the same amount of space despite differences in their value-field types.Source: §4.4.3 · p. 26, Table 8 · p. 26

4.5.1 Consecutive sequences of absorptions

• The alternative measure tracks lengths of consecutive absorption sequences, but is harder to implement and more computationally expensive without providing more information.Source: §4.5.1 · p. 27
• “Longest stagnation” counts consecutive absorbed entries of the same sign; a change in rounding direction resets the sequence, unlike the formal absorption count.Source: §4.5.1 · p. 27
• For the harmonic series, all absorptions occur consecutively at the end, so both measurement approaches give the same result.Source: §4.5.1 · p. 27, Table 9 · p. 27
• At n = 10^6, random summation has more than 10^5 absorptions but a longest sequence of only 3, so sequence length misses many absorptions.The total number of absorptions grows faster than the other reported metrics.Source: Table 10 · p. 27, §4.5.1 · p. 28
• For the e−2π series, ascending order reports no stagnation despite the greatest relative error, because catastrophic cancellation—not stagnation—is the error culprit.Default and descending order have the same stagnation data despite significantly different relative errors.Source: §4.5.1 · p. 28, Table 11 · p. 28

4.5.2 Combination of addends

• The tool records stagnation information in a single accumulator; for sums of sums, contributions aggregate, leaving no comprehensive history.The authors note that combining information from arbitrarily many operands could also make it cumbersome or meaningless to users.Source: §4.5.2 · p. 28

• In Julia experiments, stagnation relates to relative error for recursive summation of single-sign data with a growing accumulator.The authors argue for its utility as an alternative to other dynamic floating-point behavior tracking and error detection methods.Source: §5 · p. 29
• The work formally defines stagnation, applies detection to example computations, analyzes its information and performance cost, and provides the StagnationDetection.jl tool.Source: §5 · p. 29
• Further work could examine alternative definitions, more complex operation sequences, other applications, and detection performance, particularly for matrix arithmetic.The conclusion specifically identifies conjugate gradient and additional time-integration problems as possible applications.Source: §5 · p. 29