Complexity of recovering all roots of a polynomial

Given a polynomial of degree n and a list of putative roots $$\{r_i\}_{i=1}^{n}$$, we can verify that all the putative roots are indeed correct by $$n$$ applications of Horner's method. Hence verifying the solution requires $$\mathcal{O}(n)$$ storage and $$\mathcal{O}(n^2)$$ floating point operations.

Now, if we use the method described here we find that we compute all roots of a polynomial using $$\mathcal{O}(n)$$ storage and $$\mathcal{O}(n^2)$$ flops in a backwards-stable way.

Since computing the roots and verifying they are correct have the same complexity, it feels like $$\mathcal{O}(n)$$ storage and $$\mathcal{O}(n^2)$$ flops is optimal. (Certainly the storage is optimal complexity.)

Could there exist a faster method to recover the roots than $$\mathcal{O}(n^2)$$? Have $$\mathcal{O}(n\log n)$$ algorithms been ruled out somehow?

• Since you can't get analytic values (within the subset of real numbers which includes "pure" roots), the computational methods will also depend on the allowable error. Is it shown that, for computed roots of error $\epsilon$ you can do the polynomial evaluation to the same $\epsilon$ or a matching $\delta$ (to steal from Calculus) in the same order of time? Mar 10 at 15:02
• @CarlWitthoft: I believe that you cannot guarantee any error on the root, only the backward error. Mar 10 at 16:25

Evaluating a polynomial of degree $$ in $$n$$ points can be done in time $$O(n\log n)$$. This is called fast multipoint evaluation; see for instance von zur Gathen, Modern Computer Algebra, ch. 10.

• I'm not sure this is what the OP asked. My impression is that he knows how to evaluate, but is looking for the optimal algorithm for calculating roots. Mar 10 at 14:52
• @CarlWitthoft Yes, this is more a frame challenge than an answer. OP starts from the assumption that verifying that $n$ points are roots (evaluating) costs $O(n^2)$. But (surprisingly and non-obviously) this assumption is wrong, as there is a better algorithm in literature. Mar 10 at 15:23
• The challenge to the framing is useful. I think now the question should be "is there an nlog n algorithm to recover all roots?" Mar 10 at 16:26
• In this case, the answer is better than the original question. Mar 10 at 16:36
• This reference, however, states that the fast evaluation is numerically unstable: arxiv.org/ftp/arxiv/papers/1304/1304.8069.pdf Mar 10 at 17:04