On the complexity of the Plantinga-Vegter algorithm
From MaRDI portal
Publication:2172649
DOI10.1007/s00454-022-00403-xzbMath1497.65043arXiv2004.06879OpenAlexW3016434545WikidataQ114229299 ScholiaQ114229299MaRDI QIDQ2172649
Josué Tonelli-Cueto, Felipe Cucker, Alperen Ali Ergur
Publication date: 16 September 2022
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.06879
Analysis of algorithms (68W40) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)
Related Items
Functional norms, condition numbers and numerical algorithms in algebraic geometry, Certified simultaneous isotopic approximation of pairs of curves via subdivision
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Continuous amortization and extensions: with applications to bisection-based root isolation
- On sharp bounds for marginal densities of product measures
- A numerical algorithm for zero counting. III: Randomization and condition
- Computing the homology of real projective sets
- Smoothed analysis of complex conic condition numbers
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
- Approximate zeros and condition numbers
- Computing the homology of semialgebraic sets. II: General formulas
- Towards soft exact computation (invited talk)
- The complexity of subdivision for diameter-distance tests
- Computing the homology of semialgebraic sets. I: Lax formulas
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- The Littlewood-Offord problem and invertibility of random matrices
- A Primal-Dual Algorithm for Solving Polyhedral Conic Systems with a Finite-Precision Machine
- Exploiting Structure in Floating-Point Arithmetic
- Condition
- Small Ball Probabilities for Linear Images of High-Dimensional Distributions
- The probability that a slightly perturbed numerical analysis problem is difficult
- Of What Use Is Floating-Point Arithmetic in Computational Geometry?
- The Probability That a Numerical Analysis Problem is Difficult
- Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time
- High-Dimensional Probability
- Smoothed analysis for the condition number of structured real polynomial systems
- A Class of Fast and Accurate Summation Algorithms
- The Complexity of an Adaptive Subdivision Method for Approximating Real Curves
- Plantinga-Vegter Algorithm takes Average Polynomial Time
- Effective Subdivision Algorithm for Isolating Zeros of Real Systems of Equations, with Complexity Analysis
- On the volume of tubular neighborhoods of real algebraic varieties
- Numerical Inverting of Matrices of High Order. II
