research-article

Continued fraction expansion of real roots of polynomial systems

Authors:

Angelos Mantzaflaris,

Bernard Mourrain,

Elias TsigaridasAuthors Info & Claims

SNC '09: Proceedings of the 2009 conference on Symbolic numeric computation

Pages 85 - 94

https://doi.org/10.1145/1577190.1577207

Published: 03 August 2009 Publication History

Abstract

We present a new algorithm for isolating the real roots of a system of multivariate polynomials, given in the monomial basis. It is inspired by existing subdivision methods in the Bernstein basis; it can be seen as generalization of the univariate continued fraction algorithm or alternatively as a fully analog of Bernstein subdivision in the monomial basis. The representation of the subdivided domains is done through homographies, which allows us to use only integer arithmetic and to treat efficiently unbounded regions. We use univariate bounding functions, projection and preconditionning techniques to reduce the domain of search. The resulting boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. An extension of Vincent's theorem to multivariate polynomials is proved and used for the termination of the algorithm. New complexity bounds are provided for a simplified version of the algorithm. Examples computed with a preliminary C++ implementation illustrate the approach.

References

[1]

A. Alesina and M. Galuzzi. New proof of Vincent's thm. Enseignement Math&#233;matique, 44:219--256, 1998.

[2]

M. Barto&#328; and B. J&#252;ttler. Computing roots of polynomials by quadratic clipping. Comp. Aided Geom. Design, 24:125--141, 2007.

Digital Library

[3]

E. Bombieri and A. van der Poorten. Continued fractions of algebraic numbers. In Computational algebra and number theory (Sydney, 1992), pp. 137--152. Kluwer Acad. Publ., Dordrecht, 1995.

[4]

A. Eigenwillig, V. Sharma, and C. K. Yap. Almost tight recursion tree bounds for the Descartes method. In ISSAC 2006, pp. 71--78. ACM, New York, 2006.

Digital Library

[5]

G. Elber and M.-S. Kim. Geometric constraint solver using multivariate rational spline functions. In Proc. of 6th ACM Symposium on Solid Modelling and Applications, pp. 1--10. ACM Press, 2001.

Digital Library

[6]

I. Emiris, M. Hemmer, M. Karavelas, S. Limbach, B. Mourrain, E. P. Tsigaridas, and Z. Zafeirakopoulos. Cross-benchmarks of univariate algebraic kernels. ACS-TR-363602-02, INRIA, MPI and NUA, 2008.

[7]

I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas. Real Algebraic Numbers: Complexity Analysis and Experimentation. In P. Hertling, C. Hoffmann, W. Luther, and N. Revol, ed., Reliable Implementations of Real Number Algorithms: Theory and Practice, LNCS vol. 5045, pp. 57--82. Springer Verlag, 2008.

Digital Library

[8]

I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas. The dmm bound: multivariate (aggregate) separation bounds. Technical report, INRIA, March 2009.

[9]

J. Garloff and A. P. Smith. Investigation of a subdivision based algorithm for solving systems of polynomial equations. Journal of Nonlinear Analysis, 47(1):167--178, 2001.

[10]

A. Khintchine. Continued Fractions. University of Chicago Press, Chicago, 1964.

[11]

M. Marden. Geometry of Polynomials. American Mathematical Society, Providence, RI, 1966.

[12]

B. Mourrain and J. Pavone. Subdivision methods for solving polynomial equations. Special issue in honor of Daniel Lazard. JSC 44(3):292--306, 2009.

Digital Library

[13]

B. Mourrain, F. Rouillier, and M.-F. Roy. Bernstein's basis and real root isolation, pp. 459--478. MSRI Publications. Cambridge University Press, 2005.

[14]

V. Pan. Solving a polynomial equation: Some history and recent progress. SIAM Rev., 39(2):187--220, 1997.

Digital Library

[15]

V. Pan. Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding. JSC, 33(5):701--733, 2002.

Digital Library

[16]

V. Sharma. Complexity of real root isolation using continued fractions. Theor. Comput. Sci., 409(2):292--310, 2008.

Digital Library

[17]

E. C. Sherbrooke and N. M. Patrikalakis. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design, 10(5):379--405, 1993.

Digital Library

[18]

E. P. Tsigaridas and I. Z. Emiris. On the complexity of real root isolation using Continued Fractions. Theoretical Computer Science, 392:158--173, 2008.

