On the complexity of real solving bivariate systems

ABSTRACT

We consider exact real solving of well-constrained, bivariate systems of relatively prime polynomials. The main problem is to compute all common real roots in isolating interval representation, and to determine their intersection multiplicities. We present three algorithms and analyze their asymptotic bit complexity, obtaining a bound of Õ_B(N¹⁴) for the purely projection-based method, and Õ_B(N¹²) for two subresultants-based methods: these ignore polylogarithmic factors, and N bounds the degree and the bitsize of the polynomials. The previous record bound was Õ_B(N¹⁴).

Our main tool is signed subresultant sequences, extended to several variables by binary segmentation. We exploit advances on the complexity of univariate root isolation, and extend them to multipoint sign evaluation, sign evaluation of bivariate polynomials over two algebraic numbers, and real root counting over an extension field. Our algorithms apply to the problem of simultaneous inequalities; they also compute the topology of real plane algebraic curves in.

All algorithms have been implemented in maple, in conjunction with numeric filtering. We compare them against fgb/rs and synaps; we also consider maple libraries insulate and top, which compute curve topology. Our software is among the most robust, and its runtimes are within a small constant factor, with respect to the C/C++ libraries.

REFERENCES

• 1: J. Abbott. Quadratic interval refinement for real roots. In ISSAC 2006, poster. www.dima.unige.it/~abbott/.
• 2: Dennis S. Arnon , Scott McCallum, A polynomical-time algorithm for the topological type of a real algebraic curve, Journal of Symbolic Computation, v.5 n.1-2, p.213-236, February/April 1988 [doi>10.1016/S0747-7171(88)80013-0]
• 3: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• 5: Frédéric Cazals , Jean-Charles Faugère , Marc Pouget , Fabrice Rouillier, The implicit structure of ridges of a smooth parametric surface, Computer Aided Geometric Design, v.23 n.7, p.582-598, October 2006 [doi>10.1016/j.cagd.2006.04.002]
• 6: D. I. Diochnos, I. Z. Emiris, and E. P. Tsigaridas. On the complexity of real solving bivariate systems. Research Report 6116, INRIA, 2007. https://hal.inria.fr/inria-00129309.
• 7: Z. Du, V. Sharma, and C. K. Yap. Amortized bound for root isolation via Sturm sequences. Int. Workshop on Symbolic Numeric Computing, pp. 81--93, Beijing, 2005.
• 8: Arno Eigenwillig , Michael Kerber , Nicola Wolpert, Fast and exact geometric analysis of real algebraic plane curves, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277570]
• 9: Arno Eigenwillig , Vikram Sharma , Chee K. Yap, Almost tight recursion tree bounds for the Descartes method, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145786]
• 10: I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas. Real Algebraic Numbers: Complexity Analysis and Experimentation. Reliable Implementations of Real Number Algorithms: Theory and Practice, LNCS (to appear). Springer Verlag, 2007. also available in www.inria.fr/rrrt/rr-5897.html.
• 11: I. Z. Emiris and E. P. Tsigaridas. Real solving of bivariate polynomial systems. In Proc. Comp. Algebra in Scient. Comput., vol. 3718 LNCS, pp. 150--161. Springer, 2005.
• 12: Laureano González-Vega , M'Hammed El Kahoui, An improved upper complexity bound for the topology computation of a real algebraic plane curve, Journal of Complexity, v.12 n.4, p.527-544, Dec. 1996 [doi>10.1006/jcom.1996.0032]
• 13: L. Gonzalez , H. Lombardi , T. Recio , M.-F. Roy, Sturm-Habicht sequence, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.136-146, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74558]
• 14: Laureano Gonzalez-Vega , Ioana Necula, Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geometric Design, v.19 n.9, p.719-743, December 2002 [doi>10.1016/S0167-8396(02)00167-X]
• 15: Jürgen Klose, Binary segmentation for multivariate polynomials, Journal of Complexity, v.11 n.3, p.330-343, Sept. 1995 [doi>10.1006/jcom.1995.1015]
• 16: K. Ko, T. Sakkalis, and N. Patrikalakis. Resolution of multiple roots of nonlinear polynomial systems. Int. J. Shape Modelling, 11(1):121--147, 2005.
• 17: Sylvester—Habicht sequences and fast Cauchy index computation, Journal of Symbolic Computation, v.31 n.3, p.315-341, March 2001 [doi>10.1006/jsco.2000.0427]
• 18: Henri Lombardi , Marie-Françoise Roy , Mohad Safey El Din, New structure theorem for subresultants, Journal of Symbolic Computation, v.29 n.4-5, p.663-690, April/May 2000 [doi>10.1006/jsco.1999.0322]
• 19: M. Mignotte and D. Stefanescu. Polynomials: An algorithmic approach. Springer, 1999.
• 20: P. Milne. On the solution of a set of polynomial equations. In B. Donald, D. Kapur, and J. Mundy, editors, Symbolic and Numerical Computation for Artificial Intelligence, pp. 89--102. Academic Press, 1992.
• 21: B. Mourrain and J.-P. Pavone. Subdivision methods for solving polynomial equations. TR-5658, INRIA Sophia-Antipolis, 2005.
• 22: B. Mourrain, S. Pion, S. Schmitt, J.-P. Técourt, E. Tsigaridas, and N. Wolpert. Algebraic issues in computational geometry. Effective Computational Geometry for Curves and Surfaces, pp. 117--155. Springer-Verlag, 2006.
• 23: Bernard Mourrain , Philippe Trebuchet, Solving projective complete intersection faster, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.234-241, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345642]
• 24: Victor Y. Pan, Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding, Journal of Symbolic Computation, v.33 n.5, p.701-733, May 2002 [doi>10.1006/jsco.2002.0531]
• 25: P. Pedersen, M-F. Roy, and A. Szpirglas. Counting real zeros in the multivariate case. In Computational Algebraic Geometry, vol. 109 of Progress in Mathematics, pp. 203--224. Birkhäuser, Boston, 1993.
• 26: Daniel Reischert, Asymptotically fast computation of subresultants, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.233-240, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258792]
• 27: James Renegar, On the worst-case arithmetic complexity of approximating zeros of systems of polynomials, SIAM Journal on Computing, v.18 n.2, p.350-370, April 1989 [doi>10.1137/0218024]
• 28: F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. J. AAECC, 9:433--461, 1999.
• 29: Takis Sakkalis, Signs of algebraic numbers, Proceedings of the third conference on Computers and mathematics, p.130-134, May 1989, Boston, Massachusetts, United States
• 30: Takis Sakkalis , R. Farouki, Singular points of algebraic curves, Journal of Symbolic Computation, v.9 n.4, p.405-421, April 1990 [doi>10.1016/S0747-7171(08)80019-3]
• 31: Mark van Hoeij , Michael Monagan, A modular GCD algorithm over number fields presented with multiple extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.109-116, July 07-10, 2002, Lille, France [doi>10.1145/780506.780520]
• 32: Joachim von zur Gathen , Thomas Lücking, Subresultants revisited, Theoretical Computer Science, v.297 n.1-3, p.199-239, 17 March 2003 [doi>10.1016/S0304-3975(02)00639-4]
• 33: N. Wolpert. An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics. PhD thesis, MPI Informatik, 2002.
• 34: Raimund Seidel , Nicola Wolpert, On the exact computation of the topology of real algebraic curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064111]
• 35: Chee Keng Yap, Fundamental problems of algorithmic algebra, Oxford University Press, Inc., New York, NY, 1999

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Experimentation, Theory

Keywords:
maple, polynomial system, real algebraic number, realsolving, topology of real algebraic curve