CS Paper Radar

Running error bounds in finite element kernels

Michal Habera, Paul T. Kühner, Matteo Croci, Andreas Zilian

cs.MS math.NA ·submitted 2026-09-29 15:41 UTC · v1
code/data

Abstract

Rounding errors in finite element computations can lead to a complete loss of accuracy, stalled convergence, and incorrect results. Moreover, the effects of rounding errors accumulated within automatically generated and compiled kernels are difficult to analyze a priori. We present the first software framework for automated rounding error estimation within finite element kernels. The proposed methodology is based on an a posteriori technique called Running Error Analysis (REA), where a forward error estimate is automatically computed concurrently with the value. An open-source implementation is provided for the FEniCS Form Compiler (FFCx), based on a C++ backend for generating type-generic templated kernels over a custom arithmetic type that tracks both the value and its error estimate. We demonstrate REA on two examples. First, we use it to detect catastrophic cancellation in the assembly of a Neo-Hooke hyperelastic model in the small deformation regime. A series expansion circumvents the cancellation problem and the computed error estimates show this. Second, we study the assembly of the Laplace operator on a near-degenerate mesh. We demonstrate that our REA implementation typically incurs only 2-4x performance overhead. Applications of this work include robust reduced-precision computations in embedded systems, numerical debugging of new, possibly ill-conditioned or unstable PDE formulations, and guiding the design of mixed-precision kernels.

Comment
18 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Trustworthy Numerical Software in the Age of AI: What Would Turing Do?

cs.MS math.NA ·2026-11-16 ·Kimon Fountoulakis, Maksim Melnichenko, Muhammad Fetrat Qharabagh, Georgios Alexandros Georgantzas, George Spyrou +4 more
similarity 0.61
Abstract · 44 pages

AI coding agents can now produce numerical software faster than human experts can review it, raising serious concerns about usability and reliability. These and other AI tools are already transforming mathematics and software, and they will soon transform mathematical software. These concerns motivated us to assess AI-generated numerical linear algebra (NLA) kernels, which we did through an audit of a recent public GPU QR competition. All five leading kernels passed the competition's accuracy tests, and the winning kernel achieved a 107-fold speedup over the competition's baseline, which calls NVIDIA's QR routine. Yet each failed at least once on new inputs, even those from the competition's generator, under the same checker, while the baseline passed them all. In light of this, we want to develop reusable formalizations of numerical analysis methods, which remain sparsely represented in existing formal libraries. We describe VSCL, our Lean library of mathematical foundations for numerical computing. We also propose VERNA to connect these tasks by using formalized results to guide kernel assessment against explicit specifications. Drawing on Turing's work on rounding-error analysis and program checking, we discuss design principles for developing trustworthy numerical software when direct human checking is impractical.

0.16

FPScan: An Automated Constraint-Based Analyzer for Floating-Point Anomaly Detection

cs.SE math.NA ·2026-09-07 ·Julien Bortolussi, Dorra Ben Khalifa, Pierre-Loïc Garoche
benchmark similarity 0.60
Abstract · 12 pages , 7 Figures, 28th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

Writing error-free floating-point programs is a challenging task, especially for programmers who lack a strong background in numerical analysis and rounding-error propagation. State-of-the-art techniques typically aim to bound such errors using static or dynamic analysis. However, only a few tools explicitly address critical floating-point pitfalls such as absorption and catastrophic cancellation. These anomalies represent situations in which rounding errors are significantly amplified, causing the semantics of the finite-precision computation to deviate substantially from the real-number semantics. In this article, we present FPScan, a novel tool to formally define and detect both catastrophic cancellation and absorption in floating-point programs. Our approach starts with a custom static analyzer based on abstract interpretation to infer the order of magnitude of all program variables. This magnitude information is then used to build a set of first-order constraints that model error propagation and numerical precision within the program. Finally, we employ an off-the-shelf SMT solver to determine whether the program exhibits any of these critical numerical pitfalls. Experiments were conducted on FPBench, a well-known benchmark suite of floating-point programs, to evaluate the effectiveness of our tool. We also present a comparison with state-of-the-art tools regarding soundness and analysis time.

0.26

