NDLI: From approximate factorization to root isolation

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

Solving equations with size constraints for the solutions

Convex algebraic geometry and semidefinite optimization

A new truncated fourier transform algorithm

Lattices with symmetry

Exact linear and integer programming: tutorial abstract

Approximately counting semismooth integers

Critical point methods and effective real algebraic geometry: new results and trends

The complexity of factoring univariatepolynomials over the rationals: tutorial abstract

An explicit expression of the Lüroth invariant

Computer algebra: a 32-year update

Multiple GCDs. probabilistic analysis of the plain algorithm

Integrability conditions for parameterized linear difference equations

Rainbow cliques and the classification of small BLT-sets

Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields

A term rewriting system for the calculus of moving surfaces

Hermite reduction and creative telescoping for hyperexponential functions

Complexity estimates for two uncoupling algorithms

Creative telescoping for rational functions using the griffiths: dwork method

On the integration of differential fractions

Rational univariate representations of bivariate systems and applications

Separating linear forms for bivariate systems

Cylindrical algebraic decompositions for boolean combinations

Constructing a single open cell in a cylindrical algebraic decomposition

Factoring bivariate lacunary polynomials without heights

A new view on HJLS and PSLQ: sums and projections of lattices

Desingularization explains order-degree curves for ore operators

Fast algorithms for l-adic towers over finite fields

Combinatorics of 4-dimensional resultant polytopes

Simultaneous computation of the row and column rank profiles

On the complexity of computing gröbner bases for quasi-homogeneous systems

Computing rational solutions of linear matrix inequalities

Calculation of the subgroups of a trivial-fitting group

Finding hyperexponential solutions of linear ODEs by numerical evaluation

Sparse multivariate function recovery from values with noise and outlier errors

Quantum fourier transform over symmetric groups

Second order differential equations with hypergeometric solutions of degree three

Certified symbolic manipulation: bivariate simplicial polynomials

On the complexity of solving bivariate systems: the case of non-singular solutions

Enhanced computations of gröbner bases in free algebras as a new application of the letterplace paradigm

Multivariate difference-differential dimension polynomials and new invariants of difference-differential field extensions

Sparse difference resultant

From approximate factorization to root isolation

The termination of the F5 algorithm revisited

On the boolean complexity of real root refinement

Computing the invariant structure of integer matrices: fast algorithms into practice

Termination conditions for positivity proving procedures

Integration of unspecified functions and families of iterated integrals

Signature rewriting in gröbner basis computation

Finding points on real solution components and applications to differential polynomial systems

Gröbner bases of ideals invariant under a commutative group: the non-modular case

Structured FFT and TFT: symmetric and lattice polynomials

Interfacing mathemagix with C++

Verified error bounds for real solutions of positive-dimensional polynomial systems

Computing column bases of polynomial matrices

From approximate factorization to root isolation

Content Provider	ACM Digital Library
Author	Sagraloff, Michael Mehlhorn, Kurt Wang, Pengming
Abstract	We present an algorithm for isolating all roots of an arbitrary complex polynomial p which also works in the presence of multiple roots provided that arbitrary good approximations of the coefficients of p and the number of distinct roots are given. Its output consists of pairwise disjoint disks each containing one of the distinct roots of p, and its multiplicity. The algorithm uses approximate factorization as a subroutine. For the case, where Pan's algorithm [16] is used for the factorization, we derive complexity bounds for the problems of isolating and refining all roots which are stated in terms of the geometric locations of the roots only. Specializing the latter bounds to a polynomial of degree d and with integer coefficients of bitsize less than τ, we show that $Õ(d^{3}+d^{2}τ+dκ)$ bit operations are sufficient to compute isolating disks of size less than $2^{-κ}$ for all roots of p, where κ is an arbitrary positive integer. Our new algorithm has an interesting consequence on the complexity of computing the topology of a real algebraic curve specified as the zero set of a bivariate integer polynomial and for isolating the real solutions of a bivariate system. For input polynomials of degree n and bitsize τ, the currently best running time improves from $Õ(n^{9}τ+n^{8}τ^{2})$ (deterministic) to $Õ(n^{6}+n^{5}τ)$ (randomized) for topology computation and from $Õ(n^\{8\}+n^{7}τ)$ (deterministic) to $Õ(n^{6}+n^{5}τ)$ (randomized) for solving bivariate systems.
Starting Page	283
Ending Page	290
Page Count	8
File Format	PDF
ISBN	9781450320597
DOI	10.1145/2465506.2465523
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-06-26
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Certified algorithms Root refinement Bit complexity Cylindrical algebraic decomposition Root isolation Numerical algorithms
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

From approximate factorization to root isolation with application to cylindrical algebraic decomposition (2013).

From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition (2013)

3 From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition (2013)

From Approximate Factorization to Root Isolation with Application to Cylindrical lgebraic Decomposition

From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition

Efficiently Computing Real Roots of Sparse Polynomials

A near-optimal algorithm for computing real roots of sparse polynomials

An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for optimization problems

An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination

From approximate factorization to root isolation

Similar Documents

From approximate factorization to root isolation with application to cylindrical algebraic decomposition (2013).

From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition (2013)

3 From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition (2013)

From Approximate Factorization to Root Isolation with Application to Cylindrical lgebraic Decomposition

From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition

Efficiently Computing Real Roots of Sparse Polynomials

A near-optimal algorithm for computing real roots of sparse polynomials

An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for optimization problems

An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination

From approximate factorization to root isolation