El algoritmo de Schreier-Sims es un algoritmo de la teoría de grupos computacional , que lleva el nombre de los matemáticos Otto Schreier y Charles Sims . Este algoritmo puede encontrar el orden de un grupo de permutación finito, probar la pertenencia (¿una permutación dada está contenida en un grupo?) Y muchas otras tareas en tiempo polinomial. Fue introducido por Sims en 1970, basado en el lema del subgrupo de Schreier . Posteriormente, Donald Knuth mejoró la sincronización en 1991. Más tarde, se desarrolló una versión aleatoria aún más rápida del algoritmo.
Antecedentes y oportunidad
El algoritmo es un método eficiente para calcular un grupo electrógeno base y fuerte (BSGS) de un grupo de permutación . En particular, un SGS determina el orden de un grupo y facilita la prueba de pertenencia al grupo. Dado que el SGS es fundamental para muchos algoritmos en la teoría de grupos computacional, los sistemas de álgebra computacional generalmente se basan en el algoritmo de Schreier-Sims para cálculos eficientes en grupos.
El tiempo de ejecución de Schreier – Sims varía según la implementación. Dejar ser dado por generadores . Para la versión determinista del algoritmo, los posibles tiempos de ejecución son:
- requiriendo memoria
- requiriendo memoria
El uso de vectores de Schreier puede tener una influencia significativa en el rendimiento de las implementaciones del algoritmo de Schreier-Sims.
Para las variaciones de Monte Carlo del algoritmo de Schreier-Sims, tenemos la siguiente complejidad estimada:
- requiriendo memoria
En los sistemas de álgebra informática modernos, como GAP y Magma , se suele utilizar un algoritmo de Monte Carlo optimizado .
Esquema del algoritmo básico
A continuación se muestra un pseudocódigo de estilo C ++ para la idea básica del algoritmo de Schreier-Sims. Está destinado a omitir todos los detalles más finos, como la gestión de la memoria o cualquier tipo de optimización de bajo nivel, para no ofuscar las ideas más importantes del algoritmo. No es necesario que se compile realmente.
struct Group { uint stabPoint ; // Un índice en la base del punto estabilizado por el subgrupo de este grupo. OrbitTree orbitTree ; // Un árbol para realizar un seguimiento de la órbita en nuestro grupo del punto estabilizado por nuestro subgrupo. TransversalSet transversalSet ; // Un conjunto de representantes de clases laterales del subgrupo de este grupo. GeneratorSet generatorSet ; // Un conjunto de permutaciones que generan este grupo. Grupo * subgrupo ; // Un puntero al subgrupo de este grupo, o nulo para referirse al grupo trivial. Grupo ( uint stabPoint ) { esto -> stabPoint = stabPoint ; subGroup = nullptr ; } };// El conjunto de generadores dado no necesita ser un grupo electrógeno fuerte. Solo necesita generar el grupo en la raíz de la cadena. Grupo * MakeStabChain ( const GeneratorSet & generatorSet , uint * base ) { Grupo * grupo = nuevo Grupo ( 0 ); para ( generador en generatorset ) grupo -> Extender ( generador , de base ); grupo de retorno ; }// Extiende la cadena estabilizadora enraizada en este grupo con el generador dado. void Group :: Extend ( const Permutation & generator , uint * base ) { // Esta es la principal optimización de Schreier-Sims. Elimine los generadores Schreier redundantes. if ( IsMember ( generador )) return ; // Nuestro grupo se hizo más grande, pero la cadena estabilizadora arraigada en nuestro subgrupo sigue siendo la misma. generatorSet . Agregar ( generador ); // Explora todas las nuevas órbitas que podemos alcanzar con la adición del nuevo generador. // Tenga en cuenta que si el árbol estaba vacío al principio, la identidad debe devolverse // en el conjunto para satisfacer una condición del lema de Schreier. newTerritorySet = orbitTree . Crecer ( generador , base ); // Por el teorema del estabilizador de órbita, las permutaciones en el conjunto devuelto son // representantes de las clases laterales de nuestro subgrupo. para ( permutación en newTerritorySet ) transversalSet . Agregar ( permutación ); // Ahora aplicamos el lema de Schreier para encontrar nuevos generadores para nuestro subgrupo. // Algunas iteraciones de este ciclo son redundantes, pero lo ignoramos por simplicidad. for ( cosetRepresentative en transversalSet ) { for ( generador en generatorSet ) { schreierGenerator = CalcSchreierGenerator ( cosetRepresentative , generador ); if ( schreierGenerator . IsIdentity ()) continuar ; if ( ! subGroup ) subGroup = new Group ( stabPoint + 1 ); subGrupo -> Extender ( schreierGenerator , base ); } } }
Los detalles notables que se dejan aquí incluyen el crecimiento del árbol de la órbita y el cálculo de cada nuevo generador de Schreier. En lugar del árbol de la órbita, se puede usar un vector de Schreier , pero la idea es esencialmente la misma. El árbol tiene sus raíces en el elemento de identidad, que fija el punto estabilizado por el subgrupo. Cada nodo del árbol puede representar una permutación que, cuando se combina con todas las permutaciones en el camino desde la raíz hasta él, lleva ese punto a un nuevo punto no visitado por ningún otro nodo del árbol. Por el teorema del estabilizador de órbita , estos forman una transversal del subgrupo de nuestro grupo que estabiliza el punto cuya órbita completa es mantenida por el árbol. Calcular un generador de Schreier es una simple cuestión de aplicar el lema de subgrupo de Schreier .
Otro detalle que se deja fuera es la prueba de membresía. Esta prueba se basa en el proceso de tamizado. Se tamiza una permutación a lo largo de la cadena en cada paso encontrando la clase lateral que la contiene, luego se usa el representante de esa clase lateral para encontrar una permutación en el subgrupo, y el proceso se repite en el subgrupo con esa permutación encontrada. Si se alcanza el final de la cadena (es decir, llegamos al subgrupo trivial), entonces la permutación tamizada era un miembro del grupo en la parte superior de la cadena.
Referencias
- Knuth, Donald E. "Representación eficiente de grupos de permanentes". Combinatorica 11 (1991), no. 1, 33–43.
- Seress, A., algoritmos de grupo de permutación , Cambridge U Press, 2002.
- Sims, Charles C. "Métodos computacionales en el estudio de grupos de permutación", en Computational Problems in Abstract Algebra , págs. 169-183, Pergamon, Oxford, 1970.