Affine Arithmetic for Pedestrians

イントロのイントロ

この文書はMathlogと別の場所に投げるつもりで書いていたので、以降はすべて英文になっています。そのうち日本語版も用意できたらなあ。

Introduction

Affine arithmetic is a variant of interval arithmetic that takes into account the correlation between variables.

Here is an extreme example. In the case of interval arithmetic, $[x]-[x]$ will not be $0$ as long as $[x]$ has a positive diameter. This is because “$[x]-[x]$” in interval arithmetic computes the following set:
$$     \{a-b\mid\text{$a\in[x]$, $b\in[y]$}\}. $$

In the formula, $a$ and $b$ move independently on their domain. Affine arithmetic reduces such overestimation by accounting for correlations among variables.

Definition

An affine form $X=X(\epsilon)$ is a polynomial of degree zero or one, consisting of indeterminates called noise symbols $\epsilon_{1},\epsilon_{2},\dotsc,\epsilon_{n}$:
$$     X(\epsilon) = x_{0}+x_{1}\epsilon_{1}+x_{2}\epsilon_{2}+\dotsb+x_{n}\epsilon_{n}, $$
where each $x_{i}$ is a scalar or vector (not an interval). The range of $X$ is defined as follows:
$$     \operatorname{range}(X) \coloneqq \{X(s_{1},s_{2},\dotsc,s_{n})\mid s_{1},s_{2},\dotsc,s_{n}\in[-1,1]\}. $$

Let $f(x)$ be a mathematical function. In this document, we call $F(X)$ an A-extension of $f(x)$ if the map $F(X)$ satisfies the following conditions.

1. If $X$ consists of $n$ noise symbols, then $Y=F(X)$ consists of $n+m$ noise symbols, where $m$ is an appropriate non-negative integer.
2. For each $s\in[-1,1]^{n}$, there exists $t\in[-1,1]^{m}$ such that $Y(s,t)=f(X(s))$.

The composition of A-extensions is an A-extension of the composite function by definition. In addition, the inclusion
$$     f(x) \in \operatorname{range}(F(X)) $$
holds for $x\in\operatorname{range}(X)$. These properties allow affine arithmetic to be used to evaluate the range of a function if numerically computable A-extensions can be defined for elementary operations.

Well-known A-extensions

For simplicity, We ignore rounding errors caused by floating-point operations in this section.

The A-extension of addition, subtraction, and constant multiplication is obvious; it is just ordinary polynomial arithmetic.

The A-extension of multiplication $f(x,y)=xy$ is somewhat nontrivial. Let $X$, $Y$ be scalar-valued affine forms consisting of $\epsilon_{1},\epsilon_{2},\dotsc,\epsilon_{n}$. Then
$$     F(X,Y) = x_{0}y_{0}+\sum_{i=1}^{n}(x_{i}y_{0}+x_{0}y_{i})\epsilon_{i}+\Biggl(\sum_{i=1}^{n}\lvert x_{i}\rvert\sum_{j=1}^{n}\lvert y_{j}\rvert\Biggr)\epsilon_{n+1} $$
is an A-extension of $f(x,y)$ (Comba & Stolfi, 1993). Note that in this formula, $F(X,Y)$ includes the new noise symbol $\epsilon_{n+1}$. The range of nonlinear operations is enclosed by appending a new noise symbol in this way.

The A-extension of division is usually defined as the product of $X$ and $G(Y)$, the A-extension of $g(y)=1/y$. We can define $G(Y)$ as (Miyajima & Kashiwagi, 2014)
$$     G(Y) = \frac{\mu_{1}+\sigma\mu_{2}-y_{0}}{ab}-\sum_{i=1}^{n}\frac{y_{i}}{ab}\epsilon_{i}+\frac{\mu_{1}-\sigma\mu_{2}}{ab}\epsilon_{n+1}, $$
where $a$, $b$, $\sigma$, $\mu_{1}$, and $\mu_{2}$ are defined as follows.

1. $[a,b]=\operatorname{range}(Y)$. If $0\in[a,b]$, we can not define $G(Y)$.
2. $\sigma=1$ if $a>0$; otherwise $\sigma=-1$.
3. $\mu_{1}=(a+b)/2$, $\mu_{2}=\sqrt{ab}$.

Treating rounding errors

