Quelle Extend_Auts.c Sprache: C

/****************************************************************************
**
*A  Extend_Auts.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 "pq_functions.h"
#define SIZE 100
#define DEFAULT_SIZE 100000
#define DEBUG1

/* for each automorphism, compute its action on each of the generators;

   this code is a modified version of the code to be found in the file
   extend_automorphisms -- the modifications are introduced in order
   to store the automorphims much more efficiently than the 3-dimensional
   array used in that code; the efficiency is achieved by storing the
   description using two 1-dimensional arrays, head and list;

   these vectors are organised as follows --
   ptr = head[(alpha - 1) * lastg + i] is a pointer to action of
         automorphism alpha on generator i;
   length = list[ptr + 1] = length of generator-exponent string
         storing action;
   list[ptr + 2] ... list[ptr + 1 + length] contains the string */

void Extend_Auts(int **head, int **list, int start, struct pcp_vars *pcp)
{
   register int lastg = pcp->lastg;
   register int offset;
   register int alpha;
   int index = 0;
   int max_length;
   FILE *fp;
   int nmr_saved;
   int list_length;

   int saved_length;        /* total length of description saved to file */
   int restored_length = 0; /* amount of description restored from file */
   int new;                 /* new storage requirement */

   /* this used to be 5 * lastg + 4 -- April 1994 */
   if (is_space_exhausted(7 * lastg + 4, pcp))
      return;

   fp = TemporaryFile();

   save_auts(fp, *head, *list, pcp);

   fread(&nmr_saved, sizeof(int), 1, fp);
   fread(&saved_length, sizeof(int), 1, fp);

   max_length = MIN(SIZE, lastg) * lastg;
   list_length = max_length + DEFAULT_SIZE;

   if (pcp->cc != 1) {
      if ((*head)[0] < lastg)
         *head = reallocate_vector(
             *head, 1 + (*head)[0] * pcp->m, 1 + lastg * pcp->m, 0, FALSE);
      if ((*list)[0] < list_length)
         *list = reallocate_vector(
             *list, (*list)[0] + 1, list_length + 1, 0, FALSE);
      else
         list_length = (*list)[0];
   }

   for (alpha = 1; alpha <= pcp->m; ++alpha) {
      offset = (alpha - 1) * lastg;
      restored_length +=
          restore_auts(fp, offset, nmr_saved, start - 1, &index, *head, *list);
      Extend_Aut(
          start, max_length, &list_length, *head, list, offset, &index, pcp);
#ifdef DEBUG
      if (alpha != pcp->m) {
         printf("*** After automorphism %d, allocation is %d\n",
                alpha,
                list_length);
         printf("*** Value of index is now %d\n", index);
      }
#endif

      if ((new = saved_length - restored_length + index) > list_length) {
         *list = reallocate_vector(*list, list_length + 1, new + 1, 0, FALSE);
         list_length = new;
#ifdef DEBUG
         printf("*** Allocation is increased to %d\n", list_length);
#endif
      }
   }

   (*head)[0] = lastg;
   (*list)[0] = list_length;

   CloseFile(fp);

#ifdef DEBUG1
   printf("*** Final allocated space for automorphisms is %d\n", list_length);
   printf("*** Final amount used is %d\n", index);
#endif
}

/* list the action of each automorphism on each of the
   pcp generators, first .. last, by their image */

void List_Auts(int *head, int *list, int first, int last, struct pcp_vars *pcp)
{
   register int alpha, i, j, ptr, length;
   int offset = 0;
#include "access.h"

   for (alpha = 1; alpha <= pcp->m; ++alpha) {
      for (i = first; i <= MIN(last, pcp->lastg); ++i) {
         ptr = head[offset + i];
         length = list[ptr + 1];
         printf("%d --> ", i);
         for (j = ptr + 2; j <= ptr + length + 1; ++j) {
            printf("%d^%d ", FIELD2(list[j]), FIELD1(list[j]));
         }
         printf("\n");
      }
      offset += pcp->lastg;
   }
}

/* set up description of action of automorphisms on defining generators */

void Setup_Action(int **head,
                  int **list,
                  int ***auts,
                  int nmr_of_exponents,
                  struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int i, generator;
   int position, max_length, exp, alpha, offset;
   int lastg = pcp->lastg;
   int fq_rank = y[pcp->clend + 1];
   int list_length;
   int index = 0;

#include "access.h"

   *head = allocate_vector(fq_rank * pcp->m + 1, 0, FALSE);
   max_length = MIN(SIZE, lastg) * lastg;
   list_length = max_length + DEFAULT_SIZE;
   *list = allocate_vector(list_length + 1, 0, FALSE);

   for (alpha = 1; alpha <= pcp->m; ++alpha) {
      offset = (alpha - 1) * fq_rank;
      for (generator = 1; generator <= fq_rank; ++generator) {
         position = (*head)[offset + generator] = index;
         (*list)[++position] = 0;
         ++index;
         for (i = 1; i <= nmr_of_exponents; ++i) {
            if ((exp = auts[alpha][generator][i]) != 0) {
               ++(*list)[position];
               (*list)[++index] = PACK2(exp, i);
            }
         }
      }
   }

   (*head)[0] = fq_rank;
   (*list)[0] = list_length;
}

/* extend the automorphism whose action on the defining generators
   of the group is described in the two 1-dimensional arrays, head
   and list, to act on the generators of the group; the first
   generator whose image is computed is start */

void Extend_Aut(int start,
                int max_length,
                int *list_length,
                int *head,
                int **list,
                int offset,
                int *index,
                struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int i, generator;
   register int lastg = pcp->lastg;
   register int structure = pcp->structure;
   int cp1 = pcp->submlg - lastg - 2;
   int cp2 = cp1 - lastg;
   int result = cp2 - lastg;
   register int value;
   int u, v;
   int exp;
   int position, new;

#include "access.h"

   /* update submlg because of possible call to power */
   pcp->submlg -= (3 * lastg + 2);

   /* for each specified generator, compute its image under
      the action of the automorphism */

   for (generator = start; generator <= lastg; ++generator) {

#ifdef DEBUG
      if (generator % 100 == 0)
         printf("Processed generator %d\n", generator);
#endif

      /* check if there is sufficient space allocated */
      if (generator % SIZE == 1 && (new = *index + max_length) > *list_length) {
         *list = reallocate_vector(*list, *list_length + 1, new + 1, 0, FALSE);
         *list_length = new;
      }

      /* examine the definition of generator */
      value = y[structure + generator];

      if (value <= 0) {
         evaluate_image(head, *list, offset, -value, result, pcp);
      } else {

         u = PART2(value);
         v = PART3(value);

         if (v == 0)
            Extend_Pow(cp1, cp2, u, offset, head, *list, pcp);
         else
            Extend_Comm(cp1, cp2, u, v, offset, head, *list, pcp);

#if defined(GROUP)
         /* solve the appropriate equation, storing the image
            of generator under the action of alpha at result;
            in the Lie Program, Extend_Comm has already
            set up the answer at location result */

         solve_equation(cp1, cp2, result, pcp);

#endif
      }

      /* now copy the result to list */

      position = head[offset + generator] = *index;
      (*list)[++position] = 0;
      ++*index;

      for (i = 1; i <= lastg; ++i) {
         if ((exp = y[result + i]) != 0) {
            ++(*list)[position];
            (*list)[++*index] = PACK2(exp, i);
         }
      }
   }

   /* reset value of submlg */
   pcp->submlg += (3 * lastg + 2);
}

void evaluate_image(
    int *head, int *list, int offset, int ptr, int cp, struct pcp_vars *pcp)
{
   register int *y = y_address;

   int lastg = pcp->lastg;
   int i, j, start, u;
   int pointer;
   int exp;
   int image_length, relation_length;
   int next_gen, next_exp;
   int p = pcp->p;
#include "access.h"

   for (i = 1; i <= lastg; ++i)
      y[cp + i] = 0;

   if (ptr == 0)
      return;

   /* length of redundant relation */
   relation_length = y[ptr + 1];

   /* first generator in redundant relation */
   u = FIELD2(y[ptr + 1 + 1]);

   /* its exponent */
   exp = FIELD1(y[ptr + 1 + 1]);

   /* set up exp power of the image of u under alpha as exponent vector at cp */
   traverse_list(exp, head[offset + u], list, cp, pcp);

   /* now reduce the entries mod p */
   for (i = 1; i <= lastg; ++i)
      y[cp + i] %= p;

   /* now set up image of second generator as word with
      base address pointer */

   pointer = pcp->lused + 1;
   for (i = 2; i <= relation_length; ++i) {
      next_gen = FIELD2(y[ptr + 1 + i]);
      next_exp = FIELD1(y[ptr + 1 + i]);
      start = head[offset + next_gen];
      image_length = list[++start];
      y[pointer + 1] = image_length;
      for (j = 1; j <= image_length; ++j)
         y[pointer + 1 + j] = list[start + j];
      for (; next_exp > 0; --next_exp)
         collect(-pointer, cp, pcp);
   }
}

