My Project
Loading...
Searching...
No Matches
facFactorize.cc
Go to the documentation of this file.
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFactorize.cc
5 *
6 * multivariate factorization over Q(a)
7 *
8 * @author Martin Lee
9 *
10 **/
11/*****************************************************************************/
12
13
14#include "config.h"
15
16
17#include "cf_assert.h"
18#include "debug.h"
19#include "timing.h"
20
21#include "cf_algorithm.h"
22#include "facFqFactorizeUtil.h"
23#include "facFactorize.h"
24#include "facFqFactorize.h"
25#include "cf_random.h"
26#include "facHensel.h"
27#include "cf_map_ext.h"
28#include "cf_reval.h"
29#include "facSparseHensel.h"
30#include "cfUnivarGcd.h"
31
32TIMING_DEFINE_PRINT(fac_bi_factorizer)
33TIMING_DEFINE_PRINT(fac_hensel_lift)
34TIMING_DEFINE_PRINT(fac_factor_recombination)
35TIMING_DEFINE_PRINT(fac_shift_to_zero)
36TIMING_DEFINE_PRINT(fac_precompute_leadcoeff)
37TIMING_DEFINE_PRINT(fac_evaluation)
38TIMING_DEFINE_PRINT(fac_recover_factors)
39TIMING_DEFINE_PRINT(fac_preprocess_and_content)
40TIMING_DEFINE_PRINT(fac_bifactor_total)
41TIMING_DEFINE_PRINT(fac_luckswang)
42TIMING_DEFINE_PRINT(fac_lcheuristic)
43TIMING_DEFINE_PRINT(fac_cleardenom)
44TIMING_DEFINE_PRINT(fac_content)
45TIMING_DEFINE_PRINT(fac_compress)
46
48{
51
54
55 bool found= false;
56 bool allZero= true;
57 bool foundZero= false;
60 do
61 {
62 eval.insert (F);
64 bool bad= false;
65 for (int i= E.max(); i >= E.min(); i--)
66 {
67 eval.insert (eval.getFirst()( E [i], i));
69 result.append (E[i]);
70 if (!E[i].isZero())
71 allZero= false;
72 else
73 foundZero= true;
74 if (!allZero && foundZero)
75 {
76 result= CFList();
77 eval= CFList();
78 LCFeval= CFList();
79 bad= true;
80 foundZero= false;
81 break;
82 }
83 if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
84 {
85 result= CFList();
86 eval= CFList();
87 LCFeval= CFList();
88 bad= true;
89 break;
90 }
91 if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
92 {
93 result= CFList();
94 eval= CFList();
95 LCFeval= CFList();
96 bad= true;
97 break;
98 }
99 }
100
101 if (bad)
102 {
103 E.nextpoint();
104 continue;
105 }
106
107 if (degree (eval.getFirst()) != degree (F, 1))
108 {
109 result= CFList();
110 eval= CFList();
111 LCFeval= CFList();
112 E.nextpoint();
113 continue;
114 }
115
118 if (degree (gcd_deriv) > 0)
119 {
120 result= CFList();
121 eval= CFList();
122 LCFeval= CFList();
123 E.nextpoint();
124 continue;
125 }
126 iter= eval;
127 iter++;
129 if (degree (contentx) > 0)
130 {
131 result= CFList();
132 eval= CFList();
133 LCFeval= CFList();
134 E.nextpoint();
135 continue;
136 }
138 if (degree (contentx) > 0)
139 {
140 result= CFList();
141 eval= CFList();
142 LCFeval= CFList();
143 E.nextpoint();
144 continue;
145 }
146 found= true;
147 }
148 while (!found);
149
150 if (!eval.isEmpty())
152 return result;
153}
154
155
156#if defined(HAVE_NTL) || defined(HAVE_FLINT) // ratBiSqrfFactorize
157void
159 int& minFactorsLength, bool& irred,
160 const Variable& w)
161{
162 Variable x= Variable (1);
164 irred= false;
165 Variable v;
166 CFList factors;
167 CanonicalForm LCA= LC (A,1);
168 for (int j= 0; j < A.level() - 2; j++)
169 {
170 if (!Aeval[j].isEmpty())
171 {
172 v= Variable (Aeval[j].getFirst().level());
173
174 factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
175 if (factors.getFirst().inCoeffDomain())
176 factors.removeFirst();
177
178 if (minFactorsLength == 0)
179 minFactorsLength= factors.length();
180 else
182
183 if (factors.length() == 1)
184 {
185 irred= true;
186 return;
187 }
188 sortList (factors, x);
189 Aeval [j]= factors;
190 }
191 }
192}
193#endif
194
195#if defined(HAVE_NTL) || defined(HAVE_FLINT) // precomputeLeadingCoeff,
196// henselLiftAndEarly, nonMonicHenselLift
197CFList
199{
200 if (F.inCoeffDomain())
201 return CFList (F);
202
203 TIMING_START (fac_preprocess_and_content);
204 // compress and find main Variable
205 CFMap N;
206 TIMING_START (fac_compress)
208 TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
209
210 //univariate case
211 if (F.isUnivariate())
212 {
214 if (v.level() != 1)
215 result= conv (factorize (F, v));
216 else
217 result= conv (factorize (F,true));
218 if (result.getFirst().inCoeffDomain())
219 result.removeFirst();
220 return result;
221 }
222
223 //bivariate case
224 if (A.level() == 2)
225 {
227 if (buf.getFirst().inCoeffDomain())
228 buf.removeFirst();
229 return buf;
230 }
231
232 Variable x= Variable (1);
233 Variable y= Variable (2);
234
235 // remove content
236 TIMING_START (fac_content);
237 CFList contentAi;
238 CanonicalForm lcmCont= lcmContent (A, contentAi);
239 A /= lcmCont;
240 TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
241
242 // trivial after content removal
243 CFList contentAFactors;
244 if (A.inCoeffDomain())
245 {
246 for (CFListIterator i= contentAi; i.hasItem(); i++)
247 {
248 if (i.getItem().inCoeffDomain())
249 continue;
250 else
251 {
252 lcmCont /= i.getItem();
253 contentAFactors=
254 Union (multiFactorize (lcmCont, v),
255 multiFactorize (i.getItem(), v));
256 break;
257 }
258 }
259 decompress (contentAFactors, N);
260 if (isOn (SW_RATIONAL))
261 normalize (contentAFactors);
262 return contentAFactors;
263 }
264
265 // factorize content
266 TIMING_START (fac_content);
267 contentAFactors= multiFactorize (lcmCont, v);
268 TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
269
270 // univariate after content removal
271 CFList factors;
272 if (A.isUnivariate ())
273 {
274 if (v.level() != 1)
275 factors= conv (factorize (A, v));
276 else
277 factors= conv (factorize (A,true));
278 append (factors, contentAFactors);
279 decompress (factors, N);
280 return factors;
281 }
282
283 A *= bCommonDen (A);
284 CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
285 int factorNums= 2;
286 //p is irreducible. But factorize does not recognizes this. However, if you
287 //change factorNums to 2 at line 281 in facFactorize.cc it will. That change
288 //might impair performance in some cases since you do twice as many
289 //bivariate factorizations as before. Otherwise you need to change
290 //precomputeLeadingCoeff to detect these cases and trigger more bivariate
291 // factorizations.
292 // (http://www.singular.uni-kl.de:8002/trac/ticket/666)
293 CFList biFactors, bufBiFactors;
294 CanonicalForm evalPoly;
295 int lift, bufLift, lengthAeval2= A.level()-2;
296 CFList* bufAeval2= new CFList [lengthAeval2];
297 CFList* Aeval2= new CFList [lengthAeval2];
298 int counter;
299 int differentSecondVar= 0;
300 CanonicalForm bufA;
301 TIMING_END_AND_PRINT (fac_preprocess_and_content,
302 "time to preprocess poly and extract content over Q: ");
303
304 // several bivariate factorizations
305 TIMING_START (fac_bifactor_total);
306 REvaluation E (2, A.level(), IntRandom (25));
307 for (int i= 0; i < factorNums; i++)
308 {
309 counter= 0;
310 bufA= A;
311 bufAeval= CFList();
312 TIMING_START (fac_evaluation);
313 bufEvaluation= evalPoints (bufA, bufAeval, E);
314 TIMING_END_AND_PRINT (fac_evaluation,
315 "time to find evaluation point over Q: ");
316 E.nextpoint();
317 evalPoly= 0;
318
319 TIMING_START (fac_evaluation);
320 evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
321 TIMING_END_AND_PRINT (fac_evaluation,
322 "time to eval wrt diff second vars over Q: ");
323
324 for (int j= 0; j < lengthAeval2; j++)
325 {
326 if (!bufAeval2[j].isEmpty())
327 counter++;
328 }
329
330 bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
331
332 TIMING_START (fac_bi_factorizer);
333 bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
334 TIMING_END_AND_PRINT (fac_bi_factorizer,
335 "time for bivariate factorization: ");
336 bufBiFactors.removeFirst();
337
338 if (bufBiFactors.length() == 1)
339 {
340 factors.append (A);
341 appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
342 if (isOn (SW_RATIONAL))
343 normalize (factors);
344 delete [] bufAeval2;
345 delete [] Aeval2;
346 return factors;
347 }
348
349 if (i == 0)
350 {
351 Aeval= bufAeval;
352 evaluation= bufEvaluation;
353 biFactors= bufBiFactors;
354 lift= bufLift;
355 for (int j= 0; j < lengthAeval2; j++)
356 Aeval2 [j]= bufAeval2 [j];
357 differentSecondVar= counter;
358 }
359 else
360 {
361 if (bufBiFactors.length() < biFactors.length() ||
362 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
363 counter > differentSecondVar)
364 {
365 Aeval= bufAeval;
366 evaluation= bufEvaluation;
367 biFactors= bufBiFactors;
368 lift= bufLift;
369 for (int j= 0; j < lengthAeval2; j++)
370 Aeval2 [j]= bufAeval2 [j];
371 differentSecondVar= counter;
372 }
373 }
374 int k= 0;
375 for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
376 evalPoly += j.getItem()*power (x, k);
377 list.append (evalPoly);
378 }
379
380 delete [] bufAeval2;
381
382 sortList (biFactors, x);
383
385 bool irred= false;
386 TIMING_START (fac_bi_factorizer);
388 TIMING_END_AND_PRINT (fac_bi_factorizer,
389 "time for bivariate factorization wrt diff second vars over Q: ");
390
391 TIMING_END_AND_PRINT (fac_bifactor_total,
392 "total time for eval and bivar factors over Q: ");
393 if (irred)
394 {
395 factors.append (A);
396 appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
397 if (isOn (SW_RATIONAL))
398 normalize (factors);
399 delete [] Aeval2;
400 return factors;
401 }
402
403 if (minFactorsLength == 0)
404 minFactorsLength= biFactors.length();
405 else if (biFactors.length() > minFactorsLength)
406 refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
408
409 CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
410
411 sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
412
414
415 if (minFactorsLength == 1)
416 {
417 factors.append (A);
418 appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
419 if (isOn (SW_RATIONAL))
420 normalize (factors);
421 delete [] Aeval2;
422 return factors;
423 }
424
425 if (differentSecondVar == lengthAeval2)
426 {
427 bool zeroOccured= false;
429 {
430 if (iter.getItem().isZero())
431 {
432 zeroOccured= true;
433 break;
434 }
435 }
436 if (!zeroOccured)
437 {
438 factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
440 if (factors.length() == biFactors.length())
441 {
442 appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
443 normalize (factors);
444 delete [] Aeval2;
445 return factors;
446 }
447 else
448 factors= CFList();
449 //TODO case where factors.length() > 0
450 }
451 }
452
453 CFList * oldAeval= new CFList [lengthAeval2];
454 for (int i= 0; i < lengthAeval2; i++)
455 oldAeval[i]= Aeval2[i];
456
457 getLeadingCoeffs (A, Aeval2);
458
459 CFList biFactorsLCs;
460 for (CFListIterator i= biFactors; i.hasItem(); i++)
461 biFactorsLCs.append (LC (i.getItem(), 1));
462
463 Variable w;
464 TIMING_START (fac_precompute_leadcoeff);
465 CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
466 evaluation, Aeval2, lengthAeval2, w);
467
468 if (w.level() != 1)
469 changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
470 uniFactors, w);
471
472 CanonicalForm oldA= A;
473 CFList oldBiFactors= biFactors;
474
475 CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
476 bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
477 leadingCoeffs.removeFirst();
478
479 if (!LCmultiplierIsConst)
480 distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
481
482 //prepare leading coefficients
483 CFList* leadingCoeffs2= new CFList [lengthAeval2];
484 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
485 biFactors, evaluation);
486
488 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
489 bufBiFactors= biFactors;
490 bufA= A;
491 CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
492 if (!LCmultiplierIsConst)
493 {
494 testVars= Variable (2);
495 for (int i= 0; i < lengthAeval2; i++)
496 {
497 if (!oldAeval[i].isEmpty())
498 testVars *= oldAeval[i].getFirst().mvar();
499 }
500 }
501 TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
502 "time to precompute LC over Q: ");
503
504 TIMING_START (fac_luckswang);
505 CFList bufFactors= CFList();
506 bool LCheuristic= false;
507 if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
508 factors))
509 {
510 int check= biFactors.length();
511 int * index= new int [factors.length()];
512 CFList oldFactors= factors;
513 factors= recoverFactors (A, factors, index);
514
515 if (check == factors.length())
516 {
517 if (w.level() != 1)
518 {
519 for (iter= factors; iter.hasItem(); iter++)
520 iter.getItem()= swapvar (iter.getItem(), w, y);
521 }
522
523 appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
524 normalize (factors);
525 delete [] index;
526 delete [] Aeval2;
527 TIMING_END_AND_PRINT (fac_luckswang,
528 "time for successful LucksWang over Q: ");
529 return factors;
530 }
531 else if (factors.length() > 0)
532 {
533 int oneCount= 0;
534 CFList l;
535 for (int i= 0; i < check; i++)
536 {
537 if (index[i] == 1)
538 {
539 iter=biFactors;
540 for (int j=1; j <= i-oneCount; j++)
541 iter++;
542 iter.remove (1);
543 for (int j= 0; j < lengthAeval2; j++)
544 {
545 l= leadingCoeffs2[j];
546 iter= l;
547 for (int k=1; k <= i-oneCount; k++)
548 iter++;
549 iter.remove (1);
550 leadingCoeffs2[j]=l;
551 }
552 oneCount++;
553 }
554 }
555 bufFactors= factors;
556 factors= CFList();
557 }
558 else if (!LCmultiplierIsConst && factors.length() == 0)
559 {
560 LCheuristic= true;
561 factors= oldFactors;
562 CFList contents, LCs;
563 bool foundTrueMultiplier= false;
564 LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
565 contents, LCs, foundTrueMultiplier);
566 if (foundTrueMultiplier)
567 {
568 A= oldA;
569 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
570 for (int i= lengthAeval2-1; i > -1; i--)
571 leadingCoeffs2[i]= CFList();
572 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
573 leadingCoeffs, biFactors, evaluation);
574 }
575 else
576 {
577 bool foundMultiplier= false;
578 LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
579 A, leadingCoeffs2, lengthAeval2, foundMultiplier);
580 // coming from above: divide out more LCmultiplier if possible
581 if (foundMultiplier)
582 {
583 foundMultiplier= false;
584 LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
585 lengthAeval2, leadingCoeffs2, A, LCmultiplier,
586 foundMultiplier);
587 }
588 else
589 {
590 LCHeuristicCheck (LCs, contents, A, oldA,
591 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
592 if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
593 {
594 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
595 lengthAeval2, evaluation, oldBiFactors);
596 }
597 }
598
599 // patch everything together again
600 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
601 for (int i= lengthAeval2-1; i > -1; i--)
602 leadingCoeffs2[i]= CFList();
603 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
604 biFactors, evaluation);
605 }
606 factors= CFList();
607 if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
608 {
609 LCheuristic= false;
610 A= bufA;
611 biFactors= bufBiFactors;
612 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
613 LCmultiplier= bufLCmultiplier;
614 }
615 }
616 else
617 factors= CFList();
618 delete [] index;
619 }
620 TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
621
622 TIMING_START (fac_lcheuristic);
623 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
624 && fdivides (getVars (LCmultiplier), testVars))
625 {
626 LCheuristic= true;
627 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
628 lengthAeval2, evaluation, oldBiFactors);
629
630 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
631 for (int i= lengthAeval2-1; i > -1; i--)
632 leadingCoeffs2[i]= CFList();
633 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
634 biFactors, evaluation);
635
636 if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
637 {
638 LCheuristic= false;
639 A= bufA;
640 biFactors= bufBiFactors;
641 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
642 LCmultiplier= bufLCmultiplier;
643 }
644 }
645 TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
646
647tryAgainWithoutHeu:
648 //shifting to zero
649 TIMING_START (fac_shift_to_zero);
650 CanonicalForm denA= bCommonDen (A);
651 A *= denA;
653 A /= denA;
654
655 for (iter= biFactors; iter.hasItem(); iter++)
656 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
657
658 for (int i= 0; i < lengthAeval2-1; i++)
659 leadingCoeffs2[i]= CFList();
660 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
661 {
663 for (int i= A.level() - 4; i > -1; i--)
664 {
665 if (i + 1 == lengthAeval2-1)
666 leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
667 else
668 leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
669 }
670 }
671 TIMING_END_AND_PRINT (fac_shift_to_zero,
672 "time to shift evaluation point to zero: ");
673
674 CFArray Pi;
675 CFList diophant;
676 int* liftBounds= new int [A.level() - 1];
677 int liftBoundsLength= A.level() - 1;
678 for (int i= 0; i < liftBoundsLength; i++)
679 liftBounds [i]= degree (A, i + 2) + 1;
680
682 bool noOneToOne= false;
683
684 TIMING_START (fac_cleardenom);
685 CFList commonDenominators;
686 for (iter=biFactors; iter.hasItem(); iter++)
687 commonDenominators.append (bCommonDen (iter.getItem()));
688 CanonicalForm tmp1, tmp2, tmp3=1;
689 CFListIterator iter2;
690 for (int i= 0; i < lengthAeval2; i++)
691 {
692 iter2= commonDenominators;
693 for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
694 {
697 iter2.getItem()= lcm (iter2.getItem(), tmp1);
698 On (SW_RATIONAL);
699 }
700 }
701 tmp1= prod (commonDenominators);
702 for (iter= Aeval; iter.hasItem(); iter++)
703 {
704 tmp2= bCommonDen (iter.getItem()/denA);
706 tmp3= lcm (tmp2,tmp3);
707 On (SW_RATIONAL);
708 }
709 CanonicalForm multiplier;
710 multiplier= tmp3/tmp1;
711 iter2= commonDenominators;
712 for (iter=biFactors; iter.hasItem(); iter++, iter2++)
713 iter.getItem() *= iter2.getItem()*multiplier;
714
715 for (iter= Aeval; iter.hasItem(); iter++)
716 iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
717
718 for (int i= 0; i < lengthAeval2; i++)
719 {
720 iter2= commonDenominators;
721 for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
722 iter.getItem() *= iter2.getItem()*multiplier;
723 }
724 TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
725
726 TIMING_START (fac_hensel_lift);
727 factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
728 Pi, liftBounds, liftBoundsLength, noOneToOne);
729 TIMING_END_AND_PRINT (fac_hensel_lift,
730 "time for non monic hensel lifting over Q: ");
731
732 if (!noOneToOne)
733 {
734 int check= factors.length();
735 A= oldA;
736 TIMING_START (fac_recover_factors);
737 factors= recoverFactors (A, factors, evaluation);
738 TIMING_END_AND_PRINT (fac_recover_factors,
739 "time to recover factors over Q: ");
740 if (check != factors.length())
741 noOneToOne= true;
742 else
743 factors= Union (factors, bufFactors);
744 }
745 if (noOneToOne)
746 {
747 if (!LCmultiplierIsConst && LCheuristic)
748 {
749 A= bufA;
750 biFactors= bufBiFactors;
751 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
752 delete [] liftBounds;
753 LCheuristic= false;
754 goto tryAgainWithoutHeu;
755 //something probably went wrong in the heuristic
756 }
757
758 A= shift2Zero (oldA, Aeval, evaluation);
759 biFactors= oldBiFactors;
760 for (iter= biFactors; iter.hasItem(); iter++)
761 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
762 CanonicalForm LCA= LC (Aeval.getFirst(), 1);
763 CanonicalForm yToLift= power (y, lift);
764 CFListIterator i= biFactors;
765 lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
766 i++;
767
768 for (; i.hasItem(); i++)
769 lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
770
771 lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
772
773 i= biFactors;
774 yToLift= power (y, lift);
775 CanonicalForm dummy;
776 for (; i.hasItem(); i++)
777 {
778 LCA= LC (i.getItem(), 1);
779 extgcd (LCA, yToLift, LCA, dummy);
780 i.getItem()= mod (i.getItem()*LCA, yToLift);
781 }
782
783 liftBoundsLength= F.level() - 1;
784 liftBounds= liftingBounds (A, lift);
785
786 CFList MOD;
787 bool earlySuccess;
788 CFList earlyFactors;
790 CFList liftedFactors;
791 TIMING_START (fac_hensel_lift);
792 liftedFactors= henselLiftAndEarly
793 (A, MOD, liftBounds, earlySuccess, earlyFactors,
794 Aeval, biFactors, evaluation, info);
795 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
796
797 TIMING_START (fac_factor_recombination);
798 factors= factorRecombination (A, liftedFactors, MOD);
799 TIMING_END_AND_PRINT (fac_factor_recombination,
800 "time for factor recombination: ");
801
802 if (earlySuccess)
803 factors= Union (factors, earlyFactors);
804
805 for (CFListIterator i= factors; i.hasItem(); i++)
806 {
807 int kk= Aeval.getLast().level();
808 for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
809 {
810 if (i.getItem().level() < kk)
811 continue;
812 i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
813 }
814 }
815 }
816
817 if (w.level() != 1)
818 {
819 for (CFListIterator iter= factors; iter.hasItem(); iter++)
820 iter.getItem()= swapvar (iter.getItem(), w, y);
821 }
822
823 append (factors, contentAFactors);
824 decompress (factors, N);
825 if (isOn (SW_RATIONAL))
826 normalize (factors);
827
828 delete [] leadingCoeffs2;
829 delete [] oldAeval;
830 delete [] Aeval2;
831 delete[] liftBounds;
832
833 return factors;
834}
835#endif
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 getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level(const CanonicalForm &f)
List< CanonicalForm > CFList
CanonicalForm LC(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition: cfModGcd.cc:91
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: cfUnivarGcd.cc:174
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
assertions for Factory
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
This file implements functions to map between extensions of finite fields.
generate random integers, random elements of finite fields
generate random evaluation points
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool isUnivariate() const
class to evaluate a polynomial at points
Definition: cf_eval.h:32
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
generate random integers
Definition: cf_random.h:56
void remove(int moveright)
Definition: ftmpl_list.cc:526
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
class to generate random evaluation points
Definition: cf_reval.h:26
factory's class for variables
Definition: variable.h:33
int level() const
Definition: variable.h:49
functions to print debug output
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
const CanonicalForm & w
Definition: facAbsFact.cc:51
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:47
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
CanonicalForm contentx
CFListIterator iter
Definition: facFactorize.cc:59
CanonicalForm gcd_deriv
Definition: facFactorize.cc:58
Variable x
Definition: facFactorize.cc:50
CFList LCFeval
Definition: facFactorize.cc:53
CFList Evaluation & E
Definition: facFactorize.cc:48
CanonicalForm LCF
Definition: facFactorize.cc:52
CanonicalForm deriv_x
Definition: facFactorize.cc:58
bool bad
Definition: facFactorize.cc:64
bool allZero
Definition: facFactorize.cc:56
bool found
Definition: facFactorize.cc:55
CFList & eval
Definition: facFactorize.cc:47
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
bool foundZero
Definition: facFactorize.cc:57
return result
multivariate factorization over Q(a)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:34
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
else L getLast()(0
CFList tmp1
Definition: facFqBivar.cc:72
CFList tmp2
Definition: facFqBivar.cc:72
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1152
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:586
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
This file provides utility functions for multivariate factorization.
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF,...
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents,...
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors....
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
This file provides functions for factorizing a multivariate polynomial over , or GF.
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition: facHensel.cc:2855
int j
Definition: facHensel.cc:110
fq_nmod_poly_t prod
Definition: facHensel.cc:100
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449
This file defines functions for Hensel lifting.
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
This file provides functions for sparse heuristic Hensel lifting.
bool isZero(const CFArray &A)
checks if entries of A are zero
#define const
Definition: fegetopt.c:39
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
#define info
Definition: libparse.cc:1256
VAR int check
Definition: libparse.cc:1106
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
#define TIMING_DEFINE_PRINT(t)
Definition: timing.h:95
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94
int gcd(int a, int b)
Definition: walkSupport.cc:836