Taming Bitwise Behavior in GPU Kernels with Tensor Core: Black-Box Reconstruction, Compiler Enforcement, and Static Verification

cs.DC cs.PFcs.PL ·2026-09-10 ·Ziteng Yang, Nicholas J. Riasanovsky, Warren Deng, Vivek Sarkar
hot direction similarity 0.59
Abstract

Determinism and numerical reproducibility are increasingly required of GPU kernels in machine learning systems, yet deterministic implementations of the same kernel can still differ bit for bit. Floating-point reduction order is the primary cause, alongside partial-sum precision, fused multiply-add operations, and rounding placement. These choices may be hand-coded, selected by a block-level language such as Triton, or hidden inside a closed-source library such as cuBLAS or rocBLAS. A tile shape chosen for performance therefore also determines the arithmetic, potentially breaking batch invariance. Preserving a fixed order can cost up to 20 percent, while an autotuner cannot identify which configurations are bitwise equivalent. We characterize the factors determining the bitwise behavior of reductions and general matrix multiplication (GEMM). First, we introduce a descriptor of GEMM reduction order, including the partitioning of K in split-K GEMM. Using it, we perform the first black-box reconstruction of a closed-source library's arithmetic for bit-level correctness. Our family of Triton GEMMs matches NVIDIA cuBLAS in all tested cases on Blackwell and Hopper. For realistic LLM shapes with fused epilogues, it matches or exceeds torch.compile performance. Second, we enforce balanced-tree reduction during Triton lowering and introduce a data-layout optimization that brings 19 of 27 kernels on GB300 and H100 within 10 percent of free-order performance. Third, we develop sound static checkers for bitwise equivalence between compiled GPU kernels, including the first checker spanning NVIDIA PTX and AMD GCN. Integrated into Triton's autotuner, the checker restricts search to a single bit-equivalence class.

0.53

Taylor-Approximation-Based Repair of High Floating-Point Errors

cs.SE ·2026-10-10 ·Xin Yi, Liqian Chen, Hengbiao Yu, Shangwen Wang, Tao Tang +3 more
benchmark similarity 0.59
Abstract

Numerical libraries can still lose many bits of accuracy on localized ill-conditioned inputs, such as roots, poles, cancellation points, and branch boundaries. This paper presents NPTaylor, a Taylor-approximation-based framework for repairing localized high floating-point errors in numerical C routines. Given a high-error input, a localized repair domain, a high-precision oracle, and an error threshold, NPTaylor searches over Taylor degree, expansion center, segmentation, and floating-point evaluation strategy. It emits guarded C patches that use a generated Taylor evaluator inside the repair domain and fall back to the original routine outside it. Candidate patches are accepted only after validating the emitted C code on recorded local samples, guard endpoints, and the pre-repair peak input. The generated evaluator uses coefficient splitting and compensated Horner evaluation to reduce rounding error introduced by the patch itself. We evaluate NPTaylor on GSL benchmark workloads. On 38 one-input functions, both NPTaylor and AutoRNP repair all 114 configurations across three accuracy thresholds. NPTaylor is 3.33x faster by geometric-mean offline repair time and emits 0.162x as many C bytes. In the strictest setting, its median repair time is 3.74s versus 81.97s for AutoRNP. NPTaylor also repairs localized multi-input benchmark cases beyond AutoRNP's implemented one-input workflow. These results show that Taylor-based guarded patches can provide compact, efficient local repairs, while the claims remain validation-relative rather than full-domain proofs.

0.22

When Double Rounding is Correct

cs.PL ·2026-10-06 ·Brett Saiki, Bill Zorn, Cynthia Richey, Zachary Tatlock
similarity 0.59
Abstract

