2026/07/21 by Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara +2
#math.NA #cs.DC #cs.IT #cs.MS #cs.NA #math.IT
Summation error depends on partial-sum order, which standard worst-case bounds omit. To capture this dependence, we derive an exact mean-square error (MSE) recurrence for a binary reduction tree T under conditionally unbiased rounding. With unit roundoff u, the constant-nu model sets the local variance at pre-rounding value x to nu u2 x2. Its leading tree-dependent cost for the input vector p is pT KT p, where the common-ancestor kernel KT counts the internal ancestors shared by each pair of leaves. For i.i.d. inputs of mean mu and variance tau2, this expected cost is tau2 Lambda1(T) + mu2 Lambda2(T), where Lambda1 is total leaf depth and Lambda2 sums squared internal-subtree sizes; Lambda1 governs centered inputs, while Lambda2 captures nonzero means. We use these statistics to characterize optimal tree topologies and schedules. Balanced and sequential trees attain the centered extrema. For k inputs, optimal two-stage sequential blocking yields root-mean-square (RMS) error scaling as k3/4. For fixed-stage hierarchies, geometric schedules are optimal for centered inputs, whereas the optimal noncentered stage exponents halve successively. For independent centered inputs with unequal variances, Huffman coding minimizes variance-weighted depth over free leaf assignments. We extend the kernel to matrix multiplication through operand Gram matrices. We then test the approximation under round-to-nearest using exact residuals. Across binary64, binary32, and software-emulated binary16 and bfloat16, the model recovers the ordering among tree topologies; KT tracks AR(1) partial-sum costs. For GEMM, independently calibrated predictions differ from measurements by at most 3% on the tested grid. A reduction tree extracted from an array library predicts the measured RMS scaling. However, stagnation and bias in positive low-precision sums limit the model's applicability.