Multiplicando n polinômios de grau 1

O problema é calcular o polinómio . Assuma que todos os coeficientes se encaixam em uma palavra de máquina, ou seja, podem ser manipulados em unidade de tempo. $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$

Você pode fazer o tempo aplicando a FFT em uma forma de árvore. Você pode fazer ? $O(n \log^2 n)$ $O(n \log n)$

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

Boa pergunta, parece que eu já vi algo semelhante no blog de alguém, mas não me lembro onde estava.

Grigory Yaroslavtsev

Observação secundária: sabemos (trabalhando sobre Q, digamos) as n raízes

, então o problema é equivalente a: Dado

, calcule o polinômio

. (Eu acho.)

α_{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

Você pode dar uma referência ao resultado

O (n \log^{2} n)

$O(n\log^2 n)$

Mohammad Al-Turkistany

Como o @Suresh mencionou, é uma abordagem simples de dividir e conquistar. Ele pode ser generalizado de modo que n polígonos podem ter diferentes graus

, caso em que você pode dividir em uma forma de árvore Huffman. Veja Strassen: A complexidade computacional das frações continuadas.

d_{i}

$d_i$

Zeyu 10/09/10

Podemos calcular a convolução de

vetores de dimensão constante 2 no tempo

n

$n$

O (n \log n)

$O(n \log n)$

Kaveh

Respostas:

Aviso: Esta ainda não é uma resposta completa. Se os argumentos de plausibilidade o deixarem desconfortável, pare de ler.

Vou considerar uma variante em que queremos multiplicar (x - a_1) ... (x - a_n) pelos números complexos.

O problema é duplo na avaliação de um polinômio em n pontos. Sabemos que isso pode ser feito de maneira inteligente no tempo O (n log n), quando os pontos são a enésima raiz da unidade. Isso tira vantagem essencial das simetrias dos polígonos regulares subjacentes à Transformação Rápida de Fourier. Essa transformação ocorre em duas formas, convencionalmente denominadas decimação no tempo e decimação na frequência. Na raiz dois, eles se apóiam em um par de simetrias de polígonos regulares de lados pares: a simetria entrelaçada (um hexágono regular consiste em dois triângulos equilaterais entrelaçados) e a simetria de desdobramento do ventilador (corta um hexágono regular ao meio e desdobra as peças como ventiladores em triângulos equilaterais).

Nesta perspectiva, parece altamente implausível que um algoritmo O (n log n) exista para um conjunto arbitrário de n pontos sem simetrias especiais. Isso implicaria que não há nada de excepcional em termos de algoritmo nos polígonos regulares em comparação com conjuntos aleatórios de pontos no plano complexo.

Per Vognsen
fonte

Por outro lado, uma

limite inferior para um problema tal natural parece igualmente plausível!

Ω (n \log^{2} n)

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

Jeffε

Verdade! Eu gostaria de ter uma resposta mais definitiva. É muito interessante.

Por Vognsen

Recompensa concedida!

Jeffε 28/09

@PerVognsen: Você pode fornecer uma referência para este ponto de vista sobre: simetrias de polígonos / simetria de intertravamento? Ou, se essa é uma observação sua, você poderia expandir um pouco mais?

21712 Joshua Grochow