×

Motivations for an arbitrary precision interval arithmetic and the MPFI library. (English) Zbl 1078.65543

Summary: This paper justifies why an arbitrary precision interval arithmetic is needed. To provide accurate results, interval computations require small input intervals; this explains why bisection is so often employed in interval algorithms. The MPFI library has been built in order to fulfill this need. Indeed, no existing library met the required specifications. The main features of this library are briefly given and a comparison with a fixed-precision interval arithmetic, on a specific problem, is presented. It shows that the overhead due to the multiple precision is completely acceptable. Eventually, some applications based on MPFI are given: robotics, isolation of polynomial real roots (by an algorithm combining symbolic and numerical computations) and approximation of real roots with arbitrary accuracy.

MSC:

65G30 Interval and finite arithmetic
65H05 Numerical computation of solutions to single equations
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aberth, O.: Precise Numerical Methods Using C++, Academic Press, 1998. · Zbl 0932.65001
[2] Aberth, O. and Schaefer, M. J.: Precise Computation Using Range Arithmetic, via C++, ACM TOMS 18 (4) (1992), pp. 481–491. · Zbl 0892.65028 · doi:10.1145/138351.138377
[3] Alefeld, G. and Herzberger, J.: Introduction to Interval Analysis, Academic Press, 1983. · Zbl 0552.65041
[4] Auzinger, W. and Stetter, H. J.: An Elimination Algorithm for the Computation of All Zeros of a System of Multivariate Polynomial Equations, Int. Series in Numerical Mathematics, Birkhäuser 86 (1988), pp. 11–30. · Zbl 0658.65047
[5] Berz, M. and Hoefkens, J.: Verified High-Order Inversion of Functional Dependencies and Interval Newton Methods, Reliable Computing 7(5) (2001), pp. 379–398. · Zbl 1016.65030 · doi:10.1023/A:1011423909873
[6] Bini, D. and Fiorentino, G.: Numerical Computation of Polynomial Tools: MPSolve–Version 2.0, 1998, http://www.dmi.unict.it/-marotta/Articoli/mpsolve.ps.
[7] Brattka, V. and Hertling, P.: Feasible Real Random Access Machines, J. of Complexity 14(4) (1998), pp. 490–526. · Zbl 0913.68099 · doi:10.1006/jcom.1998.0488
[8] Brent, R. P.: A Fortran Multiple-Precision Arithmetic Package, ACM TOMS 4(1978), pp. 57–70. · doi:10.1145/355769.355775
[9] CANTResearch Group: Arithmos: A Reliable Integrated Computational Environment, University of Antwerpen, Belgium, 2001, http://win-www.uia.ac.be/u/cant/arithmos/.
[10] Collins, G. and Akritas, A.: Polynomial Real Root Isolation Using Descartes’ Rule of Signs, in: SYMSAC, 1976, pp. 272–275.
[11] Connell, A. E. and Corless, R. M.: An Experimental Interval Arithmetic Package in Maple, in: Num. Analysis with Automatic Result Verification, 1993. · Zbl 0829.65149
[12] Cox, D., Little, J., and O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergraduate Texts in Mathematics, Springer-Verlag, 1992. · Zbl 0756.13017
[13] Daney, D., Hanrot, G., Lefèvre, V., Pelissier, P., Rouillier, F., and Zimmermann, P.: The MPFR Library, 2001, http://www.mpfr.org/.
[14] Fortune, S.: Polynomial Root Finding Using Iterated Eigenvalue Computation, in: Proc. ISSAC’01, 2001, pp. 121–128. · Zbl 1356.65121
[15] Geulig, I. and Krämer, W.: Intervallrechnung in Maple–Die Erweiterung intpakX zum Paket intpak der Share-Library, Technical Report 99/2, Universität Karlsruhe, 1999.
[16] Hansen, E.: Global Optimization Using Interval Analysis, Marcel Dekker, 1992. · Zbl 0762.90069
[17] Hansen, E. and Greenberg, R. I.: An Interval Newton Method, J. of Applied Math. and Computing 12 (1983), pp. 89–98. · Zbl 0526.65040 · doi:10.1016/0096-3003(83)90001-2
[18] Hansen, E. and Sengupta, S.: Bounding Solutions of Systems of Equations Using Interval Analysis, BIT 21(1981), pp. 203–211. · Zbl 0455.65037
[19] Hickey, T.-J., Ju, Q., and Van Emden, M.-H.: Interval Arithmetic: from Principles to Implementation, J. of ACM 48 (5) (2001), pp. 1038–1068. · Zbl 1323.65047 · doi:10.1145/502102.502106
[20] Jaulin, L., Kieffer, M., Didrit, O., and Walter, E.: Applied Interval Analysis, Springer Verlag, 2001. · Zbl 1023.65037
[21] Kearfott, R. B.: Rigorous Global Search: Continuous Problems, Kluwer Academic Publishers, 1996. · Zbl 0876.90082
[22] Kearfott, R. B., Dawande, M., Du, K.-S., and Hu, C.-Y.: Algorithm 737: INTLIB: A Portable Fortran 77 Interval Standard-Function Library, ACM TOMS 20(4) (1994), pp. 447–459. · Zbl 0888.65057 · doi:10.1145/198429.198433
[23] Kearfott, R. B. and Walster, G. W.: On Stopping Criteria in Verified Nonlinear Systems or Optimization Algorithms, ACM TOMS 26(3) (2000), pp. 373–389. · Zbl 1365.65139 · doi:10.1145/358407.358418
[24] Keiper, J.: Interval Arithmetic in Mathematica, Interval Computations3 (1993), pp. 76–87. · Zbl 0829.65061
[25] Klatte, R., Kulisch, U., Lawo, C., Rauch, M., and Wiethoff, A.: C–XSC: A C++ Class Library for Extended Scientific Computing, Springer Verlag, 1993. · Zbl 0814.68035
[26] Krämer, W., Kulisch, U., and Lohner, R.: Numerical Toolbox for Verified Computing II– Advanced Numerical Problems, Springer, 2002.
[27] Knueppel, O.: PROFIL/BIAS–A Fast Interval Library, Computing 53(3–4) (1994), pp. 277– 287. · Zbl 0808.65055 · doi:10.1007/BF02307379
[28] Langlois, P. and Revol, N.:Validating Polynomial Numerical Computations with Complementary Automatic Methods, submitted to Mathematics and Computers in Simulation, 4th revision. INRIA research report RR–4205, 2001, http://www.inria.fr/rrrt/rr-4205.html.
[29] Lerch, M., Tischler, G., Wolff von Gudenberg, J., Hofschuster, W., and Krämer, W.: The Interval Library filib++ 2.0, Preprint 2001/4, Universität Wuppertal, 2001, http://www.math.uni-wuppertal.de/org/WRST/software/filib.html. · Zbl 1365.65140
[30] Merlet, J. P.: Les Robots parallèles, Robotique, Hermès Paris, 1990.
[31] Moore, R. E.: Interval Analysis, Prentice Hall, 1966. · Zbl 0176.13301
[32] Müller, N.: The iRRAM: Exact Arithmetic in C++, in: Workshop on Constructivity and Complexity in Analysis, Swansea, 2000. · Zbl 0985.65523
[33] Neumaier, A.: Interval Methods for Systems of Equations, Cambridge University Press, 1990. · Zbl 0715.65030
[34] Revol, N.: Interval Newton Iteration in Multiple Precision for the Univariate Case, Numerical Algorithms 34 (2) (2003), pp. 417–426. · Zbl 1035.65051 · doi:10.1023/B:NUMA.0000005354.92791.41
[35] Revol, N. and Rouillier, F.: The MPFI Library, 2001, http://perso.ens-lyon.fr/nathalie.revol/software.html. · Zbl 1078.65543
[36] Rouillier, F.: Solving Zero-Dimensional Systems through the Rational Univariate Representation, Journal of Applicable Algebra in Engineering, Communication and Computing 9 (5) (1999), pp. 433–461. · Zbl 0932.12008 · doi:10.1007/s002000050114
[37] Rouillier, F.: RS / Real Solutions, 2000, http://fgbrs.lip6.fr/-rouillie/Software/RS/.
[38] Rouillier, F. and Zimmermann, P.: Efficient Isolation of Polynomial Real Roots, J. of Computational and Applied Math. 162 (1) (2004), pp. 33–50. · Zbl 1040.65041 · doi:10.1016/j.cam.2003.08.015
[39] Rump, S.: Fast and Parallel Interval Arithmetic, BIT 39(3) (1999), pp. 534–554. · Zbl 0942.65048 · doi:10.1023/A:1022374804152
[40] Rump, S.: INTLAB–Interval Laboratory, in: Csendes, T. (ed.), Developments in Reliable Computing, Kluwer Academic Publishers, 1999, pp. 77–104.
[41] Sun Microsystems: C++ Interval Arithmetic Programming Reference, 2000.
[42] Vincent, A.-H.: Sur la résolution des équations numériques, Journal de Mathématiques Pures et Appliquées (1836), pp. 341–372.
[43] Yohe, J. M.: Portable Software for Interval Arithmetic, Computing, Suppl. 2 (1980), pp. 211–229.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.