TALK TITLE:
Integral Analysis of Adaptive Algorithms: Real Root Isolation
Chee Yap
Computer Science Theory Seminar
Courant Institute, NYU
Jan 24, 2008
ABSTRACT:
There is a recent trend to replace algebraic approaches
to meshing curves and surfaces by more numerical
approaches. The advantage of the such approaches
is that they are more practical and has adaptive complexity.
However, the complexity analysis of adaptive algorithms is
not well understood.
There is a similar trend for the 1-D case of meshing,
namely, real root isolation: Sturm methods (which is strongly algebraic)
are being surplanted by weaker Descartes methods [Rouillier-Zimmermann 2004].
We recently introduce the EVAL algorithm which
assumes primitives for function evaluation and interval evaluation.
Thus it is applicable a large class of analytic functions.
EVAL is the 1-D version of a meshing algorithm
from Vegter-Plantinga [2006].
In this talk, we introduce a novel technique
to analyze the complexity of EVAL. It is called "integral analysis"
because the complexity is expressed as an integral.
We use the framework of "stopping functions" its analysis.
Suppose f is a square-free polynomial of degree d, with
integer coefficients at most L bits. For simplicity, assume L>log d.
The "benchmark problem" is to isolated all real zeros of f.
For instance, Descartes method has complexity of O(dL)
[Eigenwillig, Sharma, Yap 2006], which is optimal.
We shall prove that EVAL has complexity O(d^2 L).
Integral analysis is a form of "continuous amortization".
The amortization comes from Mahler-Davenport type bounds for
evaluation of polynomials at algebraic points.
Joint work with Michael Burr and Felix Krahmer.
==============================================