Obliczanie sumy rzadkich wielomianów podniesionych do kwadratu w czasie O (n log n)?

Załóżmy, że mamy wielomiany stopnia co najwyżej , , tak że całkowita liczba niezerowych współczynników wynosi (tzn. Wielomiany są rzadkie). Interesuje mnie wydajny algorytm obliczania wielomianu:$p_1,...,p_m$n > m $n$$n>m$$n$

Ponieważ ten wielomian ma stopień co najwyżej $2n$ , zarówno wielkość wejściowa, jak i wyjściowa wynosi $O(n)$ . W przypadku $m=1$ możemy obliczyć wynik za pomocą FFT w czasie $O(n \log n)$ . Czy można to zrobić dla dowolnego $m<n$ ? Jeśli robi to jakąkolwiek różnicę, interesuje mnie szczególny przypadek, w którym współczynniki wynoszą 0 i 1, a obliczenia powinny być wykonywane na liczbach całkowitych.

Aktualizacja. Uświadomiłem sobie, że szybkie rozwiązanie powyższego oznaczałoby postęp w szybkim mnożeniu macierzy. W szczególności, jeśli $p_k(x)=\sum_{i=1}^n a_{ik} x^i + \sum_{j=1}^n b_{kj} x^{nj}$ to możemy odczytać $a_{ik} b_{kj}$ jako współczynnik $x^{i+nj}$ w $p_k(x)^2$ . Zatem obliczenie $p_k(x)^2$ odpowiada obliczeniu iloczynu zewnętrznego dwóch wektorów, a obliczenie sumy $\sum_k p_k(x)^2$ odpowiada obliczeniu iloczynu macierzowego. Jeśli istnieje rozwiązanie wykorzystujące czas $f(n,m)$ do obliczenia $\sum_k p_k(x)^2$ wówczas możemy pomnożyć dwie $n$ -przez $n$ macierzy w czasie $f(n^2,n)$, co oznacza, że $f(n,m)=O(n\log n)$ dla $m\leq n$ wymagałoby poważnego przełomu. Ale $f(n,m)=n^{\omega/2}$ , gdzie $\omega$ jest bieżącym wykładnikiem mnożenia macierzy, może być możliwe. Pomysły, ktoś?

Wyrównywanie wielomianu z niezerowymi współczynnikami zajmuje czas przy użyciu zwykłego zwielokrotnienia semestralnego, więc powinno być to lepsze niż FFT dla tych wielomianów, w których . Jeśli , to liczba wielomianów o większej niż wynosi , a to zajmie czas do kwadratu i łączenia (podobnie jak pozostałe wielomiany). Jest to poprawa w stosunku do oczywistego ograniczenia gdy to . O ( x 2 i ) x i < $x_i$$O(x_i^2)$ ∑ixi=nxi$x_i < \sqrt{n \log n}$$\sum_i x_i = n$$x_i$ O($\sqrt{n \log n}$O(n 3 / 2 (logn) 1 / 2 )O(mnlogn)mΘ($O(\sqrt{n / \log n})$$O(n^{3/2}({\log n})^{1/2})$$O(m n \log n)$$m$$\Theta(\sqrt{n / \log n})$

Nie pełna odpowiedź, ale może pomocna.

Uwaga: Działa dobrze tylko wtedy, gdy podpory są małe.$p_i^2$

W przypadku wielomianu , niech będzie jego wsparciem, abyć wielkością wsparcia. Większość będzie rzadka, tj. Będzie miała niewielkie wsparcie.S q = { i ∣ a i ≠ 0 } s q = | S q | p $q = a_0 + a_1x + \dots +a_nx^n$$S_q = \{i \mid a_i \not= 0\}$$s_q = |S_q|$$p_i$

Są algorytmy do namnażania się rzadki wielomiany i quasi liniowe w czasie rozmiaru nośnika produktu , patrz np http://arxiv.org/abs/0901.4323b a $a$$b$$a b$

Obsługa jest (zawarta w) , gdzie suma dwóch zbiorów i jest zdefiniowana jako . Jeśli podpory wszystkich produktów są małe, powiedzmy, liniowe w sumie , wówczas można po prostu obliczyć produkty i zsumować wszystkie jednomianowe.S a + S b S T S + T : = { s + t ∣ s ∈ S , t ∈ T } $ab$$S_a + S_b$$S$$T$$S + T := \{s + t \mid s \in S, t \in T\}$$n$

Jednak bardzo łatwo jest znaleźć wielomian i tak że rozmiar podparcia jest kwadratowy w rozmiarach podparcia i . W tej konkretnej aplikacji zajmujemy kwadrat wielomianów. Więc pytanie brzmi, jak dużo większe w porównaniu do . Zwykle stosowaną miarą jest liczba podwajająca. Istnieją zestawy z nieograniczoną liczbą podwajania. Ale jeśli możesz wykluczyć zestawy z dużą liczbą podwajającą jako wsparcie dla , możesz uzyskać szybki algorytm dla swojego problemu. $a$$b$$ab$$a$$b$$S + S$$S$$|S + S|/|S|$$p_i$

Chciałem tylko zwrócić uwagę na algorytm naturalnego przybliżenia. Nie wykorzystuje to jednak rzadkości.

Możesz użyć losowej sekwencji $(\sigma_i)_{i\in[n]}$ Biorąc $X=\sum_i \sigma_i p_i(x)$ możemy obliczyć $X^2$ w $n\log n$ czasie za pomocą FFT. Następnie $EX^2 = \sum_i p_i(x)^2 = S$ i $\sqrt{VX^2} = O(S)$. Możesz więc uzyskaćprzybliżenie$1+\varepsilon$w czasie$O(\varepsilon^{-2} n \log n )$.