source: git/factory/facFactorize.cc @ 1950d7

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