Advertisement

The Diamond Operator – Implementation of Exact Real Algebraic Numbers

  • Susanne Schmitt
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3718)

Abstract

The LEDA number type real is extended by the diamond operator, which allows to compute exactly with real algebraic numbers given as roots of polynomials. The coefficients of these polynomials can be arbitrary real algebraic numbers. The implementation is presented and experiments with two other existing implementations of real algebraic numbers (CORE, EXACUS) are done.

Keywords

Newton Method Real Root Newton Step Diamond Operator Positive Real Root 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Burnikel, C., Funke, S., Mehlhorn, K., Schirra, S., Schmitt, S.: A Separation Bound for Real Algebraic Expressions. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 254–265. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  2. 2.
    CORE (A core library for robust numeric and geometric computation) http://www.cs.nyu.edu/exact/core/
  3. 3.
    Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: An Exact Descartes Algorithm with Approximate Coefficients (extended abstract). In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  4. 4.
    Emiris, I.Z., Tsigaridas, E.P.: Comparing Real Algebraic Numbers of Small Degree. ESA 2004, 652-663. Technical Report, ECG-TR-242200-01 (2003)Google Scholar
  5. 5.
    EXACUS (Efficient and Exact Algorithms for Curves and Surfaces), http://www.mpi-sb.mpg.de/projects/EXACUS/
  6. 6.
  7. 7.
    Guibas, L., Karavelas, M.I., Russel, D.: A computational framework for handling motion. In: Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments, pp. 129–141 (2004)Google Scholar
  8. 8.
    Johnson, J.R., Krandick, W.: Polynomial Real Root Isolation using Approximate Arithmetic. In: International Symposium on Symbolic and Algebraic Computation, pp. 225–232 (1997)Google Scholar
  9. 9.
    Krandick, W., Mehlhorn, K.: New Bounds for the Descartes Method. Technical Report, Drexel University DU-CS-04-04 (2004)Google Scholar
  10. 10.
    LEDA (Library of Efficient Data Types and Algorithms), http://www.mpi-sb.mpg.de/LEDA/
  11. 11.
    Li, C., Yap, C.: A new constructive root bound for algebraic expressions. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 496–505 (2001)Google Scholar
  12. 12.
    Li, C., Yap, C.: Recent progress in exact geometric computation. In: Proc. DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science (2001)Google Scholar
  13. 13.
    Ligatsikas, Z., Rioboo, R., Roy, M.-F.: Generic computation of the real closure of an ordered field. Mathematics and Computers in Simulation 42(4-6), 541–549 (1996)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Mourrain, B., Vrahatis, M., Yakoubsohn, J.C.: On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree. J. of Complexity 18(2), 612–640 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Pion, S., Yap, C.: Constructive root bound method for k-ary rational input numbers. In: 19th ACM Symp. on Comp. Geometry, San Diego, California, pp. 256–263 (2003)Google Scholar
  16. 16.
    Dos Reis, G., Mourrain, B., Rouillier, R., Trebuchet, P.: An environment for symbolic and numeric computation. In: Proc. of the International Conference on Mathematical Software 2002, pp. 239–249. World Scientific, Singapore (2002)Google Scholar
  17. 17.
    Rioboo, R.: Towards faster real algebraic numbers. Journal of Symbolic Computation, Special issue: ISSAC 2002 36, 513–533 (2003)Google Scholar
  18. 18.
    Rouillier, F., Zimmermann, P.: Efficient Isolation of a Polynomial Real Roots. Journal of Computational and Applied Mathematics 162(1), 33–50 (2003)CrossRefMathSciNetGoogle Scholar
  19. 19.
    Schmitt, S.: Improved separation bounds for the diamond operator. Effective Computational Geometry for Curves and Surfaces ECG-TR-363108-01 Report (2004)Google Scholar
  20. 20.
    Yap, C.K.: Fundamental Problems in Algorithmic Algebra. Oxford University Press, Oxford (1999)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Susanne Schmitt
    • 1
  1. 1.MPI für InformatikSaarbrücken

Personalised recommendations