Quelle permute_elements.c Sprache: C

/****************************************************************************
**
*A  permute_elements.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"
#undef DEBUG
#include "pga_vars.h"
#include "pq_functions.h"

/* compute automorphism classes of elements of a vector space;

   procedure requests as input rank and prime and those matrices
   which act on the space;

   it also permits the computation of the permutations induced
   by multiplying each element of the vector space by a supplied
   basis element; the basis element are numbered 1 .. <rank>

   elements are generated in sequence and their images
   computed by matrix multiplication; orbits under the
   action of these permutations are then computed and
   orbit representatives listed;

   given the label of an orbit representative, its p-adic
   expansion corresponds to the element */

void expand_padic(int x, int k, int p, int *expand)
{
   register int alpha;
   register int val;

   while (x > 0 && k >= 0) {
      val = int_power(p, k);
      if (val <= x) {
         /* find largest multiple of p^k < x */
         alpha = p - 1;
         while (alpha * val > x)
            --alpha;
         expand[k] = alpha;
         x -= alpha * val;
      }
      --k;
   }
}

void padic(int p, int rank, struct pga_vars *pga)
{
   int number;
   int *expand;
   int bound = rank;
   int i, r;
   expand = allocate_vector(rank + 1, 0, FALSE);

   for (r = 1; r <= pga->nmr_orbits; ++r) {
      number = pga->rep[r];
      for (i = 0; i <= rank; ++i)
         expand[i] = 0;
      bound = rank;
      while (bound > 0 && int_power(p, bound) > number)
         --bound;
      ++bound;

      expand_padic(number, bound, p, expand);
      printf("The element with label %5d is ", number);
      print_array(expand, 0, rank);
   }
}

void permute_elements(void)
{
   int index;
   int **position;
   int rank;
   int p;
   int i;
   int label;
   int map;
   int **A;
   int **B;
   int subgp = 0;
   int **permutation;
   struct pga_vars pga;

   int *length;
   int alpha;
   int m;
   int q, x;
   int *orbit;
   char *schreier;
   int *backptr;
   int nmr_maps;
   int Degree;

   read_value(TRUE, "Input rank of vector space: ", &rank, 1);
   read_value(TRUE, "Input prime: ", &p, 2);
   read_value(TRUE, "Input number of automorphism matrices: ", &m, 0);
   read_value(TRUE, "Input number of multiplication maps: ", &nmr_maps, 0);

   Degree = int_power(p, rank);
   position = allocate_matrix(1, rank + 1, 0, 0);
   permutation = allocate_matrix(nmr_maps + m, Degree, 1, 0);

   q = rank;
   A = allocate_matrix(q, rank + 1, 0, 0);

   /* first process automorphisms */

   for (alpha = 1; alpha <= m; ++alpha) {
      printf("Input the matrix for automorphism %d\n", alpha);
      read_matrix(A, q, q);

      for (x = 0; x <= rank; ++x)
         position[0][x] = 0;

      subgp = 0;
      do {
         index = 0;
         ++position[0][0];
         while (index < rank && position[0][index] == p) {
            position[0][index] = 0;
            ++index;
            ++position[0][index];
         }

#ifdef DEBUG
         printf("\n");
         for (i = 0; i < rank; ++i)
            printf("%d ", position[0][i]);
#endif
         label = 0;
         for (i = 0; i < rank; ++i)
            label += (position[0][i] * int_power(p, i));
#ifdef DEBUG
         printf("label is %d\n", label);
#endif

         /* now multiply mod p */
         B = multiply_matrix(position, 1, q, A, q, p);
#ifdef DEBUG
         print_matrix(B, 1, q);
#endif
         label = 0;
         for (i = 0; i < rank; ++i)
            label += (B[0][i] * int_power(p, i));
#ifdef DEBUG
         printf("label is %d\n", label);
         if (subgp % 10000 == 0)
            printf("Completed %d subgroups\n", subgp);
#endif
         if (label == 0)
            label = Degree;
         permutation[alpha][++subgp] = label;

         free_matrix(B, 1, 0);

      } while (index < rank);

#ifdef DEBUG
      print_array(permutation[alpha], 1, subgp + 1);
#endif
   }

   pga.Degree = Degree;

   /* now process multiplication maps */

   for (alpha = 1; alpha <= nmr_maps; ++alpha) {
      subgp = 0;

      for (x = 0; x <= rank; ++x)
         position[0][x] = 0;

      read_value(TRUE, "Input basis element to multiply by: ", &map, 1);
      --map;

      do {
         index = 0;
         ++position[0][0];
         while (index < rank && position[0][index] == p) {
            position[0][index] = 0;
            ++index;
            ++position[0][index];
         }

#if DEBUG
         printf("\n");
         for (i = 0; i < rank; ++i)
            printf("%d ", position[0][i]);
#endif

         label = 0;
         for (i = 0; i < rank; ++i)
            label += (position[0][i] * int_power(p, i));
#if DEBUG
         printf("label is %d\n", label);
#endif

         B = allocate_matrix(1, rank + 1, 0, 0);
         for (i = 0; i < rank; ++i)
            B[0][i] = position[0][i];
         B[0][map] = (B[0][map] + 1) % p;

#if DEBUG
         print_matrix(B, 1, q);
#endif
         label = 0;
         for (i = 0; i < rank; ++i)
            label += (B[0][i] * int_power(p, i));
#if DEBUG
         printf("label is %d\n", label);
#endif

         if (label == 0)
            label = pga.Degree;

         permutation[m + alpha][++subgp] = label;
         free_matrix(B, 1, 0);

      } while (index < rank);
#if DEBUG
      print_array(permutation[m + alpha], 1, subgp + 1);
#endif
   }

   pga.Degree = subgp;
   pga.m = m + nmr_maps;
   pga.nmr_of_perms = m + nmr_maps;
   pga.soluble = FALSE;
   pga.print_orbits = FALSE;

   insoluble_compute_orbits(&orbit, &backptr, &schreier, permutation, &pga);
   length = find_orbit_reps(orbit, orbit, &pga);
   orbit_summary(length, &pga);

   padic(p, rank, &pga);
}

quality90%

¤ Dauer der Verarbeitung: 0.13 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.