What types of polynomials cause root finders to fail? 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?
 A: 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.
A: 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
