6
$\begingroup$

Finding the roots of a complex polynomial is in general extremely numerically unstable, as discussed in (1). According to Pan ((2), (3)), this produces a cubic complexity lower bound, and he presents a near-optimal algorithm which is quasilinear in arithmetic and quasicubic in boolean (control flow) complexity. His algorithm is an improvement to the splitting circle method.

However, this lower bound applies only if we want forward stable (i.e., correct) answers. If we're satisfied with backward stable answers, where it's okay to find correct roots for a slightly modified input problem, I would expect much faster complexities to be possible. Does anyone know if such an algorithm exists, and specifically if a splitting circle variant can run in quasilinear time if we only need backward stability?

Note: $\epsilon$ in $\tilde{O}(n \log(1/\epsilon))$ vaguely refers to the relative backward accuracy of the result (the amount you have to shift the coefficients to move to the roots to the computed answers). I'm not sure exactly what the correct definition of $\epsilon$ would be, since different coefficients can change the polynomial values by dramatically different amounts.

Improve this question
$\endgroup$
3
  • $\begingroup$ Good point. I added a note explaining $\epsilon$. $\endgroup$
    – Geoffrey Irving
    Aug 12 '12 at 16:18
  • $\begingroup$ you could assume that the highest coefficient is one and $x$ is scaled such that one of the well-known simple bounds for the zeros is 1; then $\epsilon$ could be the maximal absolute change of a coefficient. $\endgroup$
    – Arnold Neumaier
    Aug 12 '12 at 16:45
  • $\begingroup$ That works as long as the roots are bounded away from zero; if they approach zero the low degree coefficients start mattering a lot more than those of high degree. $\endgroup$
    – Geoffrey Irving
    Aug 12 '12 at 16:50
6
$\begingroup$

I don't know about the theoretical complexity. But the practically fastest algorithm for finding all zeros of a polynomial given as a finite power series is the algorithm by Traub [1]. It factors a degree $n$ polynomial in typically $O(n^2)$ time.

See also [2].

For factoring a polynomial accessible only through its function values, see, e.g., my paper [3].

References:

  1. Jenkins MA, Traub JF. 1972. Algorithm 419: zeros of a complex polynomial [C2]. Communications of the ACM 15: 97–99.
  2. Pan VY. 1997. Solving a Polynomial Equation: Some History and Recent Progress. SIAM Review 39: 187.
  3. Neumaier A. 2003. Enclosing clusters of zeros of polynomials. Journal of Computational and Applied Mathematics 156: 389–401. [pdf]
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, especially for your reference on coefficient-free methods! That might have been my next question otherwise, since its much more stable to evaluate something like a tridiagional characteristic polynomial using special formulas rather than coefficient expansion. Does your method work as an accurate tridiagional eigenvalue solver? $\endgroup$
    – Geoffrey Irving
    Aug 12 '12 at 16:39
3
$\begingroup$

As mentioned in [1], Reif [2] gives an $O(n \log^2 n (\log n + \log \epsilon))$ algorithm for the case when all roots are real, which is $O(n \log^3 n)$ as long as $\epsilon = n^{O(1)}$. He analyzes only the case of exact arithmetic, but after going through the algorithm I believe it is (or could be modified to be) backward stable. His method is an improved variant of the splitting circle method specialized to the real line.

In the exact arithmetic case, this gives $O(n \log^3 n)$ algorithm for the Hermitian tridiagonal eigenproblem. However, since the first step is to compute the characteristic polynomial, I believe the stability properties of this approach would be poor.

He states that a similar efficient algorithm for the general complex root case is unknown, at least by 1999.

  1. Why can't Householder reflections diagonalize a matrix?
  2. Reif, J. 1999. An efficient algorithm for the real root and symmetric tridiagonal eigenvalue problems.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.