Abstract
We present a cgal-based univariate algebraic kernel, which provides certified real-root isolation of univariate polynomials with integer coefficients and standard functionalities such as basic arithmetic operations, greatest common divisor (gcd) and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers.
We compare our kernel with other comparable kernels, demonstrating the efficiency of our approach. Our experiments are performed on large data sets including polynomials of high degree (up to 2 000) and with very large coefficients (up to 25 000 bits per coefficient).
We also address the problem of computing arrangements of x-monotone polynomial curves. We apply our kernel to this problem and demonstrate its efficiency compared to previous solutions available in cgal.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abbott, J.: Quadratic interval refinement for real roots. In: International Symposium on Symbolic and Algebraic Computation (ISSAC), poster presentation (2006)
Berberich, E., Eigenwillig, A., Hemmer, M., Hert, S., Kettner, L., Mehlhorn, K., Reichel, J., Schmitt, S., Schömer, E., Wolpert, N.: EXACUS: Efficient and Exact Algorithms for Curves and Surfaces. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 155–166. Springer, Heidelberg (2005)
Berberich, E., Hemmer, M., Karavelas, M., Teillaud, M.: Revision of the interface specification of algebaic kernel. Technical Report ACS-TR-243301-01, ACS European Project (2007)
Cgal, Computational Geometry Algorithms Library, http://www.cgal.org
Collins, G., Johnson, J., Krandick, W.: Interval Arithmetic in Cylindrical Algebraic Decomposition. Journal of Symbolic Computation 34(2), 145–157 (2002)
The Core library, http://cs.nyu.edu/exact/
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008)
Edelman, A., Kostlan, E.: How zeros of a random polynomial are real? Bulletin of American Mathematical Society 32(1), 1–37 (1995)
Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: A Descartes Algorithm for Polynomials with Bit-Stream Coefficients. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718, pp. 138–149. Springer, Heidelberg (2005)
Emiris, I., Hemmer, M., Karavelas, M., Limbach, S., Mourrain, B., Tsigaridas, E., Zafeirakopoulos, Z.: Cross-benchmarks for univariate algebraic kernels. Technical Report ACS-TR-363602-02, ACS European Project (2008)
Emiris, I.Z., Kakargias, A., Pion, S., Teillaud, M., Tsigaridas, E.P.: Towards and open curved kernel. In: Proc. 20th Annual ACM Symp. on Computational Geometry (SoCG), New York, USA, pp. 438–446 (2004)
Gmp, Gnu multiple precision arithmetic library, http://gmplib.org/
Hemmer, M., Limbach, S.: Benchmarks on a generic univariate algebraic kernel. Technical Report ACS-TR-243306-03, ACS European Project (2006)
Keyser, J., Culver, T., Manocha, D., Krishnan, S.: Efficient and exact manipulation of algebraic points and curves. Computer-Aided Design 32(11), 649–662 (2000)
Mourrain, B., Pavone, P., Trébuchet, P., Tsigaridas, E.P., Wintz, J.: Synaps, a library for dedicated applications in symbolic numeric computations. In: Stillman, M., Takayama, N., Verschelde, J. (eds.) IMA Volumes in Mathematics and its Applications, pp. 81–110. Springer, New York (2007), http://synaps.inria.fr
Mpfi, multiple precision interval arithmetic library, http://perso.ens-lyon.fr/nathalie.revol/software.html
Mpfr, library for multiple-precision floating-point computations, http://mpfr.org/
Rouillier, F., Zimmermann, Z.: Efficient isolation of polynomial’s real roots. J. of Computational and Applied Mathematics 162(1), 33–50 (2004)
Rs, a software for real solving of algebraic systems. F. Rouillier, http://fgbrs.lip6.fr
Tsigaridas, E.P., Emiris, I.Z.: On the complexity of real root isolation using Continued Fractions. Theoretical Computer Science 392, 158–173 (2008)
Tsigaridas, E.P., Emiris, I.Z.: Real algebraic numbers and polynomial systems of small degree. Theoretical Computer Science 409(2), 186–199 (2008)
Wein, R., Fogel, E.: The new design of CGAL’s arrangement package. Technical report, Tel-Aviv University (2005)
Yap, C.: Fundamental Problems of Algorithmic Algebra. Oxford University Press, Oxford (2000)
Yap, C.: Robust geometric computation. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., ch. 41, pp. 927–952. Chapman & Hall/CRC, Boca Raton (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lazard, S., Peñaranda, L., Tsigaridas, E. (2009). Univariate Algebraic Kernel and Application to Arrangements. In: Vahrenhold, J. (eds) Experimental Algorithms. SEA 2009. Lecture Notes in Computer Science, vol 5526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02011-7_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-02011-7_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02010-0
Online ISBN: 978-3-642-02011-7
eBook Packages: Computer ScienceComputer Science (R0)