source: git/factory/facFactorize.cc @ f7e9c6

jengelh-datetimespielwiese
Last change on this file since f7e9c6 was f7e9c6, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: avoid divisions
  • Property mode set to 100644
File size: 46.7 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#include "config.h"
14
15#include "assert.h"
16#include "debug.h"
17#include "timing.h"
18
19#include "cf_algorithm.h"
20#include "facFqFactorizeUtil.h"
21#include "facFactorize.h"
22#include "facFqFactorize.h"
23#include "cf_random.h"
24#include "facHensel.h"
25#include "cf_gcd_smallp.h"
26#include "cf_map_ext.h"
27#include "algext.h"
28#include "cf_reval.h"
29#include "facSparseHensel.h"
30
31TIMING_DEFINE_PRINT(fac_bi_factorize)
32TIMING_DEFINE_PRINT(fac_hensel_lift)
33TIMING_DEFINE_PRINT(fac_factor_recombination)
34
35#ifdef HAVE_NTL
36CFList evalPoints (const CanonicalForm& F, CFList& eval, Evaluation& E)
37{
38  CFList result;
39  Variable x= Variable (1);
40
41  bool found= false;
42  bool allZero= true;
43  bool foundZero= false;
44  CanonicalForm deriv_x, gcd_deriv;
45  CFListIterator iter;
46  do
47  {
48    eval.insert (F);
49    bool bad= false;
50    for (int i= E.max(); i >= E.min(); i--)
51    {
52      eval.insert (eval.getFirst()( E [i], i));
53      result.append (E[i]);
54      if (!E[i].isZero())
55        allZero= false;
56      else
57        foundZero= true;
58      if (!allZero && foundZero)
59      {
60        result= CFList();
61        eval= CFList();
62        bad= true;
63        foundZero= false;
64        break;
65      }
66      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
67      {
68        result= CFList();
69        eval= CFList();
70        bad= true;
71        break;
72      }
73    }
74
75    if (bad)
76    {
77      E.nextpoint();
78      continue;
79    }
80
81    if (degree (eval.getFirst()) != degree (F, 1))
82    {
83      result= CFList();
84      eval= CFList();
85      E.nextpoint();
86      continue;
87    }
88
89    deriv_x= deriv (eval.getFirst(), x);
90    gcd_deriv= gcd (eval.getFirst(), deriv_x);
91    if (degree (gcd_deriv) > 0)
92    {
93      result= CFList();
94      eval= CFList();
95      E.nextpoint();
96      continue;
97    }
98    iter= eval;
99    iter++;
100    CanonicalForm contentx= content (iter.getItem(), x);
101    if (degree (contentx) > 0)
102    {
103      result= CFList();
104      eval= CFList();
105      E.nextpoint();
106      continue;
107    }
108    found= true;
109  }
110  while (!found);
111
112  if (!eval.isEmpty())
113    eval.removeFirst();
114  return result;
115}
116
117void
118factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
119                                     int& minFactorsLength, bool& irred,
120                                     const Variable& w)
121{
122  Variable x= Variable (1);
123  minFactorsLength= 0;
124  irred= false;
125  Variable v;
126  CFList factors;
127  CanonicalForm LCA= LC (A,1);
128  for (int j= 0; j < A.level() - 2; j++)
129  {
130    if (!Aeval[j].isEmpty())
131    {
132      v= Variable (Aeval[j].getFirst().level());
133
134      factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
135      if (factors.getFirst().inCoeffDomain())
136        factors.removeFirst();
137
138      if (minFactorsLength == 0)
139        minFactorsLength= factors.length();
140      else
141        minFactorsLength= tmin (minFactorsLength, factors.length());
142
143      if (factors.length() == 1)
144      {
145        irred= true;
146        return;
147      }
148      sortList (factors, x);
149      Aeval [j]= factors;
150    }
151    else if (!Aeval[j].isEmpty())
152      Aeval[j]=CFList();
153  }
154}
155
156int
157testFactors (const CanonicalForm& G, const CFList& uniFactors,
158             CanonicalForm& sqrfPartF, CFList& factors,
159             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
160             const CFArray& evalPoint)
161{
162  CanonicalForm tmp;
163  CFListIterator j;
164  for (CFListIterator i= uniFactors; i.hasItem(); i++)
165  {
166    tmp= i.getItem();
167    if (i.hasItem())
168      i++;
169    else
170      break;
171    for (j= i; j.hasItem(); j++)
172    {
173      if (tmp == j.getItem())
174        return 0;
175    }
176  }
177
178  CanonicalForm F= G;
179  CFFList sqrfFactorization= sqrFree (F);
180
181  sqrfPartF= 1;
182  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
183    sqrfPartF *= i.getItem().factor();
184
185  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
186
187  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
188
189  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
190    return 0;
191
192  CFFList sqrfFactors;
193  CFList tmp2;
194  int k= 0;
195  factors= uniFactors;
196  CFFListIterator iter;
197  for (CFListIterator i= factors; i.hasItem(); i++, k++)
198  {
199    tmp= 1;
200    sqrfFactors= sqrFree (i.getItem());
201
202    for (iter= sqrfFactors; iter.hasItem(); iter++)
203    {
204      tmp2.append (iter.getItem().factor());
205      tmp *= iter.getItem().factor();
206    }
207    i.getItem()= tmp/Lc(tmp);
208    bufSqrfFactors [k]= sqrfFactors;
209  }
210
211  for (int i= 0; i < factors.length() - 1; i++)
212  {
213    for (int k= i + 1; k < factors.length(); k++)
214    {
215      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
216    }
217  }
218
219  factors= CFList();
220  for (int i= 0; i < uniFactors.length(); i++)
221  {
222    if (i == 0)
223    {
224      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
225      {
226        if (iter.getItem().factor().inCoeffDomain())
227          continue;
228        iter.getItem()= CFFactor (iter.getItem().factor()/
229                                  Lc (iter.getItem().factor()),
230                                  iter.getItem().exp());
231        factors.append (iter.getItem().factor());
232      }
233    }
234    else
235    {
236      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
237      {
238        if (iter.getItem().factor().inCoeffDomain())
239          continue;
240        iter.getItem()= CFFactor (iter.getItem().factor()/
241                               Lc (iter.getItem().factor()),
242                               iter.getItem().exp());
243        if (!find (factors, iter.getItem().factor()))
244          factors.append (iter.getItem().factor());
245      }
246    }
247  }
248
249  test= prod (factors);
250  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
251  if (test/Lc (test) != tmp/Lc (tmp))
252    return 0;
253  else
254    return 1;
255}
256
257CFList
258precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
259                        const CFList& evaluation,CFList*& differentSecondVarLCs,
260                        int length, Variable& y
261                       )
262{
263  y= Variable (1);
264  if (LCF.inCoeffDomain())
265  {
266    CFList result;
267    for (int i= 1; i <= LCFFactors.length() + 1; i++)
268      result.append (1);
269    return result;
270  }
271
272  CFMap N, M;
273  CFArray dummy= CFArray (2);
274  dummy [0]= LCF;
275  dummy [1]= Variable (2);
276  compress (dummy, M, N);
277  CanonicalForm F= M (LCF);
278  if (LCF.isUnivariate())
279  {
280    CFList result;
281    int LCFLevel= LCF.level();
282    bool found= false;
283    if (LCFLevel == 2)
284    {
285    //bivariate leading coefficients are already the true leading coefficients
286      result= LCFFactors;
287      found= true;
288    }
289    else
290    {
291      CFListIterator j;
292      for (int i= 0; i < length; i++)
293      {
294        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
295        {
296          if (j.getItem().level() == LCFLevel)
297          {
298            found= true;
299            break;
300          }
301        }
302        if (found)
303        {
304          result= differentSecondVarLCs [i];
305          break;
306        }
307      }
308      if (!found)
309        result= LCFFactors;
310    }
311    if (found)
312      result.insert (Lc (LCF));
313    else
314    {
315      for (CFListIterator i= result; i.hasItem(); i++)
316        i.getItem() *= LCF;
317      result.insert (LCF);
318    }
319    return result;
320  }
321
322  CFList factors= LCFFactors;
323
324  for (CFListIterator i= factors; i.hasItem(); i++)
325    i.getItem()= M (i.getItem());
326
327  CanonicalForm sqrfPartF;
328  CFFList * bufSqrfFactors= new CFFList [factors.length()];
329  CFList evalSqrfPartF, bufFactors;
330  CFArray evalPoint= CFArray (evaluation.length() - 1);
331  CFArray buf= CFArray (evaluation.length());
332  CFArray swap= CFArray (evaluation.length());
333  CFListIterator iter= evaluation;
334  CanonicalForm vars=getVars (LCF)*Variable (2);
335  for (int i= evaluation.length() +1; i > 1; i--, iter++)
336  {
337    buf[i-2]=iter.getItem();
338    if (degree (vars, i) > 0)
339      swap[M(Variable (i)).level()-1]=buf[i-2];
340  }
341  buf= swap;
342  for (int i= 0; i < evaluation.length() - 1; i++)
343    evalPoint[i]= buf[i+1];
344
345  //TODO sqrfPartF einmal berechnen nicht stÀndig
346  int pass= testFactors (F, factors, sqrfPartF,
347                         bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
348
349  bool foundDifferent= false;
350  Variable z;
351  Variable x= y;
352  int j= 0;
353  if (!pass)
354  {
355    int lev= 0;
356    CanonicalForm bufF;
357    CFList bufBufFactors;
358    for (int i= 0; i < length; i++)
359    {
360      if (!differentSecondVarLCs [i].isEmpty())
361      {
362        bool allConstant= true;
363        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
364        {
365          if (!iter.getItem().inCoeffDomain())
366          {
367            allConstant= false;
368            y= Variable (iter.getItem().level());
369            lev= M(y).level();
370          }
371        }
372        if (allConstant)
373          continue;
374
375        bufFactors= differentSecondVarLCs [i];
376        for (iter= bufFactors; iter.hasItem(); iter++)
377          iter.getItem()= swapvar (iter.getItem(), x, y);
378        bufF= F;
379        z= Variable (lev);
380        bufF= swapvar (bufF, x, z);
381        bufBufFactors= bufFactors;
382        evalPoint= CFArray (evaluation.length() - 1);
383        for (int k= 0; k < evaluation.length()-1; k++)
384        {
385          if (N (Variable (k+1)).level() != y.level())
386            evalPoint[k]= buf[k+1];
387          else
388            evalPoint[k]= buf[0];
389        }
390        pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
391                           bufSqrfFactors, evalSqrfPartF, evalPoint);
392        if (pass)
393        {
394          foundDifferent= true;
395          F= bufF;
396          CFList l= factors;
397          for (iter= l; iter.hasItem(); iter++)
398            iter.getItem()= swapvar (iter.getItem(), x, y);
399          differentSecondVarLCs [i]= l;
400          j= i;
401          break;
402        }
403        if (!pass && i == length - 1)
404        {
405          CFList result;
406          result.append (LCF);
407          for (int j= 1; j <= factors.length(); j++)
408            result.append (1);
409          result= distributeContent (result, differentSecondVarLCs, length);
410          if (!result.getFirst().inCoeffDomain())
411          {
412            CFListIterator iter= result;
413            CanonicalForm tmp= iter.getItem();
414            iter++;
415            for (; iter.hasItem(); iter++)
416              iter.getItem() *= tmp;
417          }
418
419          y= Variable (1);
420          delete [] bufSqrfFactors;
421          return result;
422        }
423      }
424    }
425  }
426  if (!pass)
427  {
428    CFList result;
429    result.append (LCF);
430    for (int j= 1; j <= factors.length(); j++)
431      result.append (LCF);
432    y= Variable (1);
433    delete [] bufSqrfFactors;
434    return result;
435  }
436  else
437    factors= bufFactors;
438
439
440  bufFactors= factors;
441
442  CFMap MM, NN;
443  dummy [0]= sqrfPartF;
444  dummy [1]= 1;
445  compress (dummy, MM, NN);
446  sqrfPartF= MM (sqrfPartF);
447  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
448  for (CFListIterator iter= factors; iter.hasItem(); iter++)
449    iter.getItem()= MM (iter.getItem());
450
451  CFList evaluation2;
452  for (int i= 2; i <= varsSqrfPartF.level(); i++)
453    evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
454
455  CFList interMedResult;
456  CanonicalForm oldSqrfPartF= sqrfPartF;
457  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
458  if (factors.length() > 1)
459  {
460    CanonicalForm LC1= LC (oldSqrfPartF, 1);
461    CFList leadingCoeffs;
462    for (int i= 0; i < factors.length(); i++)
463      leadingCoeffs.append (LC1);
464
465    CFList LC1eval= evaluateAtEval (LC1, evaluation2,2);
466    CFList oldFactors= factors;
467    for (CFListIterator i= oldFactors; i.hasItem(); i++)
468      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
469
470    bool success= false;
471    CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
472    CFList heuResult;
473    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
474        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
475                                  oldFactors, 2, leadingCoeffs, heuResult))
476    {
477      interMedResult= recoverFactors (oldSqrfPartF, heuResult);
478      if (oldFactors.length() == interMedResult.length())
479        success= true;
480    }
481    if (!success)
482    {
483      LC1= LC (evalSqrfPartF.getFirst(), 1);
484
485      CFArray leadingCoeffs= CFArray (factors.length());
486      for (int i= 0; i < factors.length(); i++)
487        leadingCoeffs[i]= LC1;
488
489      for (CFListIterator i= factors; i.hasItem(); i++)
490        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
491      factors.insert (1);
492
493      CanonicalForm
494      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
495
496      int liftBound= degree (newSqrfPartF,2) + 1;
497
498      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
499      CFArray Pi;
500      CFList diophant;
501      nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
502                            leadingCoeffs, false);
503
504      if (sqrfPartF.level() > 2)
505      {
506        int* liftBounds= new int [sqrfPartF.level() - 1];
507        liftBounds [0]= liftBound;
508        bool noOneToOne= false;
509        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
510        LC1= LC (evalSqrfPartF.getLast(), 1);
511        CFList LCs;
512        for (int i= 0; i < factors.length(); i++)
513          LCs.append (LC1);
514        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
515        for (int i= sqrfPartF.level() - 1; i > 2; i--)
516        {
517          for (CFListIterator j= LCs; j.hasItem(); j++)
518            j.getItem()= j.getItem() (0, i + 1);
519          leadingCoeffs2 [i - 3]= LCs;
520        }
521        sqrfPartF *= power (LC1, factors.length()-1);
522
523        int liftBoundsLength= sqrfPartF.level() - 1;
524        for (int i= 1; i < liftBoundsLength; i++)
525          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
526        evalSqrfPartF= evaluateAtZero (sqrfPartF);
527        evalSqrfPartF.removeFirst();
528        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
529                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
530        delete [] leadingCoeffs2;
531        delete [] liftBounds;
532      }
533      for (CFListIterator iter= factors; iter.hasItem(); iter++)
534        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
535
536      interMedResult=
537      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
538                      factors);
539    }
540  }
541  else
542  {
543    CanonicalForm contF=content (oldSqrfPartF,1);
544    factors= CFList (oldSqrfPartF/contF);
545    interMedResult= recoverFactors (oldSqrfPartF, factors);
546  }
547
548  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
549    iter.getItem()= NN (iter.getItem());
550
551  CFList result;
552  CFFListIterator k;
553  CanonicalForm tmp;
554  for (int i= 0; i < LCFFactors.length(); i++)
555  {
556    tmp= 1;
557    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
558    {
559      int pos= findItem (bufFactors, k.getItem().factor());
560      if (pos)
561        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
562    }
563    result.append (tmp);
564  }
565
566  for (CFListIterator i= result; i.hasItem(); i++)
567  {
568    F /= i.getItem();
569    if (foundDifferent)
570      i.getItem()= swapvar (i.getItem(), x, z);
571    i.getItem()= N (i.getItem());
572  }
573
574  if (foundDifferent)
575  {
576    CFList l= differentSecondVarLCs [j];
577    for (CFListIterator i= l; i.hasItem(); i++)
578      i.getItem()= swapvar (i.getItem(), y, z);
579    differentSecondVarLCs [j]= l;
580    F= swapvar (F, x, z);
581  }
582
583  result.insert (N (F));
584
585  result= distributeContent (result, differentSecondVarLCs, length);
586
587  if (!result.getFirst().inCoeffDomain())
588  {
589    CFListIterator i= result;
590    CanonicalForm tmp;
591    if (foundDifferent)
592      i.getItem()= swapvar (i.getItem(), Variable (2), y);
593
594    tmp= i.getItem();
595
596    i++;
597    for (; i.hasItem(); i++)
598    {
599      if (foundDifferent)
600        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
601      else
602        i.getItem() *= tmp;
603    }
604  }
605  else
606    y= Variable (1);
607
608  delete [] bufSqrfFactors;
609
610  return result;
611}
612
613
614CFList
615multiFactorize (const CanonicalForm& F, const Variable& v)
616{
617  if (F.inCoeffDomain())
618    return CFList (F);
619
620  // compress and find main Variable
621  CFMap N;
622  CanonicalForm A= myCompress (F, N);
623
624  //univariate case
625  if (F.isUnivariate())
626  {
627    CFList result;
628    if (v.level() != 1)
629      result= conv (factorize (F, v));
630    else
631      result= conv (factorize (F,true));
632    if (result.getFirst().inCoeffDomain())
633      result.removeFirst();
634    return result;
635  }
636
637  //bivariate case
638  if (A.level() == 2)
639  {
640    CFList buf= biFactorize (F, v);
641    return buf;
642  }
643
644  Variable x= Variable (1);
645  Variable y= Variable (2);
646
647  // remove content
648  CFList contentAi;
649  CanonicalForm lcmCont= lcmContent (A, contentAi);
650  A /= lcmCont;
651
652  // trivial after content removal
653  CFList contentAFactors;
654  if (A.inCoeffDomain())
655  {
656    for (CFListIterator i= contentAi; i.hasItem(); i++)
657    {
658      if (i.getItem().inCoeffDomain())
659        continue;
660      else
661      {
662        lcmCont /= i.getItem();
663        contentAFactors=
664        Union (multiFactorize (lcmCont, v),
665               multiFactorize (i.getItem(), v));
666        break;
667      }
668    }
669    decompress (contentAFactors, N);
670    if (isOn (SW_RATIONAL))
671      normalize (contentAFactors);
672    return contentAFactors;
673  }
674
675  // factorize content
676  contentAFactors= multiFactorize (lcmCont, v);
677
678  // univariate after content removal
679  CFList factors;
680  if (A.isUnivariate ())
681  {
682    if (v.level() != 1)
683      factors= conv (factorize (A, v));
684    else
685      factors= conv (factorize (A,true));
686    append (factors, contentAFactors);
687    decompress (factors, N);
688    return factors;
689  }
690
691  A *= bCommonDen (A);
692  // check main variable
693  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
694  int factorNums= 1;
695  CanonicalForm bivarEval;
696  CFList biFactors, bufBiFactors;
697  CanonicalForm evalPoly;
698  int lift, bufLift, lengthAeval2= A.level()-2;
699  CFList* bufAeval2= new CFList [lengthAeval2];
700  CFList* Aeval2= new CFList [lengthAeval2];
701  int counter;
702  int differentSecondVar= 0;
703  CanonicalForm bufA;
704  // several bivariate factorizations
705  REvaluation E (2, A.level(), IntRandom (25));
706  for (int i= 0; i < factorNums; i++)
707  {
708    counter= 0;
709    bufA= A;
710    bufAeval= CFList();
711    bufEvaluation= evalPoints (bufA, bufAeval, E);
712    E.nextpoint();
713    evalPoly= 0;
714
715    bivarEval= bufEvaluation.getLast();
716
717    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
718
719    for (int j= 0; j < lengthAeval2; j++)
720    {
721      if (!bufAeval2[j].isEmpty())
722        counter++;
723    }
724
725    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
726
727    TIMING_START (fac_bi_factorize);
728    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
729    TIMING_END_AND_PRINT (fac_bi_factorize,
730                          "time for bivariate factorization: ");
731    bufBiFactors.removeFirst();
732
733    if (bufBiFactors.length() == 1)
734    {
735      factors.append (A);
736      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
737      if (isOn (SW_RATIONAL))
738        normalize (factors);
739      delete [] bufAeval2;
740      delete [] Aeval2;
741      return factors;
742    }
743
744    if (i == 0)
745    {
746      Aeval= bufAeval;
747      evaluation= bufEvaluation;
748      biFactors= bufBiFactors;
749      lift= bufLift;
750      for (int j= 0; j < lengthAeval2; j++)
751        Aeval2 [j]= bufAeval2 [j];
752      differentSecondVar= counter;
753    }
754    else
755    {
756      if (bufBiFactors.length() < biFactors.length() ||
757          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
758          counter > differentSecondVar)
759      {
760        Aeval= bufAeval;
761        evaluation= bufEvaluation;
762        biFactors= bufBiFactors;
763        lift= bufLift;
764        for (int j= 0; j < lengthAeval2; j++)
765          Aeval2 [j]= bufAeval2 [j];
766        differentSecondVar= counter;
767      }
768    }
769    int k= 0;
770    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
771      evalPoly += j.getItem()*power (x, k);
772    list.append (evalPoly);
773  }
774
775  delete [] bufAeval2;
776
777  sortList (biFactors, x);
778
779  int minFactorsLength;
780  bool irred= false;
781  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
782
783  if (irred)
784  {
785    factors.append (A);
786    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
787    if (isOn (SW_RATIONAL))
788      normalize (factors);
789    delete [] Aeval2;
790    return factors;
791  }
792
793  if (minFactorsLength == 0)
794    minFactorsLength= biFactors.length();
795  else if (biFactors.length() > minFactorsLength)
796    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
797
798  if (differentSecondVar == lengthAeval2)
799  {
800    bool zeroOccured= false;
801    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
802    {
803      if (iter.getItem().isZero())
804      {
805        zeroOccured= true;
806        break;
807      }
808    }
809    if (!zeroOccured)
810    {
811      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
812                                minFactorsLength);
813      if (factors.length() == biFactors.length())
814      {
815        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
816        normalize (factors);
817        delete [] Aeval2;
818        return factors;
819      }
820      else
821        factors= CFList();
822      //TODO case where factors.length() > 0
823    }
824  }
825
826  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
827
828  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
829
830  CFList * oldAeval= new CFList [lengthAeval2];
831  for (int i= 0; i < lengthAeval2; i++)
832    oldAeval[i]= Aeval2[i];
833
834  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
835
836  CFList biFactorsLCs;
837  for (CFListIterator i= biFactors; i.hasItem(); i++)
838    biFactorsLCs.append (LC (i.getItem(), 1));
839
840  Variable w;
841  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
842                                          evaluation, Aeval2, lengthAeval2, w);
843
844  if (w.level() != 1)
845  {
846    A= swapvar (A, y, w);
847    int i= A.level();
848    CanonicalForm evalPoint;
849    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
850    {
851      if (i == w.level())
852      {
853        evalPoint= iter.getItem();
854        iter.getItem()= evaluation.getLast();
855        evaluation.removeLast();
856        evaluation.append (evalPoint);
857        break;
858      }
859    }
860    for (i= 0; i < lengthAeval2; i++)
861    {
862      if (oldAeval[i].isEmpty())
863        continue;
864      if (oldAeval[i].getFirst().level() == w.level())
865      {
866        CFArray tmp= copy (oldAeval[i]);
867        oldAeval[i]= biFactors; 
868        for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
869          iter.getItem()= swapvar (iter.getItem(), w, y);
870        for (int ii= 0; ii < tmp.size(); ii++)
871          tmp[ii]= swapvar (tmp[ii], w, y);
872        CFArray tmp2= CFArray (tmp.size());
873        CanonicalForm buf;
874        for (int ii= 0; ii < tmp.size(); ii++)
875        {
876          buf= tmp[ii] (evaluation.getLast(),y);
877          buf /= Lc (buf);
878          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
879        }
880        biFactors= CFList();
881        for (int j= 0; j < tmp2.size(); j++)
882          biFactors.append (tmp2[j]);
883      }
884    }
885  }
886
887  CFListIterator iter;
888  CanonicalForm oldA= A;
889  CFList oldBiFactors= biFactors;
890  if (!leadingCoeffs.getFirst().inCoeffDomain())
891  {
892    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
893    A *= tmp;
894    tmp= leadingCoeffs.getFirst();
895    iter= evaluation;
896    for (int i= A.level(); i > 2; i--, iter++)
897      tmp= tmp (iter.getItem(), i);
898    if (!tmp.inCoeffDomain())
899    {
900      for (CFListIterator i= biFactors; i.hasItem(); i++)
901      {
902        i.getItem() *= tmp/LC (i.getItem(), 1);
903        i.getItem() /= Lc (i.getItem());
904      }
905    }
906  }
907
908  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
909  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
910  leadingCoeffs.removeFirst();
911
912  //prepare leading coefficients
913  CFList* leadingCoeffs2= new CFList [lengthAeval2];
914  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
915                        evaluation);
916
917
918  Aeval= evaluateAtEval (A, evaluation, 2);
919
920  CanonicalForm hh= 1/Lc (Aeval.getFirst());
921
922  for (iter= Aeval; iter.hasItem(); iter++)
923    iter.getItem() *= hh;
924
925  A *= hh;
926
927  CFListIterator iter2;
928  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
929  bufBiFactors= biFactors;
930  bufA= A;
931  CanonicalForm bufLCmultiplier= LCmultiplier;
932  CanonicalForm testVars;
933  if (!LCmultiplierIsConst)
934  {
935    testVars= Variable (2);
936    for (int i= 0; i < lengthAeval2; i++)
937    {
938      if (!oldAeval[i].isEmpty())
939        testVars *= oldAeval[i].getFirst().mvar();
940    }
941  }
942  CFList bufFactors= CFList();
943  bool LCheuristic= false;
944  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
945                                factors))
946  {
947    int check= biFactors.length();
948    int * index= new int [factors.length()];
949    CFList oldFactors= factors;
950    factors= recoverFactors (A, factors, index);
951
952    if (check == factors.length())
953    {
954      if (w.level() != 1)
955      {
956        for (iter= factors; iter.hasItem(); iter++)
957          iter.getItem()= swapvar (iter.getItem(), w, y);
958      }
959
960      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
961      normalize (factors);
962      delete [] index;
963      delete [] Aeval2;
964      return factors;
965    }
966    else if (factors.length() > 0)
967    {
968      int oneCount= 0;
969      CFList l;
970      for (int i= 0; i < check; i++)
971      {
972        if (index[i] == 1)
973        {
974          iter=biFactors;
975          for (int j=1; j <= i-oneCount; j++)
976            iter++;
977          iter.remove (1);
978          for (int j= 0; j < lengthAeval2; j++)
979          {
980            l= leadingCoeffs2[j];
981            iter= l;
982            for (int k=1; k <= i-oneCount; k++)
983              iter++;
984            iter.remove (1);
985            leadingCoeffs2[j]=l;
986          }
987          oneCount++;
988        }
989      }
990      bufFactors= factors;
991      factors= CFList();
992    }
993    else if (!LCmultiplierIsConst && factors.length() == 0)
994    {
995      LCheuristic= true;
996      factors= oldFactors;
997      CanonicalForm cont;
998      CFList contents, LCs;
999      int index=1;
1000      bool foundTrueMultiplier= false;
1001      for (iter= factors; iter.hasItem(); iter++, index++)
1002      {
1003        cont= content (iter.getItem(), 1);
1004        cont= gcd (cont , LCmultiplier);
1005        contents.append (cont);
1006        if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
1007        {
1008          foundTrueMultiplier= true;
1009          int index2= 1;
1010          for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
1011                                                                    index2++)
1012          {
1013            if (index2 == index)
1014              continue;
1015            iter2.getItem() /= LCmultiplier;
1016          }
1017          A= oldA;
1018          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1019          for (int i= lengthAeval2-1; i > -1; i--)
1020            leadingCoeffs2[i]= CFList();
1021          prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
1022                                biFactors, evaluation );
1023          Aeval= evaluateAtEval (A, evaluation, 2);
1024
1025          hh= 1/Lc (Aeval.getFirst());
1026
1027          for (iter2= Aeval; iter2.hasItem(); iter2++)
1028            iter2.getItem() *= hh;
1029
1030          A *= hh;
1031          break;
1032        }
1033        else
1034          LCs.append (LC (iter.getItem()/cont, 1));
1035      }
1036      if (!foundTrueMultiplier)
1037      {
1038        index= 1;
1039        iter2= factors;
1040        bool foundMultiplier= false;
1041        for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
1042        {
1043          if (fdivides (iter.getItem(), LCmultiplier))
1044          {
1045            if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
1046                !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
1047            {
1048              int index2= 1;
1049              for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
1050                   iter3.hasItem(); iter3++, index2++)
1051              {
1052                if (index2 == index)
1053                {
1054                  iter3.getItem() /= LCmultiplier;
1055                  break;
1056                }
1057              }
1058              A /= LCmultiplier;
1059              foundMultiplier= true;
1060              iter.getItem()= 1;
1061            }
1062          }
1063        }
1064        // coming from above: divide out more LCmultiplier if possible
1065        if (foundMultiplier)
1066        {
1067          foundMultiplier= false;
1068          index=1;
1069          iter2= factors;
1070          for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
1071          {
1072            if (!iter.getItem().isOne() &&
1073                fdivides (iter.getItem(), LCmultiplier))
1074            {
1075              if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
1076              {
1077                int index2= 1;
1078                for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1079                     iter2++, index2++)
1080                {
1081                  if (index2 == index)
1082                  {
1083                    iter2.getItem() /= iter.getItem();
1084                    foundMultiplier= true;
1085                    break;
1086                  }
1087                }
1088                A /= iter.getItem();
1089                LCmultiplier /= iter.getItem();
1090                iter.getItem()= 1;
1091              }
1092              else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
1093              {
1094                Variable xx= Variable (2);
1095                CanonicalForm vars;
1096                vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
1097                                          xx));
1098                for (int i= 0; i < lengthAeval2; i++)
1099                {
1100                  if (oldAeval[i].isEmpty())
1101                    continue;
1102                  xx= oldAeval[i].getFirst().mvar();
1103                  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
1104                                             xx));
1105                }
1106                if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
1107                    /myGetVars (LCmultiplier) == vars)
1108                {
1109                  int index2= 1;
1110                  for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1111                       iter2++, index2++)
1112                  {
1113                    if (index2 == index)
1114                    {
1115                      iter2.getItem() /= LCmultiplier;
1116                      foundMultiplier= true;
1117                      break;
1118                    }
1119                  }
1120                  A /= LCmultiplier;
1121                  iter.getItem()= 1;
1122                }
1123              }
1124            }
1125          }
1126        }
1127        else
1128        {
1129          CanonicalForm pLCs= prod (LCs);
1130          if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
1131          {
1132            A= oldA;
1133            iter2= leadingCoeffs2[lengthAeval2-1];
1134            for (iter= contents; iter.hasItem(); iter++, iter2++)
1135              iter2.getItem() /= iter.getItem();
1136            foundMultiplier= true;
1137          }
1138          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
1139          {
1140            Variable xx;
1141            CFList vars1;
1142            CFFList sqrfMultiplier= sqrFree (LCmultiplier);
1143            if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
1144              sqrfMultiplier.removeFirst();
1145            sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
1146            xx= Variable (2);
1147            for (iter= oldBiFactors; iter.hasItem(); iter++)
1148              vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
1149            for (int i= 0; i < lengthAeval2; i++)
1150            {
1151              if (oldAeval[i].isEmpty())
1152                continue;
1153              xx= oldAeval[i].getFirst().mvar();
1154              iter2= vars1;
1155              for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
1156                iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx));
1157            }
1158            CanonicalForm tmp;
1159            iter2= vars1;
1160            for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++,
1161                                                                    iter2++)
1162            {
1163              tmp= iter.getItem()/LCmultiplier;
1164              for (int i=1; i <= tmp.level(); i++)
1165              {
1166                if (degree(tmp,i) > 0 &&
1167                    (degree(iter2.getItem(),i) > degree (tmp,i)))
1168                  iter2.getItem() /= power (Variable (i), degree (tmp,i));
1169              }
1170            }
1171            int multi;
1172            for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
1173            {
1174              multi= 0;
1175              for (iter= vars1; iter.hasItem(); iter++)
1176              {
1177                tmp= iter.getItem();
1178                while (fdivides (myGetVars (ii.getItem().factor()), tmp))
1179                {
1180                  multi++;
1181                  tmp /= myGetVars (ii.getItem().factor());
1182                }
1183              }
1184              if (multi == ii.getItem().exp())
1185              {
1186                index= 1;
1187                for (iter= vars1; iter.hasItem(); iter++, index++)
1188                {
1189                  while (fdivides (myGetVars(ii.getItem().factor()),
1190                                   iter.getItem()
1191                                  )
1192                        )
1193                  {
1194                    int index2= 1;
1195                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1196                         iter2++, index2++)
1197                    {
1198                      if (index2 == index)
1199                        continue;
1200                      else
1201                      {
1202                        tmp= ii.getItem().factor();
1203                        iter2.getItem() /= tmp;
1204                        CFListIterator iter3= evaluation;
1205                        for (int jj= A.level(); jj > 2; jj--, iter3++)
1206                          tmp= tmp (iter3.getItem(), jj);
1207                        if (!tmp.inCoeffDomain())
1208                        {
1209                          int index3= 1;
1210                          for (iter3= biFactors; iter3.hasItem(); iter3++,
1211                                                                  index3++)
1212                          {
1213                            if (index3 == index2)
1214                            {
1215                              iter3.getItem() /= tmp;
1216                              iter3.getItem() /= Lc (iter3.getItem());
1217                              break;
1218                            }
1219                          }
1220                        }
1221                        A /= ii.getItem().factor();
1222                      }
1223                    }
1224                    iter.getItem() /= getVars (ii.getItem().factor());
1225                  }
1226                }
1227              }
1228              else
1229              {
1230                index= 1;
1231                for (iter= vars1; iter.hasItem(); iter++, index++)
1232                {
1233                  if (!fdivides (myGetVars (ii.getItem().factor()),
1234                                 iter.getItem()
1235                                )
1236                     )
1237                  {
1238                    int index2= 1;
1239                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1240                         iter2++, index2++)
1241                    {
1242                      if (index2 == index)
1243                      {
1244                        tmp= power (ii.getItem().factor(), ii.getItem().exp());
1245                        iter2.getItem() /= tmp;
1246                        A /= tmp;
1247                        CFListIterator iter3= evaluation;
1248                        for (int jj= A.level(); jj > 2; jj--, iter3++)
1249                          tmp= tmp (iter3.getItem(), jj);
1250                        if (!tmp.inCoeffDomain())
1251                        {
1252                          int index3= 1;
1253                          for (iter3= biFactors; iter3.hasItem(); iter3++,
1254                                                                  index3++)
1255                          {
1256                            if (index3 == index2)
1257                            {
1258                              iter3.getItem() /= tmp;
1259                              iter3.getItem() /= Lc (iter3.getItem());
1260                              break;
1261                            }
1262                          }
1263                        }
1264                      }
1265                    }
1266                  }
1267                }
1268              }
1269            }
1270          }
1271        }
1272
1273        // patch everything together again
1274        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1275        for (int i= lengthAeval2-1; i > -1; i--)
1276          leadingCoeffs2[i]= CFList();
1277        prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
1278                              evaluation);
1279        Aeval= evaluateAtEval (A, evaluation, 2);
1280
1281        hh= 1/Lc (Aeval.getFirst());
1282
1283        for (CFListIterator i= Aeval; i.hasItem(); i++)
1284          i.getItem() *= hh;
1285
1286        A *= hh;
1287      }
1288      factors= CFList();
1289      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
1290      {
1291        LCheuristic= false;
1292        A= bufA;
1293        biFactors= bufBiFactors;
1294        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
1295        LCmultiplier= bufLCmultiplier;
1296      }
1297    }
1298    else
1299      factors= CFList();
1300    delete [] index;
1301  }
1302  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
1303      && fdivides (getVars (LCmultiplier), testVars))
1304  {
1305    LCheuristic= true;
1306    int index;
1307    Variable xx;
1308    CFList vars1;
1309    CFFList sqrfMultiplier= sqrFree (LCmultiplier);
1310    if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
1311      sqrfMultiplier.removeFirst();
1312    sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
1313    xx= Variable (2);
1314    for (iter= oldBiFactors; iter.hasItem(); iter++)
1315      vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
1316    for (int i= 0; i < lengthAeval2; i++)
1317    {
1318      if (oldAeval[i].isEmpty())
1319        continue;
1320      xx= oldAeval[i].getFirst().mvar();
1321      iter2= vars1;
1322      for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
1323        iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
1324    }
1325    CanonicalForm tmp;
1326    iter2= vars1;
1327    for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++)
1328    {
1329      tmp= iter.getItem()/LCmultiplier;
1330      for (int i=1; i <= tmp.level(); i++)
1331      {
1332        if (degree(tmp,i) > 0 && (degree(iter2.getItem(),i) > degree (tmp,i)))
1333          iter2.getItem() /= power (Variable (i), degree (tmp,i));
1334      }
1335    }
1336    int multi;
1337    for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
1338    {
1339      multi= 0;
1340      for (iter= vars1; iter.hasItem(); iter++)
1341      {
1342        tmp= iter.getItem();
1343        while (fdivides (myGetVars (ii.getItem().factor()), tmp))
1344        {
1345          multi++;
1346          tmp /= myGetVars (ii.getItem().factor());
1347        }
1348      }
1349      if (multi == ii.getItem().exp())
1350      {
1351        index= 1;
1352        for (iter= vars1; iter.hasItem(); iter++, index++)
1353        {
1354          while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
1355          {
1356            int index2= 1;
1357            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
1358                                                                      index2++)
1359            {
1360              if (index2 == index)
1361                continue;
1362              else
1363              {
1364                tmp= ii.getItem().factor();
1365                iter2.getItem() /= tmp;
1366                CFListIterator iter3= evaluation;
1367                for (int jj= A.level(); jj > 2; jj--, iter3++)
1368                  tmp= tmp (iter3.getItem(), jj);
1369                if (!tmp.inCoeffDomain())
1370                {
1371                  int index3= 1;
1372                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
1373                  {
1374                    if (index3 == index2)
1375                    {
1376                      iter3.getItem() /= tmp;
1377                      iter3.getItem() /= Lc (iter3.getItem());
1378                      break;
1379                    }
1380                  }
1381                }
1382                A /= ii.getItem().factor();
1383              }
1384            }
1385            iter.getItem() /= getVars (ii.getItem().factor());
1386          }
1387        }
1388      }
1389      else
1390      {
1391        index= 1;
1392        for (iter= vars1; iter.hasItem(); iter++, index++)
1393        {
1394          if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
1395          {
1396            int index2= 1;
1397            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
1398                                                                      index2++)
1399            {
1400              if (index2 == index)
1401              {
1402                tmp= power (ii.getItem().factor(), ii.getItem().exp());
1403                iter2.getItem() /= tmp;
1404                A /= tmp;
1405                CFListIterator iter3= evaluation;
1406                for (int jj= A.level(); jj > 2; jj--, iter3++)
1407                  tmp= tmp (iter3.getItem(), jj);
1408                if (!tmp.inCoeffDomain())
1409                {
1410                  int index3= 1;
1411                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
1412                  {
1413                    if (index3 == index2)
1414                    {
1415                      iter3.getItem() /= tmp;
1416                      iter3.getItem() /= Lc (iter3.getItem());
1417                      break;
1418                    }
1419                  }
1420                }
1421              }
1422            }
1423          }
1424        }
1425      }
1426    }
1427
1428    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1429    for (int i= lengthAeval2-1; i > -1; i--)
1430      leadingCoeffs2[i]= CFList();
1431    prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
1432                          evaluation);
1433    Aeval= evaluateAtEval (A, evaluation, 2);
1434
1435    hh= 1/Lc (Aeval.getFirst());
1436
1437    for (CFListIterator i= Aeval; i.hasItem(); i++)
1438      i.getItem() *= hh;
1439
1440    A *= hh;
1441
1442    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
1443    {
1444      LCheuristic= false;
1445      A= bufA;
1446      biFactors= bufBiFactors;
1447      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
1448      LCmultiplier= bufLCmultiplier;
1449    }
1450  }
1451
1452tryAgainWithoutHeu:
1453  //shifting to zero
1454  A= shift2Zero (A, Aeval, evaluation);
1455
1456  for (iter= biFactors; iter.hasItem(); iter++)
1457    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1458
1459  for (int i= 0; i < lengthAeval2-1; i++)
1460    leadingCoeffs2[i]= CFList();
1461  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
1462  {
1463    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
1464    for (int i= A.level() - 4; i > -1; i--)
1465    {
1466      if (i + 1 == lengthAeval2-1)
1467        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
1468      else
1469        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
1470    }
1471  }
1472
1473  CFArray Pi;
1474  CFList diophant;
1475  int* liftBounds= new int [A.level() - 1];
1476  int liftBoundsLength= A.level() - 1;
1477  for (int i= 0; i < liftBoundsLength; i++)
1478    liftBounds [i]= degree (A, i + 2) + 1;
1479
1480  Aeval.removeFirst();
1481  bool noOneToOne= false;
1482
1483  CFList commonDenominators;
1484  for (iter=biFactors; iter.hasItem(); iter++)
1485    commonDenominators.append (bCommonDen (iter.getItem()));
1486  CanonicalForm tmp1, tmp2, tmp3=1;
1487  for (int i= 0; i < lengthAeval2; i++)
1488  {
1489    iter2= commonDenominators;
1490    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
1491    {
1492      tmp1= bCommonDen (iter.getItem());
1493      Off (SW_RATIONAL);
1494      iter2.getItem()= lcm (iter2.getItem(), tmp1);
1495      On (SW_RATIONAL);
1496    }
1497  }
1498  tmp1= prod (commonDenominators);
1499  for (iter= Aeval; iter.hasItem(); iter++)
1500  {
1501    tmp2= bCommonDen (iter.getItem());
1502    Off (SW_RATIONAL);
1503    tmp3= lcm (tmp2,tmp3);
1504    On (SW_RATIONAL);
1505  }
1506  CanonicalForm multiplier;
1507  multiplier= tmp3/tmp1;
1508  iter2= commonDenominators;
1509  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
1510    iter.getItem() *= iter2.getItem()*multiplier;
1511
1512  for (iter= Aeval; iter.hasItem(); iter++)
1513    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1);
1514
1515  for (int i= 0; i < lengthAeval2; i++)
1516  {
1517    iter2= commonDenominators;
1518    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
1519      iter.getItem() *= iter2.getItem()*multiplier;
1520  }
1521
1522
1523  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
1524                               Pi, liftBounds, liftBoundsLength, noOneToOne);
1525
1526  if (!noOneToOne)
1527  {
1528    int check= factors.length();
1529    A= oldA;
1530    factors= recoverFactors (A, factors, evaluation);
1531    if (check != factors.length())
1532      noOneToOne= true;
1533    else
1534      factors= Union (factors, bufFactors);
1535  }
1536  if (noOneToOne)
1537  {
1538    if (!LCmultiplierIsConst && LCheuristic)
1539    {
1540      A= bufA;
1541      biFactors= bufBiFactors;
1542      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
1543      delete [] liftBounds;
1544      LCheuristic= false;
1545      goto tryAgainWithoutHeu;
1546      //something probably went wrong in the heuristic
1547    }
1548
1549    A= shift2Zero (oldA, Aeval, evaluation);
1550    biFactors= oldBiFactors;
1551    for (iter= biFactors; iter.hasItem(); iter++)
1552      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1553    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
1554    CanonicalForm yToLift= power (y, lift);
1555    CFListIterator i= biFactors;
1556    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
1557    i++;
1558
1559    for (; i.hasItem(); i++)
1560      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
1561
1562    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
1563
1564    i= biFactors;
1565    yToLift= power (y, lift);
1566    CanonicalForm dummy;
1567    for (; i.hasItem(); i++)
1568    {
1569      LCA= LC (i.getItem(), 1);
1570      extgcd (LCA, yToLift, LCA, dummy);
1571      i.getItem()= mod (i.getItem()*LCA, yToLift);
1572    }
1573
1574    liftBoundsLength= F.level() - 1;
1575    liftBounds= liftingBounds (A, lift);
1576
1577    CFList MOD;
1578    bool earlySuccess;
1579    CFList earlyFactors;
1580    ExtensionInfo info= ExtensionInfo (false);
1581    CFList liftedFactors;
1582    TIMING_START (fac_hensel_lift);
1583    liftedFactors= henselLiftAndEarly
1584                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
1585                    Aeval, biFactors, evaluation, info);
1586    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
1587
1588    TIMING_START (fac_factor_recombination);
1589    factors= factorRecombination (A, liftedFactors, MOD);
1590    TIMING_END_AND_PRINT (fac_factor_recombination,
1591                          "time for factor recombination: ");
1592
1593    if (earlySuccess)
1594      factors= Union (factors, earlyFactors);
1595
1596    for (CFListIterator i= factors; i.hasItem(); i++)
1597    {
1598      int kk= Aeval.getLast().level();
1599      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
1600      {
1601        if (i.getItem().level() < kk)
1602          continue;
1603       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
1604      }
1605    }
1606  }
1607
1608  if (w.level() != 1)
1609  {
1610    for (CFListIterator iter= factors; iter.hasItem(); iter++)
1611      iter.getItem()= swapvar (iter.getItem(), w, y);
1612  }
1613
1614  swap (factors, 0, 0, x);
1615  append (factors, contentAFactors);
1616  decompress (factors, N);
1617  if (isOn (SW_RATIONAL))
1618    normalize (factors);
1619
1620  delete [] leadingCoeffs2;
1621  delete [] oldAeval;
1622  delete [] Aeval2;
1623  delete[] liftBounds;
1624
1625  return factors;
1626}
1627
1628#endif
Note: See TracBrowser for help on using the repository browser.