Elamur Research⌕
☰
home / papers / 2016 / Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic

Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic

Paper · 2016 · Fredrik Johansson

Summary

Rigorous numerical computation with interval arithmetic tracks error bounds automatically. Existing arbitrary-precision interval tools such as MPFI store both endpoints at full precision and offer only a narrow set of functions. Johansson presents Arb, a portable, thread-safe C library built on midpoint-radius ("ball") arithmetic. A real number is stored as [m ± r], where only the midpoint m needs full precision and the radius r needs just a few digits. At high precision this makes interval computation nearly as cheap as plain floating-point, and about twice as cheap as endpoint intervals. Arb builds real and complex balls, polynomials, power series and matrices from this core. It also provides rigorous evaluation of many special functions, including gamma, zeta, Bessel, Airy, hypergeometric and elliptic functions, over complex arguments. The paper covers the low-level representation, how precision and error bounds are managed, and fast polynomial arithmetic with interval coefficients. Performance is competitive with non-interval libraries such as MPFR and MPC. This makes certified results practical in computer algebra and scientific computing.

Key points

  • Arb's core types are arf_t (floating-point), mag_t (unsigned bounds), arb_t (real balls), acb_t (complex numbers), arb_poly_t/acb_poly_t (polynomials) and arb_mat_t/acb_mat_t (matrices). It depends on GMP/MPIR, MPFR and FLINT.
  • As of November 2016 the library had about 1850 documented methods and roughly 650 test programs. Each test checks results for consistency on 10³–10⁶ random inputs, and the tests are also run under Valgrind.
  • Arb is LGPL-licensed and can be used from SageMath, the python-flint module and Julia's Nemo package.
  • A typical usage pattern is to repeat the computation with doubled precision until the target accuracy is reached. The paper demonstrates this by computing sin(π + e⁻¹⁰⁰⁰⁰) to 53 bits.
  • The paper describes two applications:
    • About 500 lines of wrapper code give correctly rounded versions of all transcendental functions in MPFR 3.1.3.
    • A hydrogeophysics aquifer simulation uses Arb to obtain Bessel functions at 113-bit accuracy.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Université de BordeauxBordeaux · France2 works · 38,342 citations

Also on the byline: Centre Inria de l'université de Bordeaux.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksMathematics · 233 worksComputational Theory and Mathematics · 496 worksModeling and Simulation · 12 works

Cite

Cite as Fredrik Johansson. 2016. Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic. arXiv:1611.02831.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1611.02831 · arXiv 1611.02831

@misc{johansson2016arb,
  title = {{Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic}},
  author = {Fredrik Johansson},
  year = {2016},
  doi = {10.48550/arxiv.1611.02831},
  eprint = {1611.02831},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1611.02831}
}

References

