On design and implementation of a generic number type for real algebraic number computations based on expression dags. (English) Zbl 1229.68084

Mörig, Marc; Rössling, Ivo; Schirra, Stefan

Math. Comput. Sci. 4, No. 4, 539-556 (2010).

Summary: We report on the design and implementation of a number type called Real_algebraic. This number type allows us to compute the sign of arithmetic expressions involving the operations \(+\), \(-\), \(\cdot\), \(/\), \(\root d\of{}\). The sign computation is always correct and, in this sense, not subject to rounding errors. We focus on modularity and use generic programming techniques to make key parts of the implementation exchangeable. Thus, our design allows for easily performing experiments with different implementations or thereby tailoring the number type for specific tasks. For many problems in computational geometry, instantiations of our number type Real_algebraic are a user-friendly alternative for implementing the exact geometric computation paradigm in order to abandon numerical robustness problems.

MSC:

68W30	Symbolic computation and algebraic computation
65D99	Numerical approximation and computational geometry (primarily algorithms)

Keywords:

symbolic numeric computation; exact geometric computation; algorithm engineering

Software:

Boost; CGAL; core 2; MPFR; gmp; Boost C++ Libraries; RealAlgebraic; LEDA

References:

[1]	Alexandrescu A.: Modern C++ design: generic programming and design patterns applied. Addison-Wesley Longman Publishing Co. Inc., Boston (2001)
[2]	boost C++ Libraries. http://www.boost.org/
[3]	Burnikel, C., Fleischer, R., Mehlhorn, K., Schirra, S.: Efficient exact geometric computation made easy. In: 15th ACM Symposium on Computational Geometry (SCG’99), pp. 341–350. ACM, New York (1999)
[4]	Burnikel C., Funke S., Mehlhorn K., Schirra S., Schmitt S.: A separation bound for real algebraic expressions. Algorithmica 55(1), 14–28 (2009) · Zbl 1180.68304
[5]	CGAL: Computational Geometry Algorithms Library http://www.cgal.org/ · Zbl 1322.68279
[6]	Dekker T.J.: A floating-point technique for extending the available precision. Num. Math. 18(2), 224–242 (1971) · Zbl 0226.65034
[7]	Du, Z.: Guaranteed precision for transcendental and algebraic computation made easy. PhD thesis, Courant Institute of Mathematical Sciences, New York University, May 2006
[8]	Funke S., Mehlhorn K., Näher S.: Structural filtering: a paradigm for efficient and exact geometric programs. Comput. Geometry 31(3), 179–194 (2005) · Zbl 1078.65015
[9]	Gamma E., Helm R., Johnson R., Vlissides J.: Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading (1995) · Zbl 0887.68013
[10]	GMP: The GNU multiple precision arithmetic library. http://www.gmplib.org/
[11]	Kahan W.: Further remarks on reducing truncation errors. Commun. ACM 8(1), 40 (1965)
[12]	Karamcheti, V., Li, C., Pechtchanski, I., Yap, C.: A core library for robust numeric and geometric computation. In: 15th ACM Symposium on Computational Geometry (SCG’99), pp. 351–359. ACM, New York (1999)
[13]	Knuth D.E.: Seminumerical algorithms. The Art of Computer Programming, vol. 2, 3rd edn. Addison-Wesley, Reading (1997)
[14]	LEDA: Library of Efficient Data Structures and Algorithms. http://www.algorithmic-solutions.com/ · Zbl 0850.68170
[15]	Li, C., Yap, C.: A new constructive root bound for algebraic expressions. In: SODA ’01: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 496–505, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics (2001) · Zbl 0988.65037
[16]	Mörig, M.: Deferring dag construction by storing sums of floats speeds-up exact decision computations based on expression dags. In: 3rd International Congress on Mathematical Software (ICMS 2010). LNCS, vol. 6327, pp. 109–120, September 2010 · Zbl 1295.65020
[17]	Mörig, M., Schirra, S.: On the design and performance of reliable geometric predicates using error-free transformations and exact sign of sum algorithms. In: 19th Canadian Conference on Computational Geometry (CCCG’07), pp. 45–48, August 2007
[18]	MPFR: A multiple precision floating-point library. http://www.mpfr.org/ · Zbl 1365.65302
[19]	Muller, J.-M., Brisebarre, N., de Dinechin, F., Jeannerod, C.-P., Lefèvre, V., Melquiond, G., Revol, N., Stehlé, D., Torres, S.: Handbook of Floating-Point Arithmetic. Birkhäuser Boston 2010 · Zbl 1197.65001
[20]	Ogita T., Rump S.M., Oishi S.: Accurate sum and dot product. SIAM J. Sci. Comput. 26(6), 1955–1988 (2005) · Zbl 1084.65041
[21]	Pion, S., Yap, C.: Constructive root bound for k-ary rational input numbers. In: Proceedings of the 19th ACM Symposium on Computational Geometry, pp. 256–263. ACM Press, San Diego, January 2003 · Zbl 1140.68549
[22]	RealAlgebraic: A number type for exact geometric computation. http://www.isg.cs.uni-magdeburg.de/ag/RealAlgebraic/
[23]	Schirra, S.: Much Ado about Zero. In: Efficient Algorithms. LNCS, vol. 5760, pp. 408–421, September 2009 · Zbl 1258.68177
[24]	Shewchuk J.R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete Comput. Geom. 18(3), 305–363 (1997) · Zbl 0892.68098
[25]	Shewchuk, J.R.: http://www.cs.cmu.edu/\(\sim\)quake/robust.html (1997)
[26]	Yap C.: Towards exact geometric computation. Comput. Geom. Theory Appl. 7(1-2), 3–23 (1997) · Zbl 0869.68104
[27]	Yap, C.-K.: Robust geometric computation. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, chap. 41, 2nd edn., pp. 927–952. Chapman & Hall/CRC (2004)
[28]	Yu, J., Yap, C., Du, Z., Pion, S., Brönnimann, H.: The design of Core 2: a library for exact numeric computation in geometry and algebra. In: 3rd International Congress on Mathematical Software (ICMS 2010). LNCS, vol. 6327, September 2010 · Zbl 1295.65147