1 /*****************************************************************************
2 **
3 ** eliminate.c NQ Werner Nickel
4 ** nickel@mathematik.tu-darmstadt.de
5 */
6
7
8 #include <assert.h>
9
10 #include "nq.h"
11 #include "glimt.h"
12 #include "relations.h" /* for ElimAllEpim */
13
appendExpVector(gen k,expvec ev,word w,gen * renumber)14 long appendExpVector(gen k, expvec ev, word w, gen *renumber) {
15 long l = 0;
16
17 /* Copy the negative of the exponent vector ev[] into w. */
18 for (; k <= NrCenGens; k++) {
19 if (ev[k] > (expo)0) {
20 if (Exponent[renumber[k]] != (expo)0)
21 printf("Warning: Positive entry in matrix.");
22 else {
23 w[l].g = -renumber[k];
24 w[l].e = ev[k];
25 }
26 } else if (ev[k] < (expo)0) {
27 w[l].g = renumber[k];
28 w[l].e = -ev[k];
29 } else
30 continue;
31 if (Exponent[abs(w[l].g)] != (expo)0) {
32 if (w[l].g < 0)
33 printf("Negative exponent for torsion generator.\n");
34 if (w[l].e >= Exponent[w[l].g])
35 printf("Unreduced exponent for torsion generators.\n");
36 }
37 l++;
38 }
39 w[l].g = EOW;
40 w[l].e = (expo)0;
41 l++;
42 return l;
43 }
44
elimRHS(word v,long * eRow,gen * renumber,expvec ev,expvec * M)45 static word elimRHS(word v, long *eRow, gen *renumber, expvec ev, expvec *M) {
46 word w;
47 gen cg;
48 long j, k, l;
49 expo s;
50
51 w = (word)malloc((NrPcGens + NrCenGens + 1) * sizeof(gpower));
52 if (w == (word)0) {
53 perror("elimRHS(), w");
54 exit(2);
55 }
56
57 /* copy the first NrPcGens generators into w. */
58 l = 0;
59 while (v->g != EOW && abs(v->g) <= NrPcGens) { w[l] = *v++; l++; }
60
61 /* copy the eliminating rows into ev[]. */
62 while (v->g != EOW) {
63 cg = abs(v->g) - NrPcGens;
64 if (cg <= 0)
65 printf("Warning : non-central generator in elimRHS()\n");
66 if (eRow[ cg ] == -1 || M[eRow[cg]][cg] != (expo)1)
67 /* generator cg survives. */
68 ev[ cg ] += sgn(v->g) * v->e;
69 else
70 for (k = cg + 1; k <= NrCenGens; k++)
71 ev[k] -= sgn(v->g) * v->e * M[eRow[cg]][k];
72 v++;
73 }
74 /* Reduce all entries modulo the exponents. */
75 for (k = 1; k <= NrCenGens; k++)
76 if (renumber[k] > 0 && Exponent[renumber[k]] > (expo)0)
77 if ((s = ev[k] / Exponent[renumber[k]]) != (expo)0
78 || ev[k] < (expo)0) {
79 if (ev[k] - s * M[eRow[k]][k] < (expo)0) s--;
80 for (j = k; j <= NrCenGens; j++)
81 ev[j] -= s * M[eRow[k]][j];
82 }
83 /* Now copy the exponent vector back into the word. */
84 for (k = 1; k <= NrCenGens; k++) {
85 if (ev[k] > (expo)0) {
86 w[l].g = renumber[k];
87 w[l].e = ev[k];
88 } else if (ev[k] < (expo)0) {
89 w[l].g = -renumber[k];
90 w[l].e = -ev[k];
91 } else continue;
92 if (Exponent[abs(w[l].g)] != (expo)0) {
93 if (w[l].g < 0)
94 printf("Negative exponent for torsion generator.\n");
95 if (w[l].e >= Exponent[w[l].g])
96 printf("Unreduced exponent for torsion generators.\n");
97 }
98 l++;
99 }
100 w[l].g = EOW;
101 w[l].e = (expo)0;
102 l++;
103
104 for (k = 1; k <= NrCenGens; k++) ev[k] = (expo)0;
105
106 return (word)realloc(w, l * sizeof(gpower));
107 }
108
ElimGenerators(void)109 void ElimGenerators(void) {
110
111 long i, j, k, l, n = 0, *eRow, t = 0;
112 expvec ev, *M = 0;
113 gen *renumber;
114 word v, w;
115
116 if (Verbose) t = RunTime();
117
118 M = MatrixToExpVecs();
119
120 /* first assign a new number to each central generator which is
121 not to be eliminated. */
122 renumber = (gen*) calloc(NrCenGens + 1, sizeof(gen));
123 if (renumber == (gen*)0) {
124 perror("elimGenerators(), renumber");
125 exit(2);
126 }
127 for (k = 1, i = 0; k <= NrCenGens; k++)
128 if (i >= NrRows || k != Heads[i])
129 renumber[ k ] = NrPcGens + k - n;
130 else if (M[i][k] != 1) { /* k will become a torsion element */
131 renumber[ k ] = NrPcGens + k - n;
132 Exponent[ renumber[k] ] = M[i][k];
133 i++;
134 } else { /* k will be eliminated. */
135 n++;
136 i++;
137 }
138
139 /* extend the memory for Power[], note that n is the number of
140 generators to be eliminated. */
141 Power = (word*)realloc(Power, (NrPcGens + NrCenGens + 1 - n) * sizeof(word));
142 if (Power == (word*)0) {
143 perror("elimGenerators(), Power");
144 exit(2);
145 }
146
147 /* extend the memory for Definition[]. */
148 Definition =
149 (def*)realloc(Definition, (NrPcGens + NrCenGens + 1 - n) * sizeof(def));
150 if (Definition == (def*)0) {
151 perror("elimGenerators(), Definition");
152 exit(2);
153 }
154
155 /* first we eliminate ALL central generators that occur in the
156 ** epimorphism. */
157 i = ElimAllEpim(n, M, renumber);
158
159 /* secondly we eliminate ALL generators from right hand sides of
160 ** power relations. */
161 for (j = 1; j <= NrPcGens; j++)
162 if (Exponent[j] != (expo)0) {
163 l = WordLength(Power[ j ]);
164 w = (word)malloc((l + NrCenGens + 1 - n) * sizeof(gpower));
165 WordCopy(Power[ j ], w);
166 l--;
167 l += appendExpVector(w[l].g + 1 - NrPcGens, M[i], w + l, renumber);
168
169 if (Power[j] != (word)0) free(Power[j]);
170 if (l == 1) {
171 Power[j] = (word)0;
172 free(w);
173 } else
174 Power[j] = (word)realloc(w, l * sizeof(gpower));
175 i++;
176 }
177
178 /* Thirdly we eliminate the generators from the right hand
179 ** side of conjugates, but before that we fix the definitions
180 ** of surviving generators. */
181
182 /* set up an array that specifies the row which eliminates a
183 ** generator. */
184 eRow = (long*)malloc((NrCenGens + 1) * sizeof(long));
185 if (eRow == (long*)0) {
186 perror("elimGenerators(), eRow");
187 exit(2);
188 }
189 for (k = 0; k <= NrCenGens; k++) eRow[ k ] = -1;
190 for (k = 0; k < NrRows; k++) eRow[ Heads[k] ] = k;
191
192
193 ev = (expvec)calloc((NrCenGens + 1), sizeof(expo));
194 if (ev == (expvec)0) {
195 perror("elimGenerators(), ev");
196 exit(2);
197 }
198 for (j = 1; j <= NrPcGens; j++)
199 for (i = 1; i < j; i++) {
200 if (Wt(j) + Wt(i) > Class + 1) continue;
201
202 k = Conjugate[j][i][1].g - NrPcGens;
203 if (k > 0 &&
204 i <= Dimension[1] && j > NrPcGens - Dimension[Class] &&
205 (eRow[ k ] == -1 || M[eRow[k]][k] != (expo)1)) {
206 /* Fix the definitions of surviving generators and
207 ** their power relations. */
208 Conjugate[j][i][1].g = renumber[k];
209 Definition[ renumber[k] ].h = j;
210 Definition[ renumber[k] ].g = i;
211 if (eRow[ k ] != -1) {
212 w = (word)malloc((NrCenGens + 1 - n) * sizeof(gpower));
213 if (w == (word)0) {
214 perror("elimGenerators(), w");
215 exit(2);
216 }
217 l = appendExpVector(k + 1, M[eRow[k]], w, renumber);
218 w = (word)realloc(w, l * sizeof(gpower));
219 Power[ renumber[k] ] = w;
220 }
221 } else {
222 v = elimRHS(Conjugate[j][i], eRow, renumber, ev, M);
223 if (Conjugate[j][i] != Generators[j])
224 free(Conjugate[j][i]);
225 Conjugate[j][i] = v;
226 }
227
228 if (Exponent[i] == (expo)0) {
229 v = elimRHS(Conjugate[j][-i], eRow, renumber, ev, M);
230 if (Conjugate[j][-i] != Generators[j])
231 free(Conjugate[j][-i]);
232 Conjugate[j][-i] = v;
233 }
234 if (Exponent[j] == (expo)0) {
235 v = elimRHS(Conjugate[-j][i], eRow, renumber, ev, M);
236 if (Conjugate[-j][i] != Generators[-j])
237 free(Conjugate[-j][i]);
238 Conjugate[-j][i] = v;
239 }
240 if (Exponent[j] + Exponent[i] == (expo)0) {
241 v = elimRHS(Conjugate[-j][-i], eRow, renumber, ev, M);
242 if (Conjugate[-j][-i] != Generators[-j])
243 free(Conjugate[-j][-i]);
244 Conjugate[-j][-i] = v;
245 }
246 }
247
248 /* Now adjust the sizes of the arrays */
249 assert(Commute == CommuteList[ Class + 1 ]);
250 Commute = (gen*)realloc(Commute,
251 (NrPcGens + NrCenGens + 1 - n) * sizeof(gen));
252 CommuteList[ Class + 1 ] = Commute;
253 Exponent = (expo*)realloc(Exponent,
254 (NrPcGens + NrCenGens + 1 - n) * sizeof(expo));
255
256 free(renumber);
257 free(ev);
258 free(eRow);
259
260 if (M != (expvec*)0) freeExpVecs(M);
261 NrCenGens -= n;
262
263 if (Verbose)
264 printf("# Eliminated generators (%ld msec).\n", RunTime() - t);
265 }
266