The Experts below are selected from a list of 8550 Experts worldwide ranked by ideXlab platform
Chee Yap - One of the best experts on this subject based on the ideXlab platform.
-
effective Subdivision Algorithm for isolating zeros of real systems of equations with complexity analysis
International Symposium on Symbolic and Algebraic Computation, 2019Co-Authors: Chee YapAbstract:We describe a new Algorithm Miranda for isolating the simple zeros of a function \boldsymbolf :\mathbbR ^n\to\mathbbR ^n within a box B_0\subseteq\mathbbR ^n. The function \boldsymbolf and its partial derivatives must have interval forms, but need not be polynomial. Our Subdivision-based Algorithm is "effective'' in the sense that our Algorithmic description also specifies the numerical precision that is sufficient to certify an implementation with any standard BigFloat number type. The main predicate is the Moore-Kioustelidis (MK) test, based on Miranda's Theorem (1940). Although the MK test is well-known, this paper appears to be the first synthesis of this test into a complete root isolation Algorithm. We provide a complexity analysis of our Algorithm based on intrinsic geometric parameters of the system. Our Algorithm and complexity analysis are developed using 3 levels of description (Abstract, Interval, Effective). This methodology provides a systematic pathway for achieving effective Subdivision Algorithms in general.
-
effective Subdivision Algorithm for isolating zeros of real systems of equations with complexity analysis
arXiv: Numerical Analysis, 2019Co-Authors: Chee YapAbstract:We describe a new Algorithm \texttt{Miranda} for isolating the simple zeros of a function $\boldsymbol{f}:{\mathbb R}^n\to{\mathbb R}^n$ within a box $B_0\subseteq {\mathbb R}^n$. The function $\boldsymbol{f}$ and its partial derivatives must have interval forms, but need not be polynomial. Our Subdivision-based Algorithm is "effective" in the sense that our Algorithmic description also specifies the numerical precision hat is sufficient to certify an implementation with any standard BigFloat number type. The main predicate is the Moore-Kioustelides (MK) test, based on Miranda's Theorem (1940). Although the MK test is well-known, this paper appears to be the first synthesis of this test into a complete root isolation Algorithm. We provide a complexity analysis of our Algorithm based on intrinsic geometric parameters of the system. Our Algorithm and complexity analysis are developed using 3 levels of description (Abstract, Interval, Effective). This methodology provides a systematic pathway for achieving effective Subdivision Algorithms in general.
-
complexity analysis of root clustering for a complex polynomial
International Symposium on Symbolic and Algebraic Computation, 2016Co-Authors: Ruben Becker, Michael Sagraloff, Vikram Sharma, Chee YapAbstract:Let F(z) be an arbitrary complex polynomial. We introduce the {local root clustering problem}, to compute a set of natural epsilon-clusters of roots of F(z) in some box region B0 in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is two-fold: we provide an efficient certified Subdivision Algorithm for this problem, and we provide a bit-complexity analysis based on the local geometry of the root clusters. Our computational model assumes that arbitrarily good approximations of the coefficients of F(z) are provided by means of an oracle at the cost of reading the coefficients. Our Algorithmic techniques come from a companion paper [3] and are based on the Pellet test, Graeffe and Newton iterations, and are independent of Schonhage's splitting circle method. Our Algorithm is relatively simple and promises to be efficient in practice.
-
empirical study of an evaluation based Subdivision Algorithm for complex root isolation
Symbolic Numeric Computation, 2012Co-Authors: Narayan Kamath, Irina Voiculescu, Chee YapAbstract:We provide an empirical study of Subdivision Algorithms for isolating the simple roots of a polynomial in any desired box region B0 of the complex plane. One such class of Algorithms is based on Newton-like interval methods (Moore, Krawczyk, Hansen-Sengupta). Another class of Subdivision Algorithms is based on function evaluation. Here, Yakoubsohn discussed a method that is purely based on an exclusion predicate. Recently, Sagraloff and Yap introduced another Algorithm of this type, called Ceval. We describe the first implementation of Ceval in Core Library. We compare its performance to the above mentioned Algorithms, and also to the well-known MPSolve software from Bini and Florentino. Our results suggest that certified evaluation-based methods such as Ceval are encouraging and deserve further exploration.
-
a simple but exact and efficient Algorithm for complex root isolation
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Chee Yap, Michael SagraloffAbstract:We present a new exact Subdivision Algorithm CEVAL for isolating the complex roots of a square-free polynomial in any given box. It is a generalization of a previous real root isolation Algorithm called EVAL. Under suitable conditions, our approach is applicable for general analytic functions. CEVAL is based on the simple Bolzano Principle and is easy to implement exactly. Preliminary experiments have shown its competitiveness. We further show that, for the "benchmark problem" of isolating all roots of a square-free polynomial with integer coefficients, the asymptotic complexity of both Algorithms EVAL and CEVAL matches (up a logarithmic term) that of more sophisticated real root isolation methods which are based on Descartes' Rule of Signs, Continued Fraction or Sturm sequence. In particular, we show that the tree size of EVAL matches that of other Algorithms. Our analysis is based on a novel technique called Δ-clusters from which we expect to see further applications.
Michael Sagraloff - One of the best experts on this subject based on the ideXlab platform.
-
a near optimal Subdivision Algorithm for complex root isolation based on the pellet test and newton iteration
Journal of Symbolic Computation, 2018Co-Authors: Ruben Becker, Michael Sagraloff, Vikram SharmaAbstract:Abstract We describe a Subdivision Algorithm for isolating the complex roots of a polynomial F ∈ C [ x ] . Given an oracle that provides approximations of each of the coefficients of F to any absolute error bound and given an arbitrary square B in the complex plane containing only simple roots of F, our Algorithm returns disjoint isolating disks for the roots of F in B . Our complexity analysis bounds the absolute error to which the coefficients of F have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our Algorithm is controlled by the geometry of the roots in a near neighborhood of the input square B , namely, the number of roots, their absolute values and pairwise distances. The number of Subdivision steps is near-optimal. For the benchmark problem, namely, to isolate all the roots of a polynomial of degree n with integer coefficients of bit size less than τ, our Algorithm needs O ˜ ( n 3 + n 2 τ ) bit operations, which is comparable to the record bound of Pan (2002) . It is the first time that such a bound has been achieved using Subdivision methods, and independent of divide-and-conquer techniques such as Schonhage's splitting circle technique. Our Algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schroder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer Algorithms, our Algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our Algorithm.
-
complexity analysis of root clustering for a complex polynomial
International Symposium on Symbolic and Algebraic Computation, 2016Co-Authors: Ruben Becker, Michael Sagraloff, Vikram Sharma, Chee YapAbstract:Let F(z) be an arbitrary complex polynomial. We introduce the {local root clustering problem}, to compute a set of natural epsilon-clusters of roots of F(z) in some box region B0 in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is two-fold: we provide an efficient certified Subdivision Algorithm for this problem, and we provide a bit-complexity analysis based on the local geometry of the root clusters. Our computational model assumes that arbitrarily good approximations of the coefficients of F(z) are provided by means of an oracle at the cost of reading the coefficients. Our Algorithmic techniques come from a companion paper [3] and are based on the Pellet test, Graeffe and Newton iterations, and are independent of Schonhage's splitting circle method. Our Algorithm is relatively simple and promises to be efficient in practice.
-
Computing Real Roots of Real Polynomials ... and now For Real!
2016Co-Authors: Alexander Kobel, Fabrice Rouillier, Michael SagraloffAbstract:Very recent work introduces an asymptotically fast Subdivision Algorithm, denoted ANewDsc, for isolating the real roots of a univariate real polynomial. The method combines Descartes' Rule of Signs to test intervals for the existence of roots, Newton iteration to speed up convergence against clusters of roots, and approximate computation to decrease the required precision. It achieves record bounds on the worst-case complexity for the considered problem, matching the complexity of Pan's method for computing all complex roots and improving upon the complexity of other Subdivision methods by several magnitudes. In the article at hand, we report on an implementation of ANewDsc on top of the RS root isolator. RS is a highly efficient realization of the classical Descartes method and currently serves as the default real root solver in Maple. We describe crucial design changes within ANewDsc and RS that led to a high-performance implementation without harming the theoretical complexity of the underlying Algorithm. With an excerpt of our extensive collection of benchmarks, available online at this http URL, we illustrate that the theoretical gain in performance of ANewDsc over other Subdivision methods also transfers into practice. These experiments also show that our new implementation outperforms both RS and mature competitors by magnitudes for notoriously hard instances with clustered roots. For all other instances, we avoid almost any overhead by integrating additional optimizations and heuristics.
-
a near optimal Subdivision Algorithm for complex root isolation based on the pellet test and newton iteration
arXiv: Numerical Analysis, 2015Co-Authors: Ruben Becker, Michael Sagraloff, Vikram SharmaAbstract:We describe a Subdivision Algorithm for isolating the complex roots of a polynomial $F\in\mathbb{C}[x]$. Given an oracle that provides approximations of each of the coefficients of $F$ to any absolute error bound and given an arbitrary square $\mathcal{B}$ in the complex plane containing only simple roots of $F$, our Algorithm returns disjoint isolating disks for the roots of $F$ in $\mathcal{B}$. Our complexity analysis bounds the absolute error to which the coefficients of $F$ have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our Algorithm is controlled by the geometry of the roots in a near neighborhood of the input square $\mathcal{B}$, namely, the number of roots, their absolute values and pairwise distances. The number of Subdivision steps is near-optimal. For the \emph{benchmark problem}, namely, to isolate all the roots of a polynomial of degree $n$ with integer coefficients of bit size less than $\tau$, our Algorithm needs $\tilde O(n^3+n^2\tau)$ bit operations, which is comparable to the record bound of Pan (2002). It is the first time that such a bound has been achieved using Subdivision methods, and independent of divide-and-conquer techniques such as Sch\"onhage's splitting circle technique. Our Algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a "soft-test" to count the number of roots in a disk. Using Schr\"oder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer Algorithms, our Algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our Algorithm.
-
a simple but exact and efficient Algorithm for complex root isolation
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Chee Yap, Michael SagraloffAbstract:We present a new exact Subdivision Algorithm CEVAL for isolating the complex roots of a square-free polynomial in any given box. It is a generalization of a previous real root isolation Algorithm called EVAL. Under suitable conditions, our approach is applicable for general analytic functions. CEVAL is based on the simple Bolzano Principle and is easy to implement exactly. Preliminary experiments have shown its competitiveness. We further show that, for the "benchmark problem" of isolating all roots of a square-free polynomial with integer coefficients, the asymptotic complexity of both Algorithms EVAL and CEVAL matches (up a logarithmic term) that of more sophisticated real root isolation methods which are based on Descartes' Rule of Signs, Continued Fraction or Sturm sequence. In particular, we show that the tree size of EVAL matches that of other Algorithms. Our analysis is based on a novel technique called Δ-clusters from which we expect to see further applications.
Zhongkui Lei - One of the best experts on this subject based on the ideXlab platform.
-
an improved high precision Subdivision Algorithm for single track absolute encoder using machine vision techniques
Measurement & Control, 2019Co-Authors: Pengfei Yuan, Daqing Huang, Zhongkui LeiAbstract:In order to achieve high-precision and robust measurement for a single-track absolute encoder, an improved Subdivision Algorithm based on machine vision technology is proposed. First, the composite...
-
an anti spot high precision Subdivision Algorithm for linear ccd based single track absolute encoder
Measurement, 2019Co-Authors: Pengfei Yuan, Daqing Huang, Zhongkui LeiAbstract:Abstract To improve precision performance of angular sensor, in this paper, research is performed on Subdivision technology for a single-track absolute photoelectrical encoder. Firstly, a robust Subdivision Algorithm is proposed by means of processing a feature matrix of measurement which is created from multiple grating lines’ image. Secondly, simulation of anti-noise and anti-spot is established to prove that the proposed Algorithm is robust theoretically. Finally, the Algorithm is applied in a photoelectrical encoder for real tests, experiment result shows that the Subdivision Algorithm proposed in this paper is more accurate and adaptive than the traditional way. To reduce a negative precision effect caused by noises and spots, it measures angle according to multiple grating lines by assigning different weights, making those grating lines deeply noised with lower weight, and higher weight with minor noise, thus the overall accuracy is improved. With the proposed Subdivision Algorithm, test encoder’s standard deviation of error can be increased to 1 . 6 ″ and precision achieves up to ± 0 . 9 ″ .
Zhu Hongli - One of the best experts on this subject based on the ideXlab platform.
-
classic triangular mesh Subdivision Algorithm
Computer Engineering, 2009Co-Authors: Zhu HongliAbstract:This paper makes a concise introduction to seven classic Algorithms of triangular mesh Subdivision, and makes a classification and comparison between them according to their continuity, own advantage and application status. In order to improve the visualization of triangular mesh Subdivision, interactive display control is implemented by using MFC and OpenGL while state machine model based on functional class is used as the software operating pattern. On the basis of this, the prototype implementation of Loop Algorithm is performed. The improved method of solving existing problematic issues from prototype implementation is presented.
Ron Goldman - One of the best experts on this subject based on the ideXlab platform.
-
bezier and b spline curves with knots in the complex plane
Fractals, 2011Co-Authors: Konstantinos I Tsianos, Ron GoldmanAbstract:We extend some well known Algorithms for planar Bezier and B-spline curves, including the de Casteljau Subdivision Algorithm for Bezier curves and several standard knot insertion procedures (Boehm's Algorithm, the Oslo Algorithm, and Schaefer's Algorithm) for B-splines, from the real numbers to the complex domain. We then show how to apply these polynomial and piecewise polynomial Algorithms in a complex variable to generate many well known fractal shapes such as the Sierpinski gasket, the Koch curve, and the C-curve. Thus these fractals also have Bezier and B-spline representations, albeit in the complex domain. These representations allow us to change the shape of a fractal in a natural manner by adjusting their complex Bezier and B-spline control points. We also construct natural parameterizations for these fractal shapes from their Bezier and B-spline representations.
-
Convergence and Smoothness of Nonlinear Lane–Riesenfeld Algorithms in the Functional Setting
Foundations of Computational Mathematics, 2011Co-Authors: Nira Dyn, Ron GoldmanAbstract:We investigate the Lane–Riesenfeld Subdivision Algorithm for uniform B-splines, when the arithmetic mean in the various steps of the Algorithm is replaced by nonlinear, symmetric, binary averaging rules. The averaging rules may be different in different steps of the Algorithm. We review the notion of a symmetric binary averaging rule, and we derive some of its relevant properties. We then provide sufficient conditions on the nonlinear binary averaging rules used in the Lane–Riesenfeld Algorithm that ensure the convergence of the Algorithm to a continuous function. We also show that, when the averaging rules are C ^2 with uniformly bounded second derivatives, then the limit is a C ^1 function. A canonical family of nonlinear, symmetric averaging rules, the p -averages, is presented, and the Lane–Riesenfeld Algorithm with these averages is investigated.
