Mnożenie n wielomianów stopnia 1

35

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.(a1x+b1)××(anx+bn)

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

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
3
Drobne obserwacje: znamy (pracując nad Q, powiedzmy) n pierwiastków , więc problem jest równoważny z: Biorąc pod uwagę α 1 , , α n , obliczyć wielomian ( x - α 1 ) ( X - α n ) . (Chyba.)αi=bi/aiα1,,αn(xα1)(xαn)
ShreevatsaR
1
Czy możesz podać odniesienie do wyniku ? O(nlog2n)
Mohammad Al-Turkistany
2
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. di
Zeyu,
1
Czy możemy obliczyć splot wektorów o stałym wymiarze 2 w czasie O ( n log n ) ? nO(nlogn)
Kaveh

Odpowiedzi:

7

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
3
Z drugiej strony dolna granica dla takiego naturalnego problemu wydaje się równie nieprawdopodobna! Ω(nlog2n)
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