Accelerated Newton Iteration: Roots of Black Box Polynomials and Matrix Eigenvalues

Anand Louis, Santosh S. Vempala

We study the problem of computing the largest root of a real rooted polynomial $p(x)$ to within error $\epsilon$ given only black box access to it, i.e., for any $x \in {\mathb…