source: git/factory/facFactorize.cc @ 52a933f

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