1 | /*****************************************************************************\ |
---|
2 | * Computer Algebra System SINGULAR |
---|
3 | \*****************************************************************************/ |
---|
4 | /** @file cfCharSets.cc |
---|
5 | * |
---|
6 | * This file provides functions to compute characteristic sets |
---|
7 | * |
---|
8 | * ABSTRACT: Descriptions can be found in Wang "On the Parallelization of |
---|
9 | * characteristic-set based algorithms" or Greuel/Pfister "A Singular |
---|
10 | * Introduction to Commutative Algebra". |
---|
11 | * |
---|
12 | * @authors Martin Lee, Michael Messollen |
---|
13 | * |
---|
14 | **/ |
---|
15 | /*****************************************************************************/ |
---|
16 | |
---|
17 | #include "timing.h" |
---|
18 | |
---|
19 | #include "cfCharSets.h" |
---|
20 | #include "canonicalform.h" |
---|
21 | #include "cf_algorithm.h" |
---|
22 | #include "facAlgFunc.h" |
---|
23 | |
---|
24 | TIMING_DEFINE_PRINT(neworder_time) |
---|
25 | |
---|
26 | #define __ARRAY_INIT__ -1 |
---|
27 | |
---|
28 | // the maximal degree of polys in PS wrt. variable x |
---|
29 | static int |
---|
30 | degpsmax (const CFList & PS, const Variable & x, |
---|
31 | Intarray & A, Intarray & C) |
---|
32 | { |
---|
33 | int varlevel= level(x); |
---|
34 | if (A[varlevel] != __ARRAY_INIT__) |
---|
35 | return A[varlevel]; |
---|
36 | int max= 0, temp, count= 0; |
---|
37 | |
---|
38 | for (CFListIterator i= PS; i.hasItem(); i++) |
---|
39 | { |
---|
40 | temp= degree (i.getItem(), x); |
---|
41 | if (temp > max) |
---|
42 | { |
---|
43 | max= temp; |
---|
44 | count = 0; |
---|
45 | } |
---|
46 | if (temp == max) |
---|
47 | count += max; // we count the number of polys |
---|
48 | } |
---|
49 | A[varlevel]= max; |
---|
50 | C[varlevel]= count; |
---|
51 | return max; |
---|
52 | } |
---|
53 | |
---|
54 | // the minimal non-zero degree of polys in PS wrt. x |
---|
55 | // returns 0 if variable x doesn't occure in any of the polys |
---|
56 | static int |
---|
57 | degpsmin (const CFList & PS, const Variable & x, Intarray & A, Intarray & B, |
---|
58 | Intarray & C, Intarray & D) |
---|
59 | { |
---|
60 | int varlevel= level(x); |
---|
61 | if (B[varlevel] != __ARRAY_INIT__ ) |
---|
62 | return B[varlevel]; |
---|
63 | int min= degpsmax (PS, x, A, C), temp, count= 0; |
---|
64 | |
---|
65 | if (min == 0) |
---|
66 | { |
---|
67 | B[varlevel]= min; |
---|
68 | D[varlevel]= min; |
---|
69 | return min; |
---|
70 | } |
---|
71 | else |
---|
72 | { |
---|
73 | for (CFListIterator i= PS; i.hasItem(); i++) |
---|
74 | { |
---|
75 | temp= degree (i.getItem(), x); |
---|
76 | if (temp < min && temp != 0) |
---|
77 | { |
---|
78 | min= temp; |
---|
79 | count= 0; |
---|
80 | } |
---|
81 | if (temp == min) |
---|
82 | count += min; // we count the number of polys |
---|
83 | } |
---|
84 | } |
---|
85 | B[varlevel]= min; |
---|
86 | D[varlevel]= count; |
---|
87 | return min; |
---|
88 | } |
---|
89 | |
---|
90 | // the minimal total degree of lcoeffs of polys in PS wrt. x |
---|
91 | // for those polys having degree degpsmin in x. |
---|
92 | // F will be assigned the minimal number of terms of those lcoeffs |
---|
93 | static int |
---|
94 | Tdeg (const CFList & PS, const Variable & x, Intarray & A, Intarray & B, |
---|
95 | Intarray & C, Intarray & D, Intarray & E, Intarray & F) |
---|
96 | { |
---|
97 | int k= degpsmin (PS, x, A, B, C, D), varlevel= level(x), min= 0; |
---|
98 | |
---|
99 | if (E[varlevel] != __ARRAY_INIT__) |
---|
100 | return E [varlevel]; |
---|
101 | if (k == 0) |
---|
102 | { |
---|
103 | E[varlevel]= 0; |
---|
104 | F[varlevel]= 0; |
---|
105 | } |
---|
106 | else |
---|
107 | { |
---|
108 | int nopslc= 0; |
---|
109 | CFList LCdegList; |
---|
110 | CanonicalForm elem; |
---|
111 | CFListIterator i; |
---|
112 | |
---|
113 | for (i= PS; i.hasItem(); i++) |
---|
114 | { |
---|
115 | elem= i.getItem(); |
---|
116 | if (degree (elem, x) == k) |
---|
117 | LCdegList.append (LC (elem, x)); |
---|
118 | } |
---|
119 | |
---|
120 | if (LCdegList.length() > 0) |
---|
121 | { |
---|
122 | CFList TermList; |
---|
123 | int newmin, newnopslc; |
---|
124 | |
---|
125 | min= totaldegree (LCdegList.getFirst()); |
---|
126 | TermList= get_Terms (LCdegList.getFirst()); |
---|
127 | nopslc= TermList.length(); |
---|
128 | for (i= LCdegList; i.hasItem(); i++) |
---|
129 | { |
---|
130 | elem= i.getItem(); |
---|
131 | newmin= totaldegree(elem); |
---|
132 | TermList= get_Terms(elem); |
---|
133 | newnopslc= TermList.length(); |
---|
134 | if (newmin < min) |
---|
135 | min= newmin; |
---|
136 | if (newnopslc < nopslc) |
---|
137 | nopslc= newnopslc; |
---|
138 | } |
---|
139 | |
---|
140 | } |
---|
141 | E[varlevel]= min; |
---|
142 | F[varlevel]= nopslc; |
---|
143 | } |
---|
144 | return min; |
---|
145 | } |
---|
146 | |
---|
147 | // The number of the poly in which Variable x first occures |
---|
148 | static int |
---|
149 | nr_of_poly( const CFList & PS, const Variable & x, Intarray & G) |
---|
150 | { |
---|
151 | int min= 0, varlevel= level(x); |
---|
152 | if (G[varlevel] != __ARRAY_INIT__) |
---|
153 | return G[varlevel]; |
---|
154 | for (CFListIterator i= PS; i.hasItem(); i++) |
---|
155 | { |
---|
156 | min += 1; |
---|
157 | if (degree (i.getItem(), x) > 0) |
---|
158 | break; |
---|
159 | } |
---|
160 | G[varlevel]= min; |
---|
161 | return min; |
---|
162 | } |
---|
163 | |
---|
164 | static int |
---|
165 | degord (const Variable & x, const Variable & y, const CFList & PS, |
---|
166 | Intarray & A, Intarray & B, Intarray & C, Intarray & D, |
---|
167 | Intarray & E, Intarray & F, Intarray & G) |
---|
168 | { |
---|
169 | int xlevel= level(x), ylevel= level(y); |
---|
170 | |
---|
171 | if (degpsmax(PS,y,A,C) < degpsmax(PS,x,A,C)) return 1; |
---|
172 | else if (degpsmax(PS,x,A,C) < degpsmax(PS,y,A,C) ) return 0; |
---|
173 | else if (C[ylevel] < C[xlevel]) return 1; |
---|
174 | else if (C[xlevel] < C[ylevel]) return 0; |
---|
175 | else if (degpsmin(PS,x,A,B,C,D) < degpsmin(PS,y,A,B,C,D)) return 1; |
---|
176 | else if (degpsmin(PS,y,A,B,C,D) < degpsmin(PS,x,A,B,C,D)) return 0; |
---|
177 | else if (D[ylevel] < D[xlevel]) return 1; |
---|
178 | else if (D[xlevel] < D[ylevel]) return 0; |
---|
179 | else if (Tdeg(PS,y,A,B,C,D,E,F) < Tdeg(PS,x,A,B,C,D,E,F)) return 1; |
---|
180 | else if (Tdeg(PS,x,A,B,C,D,E,F) < Tdeg(PS,y,A,B,C,D,E,F)) return 0; |
---|
181 | else if (F[ylevel] < F[xlevel]) return 1; |
---|
182 | else if (F[xlevel] < F[ylevel]) return 0; |
---|
183 | else if (nr_of_poly(PS,x,G) <= nr_of_poly(PS,y,G)) return 1; |
---|
184 | else return 0; |
---|
185 | } |
---|
186 | |
---|
187 | // determine the highest variable of all involved Variables in PS |
---|
188 | // NOTE: |
---|
189 | // this doesn't give always the correct answer: |
---|
190 | // If a variable is assigned the highest level in the definition of the |
---|
191 | // original ring, but doesn't occure in any of the |
---|
192 | // polynomials, get_max_var returns the variable with a level lower than |
---|
193 | // the highest level. |
---|
194 | // Is there a workaround? |
---|
195 | // But for the redefinition of the ring this doesn't matter due to the |
---|
196 | // implementation of neworder(). |
---|
197 | |
---|
198 | static Variable |
---|
199 | get_max_var(const CFList & PS) |
---|
200 | { |
---|
201 | Variable x= PS.getFirst().mvar(), y; |
---|
202 | for (CFListIterator i= PS; i.hasItem(); i++) |
---|
203 | { |
---|
204 | y= i.getItem().mvar(); |
---|
205 | if (y > x) |
---|
206 | x= y; |
---|
207 | } |
---|
208 | return x; |
---|
209 | } |
---|
210 | |
---|
211 | |
---|
212 | // determine if variable x is in one and only one of the polynomials in PS |
---|
213 | // first criterion for neworder |
---|
214 | static CFList |
---|
215 | only_in_one (const CFList & PS, const Variable & x) |
---|
216 | { |
---|
217 | CFList output; |
---|
218 | |
---|
219 | for (CFListIterator i= PS; i.hasItem(); i++ ) |
---|
220 | { |
---|
221 | if (degree (i.getItem(), x) >= 1) |
---|
222 | output.insert (i.getItem()); |
---|
223 | if (output.length() >= 2) |
---|
224 | break; |
---|
225 | } |
---|
226 | return output; |
---|
227 | } |
---|
228 | |
---|
229 | // initialize all Arrays (of same range) with __ARRAY_INIT__ |
---|
230 | static void |
---|
231 | initArray (const int highest_level, Intarray & A, Intarray & B, Intarray & C, |
---|
232 | Intarray & D, Intarray & E, Intarray & F, Intarray & G) |
---|
233 | { |
---|
234 | for (int i=1 ; i <= highest_level; i ++) |
---|
235 | { |
---|
236 | A[i]= __ARRAY_INIT__; |
---|
237 | B[i]= __ARRAY_INIT__; |
---|
238 | C[i]= __ARRAY_INIT__; |
---|
239 | D[i]= __ARRAY_INIT__; |
---|
240 | E[i]= __ARRAY_INIT__; |
---|
241 | F[i]= __ARRAY_INIT__; |
---|
242 | G[i]= __ARRAY_INIT__; |
---|
243 | } |
---|
244 | } |
---|
245 | |
---|
246 | // now for the second criterion; a little more complex |
---|
247 | // |
---|
248 | // idea: set up seven arrays of lenth highest_level |
---|
249 | // (of which some entries may be empty, because of only_in_one!) |
---|
250 | // A saves maxdegree of Variable x in A(level(x)) |
---|
251 | // B saves mindegree of Variable x in B(level(x)) |
---|
252 | // C saves the number of polys in PS which have degree A(level(x)) in |
---|
253 | // D(level(x)) |
---|
254 | // D saves the number of polys in PS which have degree B(level(x)) in |
---|
255 | // D(level(x)) |
---|
256 | // E saves the minimal total degree of lcoeffs of polys wrt x in E(level(x)) |
---|
257 | // F saves the minimal number of terms of lcoeffs of E(level(x)) in F(~) |
---|
258 | // G saves nr of poly Variable x has first deg <> 0 |
---|
259 | |
---|
260 | #define __INIT_GAP__ 3 |
---|
261 | static Varlist |
---|
262 | reorderb (const Varlist & difference, const CFList & PS, |
---|
263 | const int highest_level) |
---|
264 | { |
---|
265 | Intarray A(1, highest_level), B(1, highest_level), C(1, highest_level), |
---|
266 | D(1, highest_level), E(1, highest_level), F(1, highest_level), |
---|
267 | G(1, highest_level); |
---|
268 | initArray (highest_level, A, B, C, D, E, F, G); |
---|
269 | int i= 0, j, n= difference.length(), gap= 1 + __INIT_GAP__; |
---|
270 | Variable temp; |
---|
271 | Array<Variable> v(0, n); |
---|
272 | VarlistIterator J; |
---|
273 | |
---|
274 | for (J= difference; J.hasItem(); J++ ) |
---|
275 | { |
---|
276 | v[i]= J.getItem(); |
---|
277 | i++; |
---|
278 | } |
---|
279 | |
---|
280 | while (gap <= n) |
---|
281 | gap = __INIT_GAP__ * gap + 1; |
---|
282 | gap /= __INIT_GAP__; |
---|
283 | |
---|
284 | while (gap > 0) |
---|
285 | { |
---|
286 | for (i= gap; i <= n - 1; i++) |
---|
287 | { |
---|
288 | temp= v[i]; |
---|
289 | for (j= i - gap; j >=0 ; j -= gap) |
---|
290 | { |
---|
291 | if (degord (v[j], temp, PS, A, B, C, D, E, F, G)) |
---|
292 | break; |
---|
293 | v[j + gap]= v[j]; |
---|
294 | } |
---|
295 | v[j + gap]= temp; |
---|
296 | } |
---|
297 | gap /= __INIT_GAP__; |
---|
298 | } |
---|
299 | Varlist output; |
---|
300 | for (i= 0; i <= n - 1; i++) |
---|
301 | output.append (v[i]); |
---|
302 | return output; |
---|
303 | } |
---|
304 | |
---|
305 | // set up a new orderd list of Variables. |
---|
306 | // we try to reorder the variables heuristically optimal. |
---|
307 | Varlist |
---|
308 | neworder( const CFList & PolyList ) |
---|
309 | { |
---|
310 | CFList PS= PolyList, PS1=PolyList; |
---|
311 | Varlist oldorder, reorder, difference; |
---|
312 | |
---|
313 | TIMING_START(neworder_time); |
---|
314 | |
---|
315 | int highest_level= level(get_max_var(PS)); |
---|
316 | |
---|
317 | // set up oldorder and first criterion: only_in_one |
---|
318 | for (int i= highest_level; i>=1; i--) |
---|
319 | { |
---|
320 | oldorder.insert (Variable(i)); |
---|
321 | CFList is_one= only_in_one (PS1, Variable(i)); |
---|
322 | if (is_one.length() == 1) |
---|
323 | { |
---|
324 | reorder.insert (Variable(i)); |
---|
325 | PS1= Difference (PS1, is_one); |
---|
326 | } |
---|
327 | else if (is_one.length() == 0) |
---|
328 | { |
---|
329 | reorder.append (Variable (i)); // assigne it the highest level |
---|
330 | PS1= Difference (PS1, is_one); |
---|
331 | } |
---|
332 | } |
---|
333 | difference= Difference (oldorder, reorder); |
---|
334 | |
---|
335 | // rearrange the ordering of the variables! |
---|
336 | difference= reorderb (difference, PS, highest_level); |
---|
337 | reorder= Union (reorder, difference); |
---|
338 | TIMING_END(neworder_time); |
---|
339 | |
---|
340 | TIMING_PRINT(neworder_time, "\ntime used for neworder : "); |
---|
341 | |
---|
342 | return Union (reorder, Difference (oldorder, reorder)); |
---|
343 | } |
---|
344 | |
---|
345 | // the same as above, only returning a list of CanonicalForms |
---|
346 | CFList |
---|
347 | newordercf(const CFList & PolyList ) |
---|
348 | { |
---|
349 | Varlist reorder= neworder (PolyList); |
---|
350 | CFList output; |
---|
351 | |
---|
352 | for (VarlistIterator i=reorder; i.hasItem(); i++) |
---|
353 | output.append (CanonicalForm (i.getItem())); |
---|
354 | |
---|
355 | return output; |
---|
356 | } |
---|
357 | |
---|
358 | // the same as above, only returning a list of ints |
---|
359 | IntList |
---|
360 | neworderint(const CFList & PolyList ) |
---|
361 | { |
---|
362 | Varlist reorder= neworder (PolyList); |
---|
363 | IntList output; |
---|
364 | |
---|
365 | for (VarlistIterator i= reorder; i.hasItem(); i++) |
---|
366 | output.append (level (i.getItem())); |
---|
367 | |
---|
368 | return output; |
---|
369 | } |
---|
370 | |
---|
371 | // swapvar a whole list of CanonicalForms |
---|
372 | static CFList |
---|
373 | swapvar( const CFList & PS, const Variable & x, const Variable & y) |
---|
374 | { |
---|
375 | CFList ps; |
---|
376 | |
---|
377 | for (CFListIterator i = PS; i.hasItem(); i++) |
---|
378 | ps.append (swapvar (i.getItem(), x, y)); |
---|
379 | return ps; |
---|
380 | } |
---|
381 | |
---|
382 | static CFFList |
---|
383 | swapvar( const CFFList & PS, const Variable & x, const Variable & y) |
---|
384 | { |
---|
385 | CFFList ps; |
---|
386 | |
---|
387 | for (CFFListIterator i= PS; i.hasItem(); i++) |
---|
388 | ps.append (CFFactor(swapvar (i.getItem().factor(), x, y), i.getItem().exp())); |
---|
389 | return ps; |
---|
390 | } |
---|
391 | |
---|
392 | // a library function: we reorganize the global variable ordering |
---|
393 | CFList |
---|
394 | reorder (const Varlist & betterorder, const CFList & PS) |
---|
395 | { |
---|
396 | int i= 1, n= betterorder.length(); |
---|
397 | Intarray v (1, n); |
---|
398 | CFList ps= PS; |
---|
399 | |
---|
400 | //initalize: |
---|
401 | for (VarlistIterator j= betterorder; j.hasItem(); j++) |
---|
402 | { |
---|
403 | v[i]= level (j.getItem()); |
---|
404 | i++; |
---|
405 | } |
---|
406 | // reorder: |
---|
407 | for (i= 1; i <= n; i++) |
---|
408 | ps= swapvar (ps, Variable (v[i]), Variable (n + i)); |
---|
409 | return ps; |
---|
410 | } |
---|
411 | |
---|
412 | CFFList |
---|
413 | reorder( const Varlist & betterorder, const CFFList & PS) |
---|
414 | { |
---|
415 | int i= 1, n= betterorder.length(); |
---|
416 | Intarray v (1, n); |
---|
417 | CFFList ps= PS; |
---|
418 | |
---|
419 | //initalize: |
---|
420 | for (VarlistIterator j= betterorder; j.hasItem(); j++) |
---|
421 | { |
---|
422 | v[i]= level (j.getItem()); |
---|
423 | i++; |
---|
424 | } |
---|
425 | |
---|
426 | // reorder: |
---|
427 | for (i= 1; i <= n; i++) |
---|
428 | ps= swapvar (ps, Variable (v[i]), Variable (n + i)); |
---|
429 | return ps; |
---|
430 | } |
---|
431 | |
---|
432 | ListCFList |
---|
433 | reorder (const Varlist & betterorder, const ListCFList & Q) |
---|
434 | { |
---|
435 | ListCFList Q1; |
---|
436 | |
---|
437 | for (ListCFListIterator i= Q; i.hasItem(); i++) |
---|
438 | Q1.append (reorder (betterorder, i.getItem())); |
---|
439 | return Q1; |
---|
440 | } |
---|
441 | |
---|
442 | static bool |
---|
443 | lowerRank (const CanonicalForm & F, const CanonicalForm & G, int & ind) |
---|
444 | { |
---|
445 | int degF, degG, levelF, levelG; |
---|
446 | |
---|
447 | levelF= F.level(); |
---|
448 | levelG= G.level(); |
---|
449 | if (F.inCoeffDomain()) |
---|
450 | { |
---|
451 | if (G.inCoeffDomain()) |
---|
452 | ind= 1; |
---|
453 | return true; |
---|
454 | } |
---|
455 | else if (G.inCoeffDomain()) |
---|
456 | return false; |
---|
457 | else if (levelF < levelG) |
---|
458 | return true; |
---|
459 | else if (levelF == levelG) |
---|
460 | { |
---|
461 | degF= degree(F); |
---|
462 | degG= degree(G); |
---|
463 | if (degF < degG) |
---|
464 | return true; |
---|
465 | else if (degF == degG) |
---|
466 | return lowerRank (LC (F), LC (G), ind); |
---|
467 | else |
---|
468 | return false; |
---|
469 | } |
---|
470 | return false; |
---|
471 | } |
---|
472 | |
---|
473 | static |
---|
474 | CanonicalForm |
---|
475 | lowestRank (const CFList & L) |
---|
476 | { |
---|
477 | CFListIterator i= L; |
---|
478 | CanonicalForm f; |
---|
479 | int ind= 0; |
---|
480 | if (!i.hasItem()) |
---|
481 | return f; |
---|
482 | |
---|
483 | f= i.getItem(); |
---|
484 | i++; |
---|
485 | |
---|
486 | while (i.hasItem()) |
---|
487 | { |
---|
488 | if (lowerRank (i.getItem(), f, ind)) |
---|
489 | { |
---|
490 | if (ind) |
---|
491 | { |
---|
492 | if (size (i.getItem()) < size (f)) |
---|
493 | f= i.getItem(); |
---|
494 | ind= 0; |
---|
495 | } |
---|
496 | else |
---|
497 | f= i.getItem(); |
---|
498 | } |
---|
499 | i++; |
---|
500 | } |
---|
501 | return f; |
---|
502 | } |
---|
503 | |
---|
504 | CFList initials (const CFList& L) |
---|
505 | { |
---|
506 | CFList result; |
---|
507 | for (CFListIterator iter= L; iter.hasItem(); iter++) |
---|
508 | { |
---|
509 | if (!LC(iter.getItem()).inCoeffDomain()) |
---|
510 | result.append (LC (iter.getItem())); |
---|
511 | } |
---|
512 | return result; |
---|
513 | } |
---|
514 | |
---|
515 | // sort in descending order of length of elements |
---|
516 | void |
---|
517 | sortListCFList (ListCFList& list) |
---|
518 | { |
---|
519 | int l= 1; |
---|
520 | int k= 1; |
---|
521 | CFList buf; |
---|
522 | ListCFListIterator m; |
---|
523 | for (ListCFListIterator i= list; l <= list.length(); i++, l++) |
---|
524 | { |
---|
525 | for (ListCFListIterator j= list; k <= list.length() - l; k++) |
---|
526 | { |
---|
527 | m= j; |
---|
528 | m++; |
---|
529 | if (j.getItem().length() < m.getItem().length()) |
---|
530 | { |
---|
531 | buf= m.getItem(); |
---|
532 | m.getItem()= j.getItem(); |
---|
533 | j.getItem()= buf; |
---|
534 | j++; |
---|
535 | j.getItem()= m.getItem(); |
---|
536 | } |
---|
537 | else |
---|
538 | j++; |
---|
539 | } |
---|
540 | k= 1; |
---|
541 | } |
---|
542 | } |
---|
543 | |
---|
544 | |
---|
545 | // sort in descending order of level of elements |
---|
546 | void |
---|
547 | sortCFListByLevel (CFList& list) |
---|
548 | { |
---|
549 | int l= 1; |
---|
550 | int k= 1; |
---|
551 | CanonicalForm buf; |
---|
552 | CFListIterator m; |
---|
553 | for (CFListIterator i= list; l <= list.length(); i++, l++) |
---|
554 | { |
---|
555 | for (CFListIterator j= list; k <= list.length() - l; k++) |
---|
556 | { |
---|
557 | m= j; |
---|
558 | m++; |
---|
559 | if ((size (j.getItem()) < size (m.getItem())) || |
---|
560 | ((size (j.getItem()) == size (m.getItem())) |
---|
561 | && (j.getItem().level() < m.getItem().level()))) |
---|
562 | { |
---|
563 | buf= m.getItem(); |
---|
564 | m.getItem()= j.getItem(); |
---|
565 | j.getItem()= buf; |
---|
566 | j++; |
---|
567 | j.getItem()= m.getItem(); |
---|
568 | } |
---|
569 | else |
---|
570 | j++; |
---|
571 | } |
---|
572 | k= 1; |
---|
573 | } |
---|
574 | } |
---|
575 | |
---|
576 | static bool |
---|
577 | member (const CanonicalForm& f, const CFList& F) |
---|
578 | { |
---|
579 | for (CFListIterator i= F; i.hasItem(); i++) |
---|
580 | { |
---|
581 | if (i.getItem().mapinto() == f.mapinto()) |
---|
582 | return 1; |
---|
583 | } |
---|
584 | return 0; |
---|
585 | } |
---|
586 | |
---|
587 | // are list A and B the same? |
---|
588 | static bool |
---|
589 | same (const CFList& A, const CFList& B) |
---|
590 | { |
---|
591 | if (A.length() != B.length()) |
---|
592 | return 0; |
---|
593 | |
---|
594 | CFListIterator i; |
---|
595 | |
---|
596 | for (i= A; i.hasItem(); i++) |
---|
597 | { |
---|
598 | if (!member (i.getItem(), B)) |
---|
599 | return 0; |
---|
600 | } |
---|
601 | for (i= B; i.hasItem(); i++) |
---|
602 | { |
---|
603 | if (!member (i.getItem(), A)) |
---|
604 | return 0; |
---|
605 | } |
---|
606 | return 1; |
---|
607 | } |
---|
608 | |
---|
609 | |
---|
610 | // is List cs contained in List of lists pi? |
---|
611 | static bool |
---|
612 | member (const CFList& cs, const ListCFList& pi) |
---|
613 | { |
---|
614 | if (pi.isEmpty()) |
---|
615 | return 0; |
---|
616 | |
---|
617 | ListCFListIterator i; |
---|
618 | |
---|
619 | for (i= pi; i.hasItem(); i++) |
---|
620 | { |
---|
621 | if (i.getItem().length() != cs.length()) |
---|
622 | continue; |
---|
623 | if (same (cs, i.getItem())) |
---|
624 | return 1; |
---|
625 | } |
---|
626 | return 0; |
---|
627 | } |
---|
628 | |
---|
629 | // is PS a subset of Cset ? |
---|
630 | static bool |
---|
631 | subset (const CFList &PS, const CFList& Cset) |
---|
632 | { |
---|
633 | for (CFListIterator i= PS; i.hasItem(); i++) |
---|
634 | { |
---|
635 | if (!member (i.getItem(), Cset)) |
---|
636 | return 0; |
---|
637 | } |
---|
638 | return 1; |
---|
639 | } |
---|
640 | |
---|
641 | // Union of two List of Lists |
---|
642 | static ListCFList |
---|
643 | MyUnion (const ListCFList& a, const ListCFList& b) |
---|
644 | { |
---|
645 | if (a.isEmpty()) |
---|
646 | return b; |
---|
647 | if (b.isEmpty()) |
---|
648 | return a; |
---|
649 | |
---|
650 | ListCFList output; |
---|
651 | ListCFListIterator i; |
---|
652 | CFList elem; |
---|
653 | |
---|
654 | for (i= a; i.hasItem(); i++) |
---|
655 | { |
---|
656 | elem= i.getItem(); |
---|
657 | if ((!elem.isEmpty()) && (!member (elem, output))) |
---|
658 | output.append(elem); |
---|
659 | } |
---|
660 | |
---|
661 | for (i= b; i.hasItem(); i++) |
---|
662 | { |
---|
663 | elem= i.getItem(); |
---|
664 | if ((!elem.isEmpty()) && (!member (elem, output))) |
---|
665 | output.append(elem); |
---|
666 | } |
---|
667 | return output; |
---|
668 | } |
---|
669 | |
---|
670 | // Union of a and b stored in b |
---|
671 | void |
---|
672 | MyUnion2 (const ListCFList& a, ListCFList& b) |
---|
673 | { |
---|
674 | if (a.isEmpty()) |
---|
675 | return; |
---|
676 | if (b.isEmpty()) |
---|
677 | { |
---|
678 | b= a; |
---|
679 | return; |
---|
680 | } |
---|
681 | |
---|
682 | ListCFListIterator i; |
---|
683 | CFList elem; |
---|
684 | |
---|
685 | for (i= a; i.hasItem(); i++) |
---|
686 | { |
---|
687 | elem= i.getItem(); |
---|
688 | if ((!elem.isEmpty()) && (!member (elem, b))) |
---|
689 | b.insert(elem); |
---|
690 | } |
---|
691 | } |
---|
692 | |
---|
693 | //if list b is member of the list of lists remove b and return the rest |
---|
694 | static ListCFList |
---|
695 | MyDifference (const ListCFList& a, const CFList& b) |
---|
696 | { |
---|
697 | ListCFList output; |
---|
698 | ListCFListIterator i; |
---|
699 | CFList elem; |
---|
700 | |
---|
701 | for (i= a; i.hasItem(); i++) |
---|
702 | { |
---|
703 | elem= i.getItem(); |
---|
704 | if ((!elem.isEmpty()) && (!same (elem, b))) |
---|
705 | output.append (elem); |
---|
706 | } |
---|
707 | return output; |
---|
708 | } |
---|
709 | |
---|
710 | // remove all elements of b from list of lists a and return the rest |
---|
711 | static ListCFList |
---|
712 | Minus( const ListCFList& a, const ListCFList& b) |
---|
713 | { |
---|
714 | ListCFList output= a; |
---|
715 | |
---|
716 | for (ListCFListIterator i=b; i.hasItem(); i++) |
---|
717 | output = MyDifference (output, i.getItem()); |
---|
718 | |
---|
719 | return output; |
---|
720 | } |
---|
721 | |
---|
722 | static ListCFList |
---|
723 | adjoin (const CFList& is, const CFList& qs, const ListCFList& qh) |
---|
724 | { |
---|
725 | ListCFList iss, qhi; |
---|
726 | ListCFListIterator j; |
---|
727 | CFList iscopy, itt; |
---|
728 | CFListIterator i; |
---|
729 | int ind, length; |
---|
730 | |
---|
731 | for (i= is; i.hasItem(); i++) |
---|
732 | { |
---|
733 | if (i.getItem().level() > 0) |
---|
734 | iscopy= Union (CFList (i.getItem()), iscopy); |
---|
735 | } |
---|
736 | if (iscopy.isEmpty()) |
---|
737 | return iss; |
---|
738 | |
---|
739 | qhi= MyDifference (qh, qs); |
---|
740 | length= qhi.length(); |
---|
741 | |
---|
742 | for (i= iscopy; i.hasItem(); i++) |
---|
743 | { |
---|
744 | itt= Union (qs, CFList (i.getItem())); |
---|
745 | ind= 0; |
---|
746 | if (length > 0) |
---|
747 | { |
---|
748 | for (j= qhi; j.hasItem(); j++) |
---|
749 | { |
---|
750 | if (subset (j.getItem(), itt)) |
---|
751 | ind= 1; |
---|
752 | } |
---|
753 | } |
---|
754 | if (ind == 0) |
---|
755 | iss.append (itt); |
---|
756 | } |
---|
757 | return iss; |
---|
758 | } |
---|
759 | |
---|
760 | static ListCFList |
---|
761 | adjoinb (const CFList & is, const CFList & qs, const ListCFList & qh ,const CFList & cs) |
---|
762 | { |
---|
763 | ListCFList iss, qhi; |
---|
764 | ListCFListIterator j; |
---|
765 | CFList iscopy, itt; |
---|
766 | CFListIterator i; |
---|
767 | int ind, length; |
---|
768 | |
---|
769 | for (i= is ; i.hasItem(); i++) |
---|
770 | { |
---|
771 | if (i.getItem().level() > 0) |
---|
772 | iscopy= Union (CFList (i.getItem()), iscopy); |
---|
773 | } |
---|
774 | if (iscopy.isEmpty()) |
---|
775 | return iss; |
---|
776 | qhi= MyDifference (qh, qs); |
---|
777 | length= qhi.length(); |
---|
778 | for (i= iscopy; i.hasItem(); i++) |
---|
779 | { |
---|
780 | itt= Union (Union (qs, CFList (i.getItem())), cs); |
---|
781 | ind= 0; |
---|
782 | if (length > 0) |
---|
783 | { |
---|
784 | for (j= qhi; j.hasItem(); j++) |
---|
785 | { |
---|
786 | if (subset (j.getItem(), itt)) |
---|
787 | ind= 1; |
---|
788 | } |
---|
789 | } |
---|
790 | if (ind == 0) |
---|
791 | iss.append(itt); |
---|
792 | } |
---|
793 | return iss; |
---|
794 | } |
---|
795 | |
---|
796 | static void |
---|
797 | select (const ListCFList& ppi, int length, ListCFList& ppi1, ListCFList& ppi2) |
---|
798 | { |
---|
799 | CFList elem; |
---|
800 | for (ListCFListIterator i=ppi; i.hasItem(); i++) |
---|
801 | { |
---|
802 | elem = i.getItem(); |
---|
803 | if (!elem.isEmpty()) |
---|
804 | { |
---|
805 | if (length <= elem.length()) |
---|
806 | ppi2.append(elem); |
---|
807 | else |
---|
808 | ppi1.append(elem); |
---|
809 | } |
---|
810 | } |
---|
811 | } |
---|
812 | |
---|
813 | CanonicalForm normalize (const CanonicalForm& F) |
---|
814 | { |
---|
815 | if (F.isZero()) |
---|
816 | return F; |
---|
817 | if (getCharacteristic() == 0) |
---|
818 | { |
---|
819 | CanonicalForm G; |
---|
820 | bool isRat= isOn (SW_RATIONAL); |
---|
821 | if (!isRat) |
---|
822 | On (SW_RATIONAL); |
---|
823 | G= F; |
---|
824 | G *= bCommonDen (G); |
---|
825 | if (!isRat) |
---|
826 | Off (SW_RATIONAL); |
---|
827 | if (isRat) |
---|
828 | Off (SW_RATIONAL); |
---|
829 | G= F/icontent (F); |
---|
830 | if (isRat) |
---|
831 | On (SW_RATIONAL); |
---|
832 | return G; |
---|
833 | } |
---|
834 | |
---|
835 | return F/lc (F); |
---|
836 | } |
---|
837 | |
---|
838 | static |
---|
839 | CanonicalForm |
---|
840 | Prem (const CanonicalForm& F, const CanonicalForm& G) |
---|
841 | { |
---|
842 | CanonicalForm f, g, l, test, lu, lv, t, retvalue; |
---|
843 | int degF, degG, levelF, levelG; |
---|
844 | bool reord; |
---|
845 | Variable v, vg= G.mvar(); |
---|
846 | |
---|
847 | if ( (levelF= F.level()) < (levelG= G.level())) |
---|
848 | return F; |
---|
849 | else |
---|
850 | { |
---|
851 | if ( levelF == levelG ) |
---|
852 | { |
---|
853 | f= F; |
---|
854 | g= G; |
---|
855 | reord= false; |
---|
856 | v= F.mvar(); |
---|
857 | } |
---|
858 | else |
---|
859 | { |
---|
860 | v= Variable (levelF + 1); |
---|
861 | f= swapvar (F, vg, v); |
---|
862 | g= swapvar (G, vg, v); |
---|
863 | reord= true; |
---|
864 | } |
---|
865 | degG= degree (g, v ); |
---|
866 | degF= degree (f, v ); |
---|
867 | if (degG <= degF) |
---|
868 | { |
---|
869 | l= LC (g); |
---|
870 | g= g - l*power (v, degG); |
---|
871 | } |
---|
872 | else |
---|
873 | l= 1; |
---|
874 | while ((degG <= degF) && (!f.isZero())) |
---|
875 | { |
---|
876 | test= gcd (l, LC(f)); |
---|
877 | lu= l / test; |
---|
878 | lv= LC(f) / test; |
---|
879 | t= g*lv*power (v, degF - degG); |
---|
880 | |
---|
881 | if (degF == 0) |
---|
882 | f= 0; |
---|
883 | else |
---|
884 | f= f - LC (f)*power (v, degF); |
---|
885 | |
---|
886 | f= f*lu - t; |
---|
887 | degF= degree (f, v); |
---|
888 | } |
---|
889 | |
---|
890 | if (reord) |
---|
891 | retvalue= swapvar (f, vg, v); |
---|
892 | else |
---|
893 | retvalue= f; |
---|
894 | |
---|
895 | return retvalue; |
---|
896 | } |
---|
897 | } |
---|
898 | |
---|
899 | static |
---|
900 | CanonicalForm |
---|
901 | Premb (const CanonicalForm &f, const CFList &L) |
---|
902 | { |
---|
903 | CanonicalForm rem= f; |
---|
904 | CFList l= L; |
---|
905 | l.removeFirst(); |
---|
906 | CFListIterator i= l; |
---|
907 | |
---|
908 | for (i.lastItem(); i.hasItem(); i--) |
---|
909 | rem= normalize (Prem (rem, i.getItem())); |
---|
910 | |
---|
911 | CanonicalForm tmp= L.getFirst()/content (L.getFirst()); |
---|
912 | |
---|
913 | bool isRat= isOn (SW_RATIONAL); |
---|
914 | if (getCharacteristic() == 0 && !isRat) |
---|
915 | On (SW_RATIONAL); |
---|
916 | if (fdivides (tmp, rem)) |
---|
917 | { |
---|
918 | if (getCharacteristic() == 0 && !isRat) |
---|
919 | Off (SW_RATIONAL); |
---|
920 | return 0; |
---|
921 | } |
---|
922 | |
---|
923 | if (getCharacteristic() == 0 && !isRat) |
---|
924 | Off (SW_RATIONAL); |
---|
925 | |
---|
926 | rem= normalize (Prem (rem, L.getFirst())); |
---|
927 | |
---|
928 | return rem; |
---|
929 | } |
---|
930 | |
---|
931 | static |
---|
932 | CanonicalForm |
---|
933 | Prem (const CanonicalForm &f, const CFList &L) |
---|
934 | { |
---|
935 | CanonicalForm rem= f; |
---|
936 | CFListIterator i= L; |
---|
937 | |
---|
938 | for (i.lastItem(); i.hasItem(); i--) |
---|
939 | rem= normalize (Prem (rem, i.getItem())); |
---|
940 | |
---|
941 | return rem; |
---|
942 | } |
---|
943 | |
---|
944 | CFList uniGcd (const CFList& L) |
---|
945 | { |
---|
946 | CFList tmp; |
---|
947 | CanonicalForm g; |
---|
948 | CFListIterator i; |
---|
949 | for (i= L; i.hasItem(); i++) |
---|
950 | { |
---|
951 | if (i.getItem().isUnivariate() && i.getItem().level() == 1) |
---|
952 | tmp.append (i.getItem()); |
---|
953 | } |
---|
954 | if (tmp.length() <= 2) |
---|
955 | return L; |
---|
956 | i= tmp; |
---|
957 | g= i.getItem(); |
---|
958 | i++; |
---|
959 | g= gcd (g,i.getItem()); |
---|
960 | i++; |
---|
961 | for (; i.hasItem(); i++) |
---|
962 | g= gcd (g, i.getItem()); |
---|
963 | return Union (Difference (L, tmp), CFList (g)); |
---|
964 | } |
---|
965 | |
---|
966 | |
---|
967 | CFList |
---|
968 | factorsOfInitials(const CFList & L) |
---|
969 | { |
---|
970 | CFList result; |
---|
971 | CFFList factors; |
---|
972 | CanonicalForm tmp; |
---|
973 | |
---|
974 | for (CFListIterator i= L; i.hasItem(); i++) |
---|
975 | { |
---|
976 | factors= factorize (LC (i.getItem())); |
---|
977 | for (CFFListIterator j= factors; j.hasItem(); j++) |
---|
978 | { |
---|
979 | tmp= j.getItem().factor(); |
---|
980 | if (!tmp.inCoeffDomain()) |
---|
981 | result= Union (result, CFList (normalize (tmp))); |
---|
982 | } |
---|
983 | } |
---|
984 | |
---|
985 | return result; |
---|
986 | } |
---|
987 | |
---|
988 | void |
---|
989 | removeContent (CanonicalForm& F, CanonicalForm& cF) |
---|
990 | { |
---|
991 | if (size (F) == 1) |
---|
992 | { |
---|
993 | CanonicalForm tmp= F; |
---|
994 | F= F.mvar(); |
---|
995 | cF= tmp/F; |
---|
996 | if (!cF.inCoeffDomain()) |
---|
997 | cF= normalize (cF); |
---|
998 | else |
---|
999 | cF= 0; |
---|
1000 | |
---|
1001 | return; |
---|
1002 | } |
---|
1003 | |
---|
1004 | cF= content (F); |
---|
1005 | |
---|
1006 | if (cF.inCoeffDomain()) |
---|
1007 | cF= 0; |
---|
1008 | else |
---|
1009 | { |
---|
1010 | cF= normalize (cF); |
---|
1011 | F /= cF; |
---|
1012 | F= normalize (F); |
---|
1013 | } |
---|
1014 | } |
---|
1015 | |
---|
1016 | CFList |
---|
1017 | factorPSet (const CFList& PS) |
---|
1018 | { |
---|
1019 | CFList result; |
---|
1020 | CFFList factors; |
---|
1021 | CFFListIterator j; |
---|
1022 | |
---|
1023 | for (CFListIterator i= PS; i. hasItem(); i++) |
---|
1024 | { |
---|
1025 | factors= factorize (i.getItem()); |
---|
1026 | if (factors.getFirst().factor().inCoeffDomain()) |
---|
1027 | factors.removeFirst(); |
---|
1028 | for (j= factors; j.hasItem(); j++ ) |
---|
1029 | result= Union (result, CFList (normalize (j.getItem().factor()))); |
---|
1030 | } |
---|
1031 | return result; |
---|
1032 | } |
---|
1033 | |
---|
1034 | void |
---|
1035 | removeFactors (CanonicalForm& r, StoreFactors& StoredFactors, |
---|
1036 | CFList& removedFactors) |
---|
1037 | { |
---|
1038 | CanonicalForm quot; |
---|
1039 | CFList testlist; |
---|
1040 | int n= level(r); |
---|
1041 | bool divides; |
---|
1042 | CFListIterator j; |
---|
1043 | |
---|
1044 | for (int i=1; i<= n; i++) |
---|
1045 | testlist.append (CanonicalForm (Variable (i))); |
---|
1046 | |
---|
1047 | for (j= StoredFactors.FS1; j.hasItem(); j++) |
---|
1048 | { |
---|
1049 | while (fdivides (j.getItem(), r, quot)) |
---|
1050 | { |
---|
1051 | if (!quot.inCoeffDomain()) |
---|
1052 | r= quot; |
---|
1053 | else |
---|
1054 | break; |
---|
1055 | } |
---|
1056 | } |
---|
1057 | |
---|
1058 | // remove already removed factors |
---|
1059 | for (j= StoredFactors.FS2; j.hasItem(); j++) |
---|
1060 | { |
---|
1061 | divides= false; |
---|
1062 | while (fdivides (j.getItem(), r, quot)) |
---|
1063 | { |
---|
1064 | if (!quot.inCoeffDomain()) |
---|
1065 | { |
---|
1066 | divides= true; |
---|
1067 | r= quot; |
---|
1068 | } |
---|
1069 | else |
---|
1070 | break; |
---|
1071 | } |
---|
1072 | if (divides) |
---|
1073 | removedFactors= Union (removedFactors, CFList (j.getItem())); |
---|
1074 | } |
---|
1075 | r= normalize (r); |
---|
1076 | |
---|
1077 | // remove variables |
---|
1078 | for (j= testlist; j.hasItem() && !r.isOne(); j++) |
---|
1079 | { |
---|
1080 | while (fdivides (j.getItem(), r, quot)) |
---|
1081 | { |
---|
1082 | if (!quot.inCoeffDomain()) |
---|
1083 | r= quot; |
---|
1084 | else |
---|
1085 | break; |
---|
1086 | removedFactors= Union (removedFactors, CFList (j.getItem())); |
---|
1087 | } |
---|
1088 | } |
---|
1089 | } |
---|
1090 | |
---|
1091 | CFList |
---|
1092 | removeContent (const CFList & PS, StoreFactors & StoredFactors) |
---|
1093 | { |
---|
1094 | CFListIterator i= PS; |
---|
1095 | if ((!i.hasItem()) || (PS.getFirst().level() == 0 )) |
---|
1096 | return PS; |
---|
1097 | |
---|
1098 | CFList output; |
---|
1099 | CanonicalForm cc,elem; |
---|
1100 | |
---|
1101 | for (; i.hasItem(); i++) |
---|
1102 | { |
---|
1103 | elem= i.getItem(); |
---|
1104 | cc= content (elem, elem.mvar()); |
---|
1105 | if (cc.level() > 0 ) |
---|
1106 | { |
---|
1107 | output.append (elem / cc); |
---|
1108 | StoredFactors.FS1 = Union (CFList (cc), StoredFactors.FS1); |
---|
1109 | } |
---|
1110 | else |
---|
1111 | output.append(elem); |
---|
1112 | } |
---|
1113 | return output; |
---|
1114 | } |
---|
1115 | |
---|
1116 | static bool |
---|
1117 | contractsub (const CFList& cs1, const CFList& cs2) |
---|
1118 | { |
---|
1119 | CFListIterator i; |
---|
1120 | |
---|
1121 | CanonicalForm r; |
---|
1122 | for (i= cs1; i.hasItem(); i++) |
---|
1123 | { |
---|
1124 | if (Prem (i.getItem(), cs2) != 0) |
---|
1125 | return false; |
---|
1126 | } |
---|
1127 | |
---|
1128 | CFList is= factorsOfInitials (cs1); |
---|
1129 | |
---|
1130 | for (i= is; i.hasItem(); i++) |
---|
1131 | { |
---|
1132 | if (Prem (i.getItem(), cs2) == 0) |
---|
1133 | return false; |
---|
1134 | } |
---|
1135 | return true; |
---|
1136 | } |
---|
1137 | |
---|
1138 | static ListCFList |
---|
1139 | contract (const ListCFList& cs) |
---|
1140 | { |
---|
1141 | ListCFList mem, ts; |
---|
1142 | CFList iitem, jitem; |
---|
1143 | |
---|
1144 | if (cs.length() < 2) |
---|
1145 | return cs; |
---|
1146 | |
---|
1147 | int l= cs.length(); |
---|
1148 | int ii= 1; |
---|
1149 | ListCFListIterator j; |
---|
1150 | for (ListCFListIterator i= cs; i.hasItem() && ii < l; i++, ii++) |
---|
1151 | { |
---|
1152 | iitem= i.getItem(); |
---|
1153 | if (!member (iitem, mem)) |
---|
1154 | { |
---|
1155 | j= i; |
---|
1156 | j++; |
---|
1157 | for (; j.hasItem(); j++) |
---|
1158 | { |
---|
1159 | jitem= j.getItem(); |
---|
1160 | if (!member (jitem, mem)) |
---|
1161 | { |
---|
1162 | if (contractsub (iitem, jitem)) |
---|
1163 | { |
---|
1164 | ts.append (jitem); |
---|
1165 | mem.append (jitem); |
---|
1166 | } |
---|
1167 | else |
---|
1168 | { |
---|
1169 | if (contractsub (jitem, iitem)) |
---|
1170 | ts.append (iitem); // no mem.append (item) because we assume cs does not contain duplicate entries |
---|
1171 | } |
---|
1172 | } |
---|
1173 | } |
---|
1174 | } |
---|
1175 | } |
---|
1176 | return Minus (cs,ts); |
---|
1177 | } |
---|
1178 | |
---|
1179 | |
---|
1180 | CFList |
---|
1181 | basicSet (const CFList &PS) |
---|
1182 | { |
---|
1183 | CFList QS= PS, BS, RS; |
---|
1184 | CanonicalForm b; |
---|
1185 | int cb, degb; |
---|
1186 | |
---|
1187 | if (PS.length() < 2) |
---|
1188 | return PS; |
---|
1189 | |
---|
1190 | CFListIterator i; |
---|
1191 | |
---|
1192 | while (!QS.isEmpty()) |
---|
1193 | { |
---|
1194 | b= lowestRank (QS); |
---|
1195 | cb= b.level(); |
---|
1196 | |
---|
1197 | BS= Union(CFList (b), BS); |
---|
1198 | |
---|
1199 | if (cb <= 0) |
---|
1200 | return CFList(); |
---|
1201 | else |
---|
1202 | { |
---|
1203 | degb= degree (b); |
---|
1204 | RS= CFList(); |
---|
1205 | for (i= QS; i.hasItem(); i++) |
---|
1206 | { |
---|
1207 | if (degree (i.getItem(), cb) < degb) |
---|
1208 | RS= Union (CFList (i.getItem()), RS); |
---|
1209 | } |
---|
1210 | QS= RS; |
---|
1211 | } |
---|
1212 | } |
---|
1213 | |
---|
1214 | return BS; |
---|
1215 | } |
---|
1216 | |
---|
1217 | CFList |
---|
1218 | charSet (const CFList &PS) |
---|
1219 | { |
---|
1220 | CFList QS= PS, RS= PS, CSet, tmp; |
---|
1221 | CFListIterator i; |
---|
1222 | CanonicalForm r; |
---|
1223 | |
---|
1224 | while (!RS.isEmpty()) |
---|
1225 | { |
---|
1226 | CSet= basicSet (QS); |
---|
1227 | |
---|
1228 | RS= CFList(); |
---|
1229 | if (CSet.length() > 0 && CSet.getFirst().level() > 0) |
---|
1230 | { |
---|
1231 | tmp= Difference (QS, CSet); |
---|
1232 | for (i= tmp; i.hasItem(); i++) |
---|
1233 | { |
---|
1234 | r= Prem (i.getItem(), CSet); |
---|
1235 | if (r != 0) |
---|
1236 | RS= Union (RS, CFList (r)); |
---|
1237 | } |
---|
1238 | QS= Union (QS, RS); |
---|
1239 | } |
---|
1240 | } |
---|
1241 | |
---|
1242 | return CSet; |
---|
1243 | } |
---|
1244 | |
---|
1245 | /// medial set |
---|
1246 | CFList |
---|
1247 | charSetN (const CFList &PS) |
---|
1248 | { |
---|
1249 | CFList QS= PS, RS= PS, CSet, tmp; |
---|
1250 | CFListIterator i; |
---|
1251 | CanonicalForm r; |
---|
1252 | |
---|
1253 | while (!RS.isEmpty()) |
---|
1254 | { |
---|
1255 | QS= uniGcd (QS); |
---|
1256 | CSet= basicSet (QS); |
---|
1257 | |
---|
1258 | RS= CFList(); |
---|
1259 | if (CSet.length() > 0 && CSet.getFirst().level() > 0) |
---|
1260 | { |
---|
1261 | tmp= Difference (QS, CSet); |
---|
1262 | for (i= tmp; i.hasItem(); i++) |
---|
1263 | { |
---|
1264 | r= Prem (i.getItem(), CSet); |
---|
1265 | if (!r.isZero()) |
---|
1266 | RS= Union (RS, CFList (r)); |
---|
1267 | } |
---|
1268 | QS= Union (CSet, RS); |
---|
1269 | } |
---|
1270 | } |
---|
1271 | |
---|
1272 | return CSet; |
---|
1273 | } |
---|
1274 | |
---|
1275 | /// compute a characteristic set via medial set |
---|
1276 | CFList |
---|
1277 | charSetViaCharSetN (const CFList& PS) |
---|
1278 | { |
---|
1279 | CFList L; |
---|
1280 | CFFList sqrfFactors; |
---|
1281 | CanonicalForm sqrf; |
---|
1282 | CFFListIterator iter2; |
---|
1283 | for (CFListIterator iter= PS; iter.hasItem(); iter++) |
---|
1284 | { |
---|
1285 | sqrf= 1; |
---|
1286 | sqrfFactors= sqrFree (iter.getItem()); |
---|
1287 | for (iter2= sqrfFactors; iter2.hasItem(); iter2++) |
---|
1288 | sqrf *= iter2.getItem().factor(); |
---|
1289 | L= Union (L, CFList (normalize (sqrf))); |
---|
1290 | } |
---|
1291 | |
---|
1292 | CFList result= charSetN (L); |
---|
1293 | |
---|
1294 | if (result.isEmpty() || result.getFirst().inCoeffDomain()) |
---|
1295 | return CFList(1); |
---|
1296 | |
---|
1297 | CanonicalForm r; |
---|
1298 | CFList RS; |
---|
1299 | CFList tmp= Difference (L, result); |
---|
1300 | |
---|
1301 | for (CFListIterator i= tmp; i.hasItem(); i++) |
---|
1302 | { |
---|
1303 | r= Premb (i.getItem(), result); |
---|
1304 | if (!r.isZero()) |
---|
1305 | RS= Union (RS, CFList (r)); |
---|
1306 | } |
---|
1307 | if (RS.isEmpty()) |
---|
1308 | return result; |
---|
1309 | |
---|
1310 | return charSetViaCharSetN (Union (L, Union (RS, result))); |
---|
1311 | } |
---|
1312 | |
---|
1313 | /// modified medial set |
---|
1314 | CFList |
---|
1315 | modCharSet (const CFList& L, StoreFactors& StoredFactors, bool removeContents) |
---|
1316 | { |
---|
1317 | CFList QS= L, RS= L, CSet, tmp, contents, initial, removedFactors; |
---|
1318 | CFListIterator i; |
---|
1319 | CanonicalForm r, cF; |
---|
1320 | bool noRemainder= true; |
---|
1321 | StoreFactors StoredFactors2; |
---|
1322 | |
---|
1323 | QS= uniGcd (L); |
---|
1324 | |
---|
1325 | while (!RS.isEmpty()) |
---|
1326 | { |
---|
1327 | noRemainder= true; |
---|
1328 | CSet= basicSet (QS); |
---|
1329 | |
---|
1330 | initial= factorsOfInitials (CSet); |
---|
1331 | |
---|
1332 | StoredFactors2.FS1= StoredFactors.FS1; |
---|
1333 | StoredFactors2.FS2= Union (StoredFactors2.FS2, initial); |
---|
1334 | |
---|
1335 | RS= CFList(); |
---|
1336 | |
---|
1337 | if (CSet.length() > 0 && CSet.getFirst().level() > 0) |
---|
1338 | { |
---|
1339 | tmp= Difference (QS, CSet); |
---|
1340 | |
---|
1341 | for (i= tmp; i.hasItem(); i++) |
---|
1342 | { |
---|
1343 | r= Prem (i.getItem(), CSet); |
---|
1344 | if (!r.isZero()) |
---|
1345 | { |
---|
1346 | noRemainder= false; |
---|
1347 | if (removeContents) |
---|
1348 | { |
---|
1349 | removeContent (r, cF); |
---|
1350 | |
---|
1351 | if (!cF.isZero()) |
---|
1352 | contents= Union (contents, factorPSet (CFList(cF))); //factorPSet maybe too much it should suffice to do a squarefree factorization instead |
---|
1353 | } |
---|
1354 | |
---|
1355 | removeFactors (r, StoredFactors2, removedFactors); |
---|
1356 | StoredFactors2.FS1= Union (StoredFactors2.FS1, removedFactors); |
---|
1357 | StoredFactors2.FS2= Difference (StoredFactors2.FS2, removedFactors); |
---|
1358 | |
---|
1359 | removedFactors= CFList(); |
---|
1360 | |
---|
1361 | RS= Union (RS, CFList (r)); |
---|
1362 | } |
---|
1363 | } |
---|
1364 | |
---|
1365 | if (removeContents && !noRemainder) |
---|
1366 | { |
---|
1367 | StoredFactors.FS1= Union (StoredFactors2.FS1, contents); |
---|
1368 | StoredFactors.FS2= StoredFactors2.FS2; |
---|
1369 | } |
---|
1370 | else |
---|
1371 | StoredFactors= StoredFactors2; |
---|
1372 | |
---|
1373 | QS= Union (CSet, RS); |
---|
1374 | |
---|
1375 | contents= CFList(); |
---|
1376 | removedFactors= CFList(); |
---|
1377 | } |
---|
1378 | else |
---|
1379 | StoredFactors= StoredFactors2; |
---|
1380 | } |
---|
1381 | |
---|
1382 | return CSet; |
---|
1383 | } |
---|
1384 | |
---|
1385 | /// characteristic set via modified medial set |
---|
1386 | CFList |
---|
1387 | charSetViaModCharSet (const CFList& PS, StoreFactors& StoredFactors, bool removeContents) |
---|
1388 | { |
---|
1389 | CFList L; |
---|
1390 | CFFList sqrfFactors; |
---|
1391 | CanonicalForm sqrf; |
---|
1392 | CFFListIterator iter2; |
---|
1393 | for (CFListIterator iter= PS; iter.hasItem(); iter++) |
---|
1394 | { |
---|
1395 | sqrf= 1; |
---|
1396 | sqrfFactors= sqrFree (iter.getItem()); |
---|
1397 | for (iter2= sqrfFactors; iter2.hasItem(); iter2++) |
---|
1398 | sqrf *= iter2.getItem().factor(); |
---|
1399 | L= Union (L, CFList (normalize (sqrf))); |
---|
1400 | } |
---|
1401 | |
---|
1402 | L= uniGcd (L); |
---|
1403 | |
---|
1404 | CFList result= modCharSet (L, StoredFactors, removeContents); |
---|
1405 | |
---|
1406 | if (result.isEmpty() || result.getFirst().inCoeffDomain()) |
---|
1407 | return CFList(1); |
---|
1408 | |
---|
1409 | CanonicalForm r; |
---|
1410 | CFList RS; |
---|
1411 | CFList tmp= Difference (L, result); |
---|
1412 | |
---|
1413 | for (CFListIterator i= tmp; i.hasItem(); i++) |
---|
1414 | { |
---|
1415 | r= Premb (i.getItem(), result); |
---|
1416 | if (!r.isZero()) |
---|
1417 | RS= Union (RS, CFList (r)); |
---|
1418 | } |
---|
1419 | if (RS.isEmpty()) |
---|
1420 | return result; |
---|
1421 | |
---|
1422 | return charSetViaModCharSet (Union (L, Union (RS, result)), StoredFactors, removeContents); |
---|
1423 | } |
---|
1424 | |
---|
1425 | CFList |
---|
1426 | charSetViaModCharSet (const CFList& PS, bool removeContents) |
---|
1427 | { |
---|
1428 | StoreFactors tmp; |
---|
1429 | return charSetViaModCharSet (PS, tmp, removeContents); |
---|
1430 | } |
---|
1431 | |
---|
1432 | ListCFList |
---|
1433 | charSeries (const CFList& L) |
---|
1434 | { |
---|
1435 | ListCFList tmp, result, tmp2, ppi1, ppi2, qqi, ppi, alreadyConsidered; |
---|
1436 | CFList l, charset, ini; |
---|
1437 | |
---|
1438 | int count= 0; |
---|
1439 | int highestLevel= 1; |
---|
1440 | CFListIterator iter; |
---|
1441 | |
---|
1442 | StoreFactors StoredFactors; |
---|
1443 | |
---|
1444 | l= L; |
---|
1445 | |
---|
1446 | for (iter= l; iter.hasItem(); iter++) |
---|
1447 | { |
---|
1448 | iter.getItem()= normalize (iter.getItem()); |
---|
1449 | if (highestLevel < iter.getItem().level()) |
---|
1450 | highestLevel= iter.getItem().level(); |
---|
1451 | } |
---|
1452 | |
---|
1453 | tmp= ListCFList (l); |
---|
1454 | |
---|
1455 | while (!tmp.isEmpty()) |
---|
1456 | { |
---|
1457 | sortListCFList (tmp); |
---|
1458 | |
---|
1459 | l= tmp.getFirst(); |
---|
1460 | |
---|
1461 | tmp= MyDifference (tmp, l); |
---|
1462 | |
---|
1463 | select (ppi, l.length(), ppi1, ppi2); |
---|
1464 | |
---|
1465 | MyUnion2 (ppi2, qqi); |
---|
1466 | |
---|
1467 | if (count > 0) |
---|
1468 | ppi= MyUnion (ListCFList (l), ppi1); |
---|
1469 | else |
---|
1470 | ppi= ListCFList(); |
---|
1471 | |
---|
1472 | if (l.length() - 3 < highestLevel) |
---|
1473 | charset= charSetViaModCharSet (l, StoredFactors); |
---|
1474 | else |
---|
1475 | charset= charSetViaCharSetN (l); |
---|
1476 | |
---|
1477 | if (charset.length() > 0 && charset.getFirst().level() > 0) |
---|
1478 | { |
---|
1479 | result= MyUnion (result, ListCFList (charset)); |
---|
1480 | ini= factorsOfInitials (charset); |
---|
1481 | |
---|
1482 | ini= Union (ini, factorPSet (StoredFactors.FS1)); |
---|
1483 | sortCFListByLevel (ini); |
---|
1484 | } |
---|
1485 | else |
---|
1486 | { |
---|
1487 | ini= factorPSet (StoredFactors.FS1); |
---|
1488 | sortCFListByLevel (ini); |
---|
1489 | } |
---|
1490 | |
---|
1491 | tmp2= adjoin (ini, l, qqi); |
---|
1492 | tmp= MyUnion (tmp, tmp2); |
---|
1493 | |
---|
1494 | StoredFactors.FS1= CFList(); |
---|
1495 | StoredFactors.FS2= CFList(); |
---|
1496 | |
---|
1497 | ppi1= ListCFList(); |
---|
1498 | ppi2= ListCFList(); |
---|
1499 | |
---|
1500 | count++; |
---|
1501 | } |
---|
1502 | |
---|
1503 | //TODO need to remove superflous components |
---|
1504 | |
---|
1505 | return result; |
---|
1506 | } |
---|
1507 | |
---|
1508 | static bool |
---|
1509 | irreducible (const CFList & AS) |
---|
1510 | { |
---|
1511 | // AS is given by AS = { A1, A2, .. Ar }, d_i = degree(Ai) |
---|
1512 | |
---|
1513 | // 1) we test: if d_i > 1, d_j =1 for all j<>i, then AS is irreducible. |
---|
1514 | bool deg1= true; |
---|
1515 | for (CFListIterator i= AS ; i.hasItem(); i++) |
---|
1516 | { |
---|
1517 | if (degree (i.getItem()) > 1) |
---|
1518 | { |
---|
1519 | if (deg1) |
---|
1520 | deg1= false; |
---|
1521 | else |
---|
1522 | return false; // found 2nd poly with deg > 1 |
---|
1523 | } |
---|
1524 | } |
---|
1525 | return true; |
---|
1526 | } |
---|
1527 | |
---|
1528 | static CFList |
---|
1529 | irredAS (CFList & AS, int & indexRed, CanonicalForm & reducible) |
---|
1530 | { |
---|
1531 | CFFList qs; |
---|
1532 | CFList ts, as; |
---|
1533 | CanonicalForm elem; |
---|
1534 | bool ind= true; |
---|
1535 | int nr= 0, success= -1; |
---|
1536 | CFListIterator i; |
---|
1537 | |
---|
1538 | indexRed= 0; |
---|
1539 | for (i= AS; i.hasItem(); i++ ) |
---|
1540 | { |
---|
1541 | nr += 1; |
---|
1542 | if (degree (i.getItem()) > 1) |
---|
1543 | { |
---|
1544 | qs= factorize (i.getItem()); |
---|
1545 | if (qs.getFirst().factor().inCoeffDomain()) |
---|
1546 | qs.removeFirst(); |
---|
1547 | } |
---|
1548 | else |
---|
1549 | qs= CFFList (CFFactor (i.getItem(), 1)); |
---|
1550 | |
---|
1551 | if ((qs.length() >= 2 ) || (qs.getFirst().exp() > 1)) |
---|
1552 | { |
---|
1553 | indexRed= nr; |
---|
1554 | ind= false; |
---|
1555 | reducible= i.getItem(); |
---|
1556 | break; |
---|
1557 | } |
---|
1558 | } |
---|
1559 | |
---|
1560 | if (ind) |
---|
1561 | { |
---|
1562 | if (irreducible (AS)) // as quasilinear? => irreducible! |
---|
1563 | indexRed= 0; |
---|
1564 | else |
---|
1565 | { |
---|
1566 | i= AS; |
---|
1567 | for (nr= 1; nr< AS.length(); nr++) |
---|
1568 | { |
---|
1569 | as.append (i.getItem()); |
---|
1570 | i++; |
---|
1571 | if (degree (i.getItem()) > 1) |
---|
1572 | { // search for a non linear elem |
---|
1573 | qs= newfactoras (i.getItem(), as, success); |
---|
1574 | if (qs.getFirst().factor().inCoeffDomain()) |
---|
1575 | qs.removeFirst(); |
---|
1576 | if (qs.length() > 1 || qs.getFirst().exp() > 1) |
---|
1577 | { //found elem is reducible |
---|
1578 | reducible= i.getItem(); |
---|
1579 | indexRed= nr + 1; |
---|
1580 | break; |
---|
1581 | } |
---|
1582 | } |
---|
1583 | } |
---|
1584 | } |
---|
1585 | } |
---|
1586 | for (CFFListIterator k= qs; k.hasItem(); k++) |
---|
1587 | ts.append (k.getItem().factor()); |
---|
1588 | return ts; |
---|
1589 | } |
---|
1590 | |
---|
1591 | ListCFList |
---|
1592 | irrCharSeries (const CFList & PS) |
---|
1593 | { |
---|
1594 | CanonicalForm reducible, reducible2; |
---|
1595 | CFList qs, cs, factorset, is, ts, L; |
---|
1596 | CanonicalForm sqrf; |
---|
1597 | CFFList sqrfFactors; |
---|
1598 | CFFListIterator iter2; |
---|
1599 | for (CFListIterator iter= PS; iter.hasItem(); iter++) |
---|
1600 | { |
---|
1601 | sqrf= 1; |
---|
1602 | sqrfFactors= sqrFree (iter.getItem()); |
---|
1603 | if (sqrfFactors.getFirst().factor().inCoeffDomain()) |
---|
1604 | sqrfFactors.removeFirst(); |
---|
1605 | for (iter2= sqrfFactors; iter2.hasItem(); iter2++) |
---|
1606 | sqrf *= iter2.getItem().factor(); |
---|
1607 | sqrf= normalize (sqrf); |
---|
1608 | L= Union (L, CFList (sqrf)); |
---|
1609 | } |
---|
1610 | |
---|
1611 | ListCFList pi, ppi, qqi, qsi, iss, qhi= ListCFList(L); |
---|
1612 | |
---|
1613 | int nr_of_iteration= 0, indexRed, highestlevel= 0; |
---|
1614 | |
---|
1615 | for (CFListIterator iter= PS; iter.hasItem(); iter++) |
---|
1616 | { |
---|
1617 | if (level (iter.getItem()) > highestlevel) |
---|
1618 | highestlevel= level(iter.getItem()); |
---|
1619 | } |
---|
1620 | |
---|
1621 | while (!qhi.isEmpty()) |
---|
1622 | { |
---|
1623 | sortListCFList (qhi); |
---|
1624 | |
---|
1625 | qs= qhi.getFirst(); |
---|
1626 | |
---|
1627 | ListCFList ppi1,ppi2; |
---|
1628 | select (ppi, qs.length(), ppi1, ppi2); |
---|
1629 | |
---|
1630 | MyUnion2 (ppi2, qqi); |
---|
1631 | |
---|
1632 | if (nr_of_iteration == 0) |
---|
1633 | { |
---|
1634 | nr_of_iteration += 1; |
---|
1635 | ppi= ListCFList(); |
---|
1636 | } |
---|
1637 | else |
---|
1638 | { |
---|
1639 | nr_of_iteration += 1; |
---|
1640 | ppi= MyUnion (ListCFList(qs), ppi1); |
---|
1641 | } |
---|
1642 | |
---|
1643 | StoreFactors StoredFactors; |
---|
1644 | cs= charSetViaModCharSet (qs, StoredFactors); |
---|
1645 | cs= removeContent (cs, StoredFactors); |
---|
1646 | |
---|
1647 | factorset= StoredFactors.FS1; |
---|
1648 | |
---|
1649 | if (cs.getFirst().level() > 0) |
---|
1650 | { |
---|
1651 | ts= irredAS (cs, indexRed, reducible); |
---|
1652 | |
---|
1653 | if (indexRed <= 0) // irreducible |
---|
1654 | { |
---|
1655 | if (!subset (cs,qs)) |
---|
1656 | cs= charSetViaCharSetN (Union (qs,cs)); |
---|
1657 | if (!member (cs, pi)) |
---|
1658 | { |
---|
1659 | pi= MyUnion (pi, ListCFList (cs)); |
---|
1660 | if (cs.getFirst().level() > 0) |
---|
1661 | { |
---|
1662 | ts= irredAS (cs, indexRed, reducible); |
---|
1663 | |
---|
1664 | if (indexRed <= 0) //irreducible |
---|
1665 | { |
---|
1666 | qsi= MyUnion (qsi, ListCFList(cs)); |
---|
1667 | if (cs.length() == highestlevel) |
---|
1668 | is= factorPSet (factorset); |
---|
1669 | else |
---|
1670 | is= Union (factorsOfInitials (cs), factorPSet (factorset)); |
---|
1671 | iss= adjoin (is, qs, qqi); |
---|
1672 | } |
---|
1673 | } |
---|
1674 | else |
---|
1675 | iss= adjoin (factorPSet (factorset), qs, qqi); |
---|
1676 | } |
---|
1677 | else |
---|
1678 | iss= adjoin (factorPSet (factorset), qs, qqi); |
---|
1679 | } |
---|
1680 | |
---|
1681 | if (indexRed > 0) |
---|
1682 | { |
---|
1683 | is= factorPSet (factorset); |
---|
1684 | if (indexRed > 1) |
---|
1685 | { |
---|
1686 | CFList cst; |
---|
1687 | for (CFListIterator i= cs ; i.hasItem(); i++) |
---|
1688 | { |
---|
1689 | if (i.getItem() == reducible) |
---|
1690 | break; |
---|
1691 | else |
---|
1692 | cst.append (i.getItem()); |
---|
1693 | } |
---|
1694 | is= Union (factorsOfInitials (cst), is); |
---|
1695 | iss= MyUnion (adjoin (is, qs, qqi), adjoinb (ts, qs, qqi, cst)); |
---|
1696 | } |
---|
1697 | else |
---|
1698 | iss= adjoin (Union (is, ts), qs, qqi); |
---|
1699 | } |
---|
1700 | } |
---|
1701 | else |
---|
1702 | iss= adjoin (factorPSet (factorset), qs, qqi); |
---|
1703 | if (qhi.length() > 1) |
---|
1704 | { |
---|
1705 | qhi.removeFirst(); |
---|
1706 | qhi= MyUnion (qhi, iss); |
---|
1707 | } |
---|
1708 | else |
---|
1709 | qhi= iss; |
---|
1710 | } |
---|
1711 | if (!qsi.isEmpty()) |
---|
1712 | return contract (qsi); |
---|
1713 | return ListCFList(CFList (1)) ; |
---|
1714 | } |
---|
1715 | |
---|