Ball arithmetic vs interval arithmetic

Question

What are the advantages of ball arithmetic (Arb) over interval arithmetic (MPFI)?

In other words, what are the advantages of representing an interval as [center, radius] over [left, right]?

This is not about particular library (Arb vs MPFI), rather it is about advantages of a particular representation.

I'm especially interested whether one representation allows for faster arithmetic (fewer primitive operations), lesser error over-estimation and more frugal memory usage.

Tetralogy

This paper gives many arguments in favor of ball arithmetic. Just skimming it, the motivation seems more that it provides a cleaner model of computation rather than that e.g. it is more efficient. – Argive

@JohnColeman: The paper also exposes the fact that ball arithmetic and interval arithmetic are not just different representations of the same thing but have different purposes. Again, just skimming, it seems ball arithmetic does not necessarily give strict bounds; the radius may be an estimate. – Xanthophyll

I would not call it ball arithmetic if the radius is just an estimate. Mathematica has a kind of faux ball arithmetic like that, which it calls significance arithmetic. – Separates

Ball arithmetic is actually some particular form of interval arithmetic. If by "interval arithmetic" you mean like MPFI, this is inf-sup interval arithmetic. Ball arithmetic in one dimension is also called mid-rad interval arithmetic. – Revolutionize

Answer 1

In arbitrary-precision arithmetic, ball arithmetic is about twice as fast as interval arithmetic and uses half as much space. The reason is that only the center of a ball needs high precision, whereas in interval arithmetic, both endpoints need high precision. Details depend on the implementation, of course. (In practice, Arb is faster than MPFI by much more than a factor two, but this is largely due to implementation effort.)

In hardware arithmetic, balls don't really have a speed advantage over intervals, at least for scalar arithmetic. There is an obvious advantage if you look at more general forms of ball arithmetic and consider, for example, a ball matrix as a floating-point matrix + a single floating-point number for the error bound of the whole matrix in some norm, instead of working with a matrix of individual intervals or balls.

Joris van der Hoeven's article on ball arithmetic is a good take on the differences between ball and interval arithmetic: http://www.texmacs.org/joris/ball/ball.html

An important quote is: "Roughly speaking, balls should be used for the reliable approximation of numbers, whereas intervals are mainly useful for certified algorithms which rely on the subdivision of space."

Ignoring performance concerns, balls and intervals are usually interchangeable, although intervals are better suited for subdivision algorithms. Conceptually, balls are nice for representing numbers because the center-radius form corresponds naturally to how we think of approximations in mathematics. This notion also extends naturally to more general normed vector spaces.

Personally, I often think of ball arithmetic as floating-point arithmetic + error analysis, but with the error bound propagation done automatically by the computer rather than by hand. In this sense, it is a better way (for certain applications!) of doing floating-point arithmetic, not just a better way of doing interval arithmetic.

For computations with single numbers, error over-estimation has more to do with the algorithms than with the representation. MPFI guarantees that all its atomic functions compute the tightest possible intervals, but this property is not preserved as soon as you start composing functions. With either ball or interval arithmetic, blow-up tends to happen in the same way as soon as you run calculations with many dependent steps. To track error bounds resulting from large uncertainties in initial conditions, techniques such as Taylor models are often better than direct interval or ball arithmetic.

True complex balls (complex center + single radius) are sometimes better than rectangular complex intervals for representing complex numbers because the wrapping effect for multiplications is smaller. (However, Arb uses rectangular "balls" for complex numbers, so it does not have this particular advantage.)

Separates

Thank you for such a thorough answer! Huge fan of your work, by the way! – Tetralogy

Inf-sup interval arithmetic (like in MPFI) is better when one just wants the range of a function over some potentially large interval. But this is a bit like your remark on the subdivision of space. Now, I would say that arbitrary precision is not necessary in such applications. – Revolutionize