We present a general framework for analyzing the complexity of subdivision-based algorithms whose tests are based on the sizes of regions and their distance to certain sets (often varieties) intrinsic to the problem under study. We call such tests diameter-distance tests. We illustrate that diameter-distance tests are common in the literature by proving that many interval arithmetic-based tests are, in fact, diameter-distance tests. For this class of algorithms, we provide both non-adaptive bounds for the complexity, based on separation bounds, as well as adaptive bounds, by applying the framework of continuous amortization. Using this structure, we provide the first complexity analysis for the algorithm by Plantinga and Vegeter for approximating real implicit curves and surfaces. We present both adaptive and non-adaptive a priori worst-case bounds on the complexity of this algorithm both in terms of the number of subregions constructed and in terms of the bit complexity for the construction. Finally, we construct families of hypersurfaces to prove that our bounds are tight.
For univariate problems, the analysis of subdivision-based algorithms is well-understood, and there are several results, especially for the case of approximating the roots of polynomials, see, e.g., @cite_8 @cite_29 @cite_24 @cite_47 @cite_43 @cite_21 , and the references therein. Moreover, it also possible to modify the subdivision process by applying the Newton operator, see @cite_9 @cite_45 , and considerably improve both the complexity and the actual running time of the corresponding algorithms. However, in higher dimensions, very little is known. For example, there are no explicit complexity results for pure subdivision-based algorithms for approximating curves and surfaces.
@cite_8 @cite_29 @cite_21 @cite_9 @cite_24 @cite_43 @cite_45 @cite_47
2084184830 2185262283 203551860 1997509004
Let f be a univariate polynomial with real coefficients, f@?R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm. The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+lnd)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits. Our proof uses two amortization-based techniques: first, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds. This thesis deals with the application of subdivision based algorithms to the problem of isolating the roots of a complex polynomial. We provide a comprehensive comparison of the performance of three interval arithmetic based predicates (the interval Newton, Krawczyk and Hansen-Sengupta operators) with predicates based on complex analysis (the CEVAL algorithm and Yakoubsohn’s approach). In addition, we include a treatment of the mathematical theory behind these operators. Let f be a univariate polynomial with real coefficients, f ∈ R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the roots of f in a given interval. In this paper, we consider subdivision algorithms based on purely numerical primitives such as function evaluation. Such methods have adaptive complexity, are local, and are also applicable when f is transcendental. The complexity analysis of adaptive algorithms is a new challenge for computer science. In this paper, we introduce a form of continuous amortization for adaptive complexity. Our analysis is applied to an evaluation-based root isolation algorithm called EVAL. EVAL is based on an algorithm of Mitchell and can also be seen as a 1-dimensional analogue of algorithms by Plantinga and Vegter for meshing curves and surfaces. The algorithm itself is simple, but its complexity analysis is not. Our main result is an O(d3(log d+L)) bound on the subdivision-tree size of EVAL for the benchmark problem of isolating all real roots of a square-free integer polynomial f of degree d and logarithmic height L. Our proof introduces several novel techniques: First, we provide an adaptive upper bound on the complexity of EVAL using an integral, analogous to integral bounds provided by Ruppert in a different context. Such integrals can be viewed as a form of continuous amortization. In addition, we use two algebraic amortization techniques: one is based on the standard Mahler-Davenport root bounds, but the other, based on evaluation bounds, is new. We introduce a novel algorithm denoted NewDsc to isolate the real roots of a univariate square-free polynomial f with integer coefficients. The algorithm iteratively subdivides an initial interval which is known to contain all real roots of f and performs exact (rational) operations on the coefficients of f in each step. For the subdivision strategy, we combine Descartes' Rule of Signs and Newton iteration. More precisely, instead of using a fixed subdivision strategy such as bisection in each iteration, a Newton step based on the number of sign variations for an actual interval is considered, and, only if the Newton step fails, we fall back to bisection. Following this approach, quadratic convergence towards the real roots is achieved in most iterations. In terms of complexity, our method induces a recursion tree of almost optimal size O(n·log(nτ)), where n denotes the degree of the polynomial and τ the bitsize of its coefficients. The latter bound constitutes an improvement by a factor of τ upon all existing subdivision methods for the task of isolating the real roots. We further provide a detailed complexity analysis which shows that NewDsc needs only O(n3τ) bit operations to isolate all real roots of f. In comparison to existing asymptotically fast numerical algorithms (e.g. the algorithms by V. Pan and A. Schonhage), NewDsc is much easier to access and, due to its similarities to the classical Descartes method, it seems to be well suited for an efficient implementation.