GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

1
/****************************************************************************
2
**
3
*A  Extend_Auts.c               ANUPQ source                   Eamonn O'Brien
4
**
5
*Y  Copyright 1995-2001,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
6
*Y  Copyright 1995-2001,  School of Mathematical Sciences, ANU,     Australia
7
**
8
*/
9

10
#include "pq_defs.h"
11
#include "pcp_vars.h"
12
#include "pq_functions.h"
13
#define SIZE 100
14
#define DEFAULT_SIZE 100000
15
#define DEBUG1
16

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

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

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

32
void Extend_Auts(int **head, int **list, int start, struct pcp_vars *pcp)
33
{
34
   register int lastg = pcp->lastg;
35
   register int offset;
36
   register int alpha;
37
   int index = 0;
38
   int max_length;
39
   FILE *fp;
40
   int nmr_saved;
41
   int list_length;
42

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

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

51
   fp = TemporaryFile();
52

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

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

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

61
   if (pcp->cc != 1) {
62
      if ((*head)[0] < lastg)
63
         *head = reallocate_vector(
64
             *head, 1 + (*head)[0] * pcp->m, 1 + lastg * pcp->m, 0, FALSE);
65
      if ((*list)[0] < list_length)
66
         *list = reallocate_vector(
67
             *list, (*list)[0] + 1, list_length + 1, 0, FALSE);
68
      else
69
         list_length = (*list)[0];
70
   }
71

72
   for (alpha = 1; alpha <= pcp->m; ++alpha) {
73
      offset = (alpha - 1) * lastg;
74
      restored_length +=
75
          restore_auts(fp, offset, nmr_saved, start - 1, &index, *head, *list);
76
      Extend_Aut(
77
          start, max_length, &list_length, *head, list, offset, &index, pcp);
78
#ifdef DEBUG
79
      if (alpha != pcp->m) {
80
         printf("*** After automorphism %d, allocation is %d\n",
81
                alpha,
82
                list_length);
83
         printf("*** Value of index is now %d\n", index);
84
      }
85
#endif
86

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

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

99
   CloseFile(fp);
100

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

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

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

116
   for (alpha = 1; alpha <= pcp->m; ++alpha) {
117
      for (i = first; i <= MIN(last, pcp->lastg); ++i) {
118
         ptr = head[offset + i];
119
         length = list[ptr + 1];
120
         printf("%d --> ", i);
121
         for (j = ptr + 2; j <= ptr + length + 1; ++j) {
122
            printf("%d^%d ", FIELD2(list[j]), FIELD1(list[j]));
123
         }
124
         printf("\n");
125
      }
126
      offset += pcp->lastg;
127
   }
128
}
129

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

132
void Setup_Action(int **head,
133
                  int **list,
134
                  int ***auts,
135
                  int nmr_of_exponents,
136
                  struct pcp_vars *pcp)
137
{
138
   register int *y = y_address;
139

140
   register int i, generator;
141
   int position, max_length, exp, alpha, offset;
142
   int lastg = pcp->lastg;
143
   int fq_rank = y[pcp->clend + 1];
144
   int list_length;
145
   int index = 0;
146

147
#include "access.h"
148

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

154
   for (alpha = 1; alpha <= pcp->m; ++alpha) {
155
      offset = (alpha - 1) * fq_rank;
156
      for (generator = 1; generator <= fq_rank; ++generator) {
157
         position = (*head)[offset + generator] = index;
158
         (*list)[++position] = 0;
159
         ++index;
160
         for (i = 1; i <= nmr_of_exponents; ++i) {
161
            if ((exp = auts[alpha][generator][i]) != 0) {
162
               ++(*list)[position];
163
               (*list)[++index] = PACK2(exp, i);
164
            }
165
         }
166
      }
167
   }
168

169
   (*head)[0] = fq_rank;
170
   (*list)[0] = list_length;
171
}
172

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

178
void Extend_Aut(int start,
179
                int max_length,
180
                int *list_length,
181
                int *head,
182
                int **list,
183
                int offset,
184
                int *index,
185
                struct pcp_vars *pcp)
186
{
187
   register int *y = y_address;
188

189
   register int i, generator;
190
   register int lastg = pcp->lastg;
191
   register int structure = pcp->structure;
192
   int cp1 = pcp->submlg - lastg - 2;
193
   int cp2 = cp1 - lastg;
194
   int result = cp2 - lastg;
195
   register int value;
196
   int u, v;
197
   int exp;
198
   int position, new;
199

200
#include "access.h"
201

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

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

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

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

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

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

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

228
         u = PART2(value);
229
         v = PART3(value);
230

231
         if (v == 0)
232
            Extend_Pow(cp1, cp2, u, offset, head, *list, pcp);
233
         else
234
            Extend_Comm(cp1, cp2, u, v, offset, head, *list, pcp);
235

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

242
         solve_equation(cp1, cp2, result, pcp);
243

244
#endif
245
      }
246

247
      /* now copy the result to list */
248

249
      position = head[offset + generator] = *index;
250
      (*list)[++position] = 0;
251
      ++*index;
252

253

254
      for (i = 1; i <= lastg; ++i) {
255
         if ((exp = y[result + i]) != 0) {
256
            ++(*list)[position];
257
            (*list)[++*index] = PACK2(exp, i);
258
         }
259
      }
260
   }
261

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

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

271
   int lastg = pcp->lastg;
272
   int i, j, start, u;
273
   int pointer;
274
   int exp;
275
   int image_length, relation_length;
276
   int next_gen, next_exp;
277
   int p = pcp->p;
278
#include "access.h"
279

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

283
   if (ptr == 0)
284
      return;
285

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

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

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

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

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

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

305
   pointer = pcp->lused + 1;
306
   for (i = 2; i <= relation_length; ++i) {
307
      next_gen = FIELD2(y[ptr + 1 + i]);
308
      next_exp = FIELD1(y[ptr + 1 + i]);
309
      start = head[offset + next_gen];
310
      image_length = list[++start];
311
      y[pointer + 1] = image_length;
312
      for (j = 1; j <= image_length; ++j)
313
         y[pointer + 1 + j] = list[start + j];
314
      for (; next_exp > 0; --next_exp)
315
         collect(-pointer, cp, pcp);
316
   }
317
}
318

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

322
                      u^p = W * t
323

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

328
void Extend_Pow(int cp1,
329
                int cp2,
330
                int u,
331
                int offset,
332
                int *head,
333
                int *list,
334
                struct pcp_vars *pcp)
335
{
336
   register int *y = y_address;
337

338
   register int i;
339
   register int value;
340
   register int lastg = pcp->lastg;
341

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

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

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

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

356
#if defined(GROUP)
357

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

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

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

368
void Extend_Comm(int cp1,
369
                 int cp2,
370
                 int u,
371
                 int v,
372
                 int offset,
373
                 int *head,
374
                 int *list,
375
                 struct pcp_vars *pcp)
376
{
377
   register int *y = y_address;
378

379
   register int i;
380
   register int pointer, value;
381
   register int lastg = pcp->lastg;
382

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

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

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

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

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

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

404
#endif
405

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

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

416
   register int lused = pcp->lused;
417
   int str = lused + pcp->lastg;
418
   register int i;
419

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

423
   traverse_list(1, head, list, lused, pcp);
424
   power(exp, lused, pcp);
425
   vector_to_string(lused, str, pcp);
426

427
   collect(-str, cp, pcp);
428
}
429

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

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

437
   register int lused = pcp->lused;
438
   register int length = list[++head];
439
   register int i;
440

441
   y[lused + 1] = length;
442

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

446
   collect(-lused, cp, pcp);
447
}
448

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

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

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

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

468
   for (i = 1; i <= length; ++i) {
469
      value = y[string + 1 + i];
470
      generator = FIELD2(value);
471
      exp = FIELD1(value);
472
      while (exp > 0) {
473
         Collect_Image_Of_Gen(cp, head[offset + generator], list, pcp);
474
         --exp;
475
      }
476
   }
477
}
478

479