source: git/factory/facFactorize.cc @ e8880a

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