Abstract
We propose exact, complete and efficient methods for 2 problems: First, the real solving of systems of two bivariate rational polynomials of arbitrary degree. This means isolating all common real solutions in rational rectangles and calculating the respective multiplicities. Second, the computation of the sign of bivariate polynomials evaluated at two algebraic numbers of arbitrary degree. Our main motivation comes from nonlinear computational geometry and computer-aided design, where bivariate polynomials lie at the inner loop of many algorithms. The methods employed are based on Sturm-Habicht sequences, univariate resultants and rational univariate representation. We have implemented them very carefully, using advanced object-oriented programming techniques, so as to achieve high practical performance. The algorithms are integrated in the public-domain C++ software library synaps, and their efficiency is illustrated by 9 experiments against existing implementations. Our code is faster in most cases; sometimes it is even faster than numerical approaches.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Heidelberg (2003)
Busé, L., Mourrain, B., Khalil, H.: Resultant-based methods for curves intersection problems (manuscript) (2005)
Cox, D., Little, J., O’Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, vol. 185. Springer, New York (1998)
Davenport, J.H., Siret, Y., Tournier, E.: Computer Algebra. Academic Press, London (1988)
Dos Reis, G., Mourrain, B., Rouillier, R., Trébuchet, P.: An environment for symbolic and numeric computation. In: Proc. Int. Conf. Math. Software, pp. 239–249. World Scientific, Singapore (2002)
Dupont, L., Lazard, D., Lazard, S., Petitjean, S.: Near-optimal parameterization of the intersection of quadrics. In: Proc. ACM SoCG, pp. 246–255 (June 2003)
Emiris, I.Z., Tsigaridas, E.P.: Real algebraic numbers and polynomial systems of small degree (manuscript) (2005), http://www.di.uoa.gr/~et
Emiris, I.Z., Kakargias, A.V., Teillaud, M., Tsigaridas, E.P., Pion, S.: Towards an open curved kernel. In: Proc. ACM SoCG, New York, pp. 438–446 (2004)
Emiris, I.Z., Tsigaridas, E.P.: Computing with real algebraic numbers of small degree. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 652–663. Springer, Heidelberg (2004)
Gonzalez-Vega, L., Necula, I.: Efficient topology determination of implicitly defined algebraic plane curves. Comp. Aided Geom. Design 19(9), 719–743 (2002)
Guibas, L.J., Karavelas, M.I., Russel, D.: A computational framework for handling motion. In: Proc. 6th Work. Algor. Engin. & Experim (ALENEX) (2004)
Hemmer, M., Schömer, E., Wolpert, N.: Computing a 3-dimensional cell in an arrangement of quadrics: Exactly and actually! In: Proc. Annual ACM Symp. Comput. Geometry, pp. 264–273 (2001)
El Kahoui, M.: Computing with algebraic curves in generic position (2005) (submitted), http://www.mpi-sb.mpg.de/~elkahoui
Keyser, J., Culver, T., Manocha, D., Krishnan, S.: MAPC: A library for efficient and exact manipulation of algebraic points and curves. In: Proc. Annual ACM Symp. Comput. Geometry, June 1999, pp. 360–369. ACM Press, New York (1999)
Keyser, J., Culver, T., Manocha, D., Krishnan, S.: ESOLID: A system for exact boundary evaluation. Comp. Aided Design 36(2), 175–193 (2004)
Keyser, J., Ouchi, K., Rojas, M.: The Exact Rational Univariate Representation for Detecting Degeneracies. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. AMS Press (2004) (to appear)
Lickteig, T., Roy, M.-F.: Semi-algebraic complexity of quotients and sign determination of remainders. J. Complexity 12(4), 545–571 (1996)
Mourrain, B., Pavone, J.P., Trébuchet, P., Tsigaridas, E.: SYNAPS, a library for symbolic-numeric computation. In: 8th Int. Symp. on Effective Methods in Algebraic Geometry, MEGA, Italy (May 2005)
Mourrain, B., Trébuchet, Ph.: Algebraic methods for numerical solving. In: Proc. of the 3rd International Workshop on Symbolic and Numeric Algorithms for Scientific Computing 2001, Timisoara, Romania, pp. 42–57 (2002)
Mourrain, B., Vrahatis, M., Yakoubsohn, J.C.: On the complexity of isolating real roots and computing with certainty the topological degree. J. Complexity 18(2) (2002)
Rouillier, F.: Solving zero-dimensional systems through the rational univariate representation. Journal of Applicable Algebra in Engineering, Communication and Computing 9(5), 433–461 (1999)
Sakkalis, T.: Signs of algebraic numbers. Computers and Mathematics, 131–134 (1989)
Weispfenning, V.: Solving parametric polynomial equations and inequalities by symbolic algorithms. In: Proc. Computer Algebra in Science and Engineering. World Scientific, Singapore (1995)
Wolpert, N., Seidel, R.: On the Exact Computation of the Topology of Real Algebraic Curves. In: Proc. ACM SoCG, Pisa, pp. 107–115 (2004)
Yap, C.K.: Fundamental Problems of Algorithmic Algebra. Oxford University Press, New York (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Emiris, I.Z., Tsigaridas, E.P. (2005). Real Solving of Bivariate Polynomial Systems. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing. CASC 2005. Lecture Notes in Computer Science, vol 3718. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11555964_13
Download citation
DOI: https://doi.org/10.1007/11555964_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28966-1
Online ISBN: 978-3-540-32070-8
eBook Packages: Computer ScienceComputer Science (R0)