Multiplicar n polinomios de grado 1

El problema es calcular el polinomio . Suponga que todos los coeficientes caben en una palabra de máquina, es decir, pueden manipularse en unidades de tiempo. $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$

Puede hacer tiempo aplicando FFT en forma de árbol. ¿Puedes hacer ? $O(n \log^2 n)$ $O(n \log n)$

ds.algorithms reference-request open-problem polynomials Mihai
fuente

Buena pregunta, parece que he visto algo similar en el blog de alguien, pero no puedo recordar dónde estaba.

Grigory Yaroslavtsev

Observación menor: sabemos (trabajando sobre Q, por ejemplo) las n raíces , por lo que el problema es equivalente a: Dado , calcule el polinomio . (Supongo.)

α_{i} = - b_{i} / a_{i}

$\alpha_i = -b_i/a_i$

α_{1}, \dots, α_{n}

$\alpha_1, \dots , \alpha_n$

(x - α_{1}) \dots (x - α_{n})

$(x-\alpha_1)\dots(x-\alpha_n)$

ShreevatsaR

¿Puedes dar una referencia al resultado ?

O (n \log^{2} n)

$O(n\log^2 n)$

Mohammad Al-Turkistany

Como @Suresh mencionó, es un enfoque simple de divide y vencerás. Se puede generalizar para que n polys pueda tener diferentes grados , en cuyo caso se puede dividir en forma de árbol Huffman. Ver Strassen: La complejidad computacional de las fracciones continuas.

d_{i}

$d_i$

Zeyu

¿Podemos calcular la convolución de vectores de dimensión constante 2 en el tiempo ?

n

$n$

O (n \log n)

$O(n \log n)$

Kaveh

Respuestas:

Advertencia: esta aún no es una respuesta completa. Si los argumentos de plausibilidad te incomodan, deja de leer.

Consideraré una variante donde queremos multiplicar (x - a_1) ... (x - a_n) sobre los números complejos.

El problema es dual para evaluar un polinomio en n puntos. Sabemos que esto se puede hacer de manera inteligente en O (n log n) cuando los puntos son la enésima raíz de la unidad. Esto aprovecha de manera esencial las simetrías de los polígonos regulares que subyacen a la Transformada rápida de Fourier. Esa transformación viene en dos formas, convencionalmente llamadas decimación en el tiempo y decimación en la frecuencia. En la raíz dos se basan en un par dual de simetrías de polígonos regulares de lados pares: la simetría entrelazada (un hexágono regular consiste en dos triángulos equiláteros entrelazados) y la simetría de despliegue del ventilador (corta un hexágono regular por la mitad y despliega las piezas como ventiladores en triángulos equiláteros).

Desde esta perspectiva, parece muy poco plausible que exista un algoritmo O (n log n) para un conjunto arbitrario de n puntos sin simetrías especiales. Implicaría que no hay nada algorítmicamente excepcional sobre los polígonos regulares en comparación con conjuntos aleatorios de puntos en el plano complejo.

Por Vognsen
fuente

Por otro lado, ¡un límite inferior para un problema tan natural parece igualmente inverosímil!

Ω (n \log^{2} n)

$\Omega(n\log^2 n)$

Jeffε

¡Cierto! Desearía tener una respuesta más definitiva. Es muy interesante.

Por Vognsen

¡Recompensa otorgada!

Jeffε

@PerVognsen: ¿Puede dar una referencia para este punto de vista en relación con: simetrías de polígonos / simetría entrelazada? O si esto es una observación propia, ¿podría ampliarlo un poco más?

Joshua Grochow