An Introduction to Affine Arithmetic

J. Stolfi, L.H. de Figueiredo

Abstract


Affine arithmetic (AA) is a model for self-validated computation which, like standard interval arithmetic (IA), produces guaranteed enclosures for computed quantities, taking into account any uncertainties in the input data as well as all internal truncation and roundoff errors. Unlike standard IA, the quantity representations used by AA are first-order approximations, whose error is generally quadratic in the width of input intervals. In many practical applications, the higher asymptotic accuracy of AA more than compensates for the increased cost of its operations.

References


[1] R. Baker Kearfott, Algorithm 763: INTERVAL ARITHMETIC — A Fortran 90 module for an interval data type, ACM Transactions on Mathematical Software, 22, No. 4 (1996), 385–392.

W. Barth, R. Lieger, and M. Schindler. Ray tracing general parametric surfaces using interval arithmetic. The Visual Computer, 10, No. 7 (1994), 363–371.

A. Bowyer, R. Martin, H. Shou and I. Voiculescu, Affine intervals in a CSG geometric modeller, in “Proc. Uncertainty in Geometric Computations”, pp. 1–14. Kluwer Academic Publishers, July, 2001.

F.L. Chernousko and A.I. Ovseevich, Method of ellipsoids: Guaranteed estimation in dynamical systems under uncertainties and control, in “Abstracts of the International Conference on Interval and Computer-Algebraic Methods in Science and Engineering (INTERVAL/94)”, p. 66, St. Petersburg, Russia, April, 1994.

J.L.D. Comba and J. Stolfi, Affine arithmetic and its applications to computer graphics, in “Anais do VI Simpósio Brasileiro de Computação Gráfica e Processamento de Imagens (SIBGRAPI’93)”, pp. 9–18, Recife (Brazil), October, 1993.

A. de Cusatis Jr., L.H. Figueiredo and M. Gattass, Interval methods for ray casting surfaces with affine arithmetic, in “Poceedings of SIBGRAPI’99 - the 12th Brazilian Symposium on Computer Graphics and Image Processing”, pp. 65–71, 1999.

L.H. de Figueiredo, Surface intersection using affine arithmetic, in “Proc. Graphics Interface ’96”, pp. 168–175, May, 1996.

L.H. de Figueiredo and J. Stolfi, Affine arithmetic: Concepts and applications, Numerical Algorithms, (2004), to appear.

L.H. de Figueiredo, J. Stolfi and L. Velho, Approximating parametric curves with strip trees using affine arithmetic, Computer Graphics Forum, 22, No. 2 (2003), 171–179.

L.H. de Figueiredo and J. Stolfi, “Self-Validated Numerical Methods and Applications”, Brazilian Mathematics Colloquium monographs, IMPA/CNPq, Rio de Janeiro, Brazil, 1997.

T. Duff, Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry, in “Proc. SIGGRAPH’92”, pp. 131–138, July, 1992.

N. Femia and G. Spagnuolo, True worst-case circuit tolerance analysis using genetic algorithm and affine arithmetic - Part I, IEEE Trans. on Circuits and Systems, 47, No. 9 (2000), 1285–1296.

O. Gay, Libaa - C++ affine arithmetic library for GNU/Linux, Available at http://www.nongnu.org/libaa/, April, 2003.

M. Gleicher and M. Kass, An interval refinement technique for surface intersection, in “Proc. Graphics Interface ’92”, pp. 242–249, May, 1992.

S. Goldenstein, C. Vogler and D. Metaxas, “Cue integration using affine arithmetic and gaussians”, Technical Report MS-CIS-02-06, University of Pennsylvania, 2002.

L.J. Guibas, L. Ramshaw and J. Stolfi, The kinetic framework for computational geometry. in “Proc. 24th Annual Symposium on Foundations of Computer Science (FOCS)”, pp. 100–111, Tucson, Arizona, November, 1983.

E. Hansen, Global optimization using interval analysis — The one-dimensional case, Journal of Optimization Theory and Applications, 29, No. 3 (1979), 331–344.

E. Hansen, Global optimization using interval analysis — The multidimensional case, Numerische Mathematik, 34, No. 3 (1980), 247–270.

E. Hansen, “Global Optimization using Interval Analysis”, Number 165 in Monographs and Textbooks in Pure and Applied Mathematics, M. Dekker, New York, 1992.

E.R. Hansen, A generalized interval arithmetic, in “Interval Mathematics” (K. Nickel, ed.), Lecture Notes in Computer Science 29, pp. 7–18, Springer, 1975.

J. Hass, M. Hutchings and R. Schlafly, The double bubble conjecture, Electronic Research Announcements of the American Mathematical Society, 1 (1995), 98–102.

W. Heidrich, Ph. Slusallek and H.-P. Seidel, Sampling procedural shaders using affine arithmetic, ACM Transactions on Graphics (TOG), 17, No. 3, (1998), 158–176.

