Implementation of a near-optimal complex root clustering algorithm
We describe Ccluster, a software for computing natural ε ε-clusters of complex roots in a
given box of the complex plane. This algorithm from Becker et al.(2016) is near-optimal …
given box of the complex plane. This algorithm from Becker et al.(2016) is near-optimal …
Effective subdivision algorithm for isolating zeros of real systems of equations, with complexity analysis
J Xu, C Yap - Proceedings of the 2019 on International Symposium …, 2019 - dl.acm.org
We describe a new algorithm Miranda for isolating the simple zeros of a
function\boldsymbolf:\mathbbR^ n →\mathbbR^ n within a box B_0 ⊆\mathbbR^ n. The …
function\boldsymbolf:\mathbbR^ n →\mathbbR^ n within a box B_0 ⊆\mathbbR^ n. The …
Accelerated subdivision for clustering roots of polynomials given by evaluation oracles
R Imbach, VY Pan - International Workshop on Computer Algebra in …, 2022 - Springer
In our quest for the design, the analysis and the implementation of a subdivision algorithm
for finding the complex roots of univariate polynomials given by oracles for their evaluation …
for finding the complex roots of univariate polynomials given by oracles for their evaluation …
New progress in univariate polynomial root finding
R Imbach, VY Pan - Proceedings of the 45th International Symposium on …, 2020 - dl.acm.org
The recent advanced sub-division algorithm is nearly optimal for the approximation of the
roots of a dense polynomial given in monomial basis; moreover, it works locally and slightly …
roots of a dense polynomial given in monomial basis; moreover, it works locally and slightly …
Planar minimization diagrams via subdivision with applications to anisotropic Voronoi diagrams
H Bennett, E Papadopoulou… - Computer Graphics Forum, 2016 - Wiley Online Library
Abstract Let X={f1,…, fn} be a set of scalar functions of the form fi: ℝ2→ ℝ which satisfy some
natural properties. We describe a subdivision algorithm for computing a clustered ε‐isotopic …
natural properties. We describe a subdivision algorithm for computing a clustered ε‐isotopic …
Nearly Optimal Black Box Polynomial Root-finders
VY Pan - Proceedings of the 2024 Annual ACM-SIAM …, 2024 - SIAM
Univariate polynomial root-finding has been studied for four millennia and very intensively in
the last decades. Our novel nearly optimal Las Vegas randomized root-finders approximate …
the last decades. Our novel nearly optimal Las Vegas randomized root-finders approximate …
Robust geometric computation
V Sharma, CK Yap - Handbook of Discrete and Computational …, 2017 - taylorfrancis.com
Nonrobustness refers to qualitative or catastrophic failures in geometric algorithms arising
from numerical errors. Section 45.1 provides background on these problems. Although …
from numerical errors. Section 45.1 provides background on these problems. Although …
An approach for certifying homotopy continuation paths: Univariate case
Homotopy continuation is a well-known method in numerical root-finding. Recently, certified
algorithms for homotopy continuation based on Smale's alpha-theory have been developed …
algorithms for homotopy continuation based on Smale's alpha-theory have been developed …
Root-squaring for root-finding
The root-squaring iterations of Dandelin (1826), Lobachevsky (1834), and Gräffe (1837)
recursively produce the coefficients of polynomials ph (x) whose zeros are the 2 h th powers …
recursively produce the coefficients of polynomials ph (x) whose zeros are the 2 h th powers …
[HTML][HTML] Positive root isolation for poly-powers by exclusion and differentiation
We consider a class of univariate real functions—poly-power s—that extend integer
exponents to real algebraic exponents for polynomials. Our purpose is to isolate positive …
exponents to real algebraic exponents for polynomials. Our purpose is to isolate positive …