1 /****************************************************************************
2 **
3 *A tails_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 "constants.h"
13 #include "pq_functions.h"
14
15 #if defined(TAILS_FILTER) && defined(GROUP)
16
17 /* look up the definitions of two pcp generator */
18
lookup_structure(int generator,int * weight_vector,struct pcp_vars * pcp)19 int lookup_structure(int generator, int *weight_vector, struct pcp_vars *pcp)
20 {
21 register int *y = y_address;
22
23 int structure = pcp->structure;
24 int pointer = pcp->lused + 1;
25 int weight;
26 int index;
27 int i;
28
29 #include "access.h"
30
31 weight = WT(y[structure + generator]);
32 for (i = 1; i <= weight; ++i)
33 y[pointer + i] = 0;
34
35 find_definition(generator, pointer, weight, pcp);
36
37 for (i = 1; i <= weight; ++i) {
38 index = y[pointer + i];
39 ++weight_vector[index];
40 }
41 }
42
43 /* add vec1 to vec2 component wise and return sum */
44
add_weights(int * vec1,int * vec2,int length)45 int *add_weights(int *vec1, int *vec2, int length)
46 {
47 int i;
48 int *sum;
49
50 sum = allocate_vector(length, 1, TRUE);
51 for (i = 1; i <= length; ++i)
52 sum[i] = vec1[i] + vec2[i];
53
54 return sum;
55 }
56
57 /* where maximal occurrence for each generator is set to 1,
58 does any generator occur in definition with weight at least 2?
59 if so, we do not need to compute tail */
60
mo_filter(int * weight_vector,struct pcp_vars * pcp)61 Logical mo_filter(int *weight_vector, struct pcp_vars *pcp)
62 {
63 register int *y = y_address;
64
65 Logical filter;
66 int frattini_rank = y[pcp->clend + 1];
67 int moccur = pcp->ndgen + pcp->dgen;
68
69 int i;
70
71 #ifdef DEBUG
72 printf("Definition array total is ");
73 print_array(weight_vector, 1, y[pcp->clend + 1] + 1);
74 #endif
75
76 /* is maximal occurrences option set to one for each generator? */
77 for (i = moccur + 1; i <= moccur + frattini_rank; ++i)
78 if (y[i] != 1)
79 return FALSE;
80
81 filter = FALSE;
82 /* does any defining generator occur at least 2 times? */
83 for (i = 1; i <= frattini_rank && !filter; ++i)
84 filter = (weight_vector[i] >= 2);
85
86 return filter;
87 }
88
89 Logical
exp4_filter(int left,int right,int * weight_vector,struct pcp_vars * pcp)90 exp4_filter(int left, int right, int *weight_vector, struct pcp_vars *pcp)
91 {
92 register int *y = y_address;
93
94 Logical filter;
95 int frattini_rank = y[pcp->clend + 1];
96 int structure = pcp->structure;
97 int i;
98
99 #include "access.h"
100
101 #ifdef DEBUG
102 printf("Definition array total is ");
103 print_array(weight_vector, 1, y[pcp->clend + 1] + 1);
104 #endif
105
106 filter = (WT(y[structure + left]) + WT(y[structure + right]) != 5);
107 if (filter == FALSE)
108 return FALSE;
109
110 filter = FALSE;
111 /* does any defining generator occur at least 4 times? */
112 for (i = 1; i <= frattini_rank && !filter; ++i)
113 filter = (weight_vector[i] >= 4);
114
115 return filter;
116 }
117
exp5_filter(int * weight_vector,struct pcp_vars * pcp)118 Logical exp5_filter(int *weight_vector, struct pcp_vars *pcp)
119 {
120 register int *y = y_address;
121
122 int frattini_rank = y[pcp->clend + 1];
123 Logical filter;
124 int i;
125
126 #ifdef DEBUG
127 printf("Definition array total is ");
128 print_array(weight_vector, 1, y[pcp->clend + 1] + 1);
129 #endif
130
131 filter = FALSE;
132 /* does any defining generator occur at least 7 times? */
133 for (i = 1; i <= frattini_rank && !filter; ++i)
134 filter = (weight_vector[i] >= 7);
135
136 return filter;
137 }
138
139 /* calculate pth powers of class final_class generators which
140 are commutators by doing the appropriate collections */
141
calculate_tails(int final_class,int start_weight,int end_weight,struct pcp_vars * pcp)142 void calculate_tails(int final_class,
143 int start_weight,
144 int end_weight,
145 struct pcp_vars *pcp)
146 {
147 register int *y = y_address;
148
149 register int structure = pcp->structure;
150 register int class_end = pcp->clend;
151
152 register int f;
153 register int start = y[class_end + final_class - 1] + 1;
154 register int end = y[class_end + final_class];
155
156 register int s, s1, s2;
157 register int start_class = 1;
158
159 register int a, b;
160 register int value;
161 register int p1;
162 int **definition;
163
164 int exponent = pcp->extra_relations;
165 Logical filter = (pcp->nocset || exponent == 4 || exponent == 5);
166 Logical compute;
167 int *weight_vector;
168 int frattini_rank = y[pcp->clend + 1];
169 int processed, filtered;
170
171 #include "access.h"
172
173 if (filter)
174 definition = allocate_matrix(pcp->lastg, frattini_rank + 1, 0, TRUE);
175
176 if (filter || pcp->fullop || pcp->diagn)
177 printf("Processing tails for generators of weight %d and %d\n",
178 final_class,
179 1);
180
181 for (f = start; f <= end; f++) {
182 #ifdef DEBUG
183 printf("Processing generator f = %d, Lused = %d\n", f, pcp->lused);
184 #endif
185 value = y[structure + f];
186 a = PART3(value);
187 if (a == 0)
188 break;
189 b = PART2(value);
190
191 /* f is the commutator (b, a);
192 calculate the class current_class part of f^p by collecting
193 (b^p) a = b^(p-1) (ba); by formal collection, we see that
194 the class current_class part of f^p is obtained by subtracting
195 (modulo p) the rhs of the above equation from the lhs */
196
197 jacobi(b, b, a, pcp->ppower + f, pcp);
198 if (pcp->overflow)
199 return;
200 }
201
202
203 /* calculate the non left-normed commutators of class work_class
204 in the order (work_class - 2, 2), (work_class - 3, 3) .. */
205
206 class_end = pcp->clend;
207 while (--final_class >= ++start_class) {
208
209 processed = 0;
210 filtered = 0;
211
212 if (filter || pcp->fullop || pcp->diagn)
213 printf("Processing tails for generators of weight %d and %d\n",
214 final_class,
215 start_class);
216
217 start = y[class_end + final_class - 1] + 1;
218 end = y[class_end + final_class];
219 s1 = y[class_end + start_class - 1] + 1;
220
221 for (f = start; f <= end; f++) {
222 #ifdef DEBUG
223 printf("Processing generator f = %d, Lused = %d\n", f, pcp->lused);
224 #endif
225
226 if (filter) {
227 if (definition[f][0] == FALSE) {
228 lookup_structure(f, definition[f], pcp);
229 definition[f][0] = TRUE;
230 }
231 }
232
233 s2 = MIN(f - 1, y[class_end + start_class]);
234 if (s2 - s1 < 0)
235 continue;
236 p1 = y[pcp->ppcomm + f];
237 for (s = s1; s <= s2; s++) {
238 /* insert the class current_class part on (f, s) */
239 value = y[structure + s];
240 b = PART2(value);
241 a = PART3(value);
242 if (a == 0)
243 a = b;
244 else if (pcp->metabelian && PART3(y[structure + f]) != 0)
245 continue;
246
247 /* s = (b, a); calculate the class current_class part
248 of (f, (b, a)) by collecting (fb) a = f (ba) or the
249 class current_class part of (f, (b^p)) by collecting
250 (fb) b^(p - 1) = f (b^p);
251 since we require only the class current_class part -
252 the rest has been computed earlier - we calculate it
253 by subtracting (modulo p) the rhs of the above equation
254 from the lhs (proof by formal collection) */
255 if (filter) {
256 if (definition[s][0] == FALSE) {
257 lookup_structure(s, definition[s], pcp);
258 definition[s][0] = TRUE;
259 }
260 weight_vector =
261 add_weights(definition[f], definition[s], y[pcp->clend + 1]);
262 free_vector(weight_vector, 1);
263 if (pcp->nocset)
264 compute = (mo_filter(weight_vector, pcp) == FALSE);
265 else if (exponent == 4)
266 compute = (exp4_filter(f, s, weight_vector, pcp) == FALSE);
267 else if (exponent == 5)
268 compute = (exp5_filter(weight_vector, pcp) == FALSE);
269 else
270 compute = TRUE;
271
272 if (compute) {
273 jacobi(f, b, a, p1 + s, pcp);
274 ++processed;
275 } else
276 ++filtered;
277 } else
278 jacobi(f, b, a, p1 + s, pcp);
279 if (pcp->overflow)
280 return;
281 }
282 }
283 if (filter) {
284 printf("Number evaluated = %d, Number filtered = %d\n",
285 processed,
286 filtered);
287 }
288 }
289
290 if (filter)
291 free_matrix(definition, pcp->lastg, 0);
292 }
293
294 #endif
295