My Project
Loading...
Searching...
No Matches
facAlgFunc.cc
Go to the documentation of this file.
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facAlgFunc.cc
5 *
6 * This file provides functions to factorize polynomials over alg. function
7 * fields
8 *
9 * @note some of the code is code from libfac or derived from code from libfac.
10 * Libfac is written by M. Messollen. See also COPYING for license information
11 * and README for general information on characteristic sets.
12 *
13 * ABSTRACT: Descriptions can be found in B. Trager "Algebraic Factoring and
14 * Rational Function Integration" and A. Steel "Conquering Inseparability:
15 * Primary decomposition and multivariate factorization over algebraic function
16 * fields of positive characteristic"
17 *
18 * @author Martin Lee
19 *
20 **/
21/*****************************************************************************/
22
23#include "config.h"
24
25#include "cf_assert.h"
26#include "debug.h"
27
28#include "cf_generator.h"
29#include "cf_iter.h"
30#include "cf_util.h"
31#include "cf_algorithm.h"
33#include "cf_map.h"
34#include "cfModResultant.h"
35#include "cfCharSets.h"
36#include "facAlgFunc.h"
37#include "facAlgFuncUtil.h"
38
39void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
40
42alg_content (const CanonicalForm& f, const CFList& as)
43{
44 if (!f.inCoeffDomain())
45 {
46 CFIterator i= f;
47 CanonicalForm result= abs (i.coeff());
48 i++;
49 while (i.hasTerms() && !result.isOne())
50 {
51 result= alg_gcd (i.coeff(), result, as);
52 i++;
53 }
54 return result;
55 }
56
57 return abs (f);
58}
59
61alg_gcd (const CanonicalForm & fff, const CanonicalForm &ggg, const CFList &as)
62{
63 if (fff.inCoeffDomain() || ggg.inCoeffDomain())
64 return 1;
65 CanonicalForm f=fff;
66 CanonicalForm g=ggg;
67 f=Prem(f,as);
68 g=Prem(g,as);
69 if ( f.isZero() )
70 {
71 if ( g.lc().sign() < 0 ) return -g;
72 else return g;
73 }
74 else if ( g.isZero() )
75 {
76 if ( f.lc().sign() < 0 ) return -f;
77 else return f;
78 }
79
80 int v= as.getLast().level();
81 if (f.level() <= v || g.level() <= v)
82 return 1;
83
85
86 // does as appear in f and g ?
87 bool has_alg_var=false;
88 for ( CFListIterator j=as;j.hasItem(); j++ )
89 {
90 Variable v=j.getItem().mvar();
91 if (hasVar (f, v))
92 has_alg_var=true;
93 if (hasVar (g, v))
94 has_alg_var=true;
95 }
96 if (!has_alg_var)
97 {
98 /*if ((hasAlgVar(f))
99 || (hasAlgVar(g)))
100 {
101 Varlist ord;
102 for ( CFListIterator j=as;j.hasItem(); j++ )
103 ord.append(j.getItem().mvar());
104 res=algcd(f,g,as,ord);
105 }
106 else*/
107 if (!hasAlgVar (f) && !hasAlgVar (g))
108 return res=gcd(f,g);
109 }
110
111 int mvf=f.level();
112 int mvg=g.level();
113 if (mvg > mvf)
114 {
115 CanonicalForm tmp=f; f=g; g=tmp;
116 int tmp2=mvf; mvf=mvg; mvg=tmp2;
117 }
118 if (g.inBaseDomain() || f.inBaseDomain())
119 return CanonicalForm(1);
120
121 CanonicalForm c_f= alg_content (f, as);
122
123 if (mvf != mvg)
124 {
125 res= alg_gcd (g, c_f, as);
126 return res;
127 }
128 Variable x= f.mvar();
129
130 // now: mvf==mvg, f.level()==g.level()
131 CanonicalForm c_g= alg_content (g, as);
132
133 int delta= degree (f) - degree (g);
134
135 f= divide (f, c_f, as);
136 g= divide (g, c_g, as);
137
138 // gcd of contents
139 CanonicalForm c_gcd= alg_gcd (c_f, c_g, as);
140 CanonicalForm tmp;
141
142 if (delta < 0)
143 {
144 tmp= f;
145 f= g;
146 g= tmp;
147 delta= -delta;
148 }
149
150 CanonicalForm r= 1;
151
152 while (degree (g, x) > 0)
153 {
154 r= Prem (f, g);
155 r= Prem (r, as);
156 if (!r.isZero())
157 {
158 r= divide (r, alg_content (r,as), as);
159 r /= vcontent (r,Variable (v+1));
160 }
161 f= g;
162 g= r;
163 }
164
165 if (degree (g, x) == 0)
166 return c_gcd;
167
168 c_f= alg_content (f, as);
169
170 f= divide (f, c_f, as);
171
172 f *= c_gcd;
173 f /= vcontent (f, Variable (v+1));
174
175 return f;
176}
177
178static CanonicalForm
180{
181 bool on_rational = isOn(SW_RATIONAL);
182 if (!on_rational && getCharacteristic() == 0)
185 CanonicalForm fz = f * cd;
186 cd = bCommonDen( g );
187 CanonicalForm gz = g * cd;
188 if (!on_rational && getCharacteristic() == 0)
191#ifdef HAVE_NTL
192 if (getCharacteristic() == 0)
193 result= resultantZ (fz, gz,v);
194 else
195#endif
196 result= resultant (fz,gz,v);
197
198 return result;
199}
200
201/// compute the norm R of f over PPalpha, g= f (x-s*alpha)
202/// if proof==true, R is squarefree and if in addition getCharacteristic() > 0
203/// the squarefree factors of R are returned.
204/// Based on Trager's sqrf_norm algorithm.
205static CFFList
206norm (const CanonicalForm & f, const CanonicalForm & PPalpha,
207 CFGenerator & myrandom, CanonicalForm & s, CanonicalForm & g,
208 CanonicalForm & R, bool proof)
209{
210 Variable y= PPalpha.mvar(), vf= f.mvar();
211 CanonicalForm temp, Palpha= PPalpha, t;
212 int sqfreetest= 0;
213 CFFList testlist;
215
216 if (proof)
217 {
218 myrandom.reset();
219 s= myrandom.item();
220 g= f;
221 R= CanonicalForm(0);
222 }
223 else
224 {
225 if (getCharacteristic() == 0)
226 t= CanonicalForm (mapinto (myrandom.item()));
227 else
228 t= CanonicalForm (myrandom.item());
229 s= t;
230 g= f (vf - t*Palpha.mvar(), vf);
231 }
232
233 // Norm, resultante taken with respect to y
234 while (!sqfreetest)
235 {
236 R= resultante (Palpha, g, y);
237 R= R* bCommonDen(R);
238 R /= content (R);
239 if (proof)
240 {
241 // sqfree check ; R is a polynomial in K[x]
242 if (getCharacteristic() == 0)
243 {
244 temp= gcd (R, R.deriv (vf));
245 if (degree(temp,vf) != 0 || temp == temp.genZero())
246 sqfreetest= 0;
247 else
248 sqfreetest= 1;
249 }
250 else
251 {
252 Variable X;
253 testlist= sqrFree (R);
254
255 if (testlist.getFirst().factor().inCoeffDomain())
256 testlist.removeFirst();
257 sqfreetest= 1;
258 for (i= testlist; i.hasItem(); i++)
259 {
260 if (i.getItem().exp() > 1 && degree (i.getItem().factor(),R.mvar()) > 0)
261 {
262 sqfreetest= 0;
263 break;
264 }
265 }
266 }
267 if (!sqfreetest)
268 {
269 myrandom.next();
270 if (getCharacteristic() == 0)
271 t= CanonicalForm (mapinto (myrandom.item()));
272 else
273 t= CanonicalForm (myrandom.item());
274 s= t;
275 g= f (vf - t*Palpha.mvar(), vf);
276 }
277 }
278 else
279 break;
280 }
281 return testlist;
282}
283
284/// see @a norm, R is guaranteed to be squarefree
285/// Based on Trager's sqrf_norm algorithm.
286static CFFList
287sqrfNorm (const CanonicalForm & f, const CanonicalForm & PPalpha,
288 const Variable & Extension, CanonicalForm & s, CanonicalForm & g,
290{
292 if (getCharacteristic() == 0)
293 {
294 IntGenerator myrandom;
295 result= norm (f, PPalpha, myrandom, s, g, R, true);
296 }
297 else if (degree (Extension) > 0)
298 {
299 AlgExtGenerator myrandom (Extension);
300 result= norm (f, PPalpha, myrandom, s, g, R, true);
301 }
302 else
303 {
304 FFGenerator myrandom;
305 result= norm (f, PPalpha, myrandom, s, g, R, true);
306 }
307 return result;
308}
309
310// calculate a "primitive element"
311// K must have more than S elements (-> getDegOfExt)
312static CFList
314 const Variable & Extension, bool& isFunctionField,
316{
317 CFList Returnlist, Bstar= Astar;
318 CanonicalForm s, g, ra, rb, oldR, h, denra, denrb= 1;
320 CFList tmp;
321
322 bool isRat= isOn (SW_RATIONAL);
323
325 if (Astar.length() == 1)
326 {
327 R= Astar.getFirst();
328 rb= R.mvar();
329 Returnlist.append (rb);
330 if (isFunctionField)
331 Returnlist.append (denrb);
332 }
333 else
334 {
335 R=Bstar.getFirst();
336 Bstar.removeFirst();
337 for (CFListIterator i= Bstar; i.hasItem(); i++)
338 {
339 j= i;
340 j++;
341 if (getCharacteristic() == 0)
343 R /= icontent (R);
344 if (getCharacteristic() == 0)
345 On (SW_RATIONAL);
346 oldR= R;
347 //TODO normalize i.getItem over K(R)?
348 (void) sqrfNorm (i.getItem(), R, Extension, s, g, R);
349
350 backSubst.insert (s);
351
352 if (getCharacteristic() == 0)
354 R /= icontent (R);
355
356 if (getCharacteristic() == 0)
357 On (SW_RATIONAL);
358
359 if (!isFunctionField)
360 {
361 alpha= rootOf (R);
362 h= replacevar (g, g.mvar(), alpha);
363 if (getCharacteristic() == 0)
364 On (SW_RATIONAL); //needed for GCD
365 h= gcd (h, oldR);
366 h /= Lc (h);
367 ra= -h[0];
368 ra= replacevar(ra, alpha, g.mvar());
369 rb= R.mvar()-s*ra;
370 for (; j.hasItem(); j++)
371 {
372 j.getItem()= j.getItem() (rb, i.getItem().mvar());
373 j.getItem()= j.getItem() (ra, oldR.mvar());
374 }
375 prune (alpha);
376 }
377 else
378 {
379 if (getCharacteristic() == 0)
380 On (SW_RATIONAL);
381 Variable v= Variable (tmax (g.level(), oldR.level()) + 1);
382 h= swapvar (g, oldR.mvar(), v);
383 tmp= CFList (R);
384 h= alg_gcd (h, swapvar (oldR, oldR.mvar(), v), tmp);
385
386 CanonicalForm numinv, deninv;
387 numinv= QuasiInverse (tmp.getFirst(), LC (h), tmp.getFirst().mvar());
388 h *= numinv;
389 h= Prem (h, tmp);
390 deninv= LC(h);
391
392 ra= -h[0];
393 denra= gcd (ra, deninv);
394 ra /= denra;
395 denra= deninv/denra;
396 rb= R.mvar()*denra-s*ra;
397 denrb= denra;
398 for (; j.hasItem(); j++)
399 {
400 CanonicalForm powdenra= power (denra, degree (j.getItem(),
401 i.getItem().mvar()));
402 j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra,
403 i.getItem().mvar());
404 powdenra= power (denra, degree (j.getItem(), oldR.mvar()));
405 j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());
406
407 }
408 }
409
410 Returnlist.append (ra);
411 if (isFunctionField)
412 Returnlist.append (denra);
413 Returnlist.append (rb);
414 if (isFunctionField)
415 Returnlist.append (denrb);
416 }
417 }
418
419 if (isRat && getCharacteristic() == 0)
420 On (SW_RATIONAL);
421 else if (!isRat && getCharacteristic() == 0)
423
424 return Returnlist;
425}
426
427/// Trager's algorithm, i.e. convert to one field extension and
428/// factorize over this field extension
429static CFFList
430Trager (const CanonicalForm & F, const CFList & Astar,
431 const Variable & vminpoly, const CFList & as, bool isFunctionField)
432{
433 bool isRat= isOn (SW_RATIONAL);
434 CFFList L, normFactors, tmp;
435 CFFListIterator iter, iter2;
436 CanonicalForm R, Rstar, s, g, h, f= F;
437 CFList substlist, backSubsts;
438
439 substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
440 Rstar);
441
442 f= subst (f, Astar, substlist, Rstar, isFunctionField);
443
445 if (!isFunctionField)
446 {
447 alpha= rootOf (Rstar);
448 g= replacevar (f, Rstar.mvar(), alpha);
449
450 if (!isRat && getCharacteristic() == 0)
451 On (SW_RATIONAL);
452 tmp= factorize (g, alpha); // factorization over number field
453
454 for (iter= tmp; iter.hasItem(); iter++)
455 {
456 h= iter.getItem().factor();
457 if (!h.inCoeffDomain())
458 {
459 h= replacevar (h, alpha, Rstar.mvar());
460 h *= bCommonDen(h);
461 h= backSubst (h, backSubsts, Astar);
462 h= Prem (h, as);
463 L.append (CFFactor (h, iter.getItem().exp()));
464 }
465 }
466 if (!isRat && getCharacteristic() == 0)
468 prune (alpha);
469 return L;
470 }
471 // after here we are over an extension of a function field
472
473 // make quasi monic
474 CFList Rstarlist= CFList (Rstar);
475 int algExtLevel= Astar.getLast().level(); //highest level of algebraic variables
476 CanonicalForm numinv;
477 if (!isRat && getCharacteristic() == 0)
478 On (SW_RATIONAL);
479 numinv= QuasiInverse (Rstar, alg_LC (f, algExtLevel), Rstar.mvar());
480
481 f *= numinv;
482 f= Prem (f, Rstarlist);
483 f /= vcontent (f, Rstar.mvar());
484 // end quasi monic
485
486 if (degree (f) == 1)
487 {
488 f= backSubst (f, backSubsts, Astar);
489 f *= bCommonDen (f);
490 f= Prem (f, as);
491 f /= vcontent (f, as.getFirst().mvar());
492
493 return CFFList (CFFactor (f, 1));
494 }
495
496 CFGenerator * Gen;
497 if (getCharacteristic() == 0)
499 else if (degree (vminpoly) > 0)
500 Gen= AlgExtGenerator (vminpoly).clone();
501 else
503
504 CFFList LL= CFFList (CFFactor (f, 1));
505
506 Variable X;
507 do
508 {
509 tmp= CFFList();
510 for (iter= LL; iter.hasItem(); iter++)
511 {
512 f= iter.getItem().factor();
513 (void) norm (f, Rstar, *Gen, s, g, R, false);
514
515 if (hasFirstAlgVar (R, X))
516 normFactors= factorize (R, X);
517 else
518 normFactors= factorize (R);
519
520 if (normFactors.getFirst().factor().inCoeffDomain())
521 normFactors.removeFirst();
522 if (normFactors.length() < 1 || (normFactors.length() == 1 && normFactors.getLast().exp() == 1))
523 {
524 f= backSubst (f, backSubsts, Astar);
525 f *= bCommonDen (f);
526 f= Prem (f, as);
527 f /= vcontent (f, as.getFirst().mvar());
528
529 L.append (CFFactor (f, 1));
530 }
531 else
532 {
533 g= f;
534 int count= 0;
535 for (iter2= normFactors; iter2.hasItem(); iter2++)
536 {
537 CanonicalForm fnew= iter2.getItem().factor();
538 if (fnew.level() <= Rstar.level()) //factor is a constant from the function field
539 continue;
540 else
541 {
542 fnew= fnew (g.mvar() + s*Rstar.mvar(), g.mvar());
543 fnew= Prem (fnew, CFList (Rstar));
544 }
545
546 h= alg_gcd (g, fnew, Rstarlist);
547 numinv= QuasiInverse (Rstar, alg_LC (h, algExtLevel), Rstar.mvar());
548 h *= numinv;
549 h= Prem (h, Rstarlist);
550 h /= vcontent (h, Rstar.mvar());
551
552 if (h.level() > Rstar.level())
553 {
554 g= divide (g, h, Rstarlist);
555 if (degree (h) == 1 || iter2.getItem().exp() == 1)
556 {
557 h= backSubst (h, backSubsts, Astar);
558 h= Prem (h, as);
559 h *= bCommonDen (h);
560 h /= vcontent (h, as.getFirst().mvar());
561 L.append (CFFactor (h, 1));
562 }
563 else
564 tmp.append (CFFactor (h, iter2.getItem().exp()));
565 }
566 count++;
567 if (g.level() <= Rstar.level())
568 break;
569 if (count == normFactors.length() - 1)
570 {
571 if (normFactors.getLast().exp() == 1 && g.level() > Rstar.level())
572 {
573 g= backSubst (g, backSubsts, Astar);
574 g= Prem (g, as);
575 g *= bCommonDen (g);
576 g /= vcontent (g, as.getFirst().mvar());
577 L.append (CFFactor (g, 1));
578 }
579 else if (normFactors.getLast().exp() > 1 &&
580 g.level() > Rstar.level())
581 {
582 g /= vcontent (g, Rstar.mvar());
583 tmp.append (CFFactor (g, normFactors.getLast().exp()));
584 }
585 break;
586 }
587 }
588 }
589 }
590 LL= tmp;
591 (*Gen).next();
592 }
593 while (!LL.isEmpty());
594
595 if (!isRat && getCharacteristic() == 0)
597
598 delete Gen;
599
600 return L;
601}
602
603
604/// map elements in @a AS into a PIE \f$ L \f$ and record where the variables
605/// are mapped to in @a varsMapLevel, i.e @a varsMapLevel contains a list of
606/// pairs of variables \f$ v_i \f$ and integers \f$ e_i \f$ such that
607/// \f$ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) \f$
608CFList
609mapIntoPIE (CFFList& varsMapLevel, CanonicalForm& lcmVars, const CFList & AS)
610{
611 CanonicalForm varsG;
612 int j, exp= 0, tmpExp;
613 bool recurse= false;
614 CFList asnew, as= AS;
615 CFListIterator i= as, ii;
616 CFFList varsGMapLevel, tmp;
618 CFFList * varsGMap= new CFFList [as.length()];
619 for (j= 0; j < as.length(); j++)
620 varsGMap[j]= CFFList();
621 j= 0;
622 while (i.hasItem())
623 {
624 if (i.getItem().deriv() == 0)
625 {
626 deflateDegree (i.getItem(), exp, i.getItem().level());
627 i.getItem()= deflatePoly (i.getItem(), exp, i.getItem().level());
628
629 varsG= getVars (i.getItem());
630 varsG /= i.getItem().mvar();
631
632 lcmVars= lcm (varsG, lcmVars);
633
634 while (!varsG.isOne())
635 {
636 if (i.getItem().deriv (varsG.level()).isZero())
637 {
638 deflateDegree (i.getItem(), tmpExp, varsG.level());
639 if (exp >= tmpExp)
640 {
641 if (exp == tmpExp)
642 i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
643 else
644 {
645 if (j != 0)
646 recurse= true;
647 i.getItem()= deflatePoly (i.getItem(), tmpExp, varsG.level());
648 }
649 varsGMapLevel.insert (CFFactor (varsG.mvar(), exp - tmpExp));
650 }
651 else
652 {
653 i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
654 varsGMapLevel.insert (CFFactor (varsG.mvar(), 0));
655 }
656 }
657 else
658 {
659 if (j != 0)
660 recurse= true;
661 varsGMapLevel.insert (CFFactor (varsG.mvar(),exp));
662 }
663 varsG /= varsG.mvar();
664 }
665
666 if (recurse)
667 {
668 ii= as;
669 for (; ii.hasItem(); ii++)
670 {
671 if (ii.getItem() == i.getItem())
672 continue;
673 for (iter= varsGMapLevel; iter.hasItem(); iter++)
674 ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
675 iter.getItem().factor().level());
676 }
677 }
678 else
679 {
680 ii= i;
681 ii++;
682 for (; ii.hasItem(); ii++)
683 {
684 for (iter= varsGMapLevel; iter.hasItem(); iter++)
685 {
686 ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
687 iter.getItem().factor().level());
688 }
689 }
690 }
691 if (varsGMap[j].isEmpty())
692 varsGMap[j]= varsGMapLevel;
693 else
694 {
695 if (!varsGMapLevel.isEmpty())
696 {
697 tmp= varsGMap[j];
698 CFFListIterator iter2= varsGMapLevel;
699 ASSERT (tmp.length() == varsGMapLevel.length(),
700 "wrong length of lists");
701 for (iter=tmp; iter.hasItem(); iter++, iter2++)
702 iter.getItem()= CFFactor (iter.getItem().factor(),
703 iter.getItem().exp() + iter2.getItem().exp());
704 varsGMap[j]= tmp;
705 }
706 }
707 varsGMapLevel= CFFList();
708 }
709 asnew.append (i.getItem());
710 if (!recurse)
711 {
712 i++;
713 j++;
714 }
715 else
716 {
717 i= as;
718 j= 0;
719 recurse= false;
720 asnew= CFList();
721 }
722 }
723
724 while (!lcmVars.isOne())
725 {
726 varsMapLevel.insert (CFFactor (lcmVars.mvar(), 0));
727 lcmVars /= lcmVars.mvar();
728 }
729
730 for (j= 0; j < as.length(); j++)
731 {
732 if (varsGMap[j].isEmpty())
733 continue;
734
735 for (CFFListIterator iter2= varsGMap[j]; iter2.hasItem(); iter2++)
736 {
737 for (iter= varsMapLevel; iter.hasItem(); iter++)
738 {
739 if (iter.getItem().factor() == iter2.getItem().factor())
740 {
741 iter.getItem()= CFFactor (iter.getItem().factor(),
742 iter.getItem().exp() + iter2.getItem().exp());
743 }
744 }
745 }
746 }
747
748 delete [] varsGMap;
749
750 return asnew;
751}
752
753/// algorithm of A. Steel described in "Conquering Inseparability: Primary
754/// decomposition and multivariate factorization over algebraic function fields
755/// of positive characteristic" with the following modifications: we use
756/// characteristic sets in IdealOverSubfield and Trager's primitive element
757/// algorithm instead of FGLM
759SteelTrager (const CanonicalForm & f, const CFList & AS)
760{
761 CanonicalForm F= f, lcmVars= 1;
762 CFList asnew, as= AS;
763 CFListIterator i, ii;
764
765 bool derivZeroF= false;
766 int j, expF= 0, tmpExp;
767 CFFList varsMapLevel, tmp;
769
770 // check if F is separable
771 if (F.deriv().isZero())
772 {
773 derivZeroF= true;
774 deflateDegree (F, expF, F.level());
775 }
776
777 CanonicalForm varsF= getVars (F);
778 varsF /= F.mvar();
779
780 lcmVars= lcm (varsF, lcmVars);
781
782 if (derivZeroF)
783 as.append (F);
784
785 asnew= mapIntoPIE (varsMapLevel, lcmVars, as);
786
787 if (derivZeroF)
788 {
789 asnew.removeLast();
790 F= deflatePoly (F, expF, F.level());
791 }
792
793 // map variables in F
794 for (iter= varsMapLevel; iter.hasItem(); iter++)
795 {
796 if (expF > 0)
797 tmpExp= iter.getItem().exp() - expF;
798 else
799 tmpExp= iter.getItem().exp();
800
801 if (tmpExp > 0)
802 F= inflatePoly (F, tmpExp, iter.getItem().factor().level());
803 else if (tmpExp < 0)
804 F= deflatePoly (F, -tmpExp, iter.getItem().factor().level());
805 }
806
807 // factor F with minimal polys given in asnew
808 asnew.append (F);
809 asnew= charSetViaModCharSet (asnew, false);
810
811 F= asnew.getLast();
812 F /= content (F);
813
814 asnew.removeLast();
815 for (i= asnew; i.hasItem(); i++)
816 i.getItem() /= content (i.getItem());
817
818 tmp= facAlgFunc (F, asnew);
819
820 // transform back
821 j= 0;
822 int p= getCharacteristic();
823 CFList transBack;
824 CFMap M;
826
827 for (iter= varsMapLevel; iter.hasItem(); iter++)
828 {
829 if (iter.getItem().exp() > 0)
830 {
831 j++;
832 g= power (Variable (f.level() + j), ipower (p, iter.getItem().exp())) -
833 iter.getItem().factor().mvar();
834 transBack.append (g);
835 M.newpair (iter.getItem().factor().mvar(), Variable (f.level() + j));
836 }
837 }
838
839 for (i= asnew; i.hasItem(); i++)
840 transBack.insert (M (i.getItem()));
841
842 if (expF > 0)
843 tmpExp= ipower (p, expF);
844
846 CFList transform;
847
848 bool found;
849 for (iter= tmp; iter.hasItem(); iter++)
850 {
851 found= false;
852 transform= transBack;
853 CanonicalForm factor= iter.getItem().factor();
854 factor= M (factor);
855 transform.append (factor);
856 transform= modCharSet (transform, false);
857
858retry:
859 if (transform.isEmpty())
860 {
861 transform= transBack;
862 transform.append (factor);
863 transform= charSetViaCharSetN (transform);
864 }
865 for (i= transform; i.hasItem(); i++)
866 {
867 if (degree (i.getItem(), f.mvar()) > 0)
868 {
869 if (i.getItem().level() > f.level())
870 break;
871 found= true;
872 factor= i.getItem();
873 break;
874 }
875 }
876
877 if (!found)
878 {
879 found= false;
880 transform= CFList();
881 goto retry;
882 }
883
884 factor /= content (factor);
885
886 if (expF > 0)
887 {
888 int mult= tmpExp/(degree (factor)/degree (iter.getItem().factor()));
889 result.append (CFFactor (factor, iter.getItem().exp()*mult));
890 }
891 else
892 result.append (CFFactor (factor, iter.getItem().exp()));
893 }
894
895 return result;
896}
897
898/// factorize a polynomial that is irreducible over the ground field modulo an
899/// extension given by an irreducible characteristic set
900
901// 1) prepares data
902// 2) for char=p we distinguish 3 cases:
903// no transcendentals, separable and inseparable extensions
905facAlgFunc2 (const CanonicalForm & f, const CFList & as)
906{
907 bool isRat= isOn (SW_RATIONAL);
908 if (!isRat && getCharacteristic() == 0)
909 On (SW_RATIONAL);
910 Variable vf=f.mvar();
913 CFList reduceresult;
915
916// F1: [Test trivial cases]
917// 1) first trivial cases:
918 if (vf.level() <= as.getLast().level())
919 {
920 if (!isRat && getCharacteristic() == 0)
922 return CFFList(CFFactor(f,1));
923 }
924
925// 2) Setup list of those polys in AS having degree > 1
926 CFList Astar;
927 Variable x;
928 CanonicalForm elem;
929 Varlist ord, uord;
930 for (int ii= 1; ii < level (vf); ii++)
931 uord.append (Variable (ii));
932
933 for (i= as; i.hasItem(); i++)
934 {
935 elem= i.getItem();
936 x= elem.mvar();
937 if (degree (elem, x) > 1) // otherwise it's not an extension
938 {
939 Astar.append (elem);
940 ord.append (x);
941 }
942 }
943 uord= Difference (uord, ord);
944
945// 3) second trivial cases: we already proved irr. of f over no extensions
946 if (Astar.length() == 0)
947 {
948 if (!isRat && getCharacteristic() == 0)
950 return CFFList (CFFactor (f, 1));
951 }
952
953// 4) Look if elements in uord actually occur in any of the minimal
954// polynomials. If no element of uord occures in any of the minimal
955// polynomials the field is an alg. number field not an alg. function field
956 Varlist newuord= varsInAs (uord, Astar);
957
958 CFFList Factorlist;
959 Varlist gcdord= Union (ord, newuord);
960 gcdord.append (f.mvar());
961 bool isFunctionField= (newuord.length() > 0);
962
963 // TODO alg_sqrfree?
964 CanonicalForm Fgcd= 0;
965 if (isFunctionField)
966 Fgcd= alg_gcd (f, f.deriv(), Astar);
967
968 bool derivZero= f.deriv().isZero();
969 if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
970 {
971 CanonicalForm Ggcd= divide(f, Fgcd,Astar);
972 if (getCharacteristic() == 0)
973 {
974 CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
975 multiplicity (result, f, Astar);
976 if (!isRat && getCharacteristic() == 0)
978 return result;
979 }
980
981 Fgcd= pp (Fgcd);
982 Ggcd= pp (Ggcd);
983 if (!isRat && getCharacteristic() == 0)
985 return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
986 }
987
988 if (getCharacteristic() > 0)
989 {
990 IntList degreelist;
991 Variable vminpoly;
992 for (i= Astar; i.hasItem(); i++)
993 degreelist.append (degree (i.getItem()));
994
995 int extdeg= getDegOfExt (degreelist, degree (f));
996
997 if (newuord.length() == 0) // no parameters
998 {
999 if (extdeg > 1)
1000 {
1001 CanonicalForm MIPO= generateMipo (extdeg);
1002 vminpoly= rootOf(MIPO);
1003 }
1004 Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
1005 if (extdeg > 1)
1006 prune (vminpoly);
1007 return Factorlist;
1008 }
1009 else if (isInseparable(Astar) || derivZero) // inseparable case
1010 {
1011 Factorlist= SteelTrager (f, Astar);
1012 return Factorlist;
1013 }
1014 else // separable case
1015 {
1016 if (extdeg > 1)
1017 {
1018 CanonicalForm MIPO=generateMipo (extdeg);
1019 vminpoly= rootOf (MIPO);
1020 }
1021 Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1022 if (extdeg > 1)
1023 prune (vminpoly);
1024 return Factorlist;
1025 }
1026 }
1027 else // char 0
1028 {
1029 Variable vminpoly;
1030 Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1031 if (!isRat && getCharacteristic() == 0)
1032 Off (SW_RATIONAL);
1033 return Factorlist;
1034 }
1035
1036 return CFFList (CFFactor(f,1));
1037}
1038
1039
1040/// factorize a polynomial modulo an extension given by an irreducible
1041/// characteristic set
1042CFFList
1043facAlgFunc (const CanonicalForm & f, const CFList & as)
1044{
1045 bool isRat= isOn (SW_RATIONAL);
1046 if (!isRat && getCharacteristic() == 0)
1047 On (SW_RATIONAL);
1048 CFFList Output, output, Factors= factorize(f);
1049 if (Factors.getFirst().factor().inCoeffDomain())
1050 Factors.removeFirst();
1051
1052 if (as.length() == 0)
1053 {
1054 if (!isRat && getCharacteristic() == 0)
1055 Off (SW_RATIONAL);
1056 return Factors;
1057 }
1058 if (f.level() <= as.getLast().level())
1059 {
1060 if (!isRat && getCharacteristic() == 0)
1061 Off (SW_RATIONAL);
1062 return Factors;
1063 }
1064
1065 for (CFFListIterator i=Factors; i.hasItem(); i++)
1066 {
1067 if (i.getItem().factor().level() > as.getLast().level())
1068 {
1069 output= facAlgFunc2 (i.getItem().factor(), as);
1070 for (CFFListIterator j= output; j.hasItem(); j++)
1071 Output= append (Output, CFFactor (j.getItem().factor(),
1072 j.getItem().exp()*i.getItem().exp()));
1073 }
1074 }
1075
1076 if (!isRat && getCharacteristic() == 0)
1077 Off (SW_RATIONAL);
1078 return Output;
1079}
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
int degree(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
CanonicalForm FACTORY_PUBLIC vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:653
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
int level(const CanonicalForm &f)
List< CanonicalForm > CFList
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition: cfCharSets.cc:356
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition: cfCharSets.cc:284
This file provides functions to compute characteristic sets.
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:2031
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4089
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
modular resultant algorithm as described by G.
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:957
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
generate integers, elements of finite fields
Iterators for CanonicalForm's.
map polynomials
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
FILE * f
Definition: checklibs.c:9
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:94
CFGenerator * clone() const
static CFGenerator * generate()
virtual class for generators
Definition: cf_generator.h:22
virtual CanonicalForm item() const
Definition: cf_generator.h:28
virtual void next()
Definition: cf_generator.h:29
virtual void reset()
Definition: cf_generator.h:27
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
CanonicalForm genZero() const
input/output
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
generate all elements in F_p starting from 0
Definition: cf_generator.h:56
generate integers starting from 0
Definition: cf_generator.h:37
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
T getLast() const
Definition: ftmpl_list.cc:309
void insert(const T &)
Definition: ftmpl_list.cc:193
int isEmpty() const
Definition: ftmpl_list.cc:267
void removeLast()
Definition: ftmpl_list.cc:317
factory's class for variables
Definition: variable.h:33
int level() const
Definition: variable.h:49
functions to print debug output
CFFListIterator iter
Definition: facAbsBiFact.cc:53
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
CanonicalForm res
Definition: facAbsFact.cc:60
CanonicalForm factor
Definition: facAbsFact.cc:97
mipo *CanonicalForm norm
Definition: facAlgExt.cc:61
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
int hasVar(const CanonicalForm &f, const Variable &v)
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
int hasAlgVar(const CanonicalForm &f, const Variable &v)
int getDegOfExt(IntList &degreelist, int n)
bool isInseparable(const CFList &Astar)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm generateMipo(int degOfExt)
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
Utility functions for factorization over algebraic function fields.
static CFFList sqrfNorm(const CanonicalForm &f, const CanonicalForm &PPalpha, const Variable &Extension, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R)
see norm, R is guaranteed to be squarefree Based on Trager's sqrf_norm algorithm.
Definition: facAlgFunc.cc:287
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759
static CFFList Trager(const CanonicalForm &F, const CFList &Astar, const Variable &vminpoly, const CFList &as, bool isFunctionField)
Trager's algorithm, i.e. convert to one field extension and factorize over this field extension.
Definition: facAlgFunc.cc:430
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
Definition: facAlgFunc.cc:313
CFList mapIntoPIE(CFFList &varsMapLevel, CanonicalForm &lcmVars, const CFList &AS)
map elements in AS into a PIE and record where the variables are mapped to in varsMapLevel,...
Definition: facAlgFunc.cc:609
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial modulo an extension given by an irreducible characteristic set
Definition: facAlgFunc.cc:1043
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irre...
Definition: facAlgFunc.cc:905
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:99
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
Definition: facAlgFunc.cc:179
Factorization over algebraic function fields.
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
bool found
Definition: facFactorize.cc:55
CFList tmp2
Definition: facFqBivar.cc:72
int j
Definition: facHensel.cc:110
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
STATIC_VAR int * multiplicity
STATIC_VAR Poly * h
Definition: janet.cc:971
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
int status int void size_t count
Definition: si_signals.h:59
#define R
Definition: sirandom.c:27
#define M
Definition: sirandom.c:25
void prune(Variable &alpha)
Definition: variable.cc:261
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
int gcd(int a, int b)
Definition: walkSupport.cc:836