Mnożenie n wielomianów stopnia 1

Problem polega na obliczeniu wielomianu . Załóżmy, że wszystkie współczynniki mieszczą się w słowie maszynowym, tzn. Można nimi manipulować w czasie jednostkowym. $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$

Możesz zrobić czas , stosując FFT w sposób drzewny. Czy możesz zrobić ? $O(n \log^2 n)$ $O(n \log n)$

— Mihai
źródło

Ładne pytanie, wygląda na to, że widziałem coś podobnego na czyimś blogu, ale nie pamiętam, gdzie to było.

— Grigorij Jarosławcew

Drobne obserwacje: znamy (pracując nad Q, powiedzmy) n pierwiastków

, więc problem jest równoważny z: Biorąc pod uwagę

, obliczyć wielomian

. (Chyba.)

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

Czy możesz podać odniesienie do wyniku

O (n \log^{2} n)

$O(n\log^2 n)$

— Mohammad Al-Turkistany

Jak wspomniano w @Suresh, jest to proste podejście typu „dziel i rządź”. Można go uogólnić tak, że n polis może mieć różne stopnie

, w takim przypadku można podzielić w sposób drzewa Huffmana. Zobacz Strassen: Złożoność obliczeniowa ciągłych ułamków.

d_{i}

$d_i$

— Zeyu,

Czy możemy obliczyć splot

wektorów o stałym wymiarze 2 w czasie

n

$n$

O (n \log n)

$O(n \log n)$

— Kaveh

Ostrzeżenie: To nie jest jeszcze pełna odpowiedź. Jeśli argumenty wiarygodności sprawiają, że czujesz się niekomfortowo, przestań czytać.

Rozważę wariant, w którym chcemy pomnożyć (x - a_1) ... (x - a_n) przez liczby zespolone.

Problem jest podwójny przy ocenie wielomianu w n punktach. Wiemy, że można tego dokonać sprytnie w czasie O (n log n), kiedy zdarza się, że n-te korzenie są jednością. Wykorzystuje to istotną symetrię regularnych wielokątów, które leżą u podstaw szybkiej transformacji Fouriera. Ta transformacja występuje w dwóch postaciach, zwanych tradycyjnie decymacją w czasie i decymacją w częstotliwości. W rzucie drugim opierają się na podwójnej parze symetrii równomiernych regularnych wielokątów: blokującej się symetrii (regularny sześciokąt składa się z dwóch blokujących się równobocznych trójkątów) i symetrii rozkładania się wentylatora (przeciąć regularny sześciokąt na pół i rozłożyć elementy jak wentylatory w trójkąty równoboczne).

Z tej perspektywy wydaje się wysoce nieprawdopodobne, aby istniał algorytm O (n log n) dla dowolnego zestawu n punktów bez specjalnych symetrii. Oznaczałoby to, że w zwykłych wielokątach nie ma nic wyjątkowego algorytmicznie w porównaniu z losowymi zestawami punktów na płaszczyźnie złożonej.

— Per Vognsen
źródło

Z drugiej strony dolna granica

dla takiego naturalnego problemu wydaje się równie nieprawdopodobna!

Ω (n \log^{2} n)

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

— Jeffε

Prawdziwe! Chciałbym mieć bardziej jednoznaczną odpowiedź. To bardzo interesujące.

— Per Vognsen

Nagroda przyznana!

— Jeffε

@PerVognsen: Czy możesz podać odniesienie do tego punktu widzenia dotyczącego: symetrii wielokątów / symetrii blokującej? A jeśli jest to Twoja własna obserwacja, czy mógłbyś rozwinąć ją nieco bardziej?

— Joshua Grochow