Diseño de algoritmos para enumerar pares de elementos no conmutables hasta la conjugación

Question

Estoy tratando de escribir algunas de Magma código que, dado un grupo de $G$, devuelve una lista de pares de $(x,y)$ $x,y\in G$ tal que $[x,y]\neq 1$ y tales que cada par $(z,w)$ en el grupo con $[z,w]\neq 1$ es conjugado (sin tomar en cuenta el orden) a algunos de los $(x,y)$ salida por el algoritmo. Me di cuenta cuando empecé que no tengo idea de que el coste computacional de los diversos pasos en el proceso. Me encantaría aprender mucho acerca de esto, pero para mantenerse enfocado, voy a pedir un restringido pregunta:

Cuál de los siguientes tres algoritmo de diseños de manera más eficiente de resolver el problema anterior? Y ¿cómo será la respuesta a este ser afectados por el orden del grupo? Por el número de clases conjugacy?

Algoritmo de 1a

1. Calcular la acción por la conjugación de la $G$ en el conjunto de $Sym^2 G$ de pares no ordenados de elementos de $G$.
2. Restringir la atención a las parejas que no conmutan.
3. Partición de $Sym^2 G$ en órbitas y seleccione un representante de cada órbita. Volver a estas selecciones.

Algoritmo 1b

Mismo como el algoritmo 1, excepto que permiten la redundancia mediante el trabajo con los pares ordenados $G\times G$ en lugar de $Sym^2 G$.

Algoritmo 2

1. Descomponer $G$ en las clases conjugacy.
2. Ignorando el singleton clases, seleccione un representante de $x$ de cada clase.
3. Para cada representante de $x$, calcular el centralizador $H=Z_G(x)$.
4. Calcular la acción de la $H$ por conjugación en el complemento $G\setminus H$.
5. De cada órbita de esta acción, seleccione una $y$, y la salida de $(x,y)$.

Pensamientos

Matemática estética punto de vista, por ejemplo si yo estuviera escribiendo una prueba, el algoritmo de 1a sería el camino a seguir, claramente. Otros algoritmos se producen redundante listas que contengan $(x,y)$ $(y',x')$ como salidas, donde $x,x'$ $y,y'$ son simultáneamente conjugada (a menos que el grupo tiene una propiedad muy especial). Más fundamentalmente, el conjunto de conjugacy órbitas de pares no ordenados es en realidad lo que estoy tratando de conseguir un asimiento de, por lo que el algoritmo de 1a apunta directamente por él, mientras que los otros dos desde el lado.

Pero OTOH, si yo fuera a tratar de generar esta lista a mano, yo sería absolutamente escoger el algoritmo 2. Otros algoritmos de fuerza que me sostenga el conjunto de pares (ordenadas o no) todos a la vez, que es cuadrática en el orden del grupo, mientras que el algoritmo 2 nunca me obliga a contemplar un conjunto más grande que el propio grupo en cualquier momento.

¿Cómo sería un equipo de tarifa con estas preguntas? Es la computación órbitas de una acción en un gran conjunto mucho más difícil que en un pequeño conjunto? Cómo acerca de la computación en todos los centralizadores? La necesidad en el algoritmo 2 para la partición de $G$ en las órbitas de los diferentes grupos de causar más dificultades? ¿Cuáles son los temas relevantes?

Gracias de antemano.

Answer 1

Si yo realmente quería hacer esto me gustaría tratar de programación de una variedad de diferentes algoritmos y probar exhaustivamente todos ellos en una serie de ejemplos. También proporciona un buen cordura prueba de su corrección mediante la comparación de los resultados obtenidos por los diferentes métodos intentado.

Pero, de la manera que usted ha descrito el Algoritmo 1, parece como si usted tendría que empezar por formar el conjunto de todos los pares no ordenados de elementos de $G$, lo que sería imposible si $G$ era grande.

Definitivamente, me gustaría prefieren el enfoque general del Algoritmo 2. El cómputo de la conjugacy clases de $G$ y centralizadores se hace todo hecho en el mismo tiempo por el $\mathtt{ConjugacyClasses}$ función, y es probable que sea de costo insignificante en comparación con el resto del proceso.

Yo podría tratar de la numeración de la no-singleton clases de $G$ $X_1=x_1^G,X_2=x_2^G,\ldots,X_k=x_k^G$, con el correspondiente centralizadores $C_i = C_G(x_i)$. Que en parte puede evitar llegar cada desordenada par dos veces por sólo cómputo de las órbitas de $C_i$$X_j$$j \ge i$. Usted todavía obtener algunos de los representantes de la $(x,y)$ $x,y \in C_i$ dos veces, así que usted tendrá que filtrar las que al final del proceso.

Y no olvide que usted todavía tiene que poner en los representantes de la $(x,y)$ $x$ o $y$ en un singletom clase, pero que es relativamente fácil.

Answer 2

Hay un número de cosas que usted puede optimizar en tiempo de ejecución, su propio tiempo de trabajo de ejecución de código, o el uso de la memoria. Más probable es que el uso de la memoria se convierte en el primer obstáculo al mirar más grandes ejemplos (como usted no puede esperar a la esperanza para más de memoria). Así, en el final de un algoritmo como el #2 se obtiene más. (Si quieres un truco rápido para pequeños ejemplos de uso #1.)

Lo que yo haría es, sin embargo, el siguiente, que utiliza el grupo de conjugación para reducir el problema:

1. Determinar las clases Conjugacy
2. Por cada representante de la clase $x$, vamos a $C=C_G(x)$. Ejecutar (segunda vuelta) a través de todas las clases conjugacy, vamos a $y$ la representante de la clase, $D=C_G(y)$.
3. Calcular el doble de cosets $C\setminus G/D$.
4. Para cada doble coset representante de $r$ deje $z=y^r$. (Esta es la $C_i$ órbitas en la clase de $X_j$ Derek Holt respuesta ya está mencionando.)
5. La prueba de que el par $x,z$ de su propiedad.

Estos pares de $x,z$ ahora se enumeran sólo hasta el $G$-conjugacy. En la mayoría de los casos, esto significa que usted nunca tendrá que almacenar, o de ejecutar a través de algo tan grande como toda la clase, pero el número de dobles cosets es significativamente menor.

Si usted necesita ayuda con la implementación de este con GAP-que no puedo comentar sobre el Magma -- déjame saber.