The simplest method of treating rounding errors is to store rounding errors in noise symbols. Let $F(X)$ be the A-extension of the scalar-valued function $f(x)$. If $X$ consists of $n$ noise symbols $\epsilon_{1},\epsilon_{2},\dotsc,\epsilon_{n}$, assume that $F(X)$ consists of $m$, strictly greater than $n$ noise symbols. Since the noise symbols newly appended by $F(X)$ are not related to other affine forms, we can assume that their coefficients are non-negative. Let
$$     F(X) = \sum_{i=0}^{m}f_{i}(X)\epsilon_{i}, $$
where $\epsilon_{0}=1$ and each $f_{i}(X)$ is a scalar. If we can compute the approximation $f_{i}^{\mathrm{mid}}(X)$ and error bound $f_{i}^{\mathrm{rad}}(X)$ such that
$$     \lvert f_{i}(X)-f_{i}^{\mathrm{mid}}(X)\rvert \leq f_{i}^{\mathrm{rad}}(X) $$
for each $i$, then we obtain the following computable A-extension:
$$     \bar{F}(X) = \sum_{i=0}^{m}f_{i}^{\mathrm{mid}}(X)\epsilon_{i}+\Biggl(\sum_{i=0}^{m}f_{i}^{\mathrm{rad}}(X)\Biggr)\epsilon_{m}. $$

The above explanation may seem difficult, but its meaning is simple. First, we compute the A-extension in interval arithmetic. Next, replace each coefficient at its midpoint and add its radius to the coefficient of $\epsilon_{m}$. The result is then the A-extension that takes rounding errors into account. Do not forget that the last summation must be done with the rounding towards positive infinity.

Summarizing noise symbols

Complex calculations using affine arithmetic often result in so many noise symbols that the computational cost becomes impractical. In such cases, the computational cost can be reduced by summarizing noise symbols that are not so important in representing correlations between variables.

If we have an A-extension of the identity map $i\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$, $i(x)=x$ that reduces the number of noise symbols with non-zero coefficients, we can summarize noise symbols without compromising the correlation of affine forms. We can define such an A-extension $I(X)$ by converting several noise symbols into a single new noise symbol. More precisely, $I(X)$ maps a vector-valued affine form
$$     X = \begin{pmatrix}x_{1\,0}\\ x_{2\,0}\\ \vdots\\ x_{d\,0}\end{pmatrix}+\sum_{i=1}^{n}\begin{pmatrix}x_{1\,i}\\ x_{2\,i}\\ \vdots\\ x_{d\,i}\end{pmatrix}\epsilon_{i} $$
to an another vector-valued affine form
$$     I(X) = \begin{pmatrix}x_{1\,0}\\ x_{2\,0}\\ \vdots\\ x_{d\,0}\end{pmatrix}+\sum_{i\in S_{1}}\begin{pmatrix}x_{1\,i}\\ x_{2\,i}\\ \vdots\\ x_{d\,i}\end{pmatrix}\epsilon_{i}+\sum_{i\in S_{2}}\begin{pmatrix}\lvert x_{1\,i}\rvert\epsilon_{n+1}\\ \lvert x_{2\,i}\rvert\epsilon_{n+2}\\ \vdots\\ \lvert x_{d\,i}\rvert\epsilon_{n+d}\end{pmatrix}, $$
where $S_{1}$ is the index set of noise symbols to be left behind, and $S_{2}=\lbrace 1,2,\dotsc,n\rbrace\setminus S_{1}$ is the index set of noise symbols to be summarized. An efficient way to choose noise symbols to be summarized is discussed in (Kashiwagi, 2012).

References

1. J. L. D. Comba and J. Stolfi, “Affine arithmetic and its applications to computer graphics,” in Proc. VI Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI ’93), Recife, PE, Brazil, Oct. 1993. [Online]. Available: http://urlib.net/ibi/8JMKD3MGPBW34M/3D6UQ68 .
2. M. Kashiwagi, “An algorithm to reduce the number of dummy variables in affine arithmetic,” in Proc. 15th GAMM-IMACS International Symposium on Scientific Computing Computer Arithmetic and Verified Numerical Computations (SCAN 2012), Novosibirsk, Russia, Sep. 23-29, 2012, pp. 70-71. [Online]. Available: http://conf.nsc.ru/scan2012/scan2012_27 .
3. S. Miyajima and M. Kashiwagi, “A dividing method utilizing the best multiplication in affine arithmetic,” IEICE Electronics Express, vol. 1, no. 7, pp. 176-181, Jul. 2014, doi:10.1587/elex.1.176 .