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 n
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 < 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 (Σ k p k ( X ) 2 n n f ( n 2 , 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 ω
fonte
Respostas:
A quadratura de um polinômio comxEu coeficientes diferentes de zero leva tempo O(x2i) usando multiplicação ordinária termo a termo; portanto, isso deve ser preferido à FFT para os polinômios em que xi<nlogn−−−−−√ . Se∑ixi=n , em seguida, o número de polinómios comxi maior 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 ( m n logn ) m .Θ ( n / logn------√)
fonte
Não é uma resposta completa, mas talvez seja útil.
Advertência: Só funciona bem se os suportes do forem pequenos.p2Eu
Para um polinómio , deixar S q = { i | um i ≠ 0 } 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 0+ a1x + ⋯ + anxn Sq= { I | umEu≠ 0 } sq= | Sq| pEu
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.4323a b ab
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.ab Sa+Sb S T S+T:={s+t∣s∈S,t∈T} 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 ia b ab a b S+S S |S+S|/|S| pi , você poderá obter um algoritmo rápido para o seu problema.
fonte
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) .
fonte