Accelerated Newton Iteration: Roots of Black Box Polynomials and Matrix Eigenvalues
We study the problem of computing the largest root of a real rooted polynomial $p(x) to within error \varepsilon given only black box access to it, i.e. for any $x \in \mathbb R} the algorithm can query an oracle for the value of $p(x) but the algorithm is not allowed access to the coefficients of $p(x) A folklore result for this problem is that the largest root of a polynomial can be computed in $O(n \log (1/\varepsilon polynomial queries using the Newton iteration. We give a simple algorithm that queries the oracle at only $O(\log n \log(1/\varepsilon points, where $n$ is the degree of the polynomial. Our algorithm is based on a novel approach for accelerating the Newton method by using higher derivatives. As a special case, we consider the problem of computing the top eigenvalue of a symmetric matrix in \mathbb Q}{n \times n} to within error \varepsilon in time polynomial in the input description, i.e. the number of bits to describe the matrix and \log(1/\varepsilon Well known methods such as the power iteration and Lanczos iteration incur running time polynomial in $1/\varepsilon while Gaussian elimination takes \Omega(n^4) bit operations. As a corollary of our main result, we obtain a \tilde{O}(n^\omega} \log^2 |A||_F/\varepsilon bit complexity algorithm to compute the top eigenvalue of the matrix $A$ or to check if it is approximately PSD $A \succeq \varepsilon I$
ArXiv