Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR09-136 | 9th December 2009 16:26

Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique

TR09-136
Authors: Michael Burr, Felix Krahmer, Chee Yap
Publication: 11th December 2009 17:30
Keywords:

Abstract:

Let $f$ be a univariate polynomial with real coefficients, $f\in\RR[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(d^3(\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.

ISSN 1433-8092 | Imprint