32 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. W. Tucker, Validated numerics: a short introduction to rigorous computations. Princeton University Press, 2011. find
  2. T. C. Hales, J. Harrison, S. McLaughlin, T. Nipkow, S. Obua, and R. Zumkeller, “A revision of the proof of the Kepler conjecture,” in The Kepler Conjecture. Springer, 2011, pp. 341–376. find
  3. H. A. Helfgott, “The ternary Goldbach problem,” http://arxiv.org/abs/1501.05438, 2015. — [arXiv:1501.05438](https://arxiv.org/abs/1501.05438) ↗
  4. W. Tucker, “A rigorous ODE solver and Smale’s 14th problem,” Foundations of Computational Mathematics, vol. 2, no. 1, pp. 53–117, 2002. find
  5. N. Revol and F. Rouillier, “Motivations for an arbitrary precision interval arithmetic library and the MPFI library,” Reliable Computing, vol. 11, no. 4, pp. 275–290, 2005, http://perso.ens-lyon.fr/nathalie.revol/software.html. ↗
  6. L. Fousse, G. Hanrot, V. Lefèvre, P. Pélissier, and P. Zimmermann, “MPFR: A multiple-precision binary floating-point library with correct rounding,” ACM Transactions on Mathematical Software, vol. 33, no. 2, pp. 13:1–13:15, Jun. 2007, http://mpfr.org. ↗
  7. A. Enge, P. Théveny, and P. Zimmermann, “MPC: a library for multiprecision complex arithmetic with exact rounding,” http://multiprecision.org/, 2011. ↗
  8. J. van der Hoeven, “Ball arithmetic,” HAL, Tech. Rep., 2009, http://hal.archives-ouvertes.fr/hal-00432152/fr/. ↗
  9. J. van der Hoeven, G. Lecerf, B. Mourrain, P. Trébuchet, J. Berthomieu, D. N. Diatta, and A. Mantzaflaris, “Mathemagix: the quest of modularity and efficiency for symbolic and certified numeric computation?” ACM Communications in Computer Algebra, vol. 45, no. 3/4, pp. 186–188, Jan. 2012, http://ma… — [doi:10.1145/2110170.2110180](https://doi.org/10.1145/2110170.2110180) find
  10. N. Müller, “The iRRAM: Exact arithmetic in C++,” in Computability and Complexity in Analysis. Springer, 2001, pp. 222–252, http://irram.uni-trier.de. ↗
  11. D. H. Bailey and J. M. Borwein, “High-precision arithmetic in mathematical physics,” Mathematics, vol. 3, no. 2, pp. 337–367, 2015. find
  12. F. Johansson, “Efficient implementation of elementary functions in the medium-precision range,” in 22nd IEEE Symposium on Computer Arithmetic, ser. ARITH22, 2015, pp. 83–89. find
  13. ——, “Rigorous high-precision computation of the Hurwitz zeta function and its derivatives,” Numerical Algorithms, vol. 69, no. 2, pp. 253–270, June 2015. find
  14. ——, “Computing hypergeometric functions rigorously,” https://arxiv.org/abs/1606.06977, 2016. — [arXiv:1606.06977](https://arxiv.org/abs/1606.06977) ↗
  15. ——, “Arb: a C library for ball arithmetic,” ACM Communications in Computer Algebra, vol. 47, no. 4, pp. 166–169, 2013. find
  16. The GMP development team, “GMP: The GNU Multiple Precision Arithmetic Library,” http://gmplib.org. ↗
  17. The MPIR development team, “MPIR: Multiple Precision Integers and Rationals,” http://www.mpir.org. ↗
  18. W. B. Hart, “Fast Library for Number Theory: An Introduction,” in Proceedings of the Third international congress conference on Mathematical software, ser. ICMS’10. Berlin, Heidelberg: Springer-Verlag, 2010, pp. 88–91, http://flintlib.org. ↗
  19. Sage developers, SageMath, the Sage Mathematics Software System (Version 7.2.0), 2016, http://www.sagemath.org. ↗
  20. N. Nethercote and J. Seward, “Valgrind: a framework for heavyweight dynamic binary instrumentation,” in ACM Sigplan notices, vol. 42, no. 6. ACM, 2007, pp. 89–100. find
  21. N. J. A. Sloane, “OEIS A110375,” http://oeis.org/A110375, 2008. ↗
  22. F. Johansson, “Efficient implementation of the Hardy-Ramanujan-Rademacher formula,” LMS Journal of Computation and Mathematics, vol. 15, pp. 341–359, 2012. [Online]. Available: http://dx.doi.org/10.1112/S1461157012001088 — [doi:10.1112/s1461157012001088](https://doi.org/10.1112/s1461157012001088) ↗
  23. A. Enge, “The complexity of class polynomial computation via floating point approximations,” Mathematics of Computation, vol. 78, no. 266, pp. 1089–1107, 2009. find
  24. A. Bucur, A. M. Ernvall-Hytönen, A. Odžak, and L. Smajlović, “On a Li-type criterion for zero-free regions of certain Dirichlet series with real coefficients,” LMS Journal of Computation and Mathematics, vol. 19, no. 1, pp. 259–280, 2016. find
  25. G. Beliakov and Y. Matiyasevich, “Zeros of Dirichlet L-functions on the critical line with the accuracy of 40000 decimal places,” http://dx.doi.org/10.4225/16/5382D9A62073E, 2014. — [doi:10.4225/16/5382d9a62073e](https://doi.org/10.4225/16/5382d9a62073e) ↗
  26. ——, “Approximation of Riemann’s zeta function by finite Dirichlet series: A multiprecision numerical approach,” Experimental Mathematics, vol. 24, no. 2, pp. 150–161, 2015. find
  27. F. Johansson, “mpmath: a Python library for arbitrary-precision floating-point arithmetic,” http://mpmath.org, 2015. ↗
  28. W. B. Hart and A. Novocin, “Practical divide-and-conquer algorithms for polynomial arithmetic,” in Computer Algebra in Scientific Computing. Springer, 2011, pp. 200–214. find
  29. R. P. Brent and H. T. Kung, “Fast algorithms for manipulating formal power series,” Journal of the ACM, vol. 25, no. 4, pp. 581– 595, 1978. find
  30. F. Johansson, “A fast algorithm for reversion of power series,” Mathematics of Computation, vol. 84, pp. 475–484, 2015. [Online]. Available: http://dx.doi.org/10.1090/S0025-5718-2014-02857-3 — [doi:10.1090/s0025-5718-2014-02857-3](https://doi.org/10.1090/s0025-5718-2014-02857-3) ↗
  31. J. van der Hoeven, “Making fast multiplication of polynomials numerically stable,” Université Paris-Sud, Orsay, France, Tech. Rep. 2008-02, 2008. find
  32. A. Enge, “MPFRCX: a library for univariate polynomials over arbitrary precision real or complex numbers,” 2012, http://www.multiprecision.org/index.php?prog=mpfrcx. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/johansson-2016-arb-efficient-arbitrary-precision-midpoint/