Speaker: Chee Yap (NYU)

Title: Integral Analysis of Adaptive Algorithms: Real Root Isolation

Abstract: 

There is a recent trend to replace algebraic approaches to meshing
curves and surfaces by more numerical approaches.  The advantage of
the new 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 is totally
non-algebraic (it only uses function evaluation and 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" for 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).

We regard integral analysis as a form of "continuous amortization".
The amortization comes from a Mahler-Davenport type bound for
evaluation of polynomials at algebraic points.

Joint work with Michael Burr and Felix Krahmer.
==============================================