Affine arithmetic

Affine arithmetic

Affine arithmetic (AA) 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 systems, integrating functions differential equations, etc. Applications include ray tracing, plotting curves, intersecting implicit and parametric surfaces, error analysis, process control, worst-case analysis of electric circuits, and more.

Definition

In affine arithmetic, each input or computed quantity "x" is represented by a formulax = x_0 + x_1 epsilon_1 + x_2 epsilon_2 + {}cdots{} + x_n epsilon_nwhere x_0, x_1, x_2,dots, x_n are known floating-point numbers, and epsilon_1, epsilon_2,epsilon_n 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 x = 5 + 2 epsilon_k, for some "k". Conversely, the form x = 10 + 2 epsilon_3 - 5 epsilon_8 implies that the corresponding quantity "X" lies in the range [3,17] .

The sharing of a symbol epsilon_j among two affine forms x, y 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 x = 10 + 2 epsilon_3 - 6 epsilon_8 and y = 20 + 3 epsilon_4 + 4 epsilon_8, 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] .

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 x,y for "X" and "Y", one can obtain an affine form z for "Z" = "X" + "Y" simply by adding the forms — that is, setting z_j gets x_j + y_j for every "j". Similarly, one can compute an affine form z for "Z" = alpha"X", where alpha is a known constant, by setting z_j gets alpha x_j for every "j". This generalizes to arbitrary affine operations like "Z" = alpha"X" + eta"Y" + gamma.

Non-affine operations

A non-affine operation Z gets F(X,Y,dots), like multiplication Z gets X Y or Z gets sin(X), cannot be performed exactly, since the result would not be an affine form of the epsilon_i. In that case, one should take a suitable affine function "G" that approximates "F" to first order, in the ranges implied by x and y; and compute z gets G(x,y,dots) + z_kepsilon_k, where z_k is an upper bound for the absolute error |F-G| in that range, and epsilon_k is a new symbolic variable not occurring in any previous form.

The form z then gives a guaranteed enclosure for the quantity "Z"; moreover, the affine forms x,y,dots,z 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 "h"2 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 z_j. This cannot be done by rounding each z_j in a specific direction, because any such rounding would falsify the dependencies between affine forms that share the symbol epsilon_j. Instead, one must compute an upper bound delta_j to the roundoff error of each z_j, and add all those delta_j to the coefficient z_k of the new symbol epsilon_k (rounding up). Thus, because of roundoff errors, even affine operations like "Z" = alpha"X" and "Z" = "X" + "Y" will add the extra term z_kepsilon_k.

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 X_1,X_2,dots,X_m 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 A_{i,j} is the coefficient of symbol epsilon_j in the affine form of "X_i"; and b_i is the independent term of that form. Then the joint range of the quantities — that is, the range of the point (X_1,X_2,dots,X_m) — is the image of the hypercube U^n = [-1,+1] ^n by the affine map from U^n to R^m defined by epsilon o A epsilon + b.

The range of this affine map is a zonotope bounding the joint range of the quantities X_1,X_2,dots,X_m. 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 epsilon_k, 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 epsilon_k 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.

Implementation

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.

parse 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 epsilon_j. 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,x_j), containing only the terms with non-zero coefficient x_j. 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.

References

