source: git/factory/facFactorize.cc @ aba90e8

spielwiese
Last change on this file since aba90e8 was 074fe7, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: some editing chg: more updates to docu Conflicts: factory/facFqFactorize.h
  • 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#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,
416                          uniFactors, w);
417
418  CanonicalForm oldA= A;
419  CFList oldBiFactors= biFactors;
420
421  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
422  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
423  leadingCoeffs.removeFirst();
424
425  if (!LCmultiplierIsConst)
426    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
427
428  //prepare leading coefficients
429  CFList* leadingCoeffs2= new CFList [lengthAeval2];
430  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
431                        biFactors, evaluation);
432
433  CFListIterator iter;
434  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
435  bufBiFactors= biFactors;
436  bufA= A;
437  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
438  if (!LCmultiplierIsConst)
439  {
440    testVars= Variable (2);
441    for (int i= 0; i < lengthAeval2; i++)
442    {
443      if (!oldAeval[i].isEmpty())
444        testVars *= oldAeval[i].getFirst().mvar();
445    }
446  }
447  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
448                       "time to precompute LC over Q: ");
449
450  TIMING_START (fac_luckswang);
451  CFList bufFactors= CFList();
452  bool LCheuristic= false;
453  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
454                                factors))
455  {
456    int check= biFactors.length();
457    int * index= new int [factors.length()];
458    CFList oldFactors= factors;
459    factors= recoverFactors (A, factors, index);
460
461    if (check == factors.length())
462    {
463      if (w.level() != 1)
464      {
465        for (iter= factors; iter.hasItem(); iter++)
466          iter.getItem()= swapvar (iter.getItem(), w, y);
467      }
468
469      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
470      normalize (factors);
471      delete [] index;
472      delete [] Aeval2;
473      TIMING_END_AND_PRINT (fac_luckswang,
474                            "time for successful LucksWang over Q: ");
475      return factors;
476    }
477    else if (factors.length() > 0)
478    {
479      int oneCount= 0;
480      CFList l;
481      for (int i= 0; i < check; i++)
482      {
483        if (index[i] == 1)
484        {
485          iter=biFactors;
486          for (int j=1; j <= i-oneCount; j++)
487            iter++;
488          iter.remove (1);
489          for (int j= 0; j < lengthAeval2; j++)
490          {
491            l= leadingCoeffs2[j];
492            iter= l;
493            for (int k=1; k <= i-oneCount; k++)
494              iter++;
495            iter.remove (1);
496            leadingCoeffs2[j]=l;
497          }
498          oneCount++;
499        }
500      }
501      bufFactors= factors;
502      factors= CFList();
503    }
504    else if (!LCmultiplierIsConst && factors.length() == 0)
505    {
506      LCheuristic= true;
507      factors= oldFactors;
508      CFList contents, LCs;
509      bool foundTrueMultiplier= false;
510      LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
511                    contents, LCs, foundTrueMultiplier);
512      if (foundTrueMultiplier)
513      {
514          A= oldA;
515          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
516          for (int i= lengthAeval2-1; i > -1; i--)
517            leadingCoeffs2[i]= CFList();
518          prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
519                                leadingCoeffs, biFactors, evaluation);
520      }
521      else
522      {
523        bool foundMultiplier= false;
524        LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
525                      A, leadingCoeffs2, lengthAeval2, foundMultiplier);
526        // coming from above: divide out more LCmultiplier if possible
527        if (foundMultiplier)
528        {
529          foundMultiplier= false;
530          LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
531                        lengthAeval2, leadingCoeffs2, A, LCmultiplier,
532                        foundMultiplier);
533        }
534        else
535        {
536          LCHeuristicCheck (LCs, contents, A, oldA,
537                            leadingCoeffs2[lengthAeval2-1], foundMultiplier);
538          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
539          {
540            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
541                         lengthAeval2, evaluation, oldBiFactors);
542          }
543        }
544
545        // patch everything together again
546        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
547        for (int i= lengthAeval2-1; i > -1; i--)
548          leadingCoeffs2[i]= CFList();
549        prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
550                              biFactors, evaluation);
551      }
552      factors= CFList();
553      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
554      {
555        LCheuristic= false;
556        A= bufA;
557        biFactors= bufBiFactors;
558        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
559        LCmultiplier= bufLCmultiplier;
560      }
561    }
562    else
563      factors= CFList();
564    delete [] index;
565  }
566  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
567
568  TIMING_START (fac_lcheuristic);
569  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
570      && fdivides (getVars (LCmultiplier), testVars))
571  {
572    LCheuristic= true;
573    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
574                 lengthAeval2, evaluation, oldBiFactors);
575
576    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
577    for (int i= lengthAeval2-1; i > -1; i--)
578      leadingCoeffs2[i]= CFList();
579    prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
580                          biFactors, evaluation);
581
582    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
583    {
584      LCheuristic= false;
585      A= bufA;
586      biFactors= bufBiFactors;
587      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
588      LCmultiplier= bufLCmultiplier;
589    }
590  }
591  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
592
593tryAgainWithoutHeu:
594  //shifting to zero
595  TIMING_START (fac_shift_to_zero);
596  CanonicalForm denA= bCommonDen (A);
597  A *= denA;
598  A= shift2Zero (A, Aeval, evaluation);
599  A /= denA;
600
601  for (iter= biFactors; iter.hasItem(); iter++)
602    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
603
604  for (int i= 0; i < lengthAeval2-1; i++)
605    leadingCoeffs2[i]= CFList();
606  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
607  {
608    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
609    for (int i= A.level() - 4; i > -1; i--)
610    {
611      if (i + 1 == lengthAeval2-1)
612        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
613      else
614        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
615    }
616  }
617  TIMING_END_AND_PRINT (fac_shift_to_zero,
618                        "time to shift evaluation point to zero: ");
619
620  CFArray Pi;
621  CFList diophant;
622  int* liftBounds= new int [A.level() - 1];
623  int liftBoundsLength= A.level() - 1;
624  for (int i= 0; i < liftBoundsLength; i++)
625    liftBounds [i]= degree (A, i + 2) + 1;
626
627  Aeval.removeFirst();
628  bool noOneToOne= false;
629
630  TIMING_START (fac_cleardenom);
631  CFList commonDenominators;
632  for (iter=biFactors; iter.hasItem(); iter++)
633    commonDenominators.append (bCommonDen (iter.getItem()));
634  CanonicalForm tmp1, tmp2, tmp3=1;
635  CFListIterator iter2;
636  for (int i= 0; i < lengthAeval2; i++)
637  {
638    iter2= commonDenominators;
639    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
640    {
641      tmp1= bCommonDen (iter.getItem());
642      Off (SW_RATIONAL);
643      iter2.getItem()= lcm (iter2.getItem(), tmp1);
644      On (SW_RATIONAL);
645    }
646  }
647  tmp1= prod (commonDenominators);
648  for (iter= Aeval; iter.hasItem(); iter++)
649  {
650    tmp2= bCommonDen (iter.getItem()/denA);
651    Off (SW_RATIONAL);
652    tmp3= lcm (tmp2,tmp3);
653    On (SW_RATIONAL);
654  }
655  CanonicalForm multiplier;
656  multiplier= tmp3/tmp1;
657  iter2= commonDenominators;
658  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
659    iter.getItem() *= iter2.getItem()*multiplier;
660
661  for (iter= Aeval; iter.hasItem(); iter++)
662    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
663
664  for (int i= 0; i < lengthAeval2; i++)
665  {
666    iter2= commonDenominators;
667    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
668      iter.getItem() *= iter2.getItem()*multiplier;
669  }
670  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
671
672  TIMING_START (fac_hensel_lift);
673  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
674                               Pi, liftBounds, liftBoundsLength, noOneToOne);
675  TIMING_END_AND_PRINT (fac_hensel_lift,
676                        "time for non monic hensel lifting over Q: ");
677
678  if (!noOneToOne)
679  {
680    int check= factors.length();
681    A= oldA;
682    TIMING_START (fac_recover_factors);
683    factors= recoverFactors (A, factors, evaluation);
684    TIMING_END_AND_PRINT (fac_recover_factors,
685                          "time to recover factors over Q: ");
686    if (check != factors.length())
687      noOneToOne= true;
688    else
689      factors= Union (factors, bufFactors);
690  }
691  if (noOneToOne)
692  {
693    if (!LCmultiplierIsConst && LCheuristic)
694    {
695      A= bufA;
696      biFactors= bufBiFactors;
697      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
698      delete [] liftBounds;
699      LCheuristic= false;
700      goto tryAgainWithoutHeu;
701      //something probably went wrong in the heuristic
702    }
703
704    A= shift2Zero (oldA, Aeval, evaluation);
705    biFactors= oldBiFactors;
706    for (iter= biFactors; iter.hasItem(); iter++)
707      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
708    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
709    CanonicalForm yToLift= power (y, lift);
710    CFListIterator i= biFactors;
711    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
712    i++;
713
714    for (; i.hasItem(); i++)
715      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
716
717    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
718
719    i= biFactors;
720    yToLift= power (y, lift);
721    CanonicalForm dummy;
722    for (; i.hasItem(); i++)
723    {
724      LCA= LC (i.getItem(), 1);
725      extgcd (LCA, yToLift, LCA, dummy);
726      i.getItem()= mod (i.getItem()*LCA, yToLift);
727    }
728
729    liftBoundsLength= F.level() - 1;
730    liftBounds= liftingBounds (A, lift);
731
732    CFList MOD;
733    bool earlySuccess;
734    CFList earlyFactors;
735    ExtensionInfo info= ExtensionInfo (false);
736    CFList liftedFactors;
737    TIMING_START (fac_hensel_lift);
738    liftedFactors= henselLiftAndEarly
739                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
740                    Aeval, biFactors, evaluation, info);
741    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
742
743    TIMING_START (fac_factor_recombination);
744    factors= factorRecombination (A, liftedFactors, MOD);
745    TIMING_END_AND_PRINT (fac_factor_recombination,
746                          "time for factor recombination: ");
747
748    if (earlySuccess)
749      factors= Union (factors, earlyFactors);
750
751    for (CFListIterator i= factors; i.hasItem(); i++)
752    {
753      int kk= Aeval.getLast().level();
754      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
755      {
756        if (i.getItem().level() < kk)
757          continue;
758       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
759      }
760    }
761  }
762
763  if (w.level() != 1)
764  {
765    for (CFListIterator iter= factors; iter.hasItem(); iter++)
766      iter.getItem()= swapvar (iter.getItem(), w, y);
767  }
768
769  swap (factors, 0, 0, x);
770  append (factors, contentAFactors);
771  decompress (factors, N);
772  if (isOn (SW_RATIONAL))
773    normalize (factors);
774
775  delete [] leadingCoeffs2;
776  delete [] oldAeval;
777  delete [] Aeval2;
778  delete[] liftBounds;
779
780  return factors;
781}
782
783#endif
Note: See TracBrowser for help on using the repository browser.