English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of computing the largest root of a real rootedpolynomial $p(x)$ to within error $\varepsilon $ given only black box access toit, i.e., for any $x \in {\mathbb R}$, the algorithm can query an oracle forthe value of $p(x)$, but the algorithm is not allowed access to thecoefficients of $p(x)$. A folklore result for this problem is that the largestroot of a polynomial can be computed in $O(n \log (1/\varepsilon ))$ polynomialqueries using the Newton iteration. We give a simple algorithm that queries theoracle at only $O(\log n \log(1/\varepsilon ))$ points, where $n$ is the degreeof the polynomial. Our algorithm is based on a novel approach for acceleratingthe Newton method by using higher derivatives.  As a special case, we consider the problem of computing the top eigenvalue ofa 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 todescribe the matrix and $\log(1/\varepsilon )$. Well-known methods such as thepower iteration and Lanczos iteration incur running time polynomial in$1/\varepsilon $, while Gaussian elimination takes $\Omega(n^4)$ bitoperations. As a corollary of our main result, we obtain a$\tilde{O}(n^{\omega} \log^2 ( ||A||_F/\varepsilon ))$ bit complexity algorithmto compute the top eigenvalue of the matrix $A$ or to check if it isapproximately PSD ($A \succeq -\varepsilon I$).

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