source: git/factory/facFactorize.cc @ 8d1432e

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