K. Ichida and Y. Fujii, An interval arithmetic method for global optimization, Computing, 23 (1979), 85–97.

IEEE standard for binary floating-point arithmetic, ANSI/IEEE Standard 754-1985, 1985.

Y. Kanazawa and S. Oishi, A numerical method of proving the existence of solutions for nonlinear ODEs using affine arithmetic, in “Proc. SCAN’02 – 10th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics”, September, 2002.

R.B. Kearfott, An interval branch and bound algorithm for bound constrained optimization problems, Journal of Global Optimization, 2 (1992), 259–280.

O. Kn¨uppel and T. Simenec, “PROFIL/BIAS extensions”, Technical Report 93.5, Department of Computer Science III, Technical University of Hamburg-Harburg, November, 1993.

O. Kn¨uppel, “BIAS — Basic Interval Arithmetic Subroutines”, Technical Report 93.3, Department of Computer Science III, Technical University of Hamburg-Harburg, July, 1993.

O. Kn¨uppel. “PROFIL — Programmer’s Runtime Optimized Fast Interval Library”, Technical Report 93.4, Department of Computer Science III, Technical University of Hamburg-Harburg, July, 1993.

V. Kreinovich and D.J. Berleant, “Interval computations”, WWW document at http://www.cs.utep.edu/interval-comp/main.html, 2002.

A.B. Kurzhanski, Ellipsoidal calculus for uncertain dynamics, in “Abstracts of the International Conference on Interval and Computer-Algebraic Methods in Science and Engineering (INTERVAL/94)”, p. 162, St. Petersburg, Russia, April, 1994.

A. Lemke, L. Hedrich and E. Barke, Analog circuit sizing based on formal methods using affine arithmetic, in “Proc. ICCAD-2002 - International Conference on Computer Aided Design”, pp. 486–489, November, 2002.

F. Messine, Extentions of affine arithmetic: Application to unconstrained global optimization, Journal of Universal Computer Science, 8, No. 11 (2002), 992–1015.

F. Messine and A. Mahfoudi, Use of affine arithmetic in interval optimization algorithms to solve multidimensional scaling problems, in “Proc. SCAN’98 - IMACS/GAMM International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics”, pp. 22–25, Budapest, Hungary, September, 1998, to appear in Reliable Computing.

D. Michelucci and J.-M. Moreau, Lazy arithmetic, IEEE Transactions on Computers, 46, No. 9 (1997), 961–975.

D.P. Mitchell, Robust ray intersection with interval arithmetic, in “Proc. Graphics Interface ’90”, pp. 68–74, May, 1990.

R. Moore, E. Hansen and A. Leclerc, Rigorous methods for global optimization, in “Recent Advances in Global Optimization”, (C.A. Floudas and P.M. Pardalos, eds.), pp. 321–342. Princeton University Press, Princeton, NJ, 1992.

R.E. Moore, “Interval Analysis”, Prentice-Hall, 1966.

R.E. Moore, “Methods and Applications of Interval Analysis”, SIAM, Philadelphia, 1979.

S.P. Mudur and P.A. Koparkar, Interval methods for processing geometric objects, IEEE Computer Graphics & Applications, 4, No. 2 (1984), 7–17.

A. Neumaier, Taylor forms: Use and limits. Reliable Computing, 9, No. 1 (2003), 43–79.

H. Ratschek and R.L.Voller, What can interval analysis do for global optimization? Journal of Global Optimization, 1, No. 2 (1991), 111–130.

H. Ratschek and J. Rokne, “New Computer Methods for Global Optimization”, Ellis Horwood Ltd., 1988.

Reliable computing, Kluwer Academic Publishers, 1997, formerly Interval Computations.

J.M. Snyder, Interval analysis for computer graphics. in “Proc. SIGGRAPH’ 92”, pp. 121–130, July 1992, special Issue of ACM Computer Graphics.

J. Stolfi, “LIBAA: An affine arithmetic library in C”, 1993, avaliable at http://www.dcc.unicamp.br/~stolfi/.

K.G. Suffern and E.D. Fackerell, Interval methods in computer graphics. Com- puters & Graphics, 15, No. 3 (1991), 331–340.

G. Taubin, Rasterizing algebraic curves and surfaces, IEEE Computer Graphics and Applications, 14 (1994), 14–23.

R. van Iwaarden, “An Improved Unconstrained Global Optimization Algorithm”, PhD thesis, Department of Mathematics, University of Colorado at Denver, 1996.

Q. Zhang and R.R. Martin, Polynomial evaluation using affine arithmetic for curve drawing, in “Proc. of Eurographics UK 2000 Conference”, pp. 49–56, 2000.




DOI: https://doi.org/10.5540/tema.2003.04.03.0297

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia