source: git/factory/facFactorize.cc @ ba5e9e

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