Quelle permute_subgroups.c Sprache: C

/****************************************************************************
**
*A  permute_subgroups.c         ANUPQ source                   Eamonn O'Brien
**
*Y  Copyright 1995-2001,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
*Y  Copyright 1995-2001,  School of Mathematical Sciences, ANU,     Australia
**
*/

#include "pq_defs.h"
#include "pcp_vars.h"
#include "pga_vars.h"
#include "pq_functions.h"
#include "constants.h"

/* compute all of the permutations of the allowable subgroups
  induced by the extended automorphisms described in auts;
  store them in image format in a 2-dimensional array, perms */

int **permute_subgroups(FILE *LINK_input,
                        int **a,
                        int **b,
                        char **c,
                        int ***auts,
                        struct pga_vars *pga,
                        struct pcp_vars *pcp)
{
   register int alpha;
   register int nmr_of_perms;
   register int q = pga->q;
   int **A; /* automorphism matrix */
   int **perms;
   Logical soluble_group;

   soluble_group = (pga->soluble || pga->Degree == 1 || pga->nmr_of_perms == 0);

   /* set up space for automorphism matrix */
   A = allocate_matrix(q, q, 0, FALSE);

   /* set up space for orbit and stabiliser information */
   if (soluble_group && pga->space_efficient)
      space_for_orbits(a, b, c, pga);

   /* set up space to store permutations */
   nmr_of_perms = (pga->space_efficient ? 1 : MAX(pga->nmr_of_perms, 1));
   perms = allocate_matrix(nmr_of_perms, pga->Degree, 1, FALSE);

   /* the stabiliser of a reduced p-covering group may be trivial */
   if (pga->nmr_of_perms == 0)
      setup_identity_perm(perms[nmr_of_perms], pga);

   for (alpha = 1; alpha <= pga->m; ++alpha) {

      if (pga->trace)
         printf("Processing automorphism %d:\n", alpha);

      assemble_matrix(A, q, auts[alpha], pcp);

      /* check if the matrix passes some elementary tests */
      if (!valid_matrix(A, q, pga->p, 0)) {
         printf("The following automorphism matrix is invalid\n");
         print_matrix(A, q, q);
         exit(FAILURE);
      }

      if (pga->print_automorphism_matrix) {
         printf("Automorphism matrix %d is\n", alpha);
         print_matrix(A, q, q);
      }

      if (!soluble_group) {
#if defined(GAP_LINK) || defined(GAP_LINK_VIA_FILE)
         write_GAP_matrix(LINK_input, "ANUPQglb.genQ", A, q, 0, alpha);
#endif
      }

      /* is the action on the p-multiplicator non-trivial? */
      if (pga->map[alpha] != 0) {

         nmr_of_perms = (pga->space_efficient ? 1 : pga->map[alpha]);
         compute_permutation(perms[nmr_of_perms], A, pga);

         if (pga->print_permutation) {
            printf("Permutation %d is\n", alpha);
            print_array(perms[nmr_of_perms], 1, pga->Degree + 1);
         }
      }

      if (soluble_group && pga->space_efficient) {
         if (pga->map[alpha] != 0)
            orbits(perms[nmr_of_perms], *a, *b, *c, pga);
         else
            process_identity_perm(*a, *b, *c, pga);
      }
   }

   free_matrix(A, q, 0);
   return perms;
}

/* compute and store in image form the permutation that the extended
   automorphism stored in A induces on the allowable subgroups */

void compute_permutation(int *permutation, int **A, struct pga_vars *pga)
{
   register int i;

   if (pga->s != 0) {
      /* process each definition set in turn */
      pga->nmr_subgroups = 0;
      for (i = 0; i < pga->nmr_def_sets; ++i)
         compute_images(A, pga->list[i], pga->available[i], permutation, pga);
   } else {
      permutation[1] = 1;
      pga->nmr_subgroups = 1;
   }
}

/* compute the images of all allowable subgroups having definition
   set K under the action of automorphism matrix A */

void compute_images(
    int **A, int K, int depth, int *permutation, struct pga_vars *pga)

/* number of available positions */

{
   int **S;     /* standard matrix */
   int **Image; /* image of allowable subgroup under A */
   int *row;    /* indices of available positions in S */
   int *column;
   int *position; /* array to keep track of processed image */
   int *subset;   /* array to store definition set of image */
   int K_Image;   /* bit string representation of same */
   int nmr_of_bytes = pga->q * sizeof(int);
   register int i;
   register int index;
   register int s = pga->s;
   register int q = pga->q;
   register int p = pga->p;
   register int nmr_subgroups = pga->nmr_subgroups;

   S = allocate_matrix(s, q, 0, FALSE);

   Image = allocate_matrix(s, q, 0, TRUE);

   subset = allocate_vector(s, 0, 0);

   position = allocate_vector(depth + 1, 0, 1);

   /* set up row and column indices of available positions as
      arrays of length depth + 1; also set up Image as image of
      allowable subgroup with least label under action of A */

   find_available_positions(K, A, Image, &row, &column, depth, pga);

   /* for each allowable subgroup in turn, compute its image under A */

   do {

      /* make a copy of the image matrix and echelonise the copy */
      for (i = 0; i < s; ++i)
         memcpy(S[i], Image[i], nmr_of_bytes);

      K_Image = echelonise_matrix(S, s, q, p, subset, pga);

      /* compute and store the label of the resulting standard matrix */
      ++nmr_subgroups;
      if (nmr_subgroups % 1000000 == 0)
         printf("processing subgroup %d\n", nmr_subgroups);

      permutation[nmr_subgroups] = subgroup_to_label(S, K_Image, subset, pga);

      index = 0;
      ++position[0];
      update_image(A, column[index], Image, row[index], pga);

      while (index < depth && position[index] == p) {
         position[index] = 0;
         ++index;
         ++position[index];
         update_image(A, column[index], Image, row[index], pga);
      }
   } while (index < depth);

   pga->nmr_subgroups = nmr_subgroups;

   free_vector(row, 0);
   free_vector(column, 0);
   free_vector(subset, 0);
   free_vector(position, 0);
   free_matrix(S, s, 0);
   free_matrix(Image, s, 0);
}

/* add column of A to row of Image */

void
update_image(int **A, int column, int **Image, int row, struct pga_vars *pga)
{
   register int i;
   register int q = pga->q;
   register int p = pga->p;

   for (i = 0; i < q; ++i)
      Image[row][i] = (Image[row][i] + A[i][column]) % p;
}

/* set up the indices of the available positions of the standard matrices
   determined by K as two arrays, row and column; also set up Image as
   image of allowable subgroup with least label under action of A */

void find_available_positions(int K,
                              int **A,
                              int **Image,
                              int **row,
                              int **column,
                              int depth,
                              struct pga_vars *pga)
{
   register int i, j;
   register int index = 0;
   register int s = pga->s;
   register int q = pga->q;
   int *subset;

   subset = bitstring_to_subset(K, pga);

   *row = allocate_vector(depth + 1, 0, 0);
   *column = allocate_vector(depth + 1, 0, 0);
   (*row)[depth] = 0;
   (*column)[depth] = 0;

   for (i = 0; i < s; ++i) {
      update_image(A, subset[i], Image, i, pga);
      for (j = subset[i] + 1; j < q; ++j) {
         if (1 << j & K)
            continue;
         (*row)[index] = i;
         (*column)[index] = j;
         ++index;
      }
   }

   free_vector(subset, 0);
}

quality91%

¤ Dauer der Verarbeitung: 0.14 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.