CoCalc -- consistency

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
Project: cocalc-sagemath-dev-slelievre
Path: gap4r8 / pkg / anupq-3.2 / src / consistency_filter.c
Views: ⁴¹⁸³⁴⁶
1
/****************************************************************************
2
**
3
*A  consistency_filter.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

14
#if defined(CONSISTENCY_FILTER)
15

16
int *add_weights();
17

18

19
/* process those consistency relations of weight wc not already used;
20
   the value of type determines the consistency relations processed;
21
   if type = 0 then all relations are processed */
22

23
void consistency(
24
    int type, int *queue, int *queue_length, int wc, struct pcp_vars *pcp)
25
{
26
   register int *y = y_address;
27

28
   register int a;
29
   register int b;
30
   register int c;
31
   int **definition;
32
   int *copy_vector;
33
   int processed, filtered;
34

35
   register int wta; /* weight of a */
36

37
   register int a_start; /* start of range for a */
38
   register int a_end;   /* end of range for a */
39
   register int b_start;
40
   register int b_end;
41
   register int c_start;
42
   register int c_end;
43

44
   register int jacobi_wt = wc;
45
   register int bound = jacobi_wt >> 1;
46
   register int constant;
47
   register int offset;
48
   register int entry;
49
   register int p1;
50

51
   register int class_end = pcp->clend;
52
   register int p_pcomm = pcp->ppcomm;
53
   register int p_power = pcp->ppower;
54
   register int structure = pcp->structure;
55

56
   register Logical metabelian = pcp->metabelian;
57
   register Logical compute; /* is it necessary to compute jacobi? */
58
   register filter = (pcp->nocset);
59
   Logical can_filter;
60

61
   int moccur = pcp->ndgen + pcp->dgen;
62
   int frattini_rank = y[pcp->clend + 1];
63
   int l;
64
   int *weight_vector;
65

66
#include "access.h"
67

68
   processed = 0;
69
   filtered = 0;
70

71
   if (filter) {
72
      definition = allocate_matrix(pcp->lastg, frattini_rank + 1, 0, TRUE);
73
   }
74

75
   /* process the consistency equations (a^p) a = a (a^p)
76
      where 2 * WT(a) + 1 = jacobi_wt */
77

78
   if (type == 0 || type == 1) {
79
      if (MOD(jacobi_wt, 2) != 0) {
80

81
         /* find range of a */
82
         offset = class_end + bound - 1;
83
         a_start = y[offset] + 1;
84
         a_end = y[++offset];
85

86
         for (a = a_start; a <= a_end; a++) {
87
            compute =
88
                (!metabelian || (metabelian && (PART2(y[structure + a]) == 0 ||
89
                                                PART3(y[structure + a]) == 0)));
90
            if (compute) {
91
               jacobi(a, a, a, 0, pcp);
92
               if (pcp->redgen != 0 && pcp->m != 0)
93
                  queue[++*queue_length] = pcp->redgen;
94
            }
95
            if (pcp->overflow || (pcp->complete != 0 && !pcp->multiplicator))
96
               return;
97
         }
98
      }
99
   }
100

101
   /* process the consistency equations
102
      (b^p) a = b^(p - 1) (ba) and b (a^p) = (ba) a^(p - 1)
103
      where b > a and WT(b) + WT(a) + 1 = jacobi_wt */
104

105
   if (type == 0 || type == 2) {
106
      for (wta = 1; wta <= bound; ++wta) {
107

108
         /* find range of a */
109
         offset = class_end + wta - 1;
110
         a_start = y[offset] + 1;
111
         a_end = y[++offset];
112

113
         /* find maximum value of b */
114
         offset = class_end + jacobi_wt - wta - 2;
115
         b_end = y[offset + 1];
116

117
         for (a = a_start; a <= a_end; ++a) {
118

119
            /* ensure b > a */
120
            b_start = MAX(y[offset] + 1, a + 1);
121
            for (b = b_start; b <= b_end; ++b) {
122

123
               /* introduce Vaughan-Lee consistency check restriction */
124
               if (wta == 1) {
125
                  /* check if this jacobi relation has already been used
126
                     in filling in the tail on (b, a)^p */
127
                  p1 = y[p_pcomm + b];
128
                  if (y[p1 + a] <= 0 || y[p1 + a] >= pcp->first_pseudo) {
129
                     compute = (!metabelian ||
130
                                (metabelian && (PART2(y[structure + b]) == 0 ||
131
                                                PART3(y[structure + b]) == 0)));
132
                     if (compute) {
133
                        jacobi(b, b, a, 0, pcp);
134
                        if (pcp->redgen != 0 && pcp->m != 0)
135
                           queue[++*queue_length] = pcp->redgen;
136
                     }
137
                     if (pcp->overflow || pcp->complete && !pcp->multiplicator)
138
                        return;
139
                  }
140
               }
141

142
               /* check if this jacobi relation has already been
143
                  used in filling in the tail on (b, a^p) */
144
               entry = y[p_power + a];
145
               if (entry <= 0 || entry >= b) {
146
                  compute = (!metabelian ||
147
                             (metabelian && (PART2(y[structure + a]) == 0 ||
148
                                             PART3(y[structure + a]) == 0 ||
149
                                             PART2(y[structure + b]) == 0 ||
150
                                             PART3(y[structure + b]) == 0)));
151
                  if (compute) {
152
                     jacobi(b, a, a, 0, pcp);
153
                     if (pcp->redgen != 0 && pcp->m != 0)
154
                        queue[++*queue_length] = pcp->redgen;
155
                  }
156
                  if (pcp->overflow ||
157
                      (pcp->complete != 0 && !pcp->multiplicator))
158
                     return;
159
               }
160
            }
161
         }
162
      }
163
   }
164

165
   /* process the consistency equations (cb) a = c (ba), where
166
      c > b > a, WT(a) + WT(b) + WT(c) = jacobi_wt, and WT(a) = 1 */
167

168
   if (type == 0 || type == 3) {
169

170
      /* first, find maximum values of a and b */
171
      a_end = y[class_end + 1];
172
      b_end = y[class_end + ((jacobi_wt - 1) >> 1)];
173
      constant = class_end + jacobi_wt - 2;
174

175
      for (a = 1; a <= a_end; ++a) {
176
         if (filter) {
177
            if (definition[a][0] == FALSE) {
178
               lookup_structure(a, definition[a], pcp);
179
               definition[a][0] = TRUE;
180
            }
181
         }
182

183
         for (b = a + 1; b <= b_end; ++b) {
184

185
            if (filter) {
186
               if (definition[b][0] == FALSE) {
187
                  lookup_structure(b, definition[b], pcp);
188
                  definition[b][0] = TRUE;
189
               }
190
            }
191

192
            /* find range of c and ensure c > b */
193
            offset = constant - WT(y[structure + b]);
194
            c_start = MAX(y[offset] + 1, b + 1);
195
            c_end = y[++offset];
196

197
            /* where possible, avoid redoing those jacobis used to
198
               fill in tails on (c, (b, a)) */
199
            if (!metabelian) {
200
               p1 = y[p_pcomm + b];
201
               if (y[p1 + a] > 0)
202
                  c_end = MIN(c_end, y[p1 + a]);
203
            }
204

205
            for (c = c_start; c <= c_end; ++c) {
206
               can_filter = FALSE;
207
               if (filter) {
208
                  if (definition[c][0] == FALSE) {
209
                     lookup_structure(c, definition[c], pcp);
210
                     definition[c][0] = TRUE;
211
                  }
212
                  weight_vector = add_weights(
213
                      definition[a], definition[b], y[pcp->clend + 1]);
214
                  weight_vector = add_weights(
215
                      weight_vector, definition[c], y[pcp->clend + 1]);
216
                  for (l = 1; l <= frattini_rank && !can_filter; ++l)
217
                     can_filter = (weight_vector[l] > y[moccur + l]);
218
               }
219
               if (can_filter)
220
                  ++filtered;
221

222
               compute = (!metabelian ||
223
                          (metabelian && (PART2(y[structure + b]) == 0 ||
224
                                          PART3(y[structure + b]) == 0 ||
225
                                          PART2(y[structure + c]) == 0 ||
226
                                          PART3(y[structure + c]) == 0)));
227

228
               /* only evaluate if we must */
229
               if (compute && can_filter == FALSE) {
230
                  ++processed;
231
                  jacobi(c, b, a, 0, pcp);
232
                  if (pcp->redgen != 0 && pcp->m != 0)
233
                     queue[++*queue_length] = pcp->redgen;
234
               }
235
               if (pcp->overflow || (pcp->complete != 0 && !pcp->multiplicator))
236
                  return;
237
            }
238
         }
239
      }
240
   }
241

242
   if (filter) {
243
      printf(
244
          "Number evaluated = %d, Number filtered = %d\n", processed, filtered);
245
      free_matrix(definition, pcp->lastg, 0);
246
   }
247
}
248

249
#endif
250

251
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

Product

Resources

Company

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more, all in one place.

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
