Soma computacional de polinômios esparsos ao quadrado no tempo O (n log n)?

18

Suponha que tenhamos polinômios de grau no máximo , , de modo que o número total de coeficientes diferentes de zero seja (isto é, os polinômios são esparsos). Estou interessado em um algoritmo eficiente para calcular o polinômio: n n > m np1,...,pmnn>mn

ipi(x)2

Como esse polinômio tem grau no máximo , o tamanho da entrada e da saída é . No caso , podemos calcular o resultado usando FFT no tempo . Isso pode ser feito para qualquer ? Se isso faz alguma diferença, estou interessado no caso especial em que os coeficientes são 0 e 1, e o cálculo deve ser feito sobre os números inteiros.O ( n ) m = 1 O ( n log n ) m < n2nO(n)m=1O(nlogn)m<n

Atualizar. Percebi que uma solução rápida para o exposto implicaria avanços na rápida multiplicação de matrizes. Em particular, se então podemos ler como o coeficiente de em . Assim, calcular corresponde ao cálculo de um produto externo de dois vetores e calcular a soma corresponde ao cálculo de um produto matricial. Se houver uma solução usando o tempo a computação , em seguida, que pode multiplicar dois -by- matrizes em tempo um i k b k j x i + n j P k ( x ) 2 P k ( x ) 2 k p k ( x ) 2 f (pk(x)=i=1naikxi+j=1nbkjxnjaikbkjxi+njpk(x)2pk(x)2kpk(x)2Σ k p k ( X ) 2 n n f ( n 2 , n )f(n,m)kpk(x)2nnf(n2,n), o que significa que para exigiria uma grande descoberta. Mas , em que é o expoente atual da multiplicação de matrizes, pode ser possível. Idéias, alguém?m n f ( n , m ) = n ω / 2 ωf(n,m)=O(nlogn)mnf(n,m)=nω/2ω

Rasmus Pagh
fonte
1
Oi Rasmus. Acho que você pretendia que isso acontecesse no site principal. Este é o meta site, para perguntas sobre o site.
Suresh Venkat

Respostas:

3

A quadratura de um polinômio com xi coeficientes diferentes de zero leva tempo O(xi2) usando multiplicação ordinária termo a termo; portanto, isso deve ser preferido à FFT para os polinômios em que xi<nlogn . Seixi=n, em seguida, o número de polinómios comximaior do que éO(nlogn, e estes irão tomar tempoO(n 3 / 2 (logn) 1 / 2 )para quadrado e combinar (assim como as restantes polinómios). Isso é uma melhoria em relação ao óbvioO(mnlogn)vinculado quandoméΘ(O(n/logn)O(n3/2(logn)1/2)O(mnlogn)m.Θ(n/logn)

mjqxxxx
fonte
1
O que me interessa é um método que calcule a soma sem calcular cada termo. Fazer FFT ou multiplicação termo a termo para cada produto será muito lento para o aplicativo que tenho em mente.
Rasmus Pagh
2

Não é uma resposta completa, mas talvez seja útil.

Advertência: Só funciona bem se os suportes do forem pequenos.pi2

Para um polinómio , deixar S q = { i | um i0 } ser o seu apoio e s q = | S q | seja o tamanho do suporte. A maior parte da p i vai ser escassa, ou seja, terá um pequeno apoio.q=a0+a1x++anxnSq={iai0}sq=|Sq|pi

Existem algoritmos para multiplicar esparso polinómios e b em tempo quase linear no tamanho do suporte do produto uma b , ver por exemplo http://arxiv.org/abs/0901.4323abab

O suporte de é (contido em) S a + S b , onde a soma de dois conjuntos S e T é definida como S + T : = { s + t s S , t T } . Se os suportes de todos os produtos são pequenos, digamos, lineares em n no total, é possível apenas computar os produtos e somar todos os monômios.abSa+SbSTS+T:={s+tsS,tT}n

No entanto, é muito fácil encontrar polinômios e b tal que o tamanho do apoio de um b é quadrática nos tamanhos do apoio de um e b . Nesta aplicação em particular, estamos quadratura de polinômios. Portanto, a questão é quanto maior S + S em comparação com S . A medida usual para isso é o número duplicado | S + S | / | S | . Existem conjuntos com número de duplicação ilimitado. Mas se você puder excluir conjuntos com um grande número de duplicação como suporte do p iabababS+SS|S+S|/|S|pi, você poderá obter um algoritmo rápido para o seu problema.

5501
fonte
1
Embora eu não esteja familiarizado com combinatória aditiva, acho que as progressões aritméticas generalizadas e o teorema de Freiman-Ruzsa tratam de conjuntos com pequenas duplicações.
Tsuyoshi Ito
@ Tsuyoshi: Você está certo, eu vou editar minha resposta. No entanto, existem GAPs com grande constante de duplicação.
5501
Pessoalmente, não acho que essa abordagem seja promissora. Uma implicação (bastante imprecisa) do teorema de Freiman-Ruzsa é que | S + S | / | S | é pequena apenas em casos especiais e, portanto, a parte “Se você pode excluir conjuntos com maior número de duplicação como suporte do p_i” é muito grande se . No entanto, como eu disse, não estou familiarizado com combinações aditivas, e você deve aceitar minhas palavras com um grão de sal.
Tsuyoshi Ito
Obviamente, isso só funciona se o aplicativo em mente (que eu não sei) fornecer bons suportes.
5501
Seria mais fácil entender se você tornar essa suposição mais explícita em sua resposta. A maneira atual de escrever a suposição na resposta sugere que você considere que a suposição de um pequeno número de duplicação não é grande coisa.
Tsuyoshi Ito
2

Só queria observar o algoritmo de aproximação natural. Isso não tira proveito da escassez.

Você pode usar uma sequência aleatória (σi)i[n] Tomando X=iσipi(x) , podemos calcular X2 em nlogn tempo usando FFT. Em seguida, EX2=ipi(x)2=S e VX2=O(S). Portanto, você pode obter umaaproximação de1+εno tempoO(ε2nlogn).

Thomas Ahle
fonte
Boa abordagem! Mas você não precisa de mais repetições para acertar todos os coeficientes com alta probabilidade?
Rasmus Pagh 30/06
log(n/δ)1δ