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

Please wait, while we are loading the content...

A-hypergeometric functions: computational aspects

Complexity of deciding connectivity in real algebraic sets: recent results and future research directions

Asymptotic spectrum and matrix multiplication

Upper bounds on real roots and lower bounds for the permanent

Elements of computer-algebraic analysis

Algebraic statistics

On valuations of meromorphic solutions of arbitrary-order linear difference systems with polynomial coefficients

Computing Puiseux series for algebraic surfaces

The M4RIE library for dense linear algebra over small fields with even characteristic

A root isolation algorithm for sparse univariate polynomials

Computing closed form solutions of integrable connections

Solving linear ordinary differential systems in hyperexponential extensions

Relaxed p-adic Hensel lifting for algebraic systems

Solving polynomial systems over finite fields: improved analysis of the hybrid approach

A polynomial time algorithm for computing the HNF of a module over the integers of a number field

Parallel sparse polynomial multiplication on modern hardware architectures

Compositions and collisions at degree $p^{2}$

Fast computation of common left multiples of linear ordinary differential operators

Power series solutions of singular (q)-differential equations

On the complexity of solving initial value problems

Order-degree curves for hypergeometric creative telescoping

Telescopers for rational and algebraic functions via residues

Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values

Fast computation of Smith forms of sparse matrices over local rings

On the complexity of solving a bivariate polynomial system

Critical points and Gröbner bases: the unmixed case

Solving polynomial systems globally invariant under an action of the symmetric group and application to the equilibria of N vortices in the plane

Twisting q-holonomic sequences by complex roots of unity

Improving the accuracy of linear programming solvers with iterative refinement

Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions

Practical Gröbner basis computation

On the complexity of multivariate blockwise polynomial multiplication

Rational invariants of scalings from Hermite normal forms

Zeilberger's holonomic ansatz for Pfaffians

Algorithms for the universal decomposition algebra

An efficient implementation of the algorithm computing the Borel-fixed points of a Hilbert scheme

Computing real solutions of polynomial systems via low-rank moment matrix completion

Small homogeneous quandles

Border basis representation of a general quotient algebra

An algorithm to compute the differential equations for the logarithm of a polynomial

Deterministic unimodularity certification

Programming before theorizing, a case study

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

Effective de Rham cohomology: the hypersurface case

Construction of 2-closed M-representations

Near optimal tree size bounds on a simple real root isolation algorithm

An efficient programming model for memory-intensive recursive algorithms using parallel disks

Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas

Univariate real root isolation in multiple extension fields

A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras

Factorization of differential operators with ordinary differential polynomial coefficients

Computing minimal nullspace bases

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

Content Provider	ACM Digital Library
Author	Sagraloff, Michael
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 $Õ(n^{3}τ)$ 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.
Starting Page	297
Ending Page	304
Page Count	8
File Format	PDF
ISBN	9781450312691
DOI	10.1145/2442829.2442872
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-22
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

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

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

When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial

Isolating real roots of real polynomials

Efficient Isolation of a Polynomial Real Roots

A fast parallel algorithm for determining all roots of a polynomial with real roots

Efficient Isolation of a Polynomial Real Roots

On Multiple Roots in Descartes ’ Rule and Their Distance to Roots of Higher Derivatives

Multivariate Descartes' Rule (1996)

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

Similar Documents

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

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

When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial

Isolating real roots of real polynomials

Efficient Isolation of a Polynomial Real Roots

A fast parallel algorithm for determining all roots of a polynomial with real roots

Efficient Isolation of a Polynomial Real Roots

On Multiple Roots in Descartes ’ Rule and Their Distance to Roots of Higher Derivatives

Multivariate Descartes' Rule (1996)

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