skip to main content
10.1145/1277548.1277567acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

On the complexity of real solving bivariate systems

Published: 29 July 2007 Publication History

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(N14) for the purely projection-based method, and ÕB(N12) 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(N14).
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]
D. Arnon, S. McCallum. A polynomial time algorithm for the topological type of a real algebraic curve. JSC, 5:213--236, 1988.
[3]
S. Basu, R. Pollack, and M -F. Roy. Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics. Springer-Verlag, 2nd edition, 2006.
[4]
J. Canny. Some algebraic and geometric computations in PSPACE. In Proc. STOC, pp. 460--467, 1988.
[5]
F. Cazals, J.-C. Faugère, M. Pouget, and F. Rouillier. The implicit structure of ridges of a smooth parametric surface. Comput. Aided Geom. Des., 23(7):582--598, 2006.
[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]
A. Eigenwillig, M. Kerber, N. Wolpert. Fast and Exact Geometric Analysis of Real Algebraic Plane Curves. In ISSAC, 2007. ACM Press.
[9]
A. Eigenwillig, V. Sharma, and C. K. Yap. Almost tight recursion tree bounds for the Descartes method. In ISSAC, pp. 71--78, 2006. ACM Press.
[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]
L. González-Vega and M. El Kahoui. An improved upper complexity bound for the topology computation of a real algebraic plane curve. J. Complexity, 12(4):527--544, 1996.
[13]
L. González-Vega, H. Lombardi, T. Recio, and M. -F. Roy. Sturm-Habicht Sequence. In ISSAC, pp. 136--146, 1989. ACM Press.
[14]
L. González-Vega and I. Necula. Efficient topology determination of implicitly defined algebraic plane curves. Comp. Aided Geom. Design, 19(9):719--743, 2002.
[15]
J. Klose. Binary segmentation for multivariate polynomials. J. Complexity, 11(3):330--343, 1995.
[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]
T. Lickteig and M.-F. Roy. Sylvester-Habicht Sequences and Fast Cauchy Index Computation. JSC, 31(3):315--341, 2001.
[18]
H. Lombardi, M.-F. Roy, and M. Safey El Din. New Structure Theorem for Subresultants. JSC, 29(4-5):663--689, 2000.
[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]
B. Mourrain and P. Trébuchet. Solving projective complete intersection faster. In ISSAC, pp. 231--238, 2000. ACM Press.
[24]
V. Pan. Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding. JSC, 33:701--733, 2002.
[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]
D. Reischert. Asymptotically fast computation of subresultants. In ISSAC, pp. 233--240, 1997. ACM Press.
[27]
J. Renegar. On the worst-case arithmetic complexity of approximating zeros of systems of polynomials. SIAM J. Computing, 18:350--370, 1989.
[28]
F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. J. AAECC, 9:433--461, 1999.
[29]
T. Sakkalis. Signs of algebraic numbers. Computers and Mathematics, pp. 131--134, 1989.
[30]
T. Sakkalis and R. Farouki. Singular points of algebraic curves. JSC, 9(4):405--421, 1990.
[31]
M. van Hoeij and M. Monagan. A modular GCD algorithm over number fields presented with multiple extensions. In ISSAC, pp. 109--116, 2002. ACM Press.
[32]
J. von zur Gathen and T. Lücking. Subresultants revisited. TCS, 1-3(297):199--239, 2003.
[33]
N. Wolpert. An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics. PhD thesis, MPI Informatik, 2002.
[34]
N. Wolpert, R. Seidel. On the exact computation of the topology of real algebraic curves. In SoCG, pp.107--115, 2005
[35]
C. Yap. Fundamental Problems of Algorithmic Algebra. Oxford Univ. Press, New York, 2000.

Cited By

View all
  • (2023)Algorithm for Connectivity Queries on Real Algebraic CurvesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597081(345-353)Online publication date: 24-Jul-2023
  • (2013)Parallel computation of real solving bivariate polynomial systems by zero-matching methodApplied Mathematics and Computation10.1016/j.amc.2013.01.039219:14(7533-7541)Online publication date: 1-Mar-2013
  • (2010)An efficient algorithm for the stratification and triangulation of an algebraic surfaceComputational Geometry: Theory and Applications10.1016/j.comgeo.2009.01.00943:3(257-278)Online publication date: 1-Apr-2010
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation
July 2007
406 pages
ISBN:9781595937438
DOI:10.1145/1277548
  • General Chair:
  • Dongming Wang
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. maple
  2. polynomial system
  3. real algebraic number
  4. realsolving
  5. topology of real algebraic curve

Qualifiers

  • Article

Conference

ISSAC07
Sponsor:
ISSAC07: International Symposium on Symbolic and Algebraic Computation
July 29 - August 1, 2007
Ontario, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Algorithm for Connectivity Queries on Real Algebraic CurvesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597081(345-353)Online publication date: 24-Jul-2023
  • (2013)Parallel computation of real solving bivariate polynomial systems by zero-matching methodApplied Mathematics and Computation10.1016/j.amc.2013.01.039219:14(7533-7541)Online publication date: 1-Mar-2013
  • (2010)An efficient algorithm for the stratification and triangulation of an algebraic surfaceComputational Geometry: Theory and Applications10.1016/j.comgeo.2009.01.00943:3(257-278)Online publication date: 1-Apr-2010
  • (2009)Root isolation for bivariate polynomial systems with local generic position methodProceedings of the 2009 international symposium on Symbolic and algebraic computation10.1145/1576702.1576719(103-110)Online publication date: 28-Jul-2009
  • (2009)On the topology of planar algebraic curvesProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542424(361-370)Online publication date: 8-Jun-2009
  • (2009)On the asymptotic and practical complexity of solving bivariate systems over the realsJournal of Symbolic Computation10.1016/j.jsc.2008.04.00944:7(818-835)Online publication date: 1-Jul-2009
  • (2009)On the Complexity of Reliable Root ApproximationProceedings of the 11th International Workshop on Computer Algebra in Scientific Computing10.1007/978-3-642-04103-7_15(155-167)Online publication date: 1-Oct-2009
  • (2008)Exact geometric-topological analysis of algebraic surfacesProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377703(164-173)Online publication date: 9-Jun-2008
  • (2008)Real algebraic numbers and polynomial systems of small degreeTheoretical Computer Science10.1016/j.tcs.2008.09.009409:2(186-199)Online publication date: 10-Dec-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media