Digital Library

[19]

A. van der Poorten. An introduction to continued fractions. In Diophantine analysis, pp. 99--138. Cambridge University Press, 1986.

[20]

J. von zur Gathen and J. Gerhard. Fast Algorithms for Taylor Shifts and Certain Difference Equations. In Proc. Annual ACM ISSAC, pp. 40--47, 1997.

Digital Library

[21]

M. N. Vrahatis. A short proof and a generalization of Miranda's existence theorem. Proceedings of the American Mathematical Society, 107(3):701--703, 1989.

[22]

C. Yap. Fundamental Problems of Algorithmic Algebra. Oxford University Press, New York, 2000.

Digital Library

Cited By

Emiris IMourrain BTsigaridas E(2019)Separation bounds for polynomial systemsJournal of Symbolic Computation10.1016/j.jsc.2019.07.001Online publication date: Jul-2019
https://doi.org/10.1016/j.jsc.2019.07.001
Aizenshtein MBartoň MElber G(2012)Global solutions of well-constrained transcendental systems using expression trees and a single solution testComputer Aided Geometric Design10.1016/j.cagd.2011.07.00229:5(265-279)Online publication date: Jun-2012
https://doi.org/10.1016/j.cagd.2011.07.002
Mantzaflaris AMourrain BSchost ÉEmiris I(2011)Deflation and certified isolation of singular zeros of polynomial systemsProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993925(249-256)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1145/1993886.1993925
Show More Cited By

Index Terms

Continued fraction expansion of real roots of polynomial systems
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers

We elaborate on a correspondence between the coefficients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions that use only integer arithmetic (...
Continued fraction real root isolation using the Hong root bound

An investigation of the codominance maximum computing time of the continued fractions method (CF) for isolation of the real roots of a squarefree integral polynomial when applied to the two-parameter family of polynomials A a , n ( x ) = x n - 2 ( a x 2 ...
Complexity of real root isolation using continued fractions
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

The efficiency of the continued fraction algorithm for isolating the real roots of a univariate polynomial depends upon computing tight lower bounds on the smallest positive root of a polynomial. The known complexity bounds for the algorithm rely on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SNC '09: Proceedings of the 2009 conference on Symbolic numeric computation

August 2009

210 pages

ISBN:9781605586649

DOI:10.1145/1577190

Editors:
Hiroshi Kai
Ehime University, Japan
,
Hiroshi Sekigawa
NTT Communication Science Laboratories, Japan
,
General Chairs:
Tateaki Sasaki
University of Tsukuba, Japan
,
Kiyoshi Shirayanagi
Tokai University, Japan
,
Program Chair:
Ilias Kotsireas
Wilfrid Laurier University, Canada

Copyright © 2009 ACM.

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: 03 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SNC '09

Sponsor:

SNC '09: Symbolic Numeric Computation

August 3 - 5, 2009

Kyoto, Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
160
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Emiris IMourrain BTsigaridas E(2019)Separation bounds for polynomial systemsJournal of Symbolic Computation10.1016/j.jsc.2019.07.001Online publication date: Jul-2019
https://doi.org/10.1016/j.jsc.2019.07.001
Aizenshtein MBartoň MElber G(2012)Global solutions of well-constrained transcendental systems using expression trees and a single solution testComputer Aided Geometric Design10.1016/j.cagd.2011.07.00229:5(265-279)Online publication date: Jun-2012
https://doi.org/10.1016/j.cagd.2011.07.002
Mantzaflaris AMourrain BSchost ÉEmiris I(2011)Deflation and certified isolation of singular zeros of polynomial systemsProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993925(249-256)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1145/1993886.1993925
Mantzaflaris AMourrain BTsigaridas E(2011)On continued fraction expansion of real roots of polynomial systems, complexity and condition numbersTheoretical Computer Science10.1016/j.tcs.2011.01.009412:22(2312-2330)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.tcs.2011.01.009
Hodorog MSchicho J(2011)A Symbolic-Numeric Algorithm for Genus ComputationNumerical and Symbolic Scientific Computing10.1007/978-3-7091-0794-2_4(65-94)Online publication date: 12-Oct-2011
https://doi.org/10.1007/978-3-7091-0794-2_4
Emiris IMourrain BTsigaridas EKoepf W(2010)The DMM boundProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1837981(243-250)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1837934.1837981

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents