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.
A challenge to current theories of computing in the continua is the proper treatment of the zero test. Such tests are critical for extracting geometric information. Zero tests are expensive and may be uncomputable. So we seek geometric algorithms based on a weak form of such tests, called soft zero tests. Typically, algorithms with such tests can only determine the geometry for “nice” (e.g., non-degenerate, non-singular, smooth, Morse, etc) inputs. Algorithms that avoid such niceness assumptions are said to be complete. Can we design complete algorithms with soft zero tests? We address the basic problem of determining the geometry of the roots of a complex analytic function f. We assume effective box functions for f and its higher derivatives are provided. The problem is formalized as the root clustering problem, and we provide a complete (δ,e)-exact algorithm based on soft zero tests.  This paper presents two results on the complexity of root isolation via Sturm sequences. Both results exploit amortization arguments. 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. 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 give a unified ("basis free") framework for the Descartes method for real root isolation of square-free real polynomials. This framework encompasses the usual Descartes' rule of sign method for polynomials in the power basis as well as its analog in the Bernstein basis. We then give a new bound on the size of the recursion tree in the Descartes method for polynomials with real coefficients. Applied to polynomials A(X) = Eni=0 aiXi with integer coefficients |ai| < 2L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(logn), and we use it to derive the best known bit complexity bound for the integer case.  