¿Qué tipos de polinomios hacen que fallen los buscadores de raíces?

Question

Tengo la impresión de que hay ciertos tipos de polinomios con los que los buscadores de raíces tienen problemas. Es decir, raíces reales múltiples, raíces complejas muy cercanas entre sí, etc. No me interesan los polinomios de orden superior a 100.

He estado trabajando en un nuevo buscador de raíces de polinomios y quiero probarlo. Lo he probado contra Jenkins Traub, y lo hace muy bien contra eso, pero no estoy seguro de que lo esté probando con polinomios "difíciles".

Mi prueba actual consiste en encontrar las raíces de polinomios construidos con coeficientes aleatorios, o construir un polinomio a partir de raíces aleatorias (todas reales, todas imaginarias, todas complejas, o una mezcla de ellas).

¿Existe alguna documentación que defina los polinomios problemáticos conocidos que puedan probar la eficacia de un buscador de raíces? ¿O puede alguien dar algunas buenas directrices de prueba para que yo use?

Answer 1

Existen varios polinomios, en cierto modo estándar, para evaluar los algoritmos de factorización. Pueden ser de mayor grado que el que te interesa, pero muchos están de acuerdo en que los nuevos algoritmos deberían ser capaces de factorizarlos en un tiempo "razonable". (Véase este documento para obtener información sobre el rendimiento reciente).

• Zimmermann tiene una colección de polinomios $P_1, \ldots, P_8$ de grados de 156 a 972, respectivamente, procedentes de muchas fuentes que sirven de referencia común para probar el rendimiento de los algoritmos de factorización.
• van Hoeij incluye los polinomios resolventes de 5 y 6 conjuntos $M_{12,5}$ et $M_{12,6}$ en su influyente algoritmo basado en la mochila.
• En general, los polinomios de Swinnerton-Dyer tienen fama de ser difíciles de factorizar. que pueden definirse inductivamente: dado un conjunto de números primos $\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}$$ donde $\text{Res}_y(f,g)$ es la resultante de $f$ et $g$ con respecto a $y$ . (Varios otros polinomios difíciles de factorizar utilizan métodos basados en la resultante en su definición / construcción).

Hay que tener cuidado con el uso de polinomios construidos con coeficientes aleatorios, ya que tienen una estructura de raíces bien estudiada y pueden no ser tan "aleatorios" como se piensa.

Answer 2

Esto es una respuesta a mi propia pregunta. He encontrado este documento que enumera los polinomios de prueba utilizados por Jenkins Traub y otros.

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