/* given generator t of the p-multiplicator, whose definition is
   u^p; hence, we have the equation

                      u^p = W * t

   where W is a word (possibly trivial) in the generators of the group;
   find the image of t under alpha by setting up (W)alpha at cp1,
   ((u)alpha)^p at cp2, and then call solve_equation */

void Extend_Pow(int cp1,
                int cp2,
                int u,
                int offset,
                int *head,
                int *list,
                struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int i;
   register int value;
   register int lastg = pcp->lastg;

   for (i = 1; i <= lastg; ++i)
      y[cp1 + i] = y[cp2 + i] = 0;

   /* set up the image of u under alpha at cp2 */
   traverse_list(1, head[offset + u], list, cp2, pcp);

   /* raise the image of u under alpha to its pth power */
   power(pcp->p, cp2, pcp);

   /* set up image of W under alpha at cp1 */
   if ((value = y[pcp->ppower + u]) < 0)
      Collect_Image_Of_Str(-value, cp1, offset, head, list, pcp);
}

#if defined(GROUP)

/* given generator t of the p-multiplicator, whose definition is
   [u, v]; hence, we have the equation

   [u, v] = W * t, or equivalently, u * v = v * u * W * t

   where W is a word (possibly trivial) in the generators of the group;
   find the image of t under alpha by setting up
   (v)alpha * (u)alpha * (W)alpha at cp1, (u)alpha * (v)alpha at cp2
   and then call solve_equation */

void Extend_Comm(int cp1,
                 int cp2,
                 int u,
                 int v,
                 int offset,
                 int *head,
                 int *list,
                 struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int i;
   register int pointer, value;
   register int lastg = pcp->lastg;

   for (i = 1; i <= lastg; ++i)
      y[cp1 + i] = y[cp2 + i] = 0;

   /* set up the image of u under alpha at cp2 */
   traverse_list(1, head[offset + u], list, cp2, pcp);

   /* collect image of v under alpha at cp2 */
   Collect_Image_Of_Gen(cp2, head[offset + v], list, pcp);

   /* set up image of v under alpha at cp1 */
   traverse_list(1, head[offset + v], list, cp1, pcp);

   /* collect image of u under alpha at cp1 */
   Collect_Image_Of_Gen(cp1, head[offset + u], list, pcp);

   /* collect image of W under alpha at cp1 */
   pointer = y[pcp->ppcomm + u];
   if ((value = y[pointer + v]) < 0)
      Collect_Image_Of_Str(-value, cp1, offset, head, list, pcp);
}

#endif

/* there may be a case where each of the exponent and p is large
   to use the power routine to compute the exp power of the
   image of generator under automorphism -- it does not seem to
   be worthwhile where p = 5 -- needs further investigation */

void Pq_Collect_Image_Of_Gen(
    int exp, int cp, int head, int *list, struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int lused = pcp->lused;
   int str = lused + pcp->lastg;
   register int i;

   for (i = 1; i <= pcp->lastg; ++i)
      y[lused + i] = 0;

   traverse_list(1, head, list, lused, pcp);
   power(exp, lused, pcp);
   vector_to_string(lused, str, pcp);

   collect(-str, cp, pcp);
}

/* collect image of a generator under the
   action of an automorphism and store the result at cp */

void Collect_Image_Of_Gen(int cp, int head, int *list, struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int lused = pcp->lused;
   register int length = list[++head];
   register int i;

   y[lused + 1] = length;

   for (i = 1; i <= length; ++i)
      y[lused + 1 + i] = list[head + i];

   collect(-lused, cp, pcp);
}

/* collect image of supplied string under the action of
   supplied automorphism and store the result at cp */

void Collect_Image_Of_Str(
    int string, int cp, int offset, int *head, int *list, struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int i;
   register int generator, exp;
   register int value;
   register int length = y[string + 1] - 1; /* last element of string
                                               is in p-multiplicator */
#include "access.h"

   /* process the string generator by generator, collecting exp
      copies of the image of generator under action of automorphism
      -- should power routine be used? */

   for (i = 1; i <= length; ++i) {
      value = y[string + 1 + i];
      generator = FIELD2(value);
      exp = FIELD1(value);
      while (exp > 0) {
         Collect_Image_Of_Gen(cp, head[offset + generator], list, pcp);
         --exp;
      }
   }
}

quality90%

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