*L. H. de Figueiredo and J. Stolfi (2004) "Affine arithmetic: concepts and applications." "Numerical Algorithms" 37 (1–4), 147–158.
* J. L. D. Comba and J. Stolfi (1993), "Affine arithmetic and its applications to computer graphics". "Proc. SIBGRAPI'93 — VI Simpósio Brasileiro de Computação Gráfica e Processamento de Imagens (Recife, BR)", 9–18.
* L. H. de Figueiredo and J. Stolfi (1996), "Adaptive enumeration of implicit surfaces with affine arithmetic". "Computer Graphics Forum", 15 "5", 287–296.
* W. Heidrich (1997), "A compilation of affine arithmetic versions of common math library functions". Technical Report 1997-3, Universität Erlangen-Nürnberg.
* M. Kashiwagi (1998), "An all solution algorithm using affine arithmetic". "NOLTA'98 — 1998 International Symposium on Nonlinear Theory and its Applications (Crans-Montana, Switzerland)", 14–17.
* L. Egiziano, N. Femia, and G. Spagnuolo (1998), "New approaches to the true worst-case evaluation in circuit tolerance and sensitivity analysis — Part II: Calculation of the outer solution using affine arithmetic". "Proc. COMPEL'98 — 6th Workshop on Computer in Power Electronics (Villa Erba, Italy)", 19–22.
* W. Heidrich, Ph. Slusallek, and H.-P. Seidel (1998), "Sampling procedural shaders using affine arithmetic". "ACM Transactions on Graphics (TOG)", 17 "3", 158–176.
* F. Messine and A. Mahfoudi (1998), "Use of affine arithmetic in interval optimization algorithms to solve multidimensional scaling problems". "Proc. SCAN'98 — IMACS/GAMM International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (Budapest, Hungary)", 22–25.
* A. de Cusatis Jr., L. H. Figueiredo, and M. Gattass (1999), "Interval methods for ray casting surfaces with affine arithmetic". "Proc. SIBGRAPI'99 — 12th Brazilian Symposium on Computer Graphics and Image Processing", 65–71.
* K. Bühler and W. Barth (2000), "A new intersection algorithm for parametric surfaces based on linear interval estimations". "Proc. SCAN 2000 / Interval 2000 — 9th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics", ???–???.
* I. Voiculescu, J. Berchtold, A. Bowyer, R. R. Martin, and Q. Zhang (2000), "Interval and affine arithmetic for surface location of power- and Bernstein-form polynomials". "Proc. Mathematics of Surfaces IX", 410–423. Springer, ISBN 1-85233-358-8.
* Q. Zhang and R. R. Martin (2000), "Polynomial evaluation using affine arithmetic for curve drawing". "Proc. of Eurographics UK 2000 Conference", 49–56. ISBN 0-9521097-9-4.
* D. Michelucci (2000), "Reliable computations for dynamic systems". "Proc. SCAN 2000 / Interval 2000 — 9th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics", ???–???.
* N. Femia and G. Spagnuolo (2000), "True worst-case circuit tolerance analysis using genetic algorithm and affine arithmetic — Part I". "IEEE Transactions on Circuits and Systems", 47 "9", 1285–1296.
* R. Martin, H. Shou, I. Voiculescu, and G. Wang (2001), "A comparison of Bernstein hull and affine arithmetic methods for algebraic curve drawing". "Proc. Uncertainty in Geometric Computations", 143–154. Kluwer Academic Publishers, ISBN 0-7923-7309-X.
* A. Bowyer, R. Martin, H. Shou, and I. Voiculescu (2001), "Affine intervals in a CSG geometric modeller". "Proc. Uncertainty in Geometric Computations", 1–14. Kluwer Academic Publishers, ISBN 0-7923-7309-X.
* T. Kikuchi and M. Kashiwagi (2001), "Elimination of non-existence regions of the solution of nonlinear equations using affine arithmetic". "Proc. NOLTA'01 — 2001 International Symposium on Nonlinear Theory and its Applications".
* T. Miyata and M. Kashiwagi (2001), "On range evaluation of polynomials of affine arithmetic". "Proc. NOLTA'01 - 2001 International Symposium on Nonlinear Theory and its Applications".
* Y. Kanazawa and S. Oishi (2002), "A numerical method of proving the existence of solutions for nonlinear ODEs using affine arithmetic". "Proc. SCAN'02 — 10th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics".
* H. Shou, R. R.Martin, I. Voiculescu, A. Bowyer, and G. Wang (2002), "Affine arithmetic in matrix form for polynomial evaluation and algebraic curve drawing". "Progress in Natural Science", 12 "1", 77–81.
* A. Lemke, L. Hedrich, and E. Barke (2002), "Analog circuit sizing based on formal methods using affine arithmetic". "Proc. ICCAD-2002 — International Conference on Computer Aided Design", 486–489.
* F. Messine (2002), "Extensions of affine arithmetic: Application to unconstrained global optimization". "Journal of Universal Computer Science", 8 "11", 992–1015.
* K. Bühler (2002), "Implicit linear interval estimations". "Proc. 18th Spring Conference on Computer Graphics (Budmerice, Slovakia)", 123–132. ACM Press, ISBN 1-58113-608-0.
* L. H. de Figueiredo, J. Stolfi, and L. Velho (2003), "Approximating parametric curves with strip trees using affine arithmetic". "Computer Graphics Forum", 22 "2", 171–179.
* C. F. Fang, T. Chen, and R. Rutenbar (2003), "Floating-point error analysis based on affine arithmetic". "Proc. 2003 International Conf. on Acoustic, Speech and Signal Processing".
* A. Paiva, L. H. de Figueiredo, and J. Stolfi (2006), "Robust visualization of strange attractors using affine arithmetic". "Computers & Graphics", 30 "6", 1020– 1026.

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • affine arithmetic — noun A model for self validated numerical analysis in which quantities are represented as affine combinations (called affine forms) of certain primitive variables that stand for sources of uncertainty in data or approximations made during… …   Wiktionary

  • Arithmetic of abelian varieties — In mathematics, the arithmetic of abelian varieties is the study of the number theory of an abelian variety, or family of those. It goes back to the studies of Fermat on what are now recognised as elliptic curves; and has become a very… …   Wikipedia

  • Arithmetic and geometric Frobenius — In mathematics, the Frobenius endomorphism is defined in any commutative ring R that has characteristic p , where p is a prime number. Namely, the mapping φ that takes r in R to r p is a ring endomorphism of R .The image of φ is then R p , the… …   Wikipedia

  • Glossary of arithmetic and Diophantine geometry — This is a glossary of arithmetic and Diophantine geometry in mathematics, areas growing out of the traditional study of Diophantine equations to encompass large parts of number theory and algebraic geometry. Much of the theory is in the form of… …   Wikipedia

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Nathan Hurst — (born 1977) is an Australian programmer. He currently (April 2011) works as a software engineer at Google. Among the founders of the Inkscape project, he also contributes to projects such as gtkmathview, matplotlib, and the organ simulator aeolus …   Wikipedia

  • Space group — In mathematics and geometry, a space group is a symmetry group, usually for three dimensions, that divides space into discrete repeatable domains. In three dimensions, there are 219 unique types, or counted as 230 if chiral copies are considered… …   Wikipedia

  • Courbe Elliptique — Une sélection de courbes cubiques réelles définies par l équation y2 = x3 + ax + b.. La région montrée est [ 3,3]². La courbe pour a=b=0 n est pas elliptique. En mathématiques, une courbe elliptique est un cas particulier de courbe algébrique,… …   Wikipédia en Français

  • Courbes Elliptiques — Courbe elliptique Une sélection de courbes cubiques réelles définies par l équation y2 = x3 + ax + b.. La région montrée est [ 3,3]². La courbe pour a=b=0 n est pas elliptique. En mathématiques, une courbe elliptique est un cas particulier de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”