source: git/factory/facFactorize.cc @ 9ee586

spielwiese
Last change on this file since 9ee586 was 2080e2, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: renamed cf_gcd_smallp.* to cfModGcd.*
  • Property mode set to 100644
File size: 22.9 KB
Line 
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
47#ifdef HAVE_NTL
48CFList evalPoints (const CanonicalForm& F, CFList& eval, Evaluation& E)
49{
50  CFList result;
51  Variable x= Variable (1);
52
53  CanonicalForm LCF=LC (F,x);
54  CFList LCFeval;
55
56  bool found= false;
57  bool allZero= true;
58  bool foundZero= false;
59  CanonicalForm deriv_x, gcd_deriv;
60  CFListIterator iter;
61  do
62  {
63    eval.insert (F);
64    LCFeval.insert (LCF);
65    bool bad= false;
66    for (int i= E.max(); i >= E.min(); i--)
67    {
68      eval.insert (eval.getFirst()( E [i], i));
69      LCFeval.insert (LCFeval.getFirst() (E [i], i));
70      result.append (E[i]);
71      if (!E[i].isZero())
72        allZero= false;
73      else
74        foundZero= true;
75      if (!allZero && foundZero)
76      {
77        result= CFList();
78        eval= CFList();
79        LCFeval= CFList();
80        bad= true;
81        foundZero= false;
82        break;
83      }
84      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
85      {
86        result= CFList();
87        eval= CFList();
88        LCFeval= CFList();
89        bad= true;
90        break;
91      }
92      if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
93      {
94        result= CFList();
95        eval= CFList();
96        LCFeval= CFList();
97        bad= true;
98        break;
99      }
100    }
101
102    if (bad)
103    {
104      E.nextpoint();
105      continue;
106    }
107
108    if (degree (eval.getFirst()) != degree (F, 1))
109    {
110      result= CFList();
111      eval= CFList();
112      LCFeval= CFList();
113      E.nextpoint();
114      continue;
115    }
116
117    deriv_x= deriv (eval.getFirst(), x);
118    gcd_deriv= gcd (eval.getFirst(), deriv_x);
119    if (degree (gcd_deriv) > 0)
120    {
121      result= CFList();
122      eval= CFList();
123      LCFeval= CFList();
124      E.nextpoint();
125      continue;
126    }
127    iter= eval;
128    iter++;
129    CanonicalForm contentx= content (iter.getItem(), x);
130    if (degree (contentx) > 0)
131    {
132      result= CFList();
133      eval= CFList();
134      LCFeval= CFList();
135      E.nextpoint();
136      continue;
137    }
138    contentx= content (iter.getItem());
139    if (degree (contentx) > 0)
140    {
141      result= CFList();
142      eval= CFList();
143      LCFeval= CFList();
144      E.nextpoint();
145      continue;
146    }
147    found= true;
148  }
149  while (!found);
150
151  if (!eval.isEmpty())
152    eval.removeFirst();
153  return result;
154}
155
156void
157factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
158                                     int& minFactorsLength, bool& irred,
159                                     const Variable& w)
160{
161  Variable x= Variable (1);
162  minFactorsLength= 0;
163  irred= false;
164  Variable v;
165  CFList factors;
166  CanonicalForm LCA= LC (A,1);
167  for (int j= 0; j < A.level() - 2; j++)
168  {
169    if (!Aeval[j].isEmpty())
170    {
171      v= Variable (Aeval[j].getFirst().level());
172
173      factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
174      if (factors.getFirst().inCoeffDomain())
175        factors.removeFirst();
176
177      if (minFactorsLength == 0)
178        minFactorsLength= factors.length();
179      else
180        minFactorsLength= tmin (minFactorsLength, factors.length());
181
182      if (factors.length() == 1)
183      {
184        irred= true;
185        return;
186      }
187      sortList (factors, x);
188      Aeval [j]= factors;
189    }
190  }
191}
192
193CFList
194multiFactorize (const CanonicalForm& F, const Variable& v)
195{
196  if (F.inCoeffDomain())
197    return CFList (F);
198
199  TIMING_START (fac_preprocess_and_content);
200  // compress and find main Variable
201  CFMap N;
202  TIMING_START (fac_compress)
203  CanonicalForm A= myCompress (F, N);
204  TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
205
206  //univariate case
207  if (F.isUnivariate())
208  {
209    CFList result;
210    if (v.level() != 1)
211      result= conv (factorize (F, v));
212    else
213      result= conv (factorize (F,true));
214    if (result.getFirst().inCoeffDomain())
215      result.removeFirst();
216    return result;
217  }
218
219  //bivariate case
220  if (A.level() == 2)
221  {
222    CFList buf= biFactorize (F, v);
223    return buf;
224  }
225
226  Variable x= Variable (1);
227  Variable y= Variable (2);
228
229  // remove content
230  TIMING_START (fac_content);
231  CFList contentAi;
232  CanonicalForm lcmCont= lcmContent (A, contentAi);
233  A /= lcmCont;
234  TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
235
236  // trivial after content removal
237  CFList contentAFactors;
238  if (A.inCoeffDomain())
239  {
240    for (CFListIterator i= contentAi; i.hasItem(); i++)
241    {
242      if (i.getItem().inCoeffDomain())
243        continue;
244      else
245      {
246        lcmCont /= i.getItem();
247        contentAFactors=
248        Union (multiFactorize (lcmCont, v),
249               multiFactorize (i.getItem(), v));
250        break;
251      }
252    }
253    decompress (contentAFactors, N);
254    if (isOn (SW_RATIONAL))
255      normalize (contentAFactors);
256    return contentAFactors;
257  }
258
259  // factorize content
260  TIMING_START (fac_content);
261  contentAFactors= multiFactorize (lcmCont, v);
262  TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
263
264  // univariate after content removal
265  CFList factors;
266  if (A.isUnivariate ())
267  {
268    if (v.level() != 1)
269      factors= conv (factorize (A, v));
270    else
271      factors= conv (factorize (A,true));
272    append (factors, contentAFactors);
273    decompress (factors, N);
274    return factors;
275  }
276
277  A *= bCommonDen (A);
278  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
279  int factorNums= 1;
280  CFList biFactors, bufBiFactors;
281  CanonicalForm evalPoly;
282  int lift, bufLift, lengthAeval2= A.level()-2;
283  CFList* bufAeval2= new CFList [lengthAeval2];
284  CFList* Aeval2= new CFList [lengthAeval2];
285  int counter;
286  int differentSecondVar= 0;
287  CanonicalForm bufA;
288  TIMING_END_AND_PRINT (fac_preprocess_and_content,
289                       "time to preprocess poly and extract content over Q: ");
290
291  // several bivariate factorizations
292  TIMING_START (fac_bifactor_total);
293  REvaluation E (2, A.level(), IntRandom (25));
294  for (int i= 0; i < factorNums; i++)
295  {
296    counter= 0;
297    bufA= A;
298    bufAeval= CFList();
299    TIMING_START (fac_evaluation);
300    bufEvaluation= evalPoints (bufA, bufAeval, E);
301    TIMING_END_AND_PRINT (fac_evaluation,
302                          "time to find evaluation point over Q: ");
303    E.nextpoint();
304    evalPoly= 0;
305
306    TIMING_START (fac_evaluation);
307    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
308    TIMING_END_AND_PRINT (fac_evaluation,
309                          "time to eval wrt diff second vars over Q: ");
310
311    for (int j= 0; j < lengthAeval2; j++)
312    {
313      if (!bufAeval2[j].isEmpty())
314        counter++;
315    }
316
317    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
318
319    TIMING_START (fac_bi_factorizer);
320    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
321    TIMING_END_AND_PRINT (fac_bi_factorizer,
322                          "time for bivariate factorization: ");
323    bufBiFactors.removeFirst();
324
325    if (bufBiFactors.length() == 1)
326    {
327      factors.append (A);
328      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
329      if (isOn (SW_RATIONAL))
330        normalize (factors);
331      delete [] bufAeval2;
332      delete [] Aeval2;
333      return factors;
334    }
335
336    if (i == 0)
337    {
338      Aeval= bufAeval;
339      evaluation= bufEvaluation;
340      biFactors= bufBiFactors;
341      lift= bufLift;
342      for (int j= 0; j < lengthAeval2; j++)
343        Aeval2 [j]= bufAeval2 [j];
344      differentSecondVar= counter;
345    }
346    else
347    {
348      if (bufBiFactors.length() < biFactors.length() ||
349          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
350          counter > differentSecondVar)
351      {
352        Aeval= bufAeval;
353        evaluation= bufEvaluation;
354        biFactors= bufBiFactors;
355        lift= bufLift;
356        for (int j= 0; j < lengthAeval2; j++)
357          Aeval2 [j]= bufAeval2 [j];
358        differentSecondVar= counter;
359      }
360    }
361    int k= 0;
362    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
363      evalPoly += j.getItem()*power (x, k);
364    list.append (evalPoly);
365  }
366
367  delete [] bufAeval2;
368
369  sortList (biFactors, x);
370
371  int minFactorsLength;
372  bool irred= false;
373  TIMING_START (fac_bi_factorizer);
374  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
375  TIMING_END_AND_PRINT (fac_bi_factorizer,
376             "time for bivariate factorization wrt diff second vars over Q: ");
377
378  TIMING_END_AND_PRINT (fac_bifactor_total,
379                        "total time for eval and bivar factors over Q: ");
380  if (irred)
381  {
382    factors.append (A);
383    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
384    if (isOn (SW_RATIONAL))
385      normalize (factors);
386    delete [] Aeval2;
387    return factors;
388  }
389
390  if (minFactorsLength == 0)
391    minFactorsLength= biFactors.length();
392  else if (biFactors.length() > minFactorsLength)
393    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
394  minFactorsLength= tmin (minFactorsLength, biFactors.length());
395
396  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
397
398  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
399
400  minFactorsLength= tmin (minFactorsLength, biFactors.length());
401
402  if (minFactorsLength == 1)
403  {
404    factors.append (A);
405    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
406    if (isOn (SW_RATIONAL))
407      normalize (factors);
408    delete [] Aeval2;
409    return factors;
410  }
411
412  if (differentSecondVar == lengthAeval2)
413  {
414    bool zeroOccured= false;
415    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
416    {
417      if (iter.getItem().isZero())
418      {
419        zeroOccured= true;
420        break;
421      }
422    }
423    if (!zeroOccured)
424    {
425      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
426                                minFactorsLength);
427      if (factors.length() == biFactors.length())
428      {
429        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
430        normalize (factors);
431        delete [] Aeval2;
432        return factors;
433      }
434      else
435        factors= CFList();
436      //TODO case where factors.length() > 0
437    }
438  }
439
440  CFList * oldAeval= new CFList [lengthAeval2];
441  for (int i= 0; i < lengthAeval2; i++)
442    oldAeval[i]= Aeval2[i];
443
444  getLeadingCoeffs (A, Aeval2);
445
446  CFList biFactorsLCs;
447  for (CFListIterator i= biFactors; i.hasItem(); i++)
448    biFactorsLCs.append (LC (i.getItem(), 1));
449
450  Variable w;
451  TIMING_START (fac_precompute_leadcoeff);
452  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
453                                          evaluation, Aeval2, lengthAeval2, w);
454
455  if (w.level() != 1)
456    changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
457                          uniFactors, w);
458
459  CanonicalForm oldA= A;
460  CFList oldBiFactors= biFactors;
461
462  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
463  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
464  leadingCoeffs.removeFirst();
465
466  if (!LCmultiplierIsConst)
467    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
468
469  //prepare leading coefficients
470  CFList* leadingCoeffs2= new CFList [lengthAeval2];
471  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
472                        biFactors, evaluation);
473
474  CFListIterator iter;
475  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
476  bufBiFactors= biFactors;
477  bufA= A;
478  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
479  if (!LCmultiplierIsConst)
480  {
481    testVars= Variable (2);
482    for (int i= 0; i < lengthAeval2; i++)
483    {
484      if (!oldAeval[i].isEmpty())
485        testVars *= oldAeval[i].getFirst().mvar();
486    }
487  }
488  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
489                       "time to precompute LC over Q: ");
490
491  TIMING_START (fac_luckswang);
492  CFList bufFactors= CFList();
493  bool LCheuristic= false;
494  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
495                                factors))
496  {
497    int check= biFactors.length();
498    int * index= new int [factors.length()];
499    CFList oldFactors= factors;
500    factors= recoverFactors (A, factors, index);
501
502    if (check == factors.length())
503    {
504      if (w.level() != 1)
505      {
506        for (iter= factors; iter.hasItem(); iter++)
507          iter.getItem()= swapvar (iter.getItem(), w, y);
508      }
509
510      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
511      normalize (factors);
512      delete [] index;
513      delete [] Aeval2;
514      TIMING_END_AND_PRINT (fac_luckswang,
515                            "time for successful LucksWang over Q: ");
516      return factors;
517    }
518    else if (factors.length() > 0)
519    {
520      int oneCount= 0;
521      CFList l;
522      for (int i= 0; i < check; i++)
523      {
524        if (index[i] == 1)
525        {
526          iter=biFactors;
527          for (int j=1; j <= i-oneCount; j++)
528            iter++;
529          iter.remove (1);
530          for (int j= 0; j < lengthAeval2; j++)
531          {
532            l= leadingCoeffs2[j];
533            iter= l;
534            for (int k=1; k <= i-oneCount; k++)
535              iter++;
536            iter.remove (1);
537            leadingCoeffs2[j]=l;
538          }
539          oneCount++;
540        }
541      }
542      bufFactors= factors;
543      factors= CFList();
544    }
545    else if (!LCmultiplierIsConst && factors.length() == 0)
546    {
547      LCheuristic= true;
548      factors= oldFactors;
549      CFList contents, LCs;
550      bool foundTrueMultiplier= false;
551      LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
552                    contents, LCs, foundTrueMultiplier);
553      if (foundTrueMultiplier)
554      {
555          A= oldA;
556          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
557          for (int i= lengthAeval2-1; i > -1; i--)
558            leadingCoeffs2[i]= CFList();
559          prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
560                                leadingCoeffs, biFactors, evaluation);
561      }
562      else
563      {
564        bool foundMultiplier= false;
565        LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
566                      A, leadingCoeffs2, lengthAeval2, foundMultiplier);
567        // coming from above: divide out more LCmultiplier if possible
568        if (foundMultiplier)
569        {
570          foundMultiplier= false;
571          LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
572                        lengthAeval2, leadingCoeffs2, A, LCmultiplier,
573                        foundMultiplier);
574        }
575        else
576        {
577          LCHeuristicCheck (LCs, contents, A, oldA,
578                            leadingCoeffs2[lengthAeval2-1], foundMultiplier);
579          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
580          {
581            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
582                         lengthAeval2, evaluation, oldBiFactors);
583          }
584        }
585
586        // patch everything together again
587        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
588        for (int i= lengthAeval2-1; i > -1; i--)
589          leadingCoeffs2[i]= CFList();
590        prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
591                              biFactors, evaluation);
592      }
593      factors= CFList();
594      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
595      {
596        LCheuristic= false;
597        A= bufA;
598        biFactors= bufBiFactors;
599        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
600        LCmultiplier= bufLCmultiplier;
601      }
602    }
603    else
604      factors= CFList();
605    delete [] index;
606  }
607  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
608
609  TIMING_START (fac_lcheuristic);
610  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
611      && fdivides (getVars (LCmultiplier), testVars))
612  {
613    LCheuristic= true;
614    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
615                 lengthAeval2, evaluation, oldBiFactors);
616
617    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
618    for (int i= lengthAeval2-1; i > -1; i--)
619      leadingCoeffs2[i]= CFList();
620    prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
621                          biFactors, evaluation);
622
623    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
624    {
625      LCheuristic= false;
626      A= bufA;
627      biFactors= bufBiFactors;
628      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
629      LCmultiplier= bufLCmultiplier;
630    }
631  }
632  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
633
634tryAgainWithoutHeu:
635  //shifting to zero
636  TIMING_START (fac_shift_to_zero);
637  CanonicalForm denA= bCommonDen (A);
638  A *= denA;
639  A= shift2Zero (A, Aeval, evaluation);
640  A /= denA;
641
642  for (iter= biFactors; iter.hasItem(); iter++)
643    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
644
645  for (int i= 0; i < lengthAeval2-1; i++)
646    leadingCoeffs2[i]= CFList();
647  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
648  {
649    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
650    for (int i= A.level() - 4; i > -1; i--)
651    {
652      if (i + 1 == lengthAeval2-1)
653        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
654      else
655        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
656    }
657  }
658  TIMING_END_AND_PRINT (fac_shift_to_zero,
659                        "time to shift evaluation point to zero: ");
660
661  CFArray Pi;
662  CFList diophant;
663  int* liftBounds= new int [A.level() - 1];
664  int liftBoundsLength= A.level() - 1;
665  for (int i= 0; i < liftBoundsLength; i++)
666    liftBounds [i]= degree (A, i + 2) + 1;
667
668  Aeval.removeFirst();
669  bool noOneToOne= false;
670
671  TIMING_START (fac_cleardenom);
672  CFList commonDenominators;
673  for (iter=biFactors; iter.hasItem(); iter++)
674    commonDenominators.append (bCommonDen (iter.getItem()));
675  CanonicalForm tmp1, tmp2, tmp3=1;
676  CFListIterator iter2;
677  for (int i= 0; i < lengthAeval2; i++)
678  {
679    iter2= commonDenominators;
680    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
681    {
682      tmp1= bCommonDen (iter.getItem());
683      Off (SW_RATIONAL);
684      iter2.getItem()= lcm (iter2.getItem(), tmp1);
685      On (SW_RATIONAL);
686    }
687  }
688  tmp1= prod (commonDenominators);
689  for (iter= Aeval; iter.hasItem(); iter++)
690  {
691    tmp2= bCommonDen (iter.getItem()/denA);
692    Off (SW_RATIONAL);
693    tmp3= lcm (tmp2,tmp3);
694    On (SW_RATIONAL);
695  }
696  CanonicalForm multiplier;
697  multiplier= tmp3/tmp1;
698  iter2= commonDenominators;
699  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
700    iter.getItem() *= iter2.getItem()*multiplier;
701
702  for (iter= Aeval; iter.hasItem(); iter++)
703    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
704
705  for (int i= 0; i < lengthAeval2; i++)
706  {
707    iter2= commonDenominators;
708    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
709      iter.getItem() *= iter2.getItem()*multiplier;
710  }
711  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
712
713  TIMING_START (fac_hensel_lift);
714  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
715                               Pi, liftBounds, liftBoundsLength, noOneToOne);
716  TIMING_END_AND_PRINT (fac_hensel_lift,
717                        "time for non monic hensel lifting over Q: ");
718
719  if (!noOneToOne)
720  {
721    int check= factors.length();
722    A= oldA;
723    TIMING_START (fac_recover_factors);
724    factors= recoverFactors (A, factors, evaluation);
725    TIMING_END_AND_PRINT (fac_recover_factors,
726                          "time to recover factors over Q: ");
727    if (check != factors.length())
728      noOneToOne= true;
729    else
730      factors= Union (factors, bufFactors);
731  }
732  if (noOneToOne)
733  {
734    if (!LCmultiplierIsConst && LCheuristic)
735    {
736      A= bufA;
737      biFactors= bufBiFactors;
738      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
739      delete [] liftBounds;
740      LCheuristic= false;
741      goto tryAgainWithoutHeu;
742      //something probably went wrong in the heuristic
743    }
744
745    A= shift2Zero (oldA, Aeval, evaluation);
746    biFactors= oldBiFactors;
747    for (iter= biFactors; iter.hasItem(); iter++)
748      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
749    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
750    CanonicalForm yToLift= power (y, lift);
751    CFListIterator i= biFactors;
752    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
753    i++;
754
755    for (; i.hasItem(); i++)
756      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
757
758    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
759
760    i= biFactors;
761    yToLift= power (y, lift);
762    CanonicalForm dummy;
763    for (; i.hasItem(); i++)
764    {
765      LCA= LC (i.getItem(), 1);
766      extgcd (LCA, yToLift, LCA, dummy);
767      i.getItem()= mod (i.getItem()*LCA, yToLift);
768    }
769
770    liftBoundsLength= F.level() - 1;
771    liftBounds= liftingBounds (A, lift);
772
773    CFList MOD;
774    bool earlySuccess;
775    CFList earlyFactors;
776    ExtensionInfo info= ExtensionInfo (false);
777    CFList liftedFactors;
778    TIMING_START (fac_hensel_lift);
779    liftedFactors= henselLiftAndEarly
780                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
781                    Aeval, biFactors, evaluation, info);
782    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
783
784    TIMING_START (fac_factor_recombination);
785    factors= factorRecombination (A, liftedFactors, MOD);
786    TIMING_END_AND_PRINT (fac_factor_recombination,
787                          "time for factor recombination: ");
788
789    if (earlySuccess)
790      factors= Union (factors, earlyFactors);
791
792    for (CFListIterator i= factors; i.hasItem(); i++)
793    {
794      int kk= Aeval.getLast().level();
795      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
796      {
797        if (i.getItem().level() < kk)
798          continue;
799       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
800      }
801    }
802  }
803
804  if (w.level() != 1)
805  {
806    for (CFListIterator iter= factors; iter.hasItem(); iter++)
807      iter.getItem()= swapvar (iter.getItem(), w, y);
808  }
809
810  append (factors, contentAFactors);
811  decompress (factors, N);
812  if (isOn (SW_RATIONAL))
813    normalize (factors);
814
815  delete [] leadingCoeffs2;
816  delete [] oldAeval;
817  delete [] Aeval2;
818  delete[] liftBounds;
819
820  return factors;
821}
822
823#endif
Note: See TracBrowser for help on using the repository browser.