Fast and parallel interval arithmetic (Q1307245): Difference between revisions

In \(\mathbb{K}\in\{\mathbb{R}, \mathbb{C}\}\) compact intervals can be defined in a midpoint-radius representation as \[ A= \langle a,\alpha\rangle:= \{x\in \mathbb{K}:|x-a|\leq \alpha\}, \] where \(a\in\mathbb{K}\) is the midpoint and \(0\leq\alpha= \text{rad } A\in\mathbb{R}\) is the radius. For such intervals there exists a well-known midpoint-radius arithmetic with binary operations \(\oplus\), \(\ominus\), \(\odot\), \(\oslash\). These operations are defined using the midpoints and the radii of the two operands such that \[ A\circ B:= \{a\circ b: a\in A, b\in B\}\subseteq A\circledcirc B \] holds for \(\circ\in\{+,-,\cdot,/\}\). With \(\text{rad}(A\circ B)\) denoting half of the diameter of the set \(A\circ B\) it is proved that the overestimation \(\rho:= {\text{rad}(A\circledcirc B)\over \text{rad}(A\circ B)}\) is uniformly bounded by \(\gamma:= 1.5\) for any \(\circ\in \{+,-,\cdot,/\}\). This even holds (componentwise) for matrix-vector products and matrix-matrix products. In practice, it turns out that \(\gamma\) can be significantly smaller than 1.5. Conditions for such situations are listed, the property itself is illustrated by numerical examples. Algorithms for the midpoint-radius interval arithmetic are given using floating point numbers and taking into account rounding errors. The main advantage of these algorithms lies in an impressive increase of the computational speed effected -- among others -- by the possibility of using machine optimized BLAS. They can easily be implemented and are well suited for parallel and vector computers. Numerical measurements show that in view of the speed the algorithms are superior by orders of magnitude to the traditional implementations of the interval arithmetics based on the infimum-supremum representation of intervals.