FILIB++, a fast interval library supporting containment computations

ABSTRACT

filib++ is an extension of the interval library filib originally developed at the University of Karlsruhe. The most important aim of filib is the fast computation of guaranteed bounds for interval versions of a comprehensive set of elementary functions. filib++ extends this library in two aspects. First, it adds a second mode, the extended mode, that extends the exception-free computation mode (using special values to represent infinities and NaNs known from the IEEE floating-point standard 754) to intervals. In this mode, the so-called containment sets are computed to enclose the topological closure of a range of a function over an interval. Second, our new design uses templates and traits classes to obtain an efficient, easily extendable, and portable C++ library.

REFERENCES

• 1: Alefeld, G. and Herzberger, J. 1983. Introduction to Interval Computations. Academic Press, New York, NY.
• 2: Chiriaev, D. and Walster, G. 1999. Interval arithmetic specification. www.mscs.mu.edu/˜globsol/walster-papers.html.
• 3: R. Hammer , D. Ratz , U. Kulisch , M. Hocks, C++ Toolbox for Verified Scientific Computing I: Basic Numerical Problems, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 4: Hofschuster, W. and Krämer, W. 1998a. FI_LIB, eine schnelle und portable Funktionsbibliothek für reelle Argumente und reelle Intervalle im IEEE-double-Format. Preprint 98/7, Institut für Wissenschaftliches Rechnen und Mathematische Modellbildung, Universität Karlsruhe. http://www.math.uni-wuppertal.de/wrswt/preprints/prep987.ps.
• 5: Hofschuster, W. and Krämer, W. 1998b. fi_lib sources. http://www.math.uni-wuppertal.de/WRSWT/software.html.
• 6: Hofschuster, W. and Krämer, W. 2004. C-XSC 2.0---a C++ class library for extended scientific computing. In Numerical Software with Result Verification, R. Alt, A. Frommer, B. Kearfott, and W. Luther, Eds. Springer Lecture Notes in Computer Science, Vol. 2991, 15--35.
• 7: Hofschuster, W., Krämer, W., Wedner, S., and Wiethoff, A. 2001. C-XSC 2.0---a C++ class library for extended scientific computing. Preprint 01/1, Wissenschaftliches Rechnen/Software Technologie, Universität Wuppertal. http://www.math.uni-wuppertal.de/wrswt/preprints/prep_01_1.ps.
• 8: R. Baker Kearfott, Algorithm 763: INTERVAL_ARITHMETIC: a Fortran 90 module for an interval data type, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.385-392, Dec. 1996 [doi>10.1145/235815.235816]
• 9: R. B. Kearfott , M. Dawande , K. Du , C. Hu, Algorithm 737: INTLIB---a portable Fortran 77 interval standard-function library, ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.447-459, Dec. 1994 [doi>10.1145/198429.198433]
• 10: R. Baker Kearfott , Manuel Novoa, III, Algorithm 681: INTBIS, a portable interval Newton/bisection package, ACM Transactions on Mathematical Software (TOMS), v.16 n.2, p.152-157, June 1990 [doi>10.1145/78928.78931]
• 11: G. F. Corliss , Rudi Klatte, C-XSC: A C++ Class Library for Extended Scientific Computing, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 12: Knüppel, O. 1994. Profil/bias---a fast interval library. Computing 53, 277--287.
• 13: Krämer, W. 2002. Advanced software tools for validated computing. In Proceedings of the 31st Spring Conference of the Union of Bulgarian Mathematicians. Union of Bulgarian Mathematicians, Borovets, Bulgaria, 344--355.
• 14: Krämer, W. and Wolff von Gudenberg, J. 2001. Scientific Computing, Validated Numerics, Interval Methods. Kluwer Academic/Plenum Publishers, New York, NY.
• 15: Ulrich Kulisch , Rudolf Lohner , Axel Facius, Perspectives on Enclosure Methods, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 16: Lerch, M., Tischler, G., Wolff von Gudenberg, J., Hofschuster, W., and Krämer, W. 2001. The interval library filib++ 2.0 - design, features and sample programs. Preprint BUGHW-WRSWT 2001/4, Universität Wuppertal.
• 17: Lerch, M. and Wolff von Gudenberg, J. 2000. fi_lib++ : Specification, implementation and test of a library for extended interval arithmetic. In RNC4 Proceedings. 111--123.
• 18: Myers, N. 1995. Traits: a new and useful template technique. C++ Report.
• 19: Rump, S., M. 1998. Intlab--interval laboratory. In Developments in Reliable Computing, T. Csendes, Ed. KluwerAcademic Publisher, New York, NY.
• 20: Rump, S. M. 1999. Fast and parallel interval arithmetic. Bit 39, 3 (Sept.) 534--554.
• 21: Bjarne Stroustrup, The C++ Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 22: Sun Microsystems 2001. C++ Interval Arithmetic Programming Reference (Forte Developer 6 update 2). Sun Microsystems. http://www.sun.com/forte/cplusplus/interval/index.html.
• 23: Walster, G. et al. 2000a. The “simpl” closed interval system. Tech. rep., Sun Microsystems.
• 24: Walster, G. W. et al. 2000b. Extended real intervals and the topological closure of extended real numbers. Tech. rep., Sun Microsystems.
• 25: Walster, W. G., Hansen, E. R., and D. P. J. 2000. Extended real intervals and the topological closure of extended real relations. Tech. rep., Sun Microsystems.
• 26: Wolff von Gudenberg, J. 2000. Interval arithmetic and multimedia architectures. Tech. Rep. 265, Informatik, Universität Würzburg.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Interval arithmetic

General Terms:
Algorithms, Reliability, Standardization

Keywords:
C++ class library, containment computations, containment sets, exception free computations, filib++, guaranteed numerical results, interval arithmetic, interval computations, templates, traits class, validated numerics, validation