staticvoid enforce_exp_law(struct pcp_vars *pcp); staticint **start_pga_run(Logical *identity_map, int ***auts, struct pga_vars *pga, struct pcp_vars *pcp); staticint **
group_completed(int ***auts, struct pga_vars *pga, struct pcp_vars *pcp); staticint **finish_pga_run(Logical *identity_map,
FILE *cover_tmp_file,
FILE *group_file, int ***auts, struct pga_vars *pga, struct pcp_vars *pcp); staticint **find_stabiliser(Logical *identity_map, int non_standard, int ***auts, int **perms, int *a, int *b, char *c, int *orbit_length, struct pga_vars *pga, struct pcp_vars *pcp); staticvoid
trace(char *word_map, int *depth, int label, int *backptr, char *schreier); staticchar *find_word(int *word_length,
Logical soluble_group, int **perms, int rep, int non_standard, int orbit_length, int *b, char *c, struct pga_vars *pga); staticint **standard_map(char *word_map, int word_length,
Logical *identity_map, int rep, int ***auts, struct pga_vars *pga, struct pcp_vars *pcp); staticint inverse_image(int l, int *perms, struct pga_vars *pga); staticvoid list_subgroup(int rep, struct pga_vars *pga, struct pcp_vars *pcp);
/* compute a standard presentation for a group;
this procedure assumes that -- an arbitrary finite presentation has been supplied; -- a standard presentation has been computed for the class c p-quotient; -- a presentation for the p-covering group computed using this standard presentation has been set up before the call to this procedure;
we will now compute the standard presentation for the
class c + 1 p-quotient */
void standard_presentation(Logical *identity_map, int standard_output, int ***auts, struct pga_vars *pga, struct pcp_vars *pcp)
{ int i; int **map; #ifdefined(TIME) int t; #endif
/* commence a partial run of p-group generation in order
to determine the standard presentation for this class */
staticint **start_pga_run(Logical *identity_map, int ***auts, struct pga_vars *pga, struct pcp_vars *pcp)
{
FILE *cover_file; /* store complete p-cover of group */
FILE *cover_tmp_file; /* store (reduced) p-cover of group */
FILE *group_file; /* store class c + 1 quotient of group */ int **map; /* automorphism to apply to presentation */ #ifdefined(TIME) int t = runTime(); #endif
/* save (reduced) p-covering group presentation to temporary file */
cover_tmp_file = TemporaryFile();
save_pcp(cover_tmp_file, pcp);
RESET(cover_tmp_file);
/* we need compute the class c + 1 quotient only on the first time through or if the map applied to the previous presentation was not the identity; in these cases, before computing class c + 1 quotient, restore complete p-cover; we cannot use the reduced p-cover because a presentation having redundant generators can cause difficulties with interaction
between update_generators and eliminate */
/* enforce exponent law on complete p-cover */
enforce_exp_law(pcp);
/* now compute the presentation for the class c + 1 quotient */
pcp->multiplicator = FALSE;
update_generators(pcp);
collect_relations(pcp);
eliminate(FALSE, pcp); if (pcp->overflow || !pcp->valid) exit(FAILURE);
/* when relations are enforced, the group may complete */ if (pcp->complete) {
map = group_completed(auts, pga, pcp);
*identity_map = TRUE;
CloseFile(cover_tmp_file); return map;
}
/* save presentation for class c + 1 quotient to file */
group_file = OpenFile("ISOM_group_file", "w+");
save_pcp(group_file, pcp);
} else { /* we must restore the presentation to correctly determine step size */
group_file = OpenFile("ISOM_group_file", "r");
restore_pcp(group_file, pcp);
}
RESET(group_file);
#ifdefined(TIME)
t = runTime() - t;
printf("Time to compute class c + 1 is %.2f seconds\n", t * CLK_SCALE); #endif
map_array_size = pcp->lastg;
standard = allocate_matrix(pcp->lastg, pcp->lastg, 1, FALSE);
for (i = 1; i <= pga->ndgen; ++i) for (j = 1; j <= pcp->lastg; ++j)
standard[i][j] = (i == j) ? 1 : 0;
return standard;
}
/* complete pga run to compute standard presentation for this class */
staticint **finish_pga_run(Logical *identity_map,
FILE *cover_tmp_file,
FILE *group_file, int ***auts, struct pga_vars *pga, struct pcp_vars *pcp)
{ int **perms;
FILE *LINK_input = 0; int k; int upper_step;
Logical soluble_group; #ifdefined(GAP_LINK)
Logical process_fork = FALSE; /* has GAP process forked? */ #endif int *a; int *b; char *c; int *orbit_length; int **subgroup_matrix; int K; /* bit string representation of definition set */ int *subset; /* definition set */ int non_standard; /* label for allowable subgroup defining
non-standard presentation */ int **map; /* automorphism to apply to presentation */ #ifdefined(TIME) int t; #endif
/* now find allowable subgroup which determines the class c + 1 quotient */
subgroup_matrix = find_allowable_subgroup(
2, cover_tmp_file, group_file, &K, &subset, pga, pcp);
if (output == MAX_STANDARD_PRINT) {
printf("Non-standard label is %d\n", non_standard);
printf("Required step size is %d\n", pga->step_size);
printf("Relative step size is %d\n", pga->s);
printf("Rank of characteristic subgroup is %d\n", pga->q);
}
if (pga->final_stage && output >= DEFAULT_STANDARD_PRINT) {
printf("\nThe standard presentation for the class %d %d-quotient is\n",
pcp->cc,
pcp->p);
print_presentation(TRUE, pcp); #ifdef HAVE_GMP char *s = pga->upper_bound ? "at most " : ""; /* Originally pq checked the whole automorphism group. * Now it checks only coset reps. of inner automorphisms
* i.e. those auts that are in 1-1 correspondence with outer auts. */
printf("Subset of automorphism group to check has order bound %s", s);
mpz_out_str(stdout, 10, &(pga->aut_order));
printf("\n"); #endif
}
#ifdefined(GAP_LINK) if (process_fork)
QuitGap(); #endif
free_space(TRUE, perms, orbit_length, a, b, c, pga);
/* find the stabiliser of the representative of the orbit which
contains the non-standard allowable subgroup */
staticint **find_stabiliser(Logical *identity_map, int non_standard, int ***auts, int **perms, int *a, int *b, char *c, int *orbit_length, struct pga_vars *pga, struct pcp_vars *pcp)
{
FILE *Status;
FILE *OutputFile;
Logical soluble_group; int rep[2]; int length[2]; int **map; int i; int word_length = 0; char *word_map;
/* what is the orbit representative of non_standard? */ if (soluble_group)
rep[1] = abs(a[non_standard]); else { if (a[non_standard] < 0)
rep[1] = pga->rep[abs(a[non_standard])]; else
rep[1] = abs(a[non_standard]);
}
/* find the length of the orbit having this representative */ for (i = 1; i <= pga->nmr_orbits && pga->rep[i] != rep[1]; ++i)
; if (pga->rep[i] == rep[1]) {
length[1] = orbit_length[i]; if (output == MAX_STANDARD_PRINT)
printf("The non-standard subgroup %d has orbit representative %d\n",
non_standard,
pga->rep[i]);
} else {
printf("%d is not an orbit representative\n", rep[1]); exit(FAILURE);
}
/* printf ("True Orbit length is %d\n", length[1]);
*/
/* now evaluate the action of standard map on pcp */
map = standard_map(
word_map, word_length, identity_map, rep[1], auts, pga, pcp);
#ifdefined(TIME)
t = runTime() - t;
printf("Time to process representative is %.2f seconds\n", t * CLK_SCALE); #endif
RESET(OutputFile);
restore_pcp(OutputFile, pcp);
if (!pcp->complete)
last_class(pcp);
Status = OpenFile("ISOM_Status", "w"); if (pga->final_stage)
fprintf(Status, "%d ", END_OF_CLASS); else
fprintf(Status, "%d ", MIDDLE_OF_CLASS); if (pcp->newgen == 0)
fprintf(Status, "%d ", TERMINAL); else
fprintf(Status, "%d ", CAPABLE);
CloseFile(Status);
CloseFile(OutputFile);
return map;
}
void trace(char *word_map, int *depth, int label, int *backptr, char *schreier)
{ if (schreier[label] != 0) {
word_map[++*depth] = schreier[label];
trace(word_map, depth, backptr[label], backptr, schreier);
}
}
/* find word in defining permutations which maps orbit representative to label;
store each component of the word of length word_length in array word */
staticchar *find_word(int *word_length,
Logical soluble_group, int **perms, int rep, int non_standard, int orbit_length, int *b, char *c, struct pga_vars *pga)
{ int perm_number; char *word_map; char *word_perm; int i, l; char *d; char temp;
/* we store word which maps non-standard label to orbit representative; in image_of_generator, the word is evaluated starting from the
last letter -- hence after computing the word, we reverse it */
if (soluble_group) {
d = find_permutation(b, c, pga);
l = non_standard; while (l != rep) {
word_map[++*word_length] = d[l]; if ((perm_number = pga->map[(int)d[l]]) != 0)
l = inverse_image(l, perms[perm_number], pga);
} /* reverse word */ for (i = 1; i <= *word_length / 2; ++i) {
temp = word_map[i];
word_map[i] = word_map[*word_length - i + 1];
word_map[*word_length - i + 1] = temp;
}
free_char_vector(d, 1);
} else {
word_perm = allocate_char_vector(orbit_length, 1, FALSE);
trace(word_perm, word_length, non_standard, b, c); for (i = 1; i <= *word_length; ++i)
word_map[i] = preimage(word_perm[*word_length - i + 1], pga);
free_char_vector(word_perm, 1);
}
return word_map;
}
/* compute the automorphism which maps the non-standard subgroup, non_standard, to the orbit representative, rep; the word and
its length are supplied as word_map and word_length */
staticint **standard_map(char *word_map, int word_length,
Logical *identity_map, int rep, int ***auts, struct pga_vars *pga, struct pcp_vars *pcp)
{ registerint *y = y_address;
int nmr_of_generators = y[pcp->clend + pcp->cc - 1] + pga->s; registerint pointer = pcp->lused + 1; int cp = pcp->lused; int **standard; int i, j;
/* copy the word into y */ for (i = 1; i <= word_length; ++i)
y[pointer + i] = word_map[i];
free_char_vector(word_map, 1);
y[pointer] = word_length;
#ifdefined(DEBUG)
printf("The word is ");
print_array(y, pointer, pointer + word_length + 1); #endif
pcp->lused += word_length + 1;
cp = pcp->lused;
map_array_size = pcp->lastg;
standard = allocate_matrix(pcp->lastg, nmr_of_generators, 1, FALSE);
if (word_length == 0) { for (i = 1; i <= pga->ndgen; ++i) for (j = 1; j <= nmr_of_generators; ++j)
standard[i][j] = (i == j) ? 1 : 0;
*identity_map = TRUE;
} else { for (i = 1; i <= pga->ndgen; ++i) { /* compute image of defining generator i under standard map */
image_of_generator(i, pointer, auts, pga, pcp);
/* copy restriction of result into standard array */ for (j = 1; j <= nmr_of_generators; ++j) {
standard[i][j] = y[cp + j];
}
}
*identity_map = FALSE;
}
y[pointer] = 0;
if (!pga->final_stage)
list_subgroup(rep, pga, pcp);
return standard;
}
/* find the image of l under the inverse of the supplied permutation */
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.