source: git/factory/facFactorize.cc @ 1dc25bf

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