A Second-Moment Theory for Floating-Point Reduction Trees

DOI10.48550/arXiv.2607.18758MaRDI QIDQ7284192arXivFDO

Authors Piyush Sao, Pedro Valero-Lara, Keita Teranishi, Sudip K. Seal, Narasinga Miniskar, Sudip Seal

Publication date 21 July 2026

Published in arXiv

Tldr We derive a second-moment theory for floating-point summations in binary reduction trees using conditionally unbiased rounding. The theory provides an exact mean-square error cost of p^T K_T p, where K_T is the common-ancestor kernel counting shared ancestors in the tree T, and enables optimal topology and scheduling for i.i.d. inputs with any distribution.

Full work available at URL https://doi.org/10.48550/arXiv.2607.18758

arXiv classification

cs.MSmath.NAcs.ITcs.DC

Cites work

• A Class of Fast and Accurate Summation Algorithms
• A Method for the Construction of Minimum-Redundancy Codes
• A fast algorithm for optimal length-limited Huffman codes
• Accurate Sum and Dot Product
• Best “ordering” for floating-point addition
• FPRev: Revealing the Order of Floating-Point Summation by Numerical Testing
• Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors
• Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees
• Mixed precision block fused multiply-add: error analysis and application to GPU tensor cores
• Numerical inverting of matrices of high order
• On Floating-Point Summation
• On roundoff error distributions in floating point and logarithmic arithmetic
• Precision-aware deterministic and probabilistic error bounds for floating point summation
• Probabilistic Error Analysis of Limited-Precision Stochastic Rounding: Horner's Algorithm and Pairwise Summation
• Reducing floating point error in dot product using the superblock family of algorithms
• Reproducible and accurate matrix multiplication
• Stochastic Rounding Variance and Probabilistic Bounds: A New Approach
• Stochastic rounding and its probabilistic backward error analysis
• Test of probabilistic models for the propagation of roundoff errors
• Tests of probabilistic models for propagation of roundoff errors
• The Accuracy of Floating Point Summation
• The ancestral matrix of a rooted tree

This page was built for publication: A Second-Moment Theory for Floating-Point Reduction Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7284192)