4

I am under the impression there are certain types of polynomials that root finders have trouble with. In other words, multiple real roots, complex roots very near to each other, etc. I am not interested in polynomials with order greater than 100.

I have been working on a new polynomial root finder and want to test it. I have bench marked it against Jenkins Traub, and do very well against that, but I am not sure that I am testing it with "difficult" polynomials.

My current test involves finding the roots of polynomials built with random coefficients, or building a polynomial from random roots (all real, all imaginary, all complex, or a mixture of these).

Is there any documentation that defines known problematic polynomials that can test the effectiveness of a root finder? Or can someone give some good testing guidelines for me to use?

user5108_Dan
  • 193

2 Answers2

2

There are several, somewhat standard polynomials for benchmarking factorization algorithms. They may be of larger degree than what you're interested in but many agree that new algorithms should be able to factor these in a "reasonable" amount of time. (See this paper for some recent performance information.)

  • Zimmermann has a collection of polynomials $P_1, \ldots, P_8$ of degrees from 156 to 972, respectively, coming from many sources which serve as a common benchmark for testing the performance of factoring algorithms.
  • van Hoeij includes the 5-set and 6-set resolvent polynomials $M_{12,5}$ and $M_{12,6}$ in his highly influential knapsack-based algorithm.
  • In general, the Swinnerton-Dyer polynomials are notorious for being difficult to factor. which can be defined inductively: given a set of prime numbers $\mathcal{P}$, $$ \begin{align} S_\emptyset(x) &= x, \\ S_{\mathcal{P} \cup \{p\}} &= \text{Res}_y\big((x+y)^2 - p, S_\mathcal{P}(y)\big) \end{align} $$ where $\text{Res}_y(f,g)$ is the resultant of $f$ and $g$ with respect to $y$. (Several other difficult to factor polynomials use resultant-based methods in their definition / construction.)

Care should be taken with using polynomials constructed using random coefficients as they have well-studied root structure and may not be as "random" as you think.

Chris Swierczewski
  • 440
  • I appreciate your answer, but I am an Electrical Engineer, not a mathematician, and this is a bit over my head, and for some reason I can't unzip the files on the Zimmernan site. I am not trying to push the state of the art. I needed a root finder more accurate and simpler than J-T, and now I need to rigorously test my work. Unfortunately, everything I find on root finding is either written for professional mathematicians, or for kids learning the quadratic formula. There seems to be nothing in between. – user5108_Dan Aug 05 '15 at 15:42
  • Typically, one doesn't need to test if a root-finding method works for high-multiplicity roots since a square-free factorization is usually applied first. This can be efficiently done using Yun's algorithm.

    I suppose one way to test if a numerical root was found would be to use Newton's method on the output. If the roots are sufficiently good approximations then Newton's method will converge in one iteration.

     – Chris Swierczewski Aug 05 '15 at 16:27
1

This is an answer to my own question. I found this paper that lists the test polynomials used by Jenkins Traub and others.

http://homepages.neiu.edu/~zzeng/Papers/zrootpak.pdf

user5108_Dan
  • 193