[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2442829.2442872acmotherconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
research-article

When Newton meets Descartes: a simple and fast algorithm to isolate the real roots of a polynomial

Published: 22 July 2012 Publication History

Abstract

We introduce a novel algorithm denoted NewDsc to isolate the real roots of a univariate square-free polynomial f with integer coefficients. The algorithm iteratively subdivides an initial interval which is known to contain all real roots of f and performs exact (rational) operations on the coefficients of f in each step. For the subdivision strategy, we combine Descartes' Rule of Signs and Newton iteration. More precisely, instead of using a fixed subdivision strategy such as bisection in each iteration, a Newton step based on the number of sign variations for an actual interval is considered, and, only if the Newton step fails, we fall back to bisection. Following this approach, quadratic convergence towards the real roots is achieved in most iterations. In terms of complexity, our method induces a recursion tree of almost optimal size O(n·log(nτ)), where n denotes the degree of the polynomial and τ the bitsize of its coefficients. The latter bound constitutes an improvement by a factor of τ upon all existing subdivision methods for the task of isolating the real roots. We further provide a detailed complexity analysis which shows that NewDsc needs only Õ(n3τ) bit operations to isolate all real roots of f. In comparison to existing asymptotically fast numerical algorithms (e.g. the algorithms by V. Pan and A. Schönhage), NewDsc is much easier to access and, due to its similarities to the classical Descartes method, it seems to be well suited for an efficient implementation.

References

[1]
J. Abbott. Quadratic interval refinement for real roots. Poster presented at ISSAC, 2006.
[2]
A. G. Akritas and A. Strzeboński. A comparative study of two real root isolation methods. Nonlinear Analysis:Modelling and Control, 10(4):297--304, 2005.
[3]
A. Alesina and M. Galuzzi. A new proof of Vincent's theorem. L'Enseignement Mathematique, 44:219--256, 1998.
[4]
D. Bini and G. Fiorentino. Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numerical Algorithms, 23:127--173, 2000.
[5]
G. Collins and A. Akritas. Polynomial real root isolation using Descartes' rule of signs. In ISSAC, pages 272--275, 1976.
[6]
Z. Du, V. Sharma, and C. Yap. Amortized bounds for root isolation via Sturm sequences. In SNC, pages 113--130. 2007.
[7]
A. Eigenwillig. Real Root Isolation for Exact and Approximate Polynomials using Descartes' Rule of Signs. PhD thesis, Universität des Saarlandes, May 2008.
[8]
A. Eigenwillig, V. Sharma, and C. Yap. Almost tight complexity bounds for the Descartes method. In ISSAC, pages 71--78, 2006.
[9]
X. Gourdon. Combinatoire, Algorithmique et Géométrie des Polynômes. Thèse, École polytechnique, 1996.
[10]
M. Hemmer, E. P. Tsigaridas, Z. Zafeirakopoulos, I. Z. Emiris, M. I. Karavelas, and B. Mourrain. Experimental evaluation and cross-benchmarking of univariate real solvers. In SNC, pages 45--54, 2009.
[11]
M. Kerber and M. Sagraloff. Efficient real root approximation. In ISSAC, pages 209--216, 2011.
[12]
N. Obreshkoff. Verteilung und Berechnung der Nullstellen reeller Polynome. VEB Deutscher Verlag der Wissenschaften, 1963.
[13]
N. Obreshkoff. Zeros of Polynomials. Marina Drinov, Sofia, 2003. Translation of the Bulgarian original.
[14]
V. Y. Pan. Solving a polynomial equation: some history and recent progress. SIAM Review, 39(2):187--220, 1997.
[15]
V. Y. Pan. Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding. J. Symb. Comput., 33(5):701--733, 2002.
[16]
F. Rouillier and P. Zimmermann. Efficient isolation of {a} polynomial's real roots. J. Computational and Applied Mathematics, 162:33--50, 2004.
[17]
M. Sagraloff. A general approach to isolating roots of a bitstream polynomial. Math. in Comput. Sci., 4(4):481--506, 2010.
[18]
M. Sagraloff. On the complexity of real root isolation. arXiv:1011.0344v2, 2011.
[19]
M. Sagraloff and C.-K. Yap. A simple but exact and efficient algorithm for complex root isolation. In ISSAC, pages 353--360, 2011.
[20]
A. Schönhage. The fundamental theorem of algebra in terms of computational complexity, 1982. Manuscript, Department of Mathematics, University of Tübingen. Updated 2004.
[21]
E. P. Tsigaridas and I. Z. Emiris. On the complexity of real root isolation using continued fractions. Theor. Comput. Sci., 392(1-3):158--173, 2008.
[22]
J. von zur Gathen and J. Gerhard. Fast algorithms for Taylor shifts and certain difference equations. In ISSAC, pages 40--47, 1997.
[23]
C. K. Yap. Fundamental Problems of Algorithmic Algebra. Oxford University Press, 2000.

Cited By

View all
  • (2023)Isolating clusters of zeros of analytic systems using arbitrary-degree inflationProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597094(126-134)Online publication date: 24-Jul-2023
  • (2022)Integer polynomial recovery from outputs and its application to cryptanalysis of a protocol for secure sortingJournal of Mathematical Cryptology10.1515/jmc-2021-005416:1(251-277)Online publication date: 18-Aug-2022
  • (2021)A symbolic-numerical algorithm for isolating real roots of certain radical expressionsJournal of Computational and Applied Mathematics10.1016/j.cam.2021.113424391:COnline publication date: 1-Aug-2021
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences
ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation
July 2012
390 pages
ISBN:9781450312691
DOI:10.1145/2442829
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

  • Grenoble University: Grenoble University
  • INRIA: Institut Natl de Recherche en Info et en Automatique

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 July 2012

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

ISSAC'12
Sponsor:
  • Grenoble University
  • INRIA

Acceptance Rates

ISSAC '12 Paper Acceptance Rate 46 of 86 submissions, 53%;
Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2023)Isolating clusters of zeros of analytic systems using arbitrary-degree inflationProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597094(126-134)Online publication date: 24-Jul-2023
  • (2022)Integer polynomial recovery from outputs and its application to cryptanalysis of a protocol for secure sortingJournal of Mathematical Cryptology10.1515/jmc-2021-005416:1(251-277)Online publication date: 18-Aug-2022
  • (2021)A symbolic-numerical algorithm for isolating real roots of certain radical expressionsJournal of Computational and Applied Mathematics10.1016/j.cam.2021.113424391:COnline publication date: 1-Aug-2021
  • (2021)On the Complexity of Computing the Topology of Real Algebraic Space CurvesJournal of Systems Science and Complexity10.1007/s11424-020-9164-2Online publication date: 12-Jan-2021
  • (2020)The complexity of subdivision for diameter-distance testsJournal of Symbolic Computation10.1016/j.jsc.2019.06.004101(1-27)Online publication date: Nov-2020
  • (2016)Complexity Analysis of Root Clustering for a Complex PolynomialProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930939(71-78)Online publication date: 20-Jul-2016
  • (2016)Computing Real Roots of Real Polynomials ... and now For Real!Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930937(303-310)Online publication date: 20-Jul-2016
  • (2015)Near Optimal Subdivision Algorithms for Real Root IsolationProceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2755996.2756656(331-338)Online publication date: 24-Jun-2015
  • (2015)A generic position based method for real root isolation of zero-dimensional polynomial systemsJournal of Symbolic Computation10.1016/j.jsc.2014.09.01768:P1(204-224)Online publication date: 1-May-2015
  • (2015)Separating linear forms and Rational Univariate Representations of bivariate systemsJournal of Symbolic Computation10.1016/j.jsc.2014.08.00968:P1(84-119)Online publication date: 1-May-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media