Number libraries, which implement number formats and their arithmetic in software, are used to simulate hardware, making hardware behavior reproducible and thus verifiable and easier to design. However, modern machine learning accelerators are difficult to simulate, as they increasingly use specialized number formats that existing number libraries do not support. It is costly to extend these libraries using traditional methods: each combination of operation, format, and rounding mode typically requires a bespoke implementation. An easier way is to double round - compute at higher precision, then re-round - so that one high-precision kernel serves many formats, but double rounding is only known to be correct in select cases. We give a precise, efficiently checkable characterization of when double rounding is correct across many formats and rounding modes. Our result rests on a novel abstract number format that unifies fixed- and floating-point representations, reducing the correctness of double rounding to format containment: whether every value of one format is representable in another. We mechanized these results in Lean 4. In addition, we introduce a format inference algorithm that, given a sequence of operations, bounds each expression by a number format guaranteed to contain its result. We apply these insights in two ways. First, we present MPFX, a correctly-rounded, multi-precision number library that exploits correct double rounding to efficiently simulate many number formats. MPFX's correctly-rounded operations are up to 11x (mean: 6.05x) faster than MPFR's, and competitive with SoftFloat's - between 0.46x and 1.63x as fast (mean: 0.94x) - at the same precision. Second, in a case study, we implement a software simulation of a hardware specification using both SoftFloat and MPFX's primitives; the MPFX version is up to 13.5x faster.

0.11

Love Handles: Decimation for Deformation Handles with Compact Support and Low Memory Footprints

cs.GR ·2026-08-18 ·David IW Levin, Paul Kry, Kartic Subr, Ryan Schmidt, Etienne Vouga +1 more
similarity 0.59
Abstract

Estimating the deformation of solids via physical simulation is an important problem spanning fields such as computer animation, engineering and robotics. Such simulations are computationally expensive and scale poorly when the representation of an object is refined by increasing the level of discretization. Reduced Order Methods (ROM) offer computational savings by decreasing the number of degrees of freedom, for example by using \emph{handles} that control groups of vertices. We present the first decimation-based algorithm for computing a sparse, compactly supported set of deformation handles. The crux of our method utilizes iterative algebraic simplification to optimize handle deformation to match any input deformation, such as linear vibration modes. This applies to any volumetric input mesh, including those with high genus or porous features, since we do not alter the geometry. We also devise an efficient algorithm to compute and update compact supports and their associated weights. We leverage compact support to develop an efficient, reduced-cubature computation scheme. Once optimized, our handles offer a memory-efficient solution while enabling real-time elastodynamics simulation of complex geometry. We show real-time performance on a variety of tetrahedral meshes with up to 796,623 tetrahedra.

0.23

FloatLib: Verified Floating-Point Arithmetic in Lean

cs.LO cs.PL ·2026-09-16 ·Robert Joseph George, Will Adkisson, Anima Anandkumar
code/data similarity 0.59
Abstract · 30 pages, 7 figures, 6 tables. Software and evaluation artifacts available at https://github.com/lean-dojo/FloatLib

We present FloatLib, a verified arbitrary-precision floating-point arithmetic library in Lean 4 that combines broad format coverage, machine-checked correctness, and efficient certified execution. To our knowledge, FloatLib is the first Lean library to unify IEEE binary and decimal arithmetic, arbitrary-width posits, P3109, and user-defined formats and rounding rules behind interchangeable certified software backends. Every certified backend is proved equal to a complete encoded specification, preserving signed zeros and exceptional values, while numerical theorems connect execution to real rounding, error bounds, and exactness. FloatLib combines exhaustive certified tables for small formats with verified word and limb kernels based on guard-and-sticky invariants and independently checked quotient candidates. Its posit development additionally proves standard rounding thresholds and exact quire accumulation within capacity for arbitrary widths. Across matched workloads, FloatLib achieves speedups of up to 1.46x over FLoPS and 116x over Universal, while remaining slower in some regimes such as binary arithmetic against MPFR. Independent conformance testing includes more than 102 million TestFloat evaluations with zero differences under the tested relation. We release the library, proofs, benchmarks, evaluation data, and guide as open source.

0.38

How Numerical Errors Scale with Hardware

cs.DC ·2026-10-26 ·Niklas Baumgarten
similarity 0.58
Abstract

In this short technical note, we outline how to bound numerical errors with respect to computational resources. We consider algorithms with known complexity estimates that can be executed in parallel and combine these estimates with parallelization laws. We suppose that the proposed approach generalizes beyond the presented examples and argue that it provides a straightforward and fair framework for comparing algorithms, hardware systems, and software implementations. This is achieved by imposing identical resource or energy budgets on each configuration, and comparing the resulting numerical error evaluations.

0.24