source: git/factory/facFactorize.cc @ f5d2647

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