Affine arithmetic
Encyclopedia
Affine arithmetic is a model for self-validated numerical analysis
. In AA, the quantities of interest are represented as affine combinations (affine forms) of certain primitive variables, which stand for sources of uncertainty in the data or approximations made during the computation.
Affine arithmetic is meant to be an improvement on interval arithmetic
(IA), and is similar to generalized interval arithmetic, first-order Taylor arithmetic, the center-slope model, and ellipsoid calculus — in the sense that it is an automatic method to derive first-order guaranteed approximations to general formulas.
Affine arithmetic is potentially useful in every numeric problem where one needs guaranteed enclosures to smooth functions, such as solving systems of non-linear equations, analyzing dynamical system
s, integrating
functions differential equation
s, etc. Applications include ray tracing, plotting
curve
s, intersecting implicit and parametric surface
s, error analysis
, process control
, worst-case analysis of electric circuits, and more.
where
are known floating-point numbers, and 
are symbolic variables whose values are only known to lie in the range [-1,+1].
Thus, for example, a quantity X which is known to lie in the range [3,7] can be represented by the affine form
, for some k. Conversely, the form 
implies that the corresponding quantity X lies in the range [3,17].
The sharing of a symbol
among two affine forms 
, 
implies that the corresponding quantities X, Y are partially dependent, in the sense that their joint range is smaller than the Cartesian product
of their separate ranges. For example, if
and
,
then the individual ranges of X and Y are [2,18] and [13,27], but the joint range of the pair (X,Y) is the hexagon with corners (2,27), (6,27), (18,19), (18,13), (14,13), (2,21) — which is a proper subset of the rectangle
[2,18]×[13,27].
for X and Y, one can obtain an affine form 
for Z = X + Y simply by adding the forms — that is, setting 
for every j. Similarly, one can compute an affine form 
for Z = 
X, where 
is a known constant, by setting 
for every j. This generalizes to arbitrary affine operations like Z = 
X + 
Y + 
.
, like multiplication 
or 
, cannot be performed exactly, since the result would not be an affine form of the 
. In that case, one should take a suitable affine function G that approximates F to first order, in the ranges implied by 
and 
; and compute 
, where 
is an upper bound for the absolute error 
in that range, and 
is a new symbolic variable not occurring in any previous form.
The form
then gives a guaranteed enclosure for the quantity Z; moreover, the affine forms 
jointly provide a guaranteed enclosure for the point (X,Y,...,Z), which is often much smaller than the Cartesian product of the ranges of the individual forms.
For smooth functions, the approximation errors made at each step are proportional to the square h2 of the width h of the input intervals. For this reason, affine arithmetic will often yield much tighter bounds than standard interval arithmetic (whose errors are proportional to h).
. This cannot be done by rounding each 
in a specific direction, because any such rounding would falsify the dependencies between affine forms that share the symbol 
. Instead, one must compute an upper bound 
to the roundoff error of each 
, and add all those 
to the coefficient 
of the new symbol 
(rounding up). Thus, because of roundoff errors, even affine operations like Z = 
X and Z = X + Y will add the extra term 
.
The handling of roundoff errors increases the code complexity and execution time of AA operations. In applications where those errors are known to be unimportant (because they are dominated by uncertainties in the input data and/or by the linearization errors), one may use a simplified AA library that does not implement roundoff error control.
be all input and computed quantities in use at some point during a computation. The affine forms for those quantities can be represented by a single coefficient matrix A and a vector b, where element 
is the coefficient of symbol 
in the affine form of 
; and 
is the independent term of that form. Then the joint range of the quantities — that is, the range of the point 
— is the image of the hypercube 
by the affine map from 
to 
defined by 
.
The range of this affine map is a zonotope bounding the joint range of the quantities
. Thus one could say that AA is a "zonotope arithmetic". Each step of AA usually entails adding one more row and one more column to the matrix A.
, the number of terms in an affine form may be proportional to the number of operations used to compute it. Thus, it is often necessary to apply "symbol condensation" steps, where two or more symbols 
are replaced by a smaller set of new symbols. Geometrically, this means replacing a complicated zonotope P by a simpler zonotope Q that encloses it. This operation can be done without destroying the first-order approximation property of the final zonotope.
. In this situation, the matrix and vector implementations are too wasteful of time and space.
In such situations, one should use a sparse
implementation. Namely, each affine form is stored as a list of pairs (j,
), containing only the terms with non-zero coefficient 
. For efficiency, the terms should be sorted in order of j. This representation makes the AA operations somewhat more complicated; however, the cost of each operation becomes proportional to the number of nonzero terms appearing in the operands, instead of the number of total symbols used so far.
This is the representation used by LibAffa.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
. In AA, the quantities of interest are represented as affine combinations (affine forms) of certain primitive variables, which stand for sources of uncertainty in the data or approximations made during the computation.
Affine arithmetic is meant to be an improvement on interval arithmetic
Interval arithmetic
Interval arithmetic, interval mathematics, interval analysis, or interval computation, is a method developed by mathematicians since the 1950s and 1960s as an approach to putting bounds on rounding errors and measurement errors in mathematical computation and thus developing numerical methods that...
(IA), and is similar to generalized interval arithmetic, first-order Taylor arithmetic, the center-slope model, and ellipsoid calculus — in the sense that it is an automatic method to derive first-order guaranteed approximations to general formulas.
Affine arithmetic is potentially useful in every numeric problem where one needs guaranteed enclosures to smooth functions, such as solving systems of non-linear equations, analyzing dynamical system
Dynamical system
A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
s, integrating
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...
functions differential equation
Differential equation
A differential equation is a mathematical equation for an unknown function of one or several variables that relates the values of the function itself and its derivatives of various orders...
s, etc. Applications include ray tracing, plotting
2D computer graphics
2D computer graphics is the computer-based generation of digital images—mostly from two-dimensional models and by techniques specific to them...
curve
Curve
In mathematics, a curve is, generally speaking, an object similar to a line but which is not required to be straight...
s, intersecting implicit and parametric surface
Parametric surface
A parametric surface is a surface in the Euclidean space R3 which is defined by a parametric equation with two parameters. Parametric representation is the most general way to specify a surface. Surfaces that occur in two of the main theorems of vector calculus, Stokes' theorem and the divergence...
s, error analysis
Error analysis
Error analysis is the study of kind and quantity of error that occurs, particularly in the fields of applied mathematics , applied linguistics and statistics.- Error analysis in numerical modeling :...
, process control
Process control
Process control is a statistics and engineering discipline that deals with architectures, mechanisms and algorithms for maintaining the output of a specific process within a desired range...
, worst-case analysis of electric circuits, and more.
Definition
In affine arithmetic, each input or computed quantity x is represented by a formulawhere
are known floating-point numbers, and are symbolic variables whose values are only known to lie in the range [-1,+1].Thus, for example, a quantity X which is known to lie in the range [3,7] can be represented by the affine form
, for some k. Conversely, the form implies that the corresponding quantity X lies in the range [3,17].The sharing of a symbol
among two affine forms , implies that the corresponding quantities X, Y are partially dependent, in the sense that their joint range is smaller than the Cartesian productCartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
of their separate ranges. For example, if
and,then the individual ranges of X and Y are [2,18] and [13,27], but the joint range of the pair (X,Y) is the hexagon with corners (2,27), (6,27), (18,19), (18,13), (14,13), (2,21) — which is a proper subset of the rectangle
Rectangle
In Euclidean plane geometry, a rectangle is any quadrilateral with four right angles. The term "oblong" is occasionally used to refer to a non-square rectangle...
[2,18]×[13,27].
Affine arithmetic operations
Affine forms can be combined with the standard arithmetic operations or elementary functions, to obtain guaranteed approximations to formulas.Affine operations
For example, given affine forms for X and Y, one can obtain an affine form for Z = X + Y simply by adding the forms — that is, setting for every j. Similarly, one can compute an affine form for Z = X, where is a known constant, by setting for every j. This generalizes to arbitrary affine operations like Z = X + Y + .Non-affine operations
A non-affine operation , like multiplication or , cannot be performed exactly, since the result would not be an affine form of the . In that case, one should take a suitable affine function G that approximates F to first order, in the ranges implied by and ; and compute , where is an upper bound for the absolute error in that range, and is a new symbolic variable not occurring in any previous form.The form
then gives a guaranteed enclosure for the quantity Z; moreover, the affine forms jointly provide a guaranteed enclosure for the point (X,Y,...,Z), which is often much smaller than the Cartesian product of the ranges of the individual forms.Chaining operations
Systematic use of this method allows arbitrary computations on given quantities to be replaced by equivalent computations on their affine forms, while preserving first-order correlations between the input and output and guaranteeing the complete enclosure of the joint range. One simply replaces each arithmetic operation or elementary function call in the formula by a call to the corresponding AA library routine.For smooth functions, the approximation errors made at each step are proportional to the square h2 of the width h of the input intervals. For this reason, affine arithmetic will often yield much tighter bounds than standard interval arithmetic (whose errors are proportional to h).
Roundoff errors
In order to provide guaranteed enclosure, affine arithmetic operations must account for the roundoff errors in the computation of the resulting coefficients. This cannot be done by rounding each in a specific direction, because any such rounding would falsify the dependencies between affine forms that share the symbol . Instead, one must compute an upper bound to the roundoff error of each , and add all those to the coefficient of the new symbol (rounding up). Thus, because of roundoff errors, even affine operations like Z = X and Z = X + Y will add the extra term .The handling of roundoff errors increases the code complexity and execution time of AA operations. In applications where those errors are known to be unimportant (because they are dominated by uncertainties in the input data and/or by the linearization errors), one may use a simplified AA library that does not implement roundoff error control.
Affine projection model
Affine arithmetic can be viewed in matrix form as follows. Let be all input and computed quantities in use at some point during a computation. The affine forms for those quantities can be represented by a single coefficient matrix A and a vector b, where element is the coefficient of symbol in the affine form of ; and is the independent term of that form. Then the joint range of the quantities — that is, the range of the point — is the image of the hypercube by the affine map from to defined by .The range of this affine map is a zonotope bounding the joint range of the quantities
. Thus one could say that AA is a "zonotope arithmetic". Each step of AA usually entails adding one more row and one more column to the matrix A.Affine form simplification
Since each AA operation generally creates a new symbol, the number of terms in an affine form may be proportional to the number of operations used to compute it. Thus, it is often necessary to apply "symbol condensation" steps, where two or more symbols are replaced by a smaller set of new symbols. Geometrically, this means replacing a complicated zonotope P by a simpler zonotope Q that encloses it. This operation can be done without destroying the first-order approximation property of the final zonotope.Matrix implementation
Affine arithmetic can be implemented by a global array A and a global vector b, as described above. This approach is reasonably adequate when the set of quantities to be computed is small and known in advance. In this approach, the programmer must maintain externally the correspondence between the row indices and the quantities of interest. Global variables hold the number m of affine forms (rows) computed so far, and the number n of symbols (columns) used so far; these are automatically updated at each AA operation.Vector implementation
Alternatively, each affine form can be implemented as a separate vector of coefficients. This approach is more convenient for programming, especially when there are calls to library procedures that may use AA internally. Each affine form can be given a mnemonic name; it can be allocated when needed, be passed to procedures, and reclaimed when no longer needed. The AA code then looks much closer to the original formula. A global variable holds the number n of symbols used so far.Sparse vector implementation
On fairly long computations, the set of "live" quantities (that will be used in future computations) is much smaller than the set of all computed quantities; and ditto for the set of "live" symbols. In this situation, the matrix and vector implementations are too wasteful of time and space.In such situations, one should use a sparse
Sparse array
In computer science, a sparse array is an array in which most of the elements have the same value . The occurrence of zero elements in a large array is inconvenient for both computation and storage...
implementation. Namely, each affine form is stored as a list of pairs (j,
), containing only the terms with non-zero coefficient . For efficiency, the terms should be sorted in order of j. This representation makes the AA operations somewhat more complicated; however, the cost of each operation becomes proportional to the number of nonzero terms appearing in the operands, instead of the number of total symbols used so far.This is the representation used by LibAffa.
External links
- http://www.dcc.unicamp.br/~stolfi/EXPORT/projects/affine-arith/Welcome.html Stolfi's page on AA.
- http://savannah.nongnu.org/projects/libaffa LibAffa, an LGPL implementation of affine arithmetic.
- http://sourceforge.net/projects/asol/ ASOL, a branch-and-prune method to find all solutions to systems of nonlinear equations using affine arithmetic