Complexity Analysis of Algorithms in Algebraic Computation

Candidate: Vikram Sharma

Advisor: Chee Yap

Numerical computations with real algebraic numbers require algorithms for approximating and
isolating real roots of polynomials. A classical choice for root approximation is Newton's method.
For an analytic function on a Banach space, Smale introduced the concept of approximate zeros,
i.e., points from which Newton's method for the function converges quadratically. To identify these
approximate zeros he gave computationally verifiable convergence criteria called point estimates.
However, in developing these results Smale assumed that Newton's method is computed exactly.
For a system of $n$ homogeneous polynomials in $n+1$ variables, Malajovich developed point
estimates for a different definition of approximate zero, assuming that all operations in Newton's
method are computed with fixed precision. In the first half of this dissertation, we develop point
estimates for these two different definitions of approximate zeros of an analytic function on a
Banach space, but assume the strong bigfloat computational model of Brent, i.e., where all operations
involve bigfloats with varying precision. In this model, we derive a uniform complexity bound
for approximating a root of a zero-dimensional system of $n$ integer polynomials in $n$ variables.
We also derive a non-asymptotic bound, in terms of the condition number of the system, on the
precision required to implement the robust Newton method

The second part of the dissertation analyses the worst-case complexity of two algorithms for
isolating real roots of a square-free polynomial with real coefficients: The Descartes method
and Akritas' continued fractions algorithm. The analysis of both algorithms is based upon
amortization bounds such as the Davenport-Mahler bound. For the Descartes method, we give
a unified framework that encompasses both the power basis and the Bernstein basis variant
of the method; we derive an $O(n(L+\log n))$ bound on the size of the recursion tree obtained
by applying the method to a square-free polynomial of degree n with integer coefficients
of bit-length $L$, the bound is tight for $L=\Omega(\log n)$; based upon this result we
readily obtain the best known bit-complexity bound of $\wt{O}(n^4L2) $ for the Descartes
method, where $\wt{O}$ means we ignore logarithmic factors. Similar worst case bounds
on the bit-complexity of Akritas' algorithm were not known in the literature. We provide the
first such bound, $\wt{O}(n^{12}L3)$, for a square-free integer polynomial of degree $n$
and coefficients of bit-length $L$.