¿Calcular la suma de polinomios dispersos al cuadrado en el tiempo O (n log n)?

18

Supongamos que tenemos polinomios p1,...,pm de grado como máximo n , n>m , de modo que el número total de coeficientes distintos de cero es n (es decir, los polinomios son escasos). Estoy interesado en un algoritmo eficiente para calcular el polinomio:

ipi(x)2

Como este polinomio tiene un grado máximo de 2n , tanto el tamaño de entrada como el de salida es O(n) . En el caso m=1 , podemos calcular el resultado usando FFT en el tiempo O(nlogn) . ¿Se puede hacer esto para cualquier m<n ? Si hace alguna diferencia, estoy interesado en el caso especial donde los coeficientes son 0 y 1, y el cálculo debe hacerse sobre los enteros.

Actualizar. Me di cuenta de que una solución rápida para lo anterior implicaría avances en la multiplicación rápida de matrices. En particular, si pk(x)=i=1naikxi+j=1nbkjxnj entonces puede leer aikbkj como el coeficiente de xi+nj en pk(x)2 . Por lo tanto, calcularpk(x)2 corresponde a calcular un producto externo de dos vectores, y calcular la sumakpk(x)2 corresponde a calcular un producto matricial. Si hay una solución usando el tiempof(n,m) para calcularkpk(x)2 entonces podemos multiplicar dosmatricesn -by-n en el tiempo , lo que significa que f ( n , m ) = O ( n log n ) para m n requeriría un avance importante. Pero f ( n , m ) = n ω / 2 , donde ω es el exponente actual de la multiplicación de matrices, podría ser posible. Ideas, alguien?f(n2,n)f(n,m)=O(nlogn)mnf(n,m)=nω/2ω

Rasmus Pagh
fuente
1
Hola rasmus Creo que pretendías que esto fuera al sitio principal. Este es el meta sitio, para preguntas sobre el sitio.
Suresh Venkat

Respuestas:

3

La cuadratura de un polinomio con coeficientes distintos de cero lleva tiempo O ( x 2 i ) usando la multiplicación ordinaria término por término, por lo que debería preferirse a la FFT para aquellos polinomios donde x i < xiO(xi2) . Siixi=n, entonces el número de polinomios conximayor quexi<nlognixi=nxi esO(nlogn, y estos tomarán tiempoO(n 3 / 2 (logn) 1 / 2 )de la plaza y combinar (al igual que los polinomios restantes). Esta es una mejora sobre el obvioO(mnlogn)vinculado cuandomesΘ(O(n/logn)O(n3/2(logn)1/2)O(mnlogn)m.Θ(n/logn)

mjqxxxx
fuente
1
Lo que me interesa es un método que calcule la suma sin calcular cada término. Hacer FFT o multiplicación término por término para cada producto será demasiado lento para la aplicación que tengo en mente.
Rasmus Pagh
2

No es una respuesta completa pero puede ser útil.

Advertencia: solo funciona bien si los soportes del son pequeños.pi2

Para un polinomio , que S q = { i a i0 } sea ​​su soporte y s q = | S q | Ser del tamaño del soporte. La mayoría de los p i serán escasos, es decir, tendrán un pequeño soporte.q=a0+a1x++anxnSq={iai0}sq=|Sq|pi

Hay algoritmos para multiplicar polinomios dispersos y b en tiempo cuasi lineal en el tamaño del soporte del producto a b , consulte, por ejemplo, http://arxiv.org/abs/0901.4323abab

El soporte de está (contenido en) S a + S b , donde la suma de dos conjuntos S y T se define como S + T : = { s + t s S , t T } . Si los soportes de todos los productos son pequeños, digamos, lineales en n en total, entonces uno puede calcular los productos y sumar todos los monomios.abSa+SbSTS+T:={s+tsS,tT}n

Sin embargo, es muy fácil encontrar polinomios y b de tal manera que el tamaño del soporte de a b sea ​​cuadrático en los tamaños del soporte de a y b . En esta aplicación en particular, estamos cuadrando polinomios. Así que la pregunta es cuánto más grande S + S en comparación con S . La medida habitual para esto es el número de duplicación | S + S | / | S | . Hay conjuntos con un número de duplicación ilimitado. Pero si puede excluir conjuntos con un gran número de duplicación como soportes de la p iabababS+SS|S+S|/|S|pi, entonces puede obtener un algoritmo rápido para su problema.

5501
fuente
1
Aunque no estoy familiarizado con la combinatoria aditiva, creo que las progresiones aritméticas generalizadas y el teorema de Freiman-Ruzsa se refieren a conjuntos con una pequeña duplicación.
Tsuyoshi Ito
@ Tsuyoshi: Tienes razón, editaré mi respuesta. Sin embargo, hay BPA con una gran duplicación constante.
5501
Personalmente, no creo que este enfoque sea prometedor. Una implicación (bastante imprecisa) del teorema de Freiman-Ruzsa es que | S + S | / | S | es pequeño solo en casos especiales y, por lo tanto, la parte "Si puede excluir conjuntos con un número de duplicación mayor como soporte de p_i" es un if muy grande . Sin embargo, como dije, no estoy familiarizado con la combinatoria aditiva, y debería tomar mis palabras con un grano de sal.
Tsuyoshi Ito
Por supuesto, solo funciona si la aplicación en mente (que no sé) ofrece buenos soportes.
5501
Entonces sería más fácil de entender si haces esa suposición más explícita en tu respuesta. La forma actual de escribir el supuesto en la respuesta sugiere que considere que el supuesto de un número de duplicación pequeño no es un gran problema.
Tsuyoshi Ito
2

Solo quería notar el algoritmo de aproximación natural. Sin embargo, esto no aprovecha la escasez.

(σi)i[n]X=iσipi(x)X2nlogn time using FFT. Then EX2=ipi(x)2=S and VX2=O(S). So you can get a 1+ε approximation in time O(ε2nlogn).

Thomas Ahle
fuente
Nice approach! But don't you need more repetitions to get all coefficients right with high probability?
Rasmus Pagh
@RasmusPagh Right, you'll probably get a log(n/δ) term if you want all coefficients to be preserved with probability 1δ.
Thomas Ahle