Encontrar coeficientes en polinomio de manera eficiente

Question

Encontrar coeficientes en polinomio de manera eficiente

brecha
Matemáticas
polinomios

Dominik B.

Dada una transitiva $G$ -colocar $M$ . Estoy interesado en encontrar el número de puntos fijos de $G$ actuando $\operatorname{Pot}_a( M ) := \left\{ N\subseteq M; |N| = a \right\}$ utilizando la tabla de notas de $G$ . Dejar $U_1, \dots, U_s$ ser representantes de las clases de conjugación de subgrupos de $G$ . Para cada uno de ellos, un polinomio

{pag}_{{tu}_{i}} := \prod_{yo = 1}^{s} (\sum_{j = 0}^{{metro}_{i, yo}} (\binom{{metro}_{i, yo}}{j}) \cdot X^{λ (i, yo) \cdot j})

$p_{U_i} := \prod_{l=1}^s \left( \sum_{j=0}^{m_{i,l}} \binom{m_{i,l}}{j}\cdot x^{\lambda(i,l)\cdot j} \right)$

se define, donde $\lambda(i,l), m_{i,l}\in \mathbb N_0$ . Dejar $p := \sum_{i=1}^s p_i$ . El coeficiente de $x^p$ es el número de puntos fijos $G$ tiene en $\operatorname{Pot}_p( M )$ . El problema es calcular estos coeficientes de manera eficiente. Mi enfoque fue calcular

{pag}_{{tu}_{i}} := \prod_{yo = 1}^{s} (\sum_{j = 0}^{{metro}_{i, yo}} (\binom{{metro}_{i, yo}}{j}) \cdot X^{λ (i, yo) \cdot j} modificación X^{pag + 1}) modificación X^{pag + 1} .

$p_{U_i} := \prod_{l=1}^s \left( \sum_{j=0}^{m_{i,l}} \binom{m_{i,l}}{j}\cdot x^{\lambda(i,l)\cdot j} \operatorname{mod}x^{p+1} \right) \operatorname{ mod } x^{p+1}.$

Cada transitiva $G$ -set corresponde a una fila en la tabla de marcas de $G$ desde $M\cong G/U_k$ para algunos $U_k \leq G$ . Resulta que calcular los puntos fijos de $S_8$ en $\operatorname{Pot}_2( G/U_p )$ para $p=2 \dots 148$ lleva más de 10 horas (todavía sin terminar), lo cual no es aceptable. Para definir el polinomio utilicé las funciones internas GAP Product, Sum y mod. ¿Tiene alguna sugerencia sobre cómo puedo calcular los coeficientes más rápido?

Dominik B.

El cálculo tomó alrededor de 22 horas. El principal problema de GAP es calcular el

p_{U_{i}}

$p_{U_i}$ . Lleva mucho tiempo definir este polinomio para GAP.

Olexandr Konovalov

Para la suma interna, puede usar PolynomialByExtRepo incluso PolynomialByExtRepNC si confía en los argumentos, consulte aquí . Entonces al menos no tienes que usar Sume inner mod. Sin embargo, no estoy seguro de cuánta aceleración obtendrá, ya que espero que sea la multiplicación lo que lleva la mayor parte del tiempo, pero de todos modos esta sería una optimización que vale la pena. Esperamos saber si esto tendrá algún efecto, luego veamos más.

Dominik B.

@AlexanderKonovalov ¡Muchas gracias, esto fue realmente útil! Para los ejemplos pequeños, toma aproximadamente un 30% menos de tiempo que antes, los ejemplos grandes todavía se están ejecutando. Tuve que cambiar un poco el código, por ejemplo, reemplazar mod por QuotRemLaurpols y agregar algunos bucles if. Pero tienes razón, la mayor parte del tiempo se usa para calcular el producto. Tienes alguna otra sugerencia?

Dominik B.

@AlexanderKonovalov Bueno, ¡resulta que el efecto en grupos más grandes es mucho mejor! El cálculo que antes tomaba 22 horas ahora se completa en 59 minutos. Gracias, estoy muy agradecido. Sin embargo, estaría interesado en cualquier consejo adicional que me puedan dar.

Olexandr Konovalov

¡Excelente! Para más consejos, para este cálculo de una hora es interesante saber qué es

s

$s$ (el número de polinomios a multiplicar) y cuáles son sus grados? ¿Estos polinomios son densos o dispersos? Si son escasos, ¿cuántos monomios tienen? Finalmente, ¿está interesado en conocer solo un coeficiente para

x^{p}

$x^p$ por un fijo

p

$p$ a la vez, si eso podría ser más rápido, o si desea calcular todo el polinomio de todos modos?

Olexandr Konovalov

Tenía algunas ideas más, quizás esto podría mejorarse aún más usando la funcionalidad descrita en Aritmética para representaciones externas de polinomios o incluso vectores como coeficientes de polinomios . El objetivo principal es evitar conversiones de ida y vuelta entre polinomios como objetos GAP y los dados por sus representaciones externas.

Dominik B.

@AlexanderKonovalov Gracias nuevamente, cambiaré el código hoy usando solo las representaciones externas de polinomios.

s

$s$ es el tamaño de la tabla de marcas (

T

$T$ ) de

G

$G$ , entonces

s

$s$ es el número de clases de conjugación de subgrupos de

G

$G$ . Para cada subgrupo

U_{i}

$U_i$ ,

λ (i, l) := | G / U_{i} | / | G / U_{l} |

$\lambda(i,l) := |G/U_i|/|G/U_l|$ y

m_{i, l}

$m_{i,l}$ se obtiene multiplicando el

i

$i$ y

l

$l$ la fila de

T

$T$ entrada por entrada. Esto te da un vector que luego se multiplica por

T^{- 1}

$T^{-1}$ . Las entradas de este vector son las

m_{i, l}

$m_{i,l}$ .

Dominik B.

λ (i, l) \notin Z

$\lambda(i,l) \notin \mathbb Z$ si y solo si

m_{i, l} = 0

$m_{i,l}=0$ . Si

G = S_{n}

$G=S_n$ el polinomio es denso. Todavía no estoy seguro del grado, pero lo pensaré. Por ahora, solo estoy interesado en el coeficiente de algunos

x^{p}

$x^p$ en

\sum_{i = 1}^{s} p_{U_{i}}

$\sum_{i=1}^s p_{U_i}$ dónde

p

$p$ se sabe antes. No estoy interesado en todo el polinomio.

Olexandr Konovalov

¡Bien! Solo mantén la versión anterior como respaldo. Me pondré en contacto más tarde hoy, trataré de organizar todos los comentarios en una especie de respuesta adecuada. También existe la idea de calcular solo el coeficiente deseado, omitiendo la multiplicación completa de todos los polinomios.

Olexandr Konovalov

He hecho algunos experimentos con ProductCoeffs, tal vez eso podría ser más eficiente que usar iteradores, por favor, eche un vistazo.

Respuestas (1)

Encontrar coeficientes en polinomio de manera eficiente

El cálculo tomó alrededor de 22 horas. El principal problema de GAP es calcular el $p_{U_i}$ . Lleva mucho tiempo definir este polinomio para GAP.
Para la suma interna, puede usar PolynomialByExtRepo incluso PolynomialByExtRepNC si confía en los argumentos, consulte aquí . Entonces al menos no tienes que usar Sume inner mod. Sin embargo, no estoy seguro de cuánta aceleración obtendrá, ya que espero que sea la multiplicación lo que lleva la mayor parte del tiempo, pero de todos modos esta sería una optimización que vale la pena. Esperamos saber si esto tendrá algún efecto, luego veamos más.
@AlexanderKonovalov ¡Muchas gracias, esto fue realmente útil! Para los ejemplos pequeños, toma aproximadamente un 30% menos de tiempo que antes, los ejemplos grandes todavía se están ejecutando. Tuve que cambiar un poco el código, por ejemplo, reemplazar mod por QuotRemLaurpols y agregar algunos bucles if. Pero tienes razón, la mayor parte del tiempo se usa para calcular el producto. Tienes alguna otra sugerencia?
@AlexanderKonovalov Bueno, ¡resulta que el efecto en grupos más grandes es mucho mejor! El cálculo que antes tomaba 22 horas ahora se completa en 59 minutos. Gracias, estoy muy agradecido. Sin embargo, estaría interesado en cualquier consejo adicional que me puedan dar.
¡Excelente! Para más consejos, para este cálculo de una hora es interesante saber qué es $s$ (el número de polinomios a multiplicar) y cuáles son sus grados? ¿Estos polinomios son densos o dispersos? Si son escasos, ¿cuántos monomios tienen? Finalmente, ¿está interesado en conocer solo un coeficiente para $x^p$ por un fijo $p$ a la vez, si eso podría ser más rápido, o si desea calcular todo el polinomio de todos modos?
Tenía algunas ideas más, quizás esto podría mejorarse aún más usando la funcionalidad descrita en Aritmética para representaciones externas de polinomios o incluso vectores como coeficientes de polinomios . El objetivo principal es evitar conversiones de ida y vuelta entre polinomios como objetos GAP y los dados por sus representaciones externas.
@AlexanderKonovalov Gracias nuevamente, cambiaré el código hoy usando solo las representaciones externas de polinomios. $s$ es el tamaño de la tabla de marcas ( $T$ ) de $G$ , entonces $s$ es el número de clases de conjugación de subgrupos de $G$ . Para cada subgrupo $U_i$ , $\lambda(i,l) := |G/U_i|/|G/U_l|$ y $m_{i,l}$ se obtiene multiplicando el $i$ y $l$ la fila de $T$ entrada por entrada. Esto te da un vector que luego se multiplica por $T^{-1}$ . Las entradas de este vector son las $m_{i,l}$ .
$\lambda(i,l) \notin \mathbb Z$ si y solo si $m_{i,l}=0$ . Si $G=S_n$ el polinomio es denso. Todavía no estoy seguro del grado, pero lo pensaré. Por ahora, solo estoy interesado en el coeficiente de algunos $x^p$ en $\sum_{i=1}^s p_{U_i}$ dónde $p$ se sabe antes. No estoy interesado en todo el polinomio.
¡Bien! Solo mantén la versión anterior como respaldo. Me pondré en contacto más tarde hoy, trataré de organizar todos los comentarios en una especie de respuesta adecuada. También existe la idea de calcular solo el coeficiente deseado, omitiendo la multiplicación completa de todos los polinomios.
He hecho algunos experimentos con ProductCoeffs, tal vez eso podría ser más eficiente que usar iteradores, por favor, eche un vistazo.

Olexandr Konovalov · Answer 1

Gracias, esa es realmente una pregunta interesante!

$0$ -th enfoque

Al multiplicar polinomios con coeficientes enteros, el valor absoluto de los coeficientes puede aumentar bastante rápido. Es importante verificar que GAP esté compilado con la biblioteca GMP para una aritmética rápida de enteros. Debería ver gmpen la línea 4 de la pantalla de inicio de GAP:

 Libs used:  gmp, readline

La compatibilidad con GMP se introdujo en GAP 4.5 (2012) y ahora es una opción predeterminada, por lo que lo más probable es que así sea.

Paso 1

El primer paso es ensamblar directamente el polinomio de la lista de coeficientes en lugar de calcularlo como la suma de monomios. En el siguiente ejemplo creo una lista aleatoria lde un $1000$ enteros entre $-10$ y $10$ , y luego compare estas dos formas de crear un polinomio con coeficientes dados por esta lista:

gap> x:=Indeterminate(Rationals,"x");
gap> l:=List([1..10000],i->Random(Integers));;
gap> f:=Sum([1..10000], i-> l[i]*x^i);;time;
2268
gap> f1:=LaurentPolynomialByCoefficients(FamilyObj(1),l,1);;time;
1
gap> f=f1;
true

timedevuelve el tiempo de CPU del último comando en milisegundos, por lo que verá que LaurentPolynomialByCoefficientslo hace instantáneamente, mientras que el otro enfoque tarda más de dos segundos. Consulte más en "Creación de funciones racionales" del capítulo Polinomios y funciones racionales del manual de referencia de GAP; también hay más funciones de bajo nivel como PolynomialByExtRepy PolynomialByExtRepNC, LaurentPolynomialByExtRepy LaurentPolynomialByExtRepNC, donde NCsignifica "sin verificación" y solo debe usarse si la velocidad es requerida y se sabe que los argumentos están en forma correcta. A menos que esto esté garantizado para los parámetros, LaurentPolynomialByCoefficientsdebe usarse para estar seguro.

Obviamente, ahora ya no es necesario realizar modeste paso, ya que uno podría simplemente truncar la lista de coeficientes (o no calcular la lista completa en absoluto).

Observación: se verificó el paso 1 (consulte los comentarios del autor de la pregunta más arriba) y se redujo en un ejemplo el tiempo de ejecución general de 22 horas a 59 minutos. Los pasos a continuación son solo sugerencias, que requieren más experimentación y ajuste del código.

Paso 2(a)

Quizás esto podría mejorarse aún más usando la funcionalidad descrita en Aritmética para representaciones externas de polinomios o incluso vectores como coeficientes de polinomios . El objetivo principal es evitar conversiones de ida y vuelta entre polinomios como objetos GAP y polinomios dados por sus representaciones externas.

Agregado más adelante: en particular, considere ProductCoeffscuál le permite multiplicar polinomios solo parcialmente: ProductCoeffs( list1[, len1], list2[, len2] )asume que $p1$ (y $p2$ ) son polinomios dados por las primeras len1( len2) entradas de la lista de coeficientes list2( list2). Si len1y len2se omiten, tienen por defecto las longitudes de list1y list2. Luego devuelve la lista de coeficientes del producto de $p1$ y $p2$ .

Si no se restringen las longitudes, el rendimiento es el mismo:

gap> x:=Indeterminate(Rationals,"x");;
gap> deg:=10000;;
gap> l1:=List([1 .. deg],i->Random(Integers));;
gap> f1:=LaurentPolynomialByCoefficients(FamilyObj(1),l1,0);;
gap> l2:=List([1 .. deg],i->Random(Integers));;
gap> f2:=LaurentPolynomialByCoefficients(FamilyObj(1),l2,0);;
gap> f:=f1*f2;;time;
3819
gap> t:=ProductCoeffs(CoefficientsOfUnivariatePolynomial(f1), CoefficientsOfUnivariatePolynomial(f2));;time;
3787
gap> CoefficientsOfUnivariatePolynomial(f)=t;
true

Pero ahora supongamos que queremos calcular el coeficiente para $x^{10}$ en el producto de $p1$ y $p2$ . Entonces no tenemos que usar monomios de grado 11 y superior. Así hacemos:

gap> p:=10;
10
gap> tcut:=ProductCoeffs(CoefficientsOfUnivariatePolynomial(f1), p+1, CoefficientsOfUnivariatePolynomial(f2), p+1);;time;
0
gap> CoefficientsOfUnivariatePolynomial(f){[1..p+1]}=tcut{[1..p+1]};
true

así que estamos obteniendo el resultado instantáneamente, saltándonos el trato con todos los monomios de grados superiores. En la misma configuración, tengo $43$ ms para $p=1000$ y $977$ ms para $p=5000$ , por lo que su millaje puede variar, y cuanto menor sea $p$ Es decir, mejor debería ser la aceleración.

Paso 2(b)

Se podría intentar experimentar con la multiplicación paralelizante de polinomios (dada por representaciones internas o externas). El número de polinomios a multiplicar es el número de clases de conjugación de $G$ , p.ej $22$ para $S_8$ . El enfoque más simple sería dividir la lista de polinomios en fragmentos y luego encontrar un producto de cada fragmento en paralelo y luego multiplicar los productos resultantes (posiblemente con otra iteración paralela, según la cantidad de fragmentos y nodos). De todos modos, el grado irá subiendo, y el cuello de botella obvio sería el último paso con la multiplicación secuencial de dos o tres polinomios. Si desea intentar experimentar con esto, mire el paquete SCSCP . También podría proporcionar un código para la multiplicación paralela de polinomios de Karatsuba con el paquete SCSCP: para polinomios de gran grado, también podría acelerarlo un poco.

Paso 2(c)

Otra sugerencia especulativa proviene del hecho de que puede estar interesado solo en un solo coeficiente. Eso sería mucho más útil si los polinomios fueran dispersos, pero aun así puede valer la pena intentarlo en el caso denso. La idea sería iterar sobre el producto cartesiano de grados de monomios (usando IteratorOfCartesianProduct), verificar para cada tupla si la suma de grados de monomios es igual al grado que le interesa, y si es así, sume el producto de los respectivos coeficientes a alguna variable acumulativa. El pseudocódigo para calcular pel coeficiente -th en GAP podría verse así

degs:= < list of degrees of polynomials >
degranges := List( degs, i -> [1..i] ); # list of ranges 
# for sparse polynomial, take the list of degrees of monomials instead of a range

coeff := 0;

iter:=IteratorOfCartesianProduct(degranges);

for t in iter do
  # t is a tuple of degrees of monomials 
  if Sum(t) = p then
    coeff := coeff + Product( List( [1..Length(t)], i -> 
                              < coefficient for x^t[i] in the i-th polynomial > 
  fi;
od;

Encontrar coeficientes en polinomio de manera eficiente

Dominik B.

Dominik B.

Olexandr Konovalov

Dominik B.

Dominik B.

Olexandr Konovalov

Olexandr Konovalov

Dominik B.

Dominik B.

Olexandr Konovalov

Olexandr Konovalov

Respuestas (1)

Olexandr Konovalov

¿Cómo resolver esta ecuación algebraica de octavo grado resoluble por radicales?

¿Cómo te acercas al completar el cuadrado?

¿Cómo verificar las raíces de un polinomio de un cierto número establecido en cierto rango?

Generalizando r(n2)=r(n)2,r(n2)=r(n)2,\,r(n^2) = r(n)^2,\, para r(n):=r( n):=\,r(n) := invertir los dígitos de nnn

polinomio con coeficientes enteros

Condición para que las raíces de la cuarta sean reales y dos sean coincidentes

Encontrar el número de raíces reales de un polinomio

la suma del recíproco de los cuadrados de las raíces

¿Cuál es la forma más fácil de factorizar este término cúbico?

Demostrar que los coeficientes del polinomio son polinomios simétricos elementales