On the complexity of isolating real roots and computing with certainty the topological degree

DOI10.1006/jcom.2001.0636zbMath1008.65022OpenAlexW2003860131MaRDI QIDQ700184

Jean-Claude Yakoubsohn, Mourrain, Bernard, Michael N. Vrahatis

Publication date: 30 September 2002

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.2001.0636

zbMATH Keywords

complexityalgorithmtopological degreezero isolationreal rootsB-SplinesStenger's degree computational method

Mathematics Subject Classification ID

Degree, winding number (55M25) Numerical computation of solutions to single equations (65H05) Complexity and performance of numerical algorithms (65Y20)

Related Items (20)

Continuous amortization and extensions: with applications to bisection-based root isolation ⋮ Real algebraic numbers and polynomial systems of small degree ⋮ Certified numerical real root isolation for bivariate nonlinear systems ⋮ Existence and computation of short-run equilibria in economic geography ⋮ A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration ⋮ Robust feasibility of systems of quadratic equations using topological degree theory ⋮ Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions ⋮ Topological degree theory and local analysis of area preserving maps ⋮ Univariate real root isolation in an extension field and applications ⋮ A reliable algorithm for computing the topological degree of a mapping in \(\mathbb R^{2}\) ⋮ A two-steps algorithm for approximating real roots of a polynomial in Bernstein basis ⋮ On the computation of an arrangement of quadrics in 3D ⋮ Determining the number of real roots of polynomials through neural networks ⋮ Topology and arrangement computation of semi-algebraic planar curves ⋮ Subdivision methods for solving polynomial equations ⋮ An Adapted Branch and Bound Algorithm for Approximating Real Root of a Ploynomial ⋮ On perturbation of roots of homogeneous algebraic systems ⋮ COMPUTING TWO LINCHPINS OF TOPOLOGICAL DEGREE BY A NOVEL DIFFERENTIAL EVOLUTION ALGORITHM ⋮ Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions ⋮ Survey on generalizations of the intermediate value theorem and applications

Uses Software

• CHABIS
• INTBIS
• RFSFNS
• ZEBEC
• INTOPT_90
• ISOLATE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of computing topological degree of Lipschitz functions in n dimensions
• ZEBEC: A mathematical software package for computing simple zeros of Bessel functions of real order and complex argument
• Asymptotic near optimality of the bisection method
• Derived eigenvalues of symmetric matrices, with applications to distance geometry
• A rapid generalized method of bisection for solving systems of non-linear equations
• Optimal solution of nonlinear equations
• The dimension of bivariate spline spaces of smoothness r for degree \(d\geq 4r+1\)
• On the construction of sufficient refinements for computation of topological degree
• Bisection is optimal
• On the calculation of the exact number of zeroes of a set of equations
• On the determination of the number and multiplicity of zeros of a function
• Computing the topological degree of a mapping in \(R^n\)
• An efficient degree-computation method for a generalized method of bisection
• A simplification of Stenger's topological degree formula
• RFSFNS: A portable package for the numerical determination of the number and the calculation of roots of Bessel functions
• Rigorous global search: continuous problems
• Computing the topological degree with noisy information
• An efficient method for locating and computing periodic orbits of nonlinear mappings
• Deflation techniques for the calculation of further solutions of a nonlinear system
• A bisection method for systems of nonlinear equations
• A Short Proof and a Generalization of Miranda's Existence Theorem
• Algorithm 666: Chabis: a mathematical software package for locating and evaluating roots of systems of nonlinear equations
• Interval Slopes for Rational Functions and Associated Centered Forms
• The determination of the location of the global maximum of a function in the presence of several local extrema
• Some tests of generalized bisection
• Solving systems of nonlinear equations using the nonzero value of the topological degree
• Simplicial and Continuation Methods for Approximating Fixed Points and Solutions to Systems of Equations
• Bounding the Solution of Interval Linear Equations
• The Calculation of the Topological Degree by Quadrature
• A two-dimensional analogue to the method of bisections for solving nonlinear equations
• An algorithm for numerical calculation of topological degree
• A Three-Dimensional Analogue to the Method of Bisections for Solving Nonlinear Equations
• Structure and Breakdown of Invariant Tori in a 4-D Mapping Model of Accelerator Dynamics
• Computation of Topological Degree Using Interval Arithmetic, and Applications
• The topological degree theory for the localization and computation of complex zeros of bessel functions
• PERIODIC ORBITS AND INVARIANT SURFACES OF 4D NONLINEAR MAPPINGS
• On the Localization and Computation of Zeros of Bessel Functions
• The Poincare-Miranda Theorem
• Locating and Computing Zeros of Airy Functions
• Algorithm 681: INTBIS, a portable interval Newton/bisection package
• Existence Verification for Singular Zeros of Complex Nonlinear Systems
• Locating and Computing Arbitrarily Distributed Zeros
• An Optimal Complexity Algorithm for Computing the Topological Degree in Two Dimensions
• Locating and Computing All the Simple Roots and Extrema of a Function
• Application of the characteristic bisection method for locating and computing periodic orbits in molecular systems
• Locating and computing in parallel all the simple roots of special functions using PVM

This page was built for publication: On the complexity of isolating real roots and computing with certainty the topological degree