Supongamos que tenemos polinomios de grado como máximo , , de modo que el número total de coeficientes distintos de cero es (es decir, los polinomios son escasos). Estoy interesado en un algoritmo eficiente para calcular el polinomio:
Como este polinomio tiene un grado máximo de , tanto el tamaño de entrada como el de salida es . En el caso , podemos calcular el resultado usando FFT en el tiempo . ¿Se puede hacer esto para cualquier ? 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 entonces puede leer como el coeficiente de en . Por lo tanto, calcular corresponde a calcular un producto externo de dos vectores, y calcular la suma corresponde a calcular un producto matricial. Si hay una solución usando el tiempo para calcular entonces podemos multiplicar dosmatrices -by- 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?
fuente
Respuestas:
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 < √xi O(x2i) . Si∑ixi=n, entonces el número de polinomios conximayor que √xi<nlogn−−−−−√ ∑ixi=n xi 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−−−−−−√)
fuente
No es una respuesta completa pero puede ser útil.
Advertencia: solo funciona bien si los soportes del son pequeños.p2i
Para un polinomio , que S q = { i ∣ a i ≠ 0 } 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+⋯+anxn Sq={i∣ai≠0} 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.4323a b ab
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.ab Sa+Sb S T S+T:={s+t∣s∈S,t∈T} 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 ia b ab a b S+S S |S+S|/|S| pi , entonces puede obtener un algoritmo rápido para su problema.
fuente
Solo quería notar el algoritmo de aproximación natural. Sin embargo, esto no aprovecha la escasez.
fuente