Interval Arithmetic

Summary

Numerical computations underpin scientific simulation, engineering, and data analysis, yet their results are affected by finite precision and uncertain inputs. Rounding errors can accumulate or be amplified, making numerical results difficult to verify. Interval computing addresses this problem by representing quantities through lower and upper bounds and propagating them through computations. With suitable arithmetic and outward rounding, the resulting intervals provide reliable enclosures of the mathematical results.

A central challenge is obtaining enclosures that are both trustworthy and informative. Interval widths can grow through conservative rounding, repeated operations, and the loss of dependencies between quantities. Tighter bounds may require additional computation or alternative numerical formulations, creating a trade-off between enclosure quality and computational efficiency.

Computational cost and usability present further challenges. Interval arithmetic increases arithmetic work and memory traffic, while rounding-mode changes and conditional branches can hinder compiler optimizations and parallel execution. Ambiguous interval comparisons also require appropriate branching semantics to preserve feasible outcomes. Meanwhile, specialized implementations and interfaces can complicate integration into existing software. Practical interval computing must therefore combine numerical reliability, efficient execution, and familiar programming abstractions.

Our project investigates how numerical algorithms, rounding methods, data representations, and programming abstractions can make interval computing practical in demanding applications. The broader goal is to preserve reliable enclosures while understanding and reducing the costs of obtaining them. This includes studying the balance between enclosure tightness and execution time, the interaction between arithmetic and data layout, the handling of interval-valued comparisons and conditional branches, and the extent to which compilers can generate efficient parallel code from usable interfaces.

One of our contribution is VILIB++, a C++ library for efficient, automatically vectorized interval arithmetic (Qi and Strzodka). It addresses the difficulty of implementing outward rounding in a form that compilers can parallelize. A branchless additive correction avoids changes to the global rounding mode, while overloaded arithmetic operators preserve familiar expressions. Suitable existing code can therefore use interval values without handwritten SIMD instructions.

The benefits are already visible in the four basic interval operations: addition, subtraction, multiplication, and division. In the reported double-precision arithmetic benchmarks, VILIB++ achieves roughly twelve times the addition and subtraction throughput of the fastest tested FILIB++ policies. Multiplication also gains several-fold in throughput, with the improvement depending on interval signs and data layout. Division shows smaller gains, reaching approximately 1.5–2 times the throughput of the optimized FILIB++ implementations when using the best-performing VILIB++ layouts. These measurements demonstrate the potential of automatic vectorization for interval arithmetic on the tested system (Qi and Strzodka).

These arithmetic gains also benefit application kernels: VILIB++ can keep low-degree polynomial evaluations and small stencil computations limited by memory bandwidth. The additional arithmetic work is then largely hidden behind the movement of interval data. These benefits come with wider enclosures than rounding-mode switching, and their extent depends on the computation, compiler, and data layout. VILIB++ demonstrates one way to balance reliability, usability, and parallel efficiency within the broader interval-computing project.

Figures

Figure 1. Enclosures and control flow. Left: both intervals contain the exact result; the tighter enclosure gives more information. Right: for an input in [−1, 2], the condition x > 0 admits both branches. Interval evaluations of f on [−1, 0] and g on [0, 2] produce output enclosures F = [a, b] and G = [c, d]. The positive branch conservatively includes zero so that both inputs use closed intervals. Merging the output enclosures gives Y = hull(F ∪ G) = [min(a, c), max(b, d)].

Conceptual illustration of valid enclosures and interval-valued comparisons.

Figure 2. Basic-operation speedup. VILIB++ is compared against the fastest tested implementation among Boost Interval and the FILIB++ policies. AoS and SoA denote arrays of structures and structures of arrays. Multiplication uses positive intervals or two intervals crossing zero. Dashed lines mark 1×. Measurements use double-precision bounds on an AMD EPYC 7662.

Speedups of basic interval operations with GCC and ICX.

Table 1. Enclosure tightness. Mean relative enclosure widths for point-interval inputs producing normal results; smaller values indicate tighter enclosures.

Operation FILIB++ RMS VILIB++ VILIB++ / RMS
Addition 1.534 × 10⁻¹⁶ 3.079 × 10⁻¹⁶ 2.01×
Subtraction 1.534 × 10⁻¹⁶ 3.079 × 10⁻¹⁶ 2.01×
Multiplication 1.600 × 10⁻¹⁶ 3.200 × 10⁻¹⁶ 2.00×
Division 1.602 × 10⁻¹⁶ 3.204 × 10⁻¹⁶ 2.00×

Figure 3. Interval stencil computations. VILIB++ sustains high effective memory bandwidth for small stencils. As the number of stencil points increases, arithmetic work becomes more significant; compiler and data-layout choices affect the resulting throughput. Dotted lines show AoS and solid lines SoA. The separately measured copy-bandwidth reference is 99 GB/s.

Effective memory bandwidth for one-dimensional interval stencils.

Figure 4. Interval polynomial evaluation. VILIB++ maintains high effective memory bandwidth over a wider range of polynomial degrees than the comparison libraries. The difference between AoS and SoA is especially pronounced with ICX. Dotted lines show AoS and solid lines SoA; the separately measured copy-bandwidth reference is 99 GB/s.

Effective memory bandwidth for interval polynomial evaluation with Horner's scheme.

Code

Publications

  1. Xingjian Qi and Robert Strzodka
    VILIB++: High Performance C++ Library for Auto-Vectorizing Interval Arithmetic
    Proceedings of the 55th International Conference on Parallel Processing, ICPP 2026, Singapore, 28 September 2026 - 1 October 2026, 260–270, ACM, 2026
    link | bib 
    @inproceedings{DBLP:conf/icpp/QiS26,
  author = {Qi, Xingjian and Strzodka, Robert},
  title = {{VILIB++:} High Performance {C++} Library for Auto-Vectorizing Interval
                    Arithmetic},
  booktitle = {Proceedings of the 55th International Conference on Parallel Processing,
                    {ICPP} 2026, Singapore, 28 September 2026 - 1 October 2026},
  pages = {260--270},
  publisher = {{ACM}},
  year = {2026},
  url = {https://doi.org/10.1145/3832810.3832828}
  doi = {10.1145/3832810.3832828},
  timestamp = {Tue, 29 Sep 2026 09:32:13 +0200},
}
  2. Moritz Beutel and Robert Strzodka
    A Paradigm for Interval-Aware Programming
    Lecture Notes in Computer ScienceNext Generation Arithmetic - 4th International Conference, CoNGA 2023, Singapore, March 1-2, 2023, Proceedings, 13851, 38–60, Springer, 2023
    link | bib 
    @inproceedings{DBLP:conf/conga/beutel_paradigm_2023,
  author = {Beutel, Moritz and Strzodka, Robert},
  editor = {Gustafson, John L. and Leong, Siew Hoon and Michalewicz, Marek T.},
  title = {A Paradigm for Interval-Aware Programming},
  booktitle = {Next Generation Arithmetic - 4th International Conference, CoNGA 2023,
                    Singapore, March 1-2, 2023, Proceedings},
  series = {Lecture Notes in Computer Science},
  volume = {13851},
  pages = {38--60},
  publisher = {Springer},
  year = {2023},
  url = {https://posithub.org/conga/2023/assets/pdf/Interval-awareProgramming.pdf}
  doi = {10.1007/978-3-031-32180-1\_3},
  timestamp = {Sun, 06 Aug 2023 11:41:27 +0200},
}

Current people

Past people

  • Moritz Beutel

Contact