source: git/factory/facFactorize.cc @ 229530

spielwiese
Last change on this file since 229530 was 229530, checked in by Martin Lee <martinlee84@…>, 12 years ago
fixed memory leaks in factorization and replaced mpz_fdiv_q by mpz_divexact in int_rat.cc git-svn-id: file:///usr/local/Singular/svn/trunk@14398 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 21.9 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqFactorize.cc
5 *
6 * multivariate factorization over Q(a)
7 *
8 * @author Martin Lee
9 *
10 * @internal @version \$Id$
11 *
12 **/
13/*****************************************************************************/
14
15#include <config.h>
16
17#include "assert.h"
18#include "debug.h"
19#include "timing.h"
20
21#include "facFqFactorizeUtil.h"
22#include "facFactorize.h"
23#include "facFqFactorize.h"
24#include "cf_random.h"
25#include "facHensel.h"
26#include "cf_gcd_smallp.h"
27#include "cf_map_ext.h"
28#include "algext.h"
29#include "cf_reval.h"
30
31CFList evalPoints (const CanonicalForm& F, CFList& eval, Evaluation& E)
32{
33  CFList result;
34  Variable x= Variable (1);
35
36  bool found= false;
37  CanonicalForm deriv_x, gcd_deriv;
38  CFListIterator iter;
39  do
40  {
41    eval.insert (F);
42    bool bad= false;
43    for (int i= E.max(); i >= E.min(); i--)
44    {
45      eval.insert (eval.getFirst()( E [i], i));
46      result.append (E[i]);
47      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
48      {
49        result= CFList();
50        eval= CFList();
51        bad= true;
52        break;
53      }
54    }
55
56    if (bad)
57    {
58      E.nextpoint();
59      continue;
60    }
61
62    if (degree (eval.getFirst()) != degree (F, 1))
63    {
64      result= CFList();
65      eval= CFList();
66      E.nextpoint();
67      continue;
68    }
69
70    deriv_x= deriv (eval.getFirst(), x);
71    gcd_deriv= gcd (eval.getFirst(), deriv_x);
72    if (degree (gcd_deriv) > 0)
73    {
74      result= CFList();
75      eval= CFList();
76      E.nextpoint();
77      continue;
78    }
79    iter= eval;
80    iter++;
81    CanonicalForm contentx= content (iter.getItem(), x);
82    if (degree (contentx) > 0)
83    {
84      result= CFList();
85      eval= CFList();
86      E.nextpoint();
87      continue;
88    }
89    found= true;
90  }
91  while (!found);
92
93  if (!eval.isEmpty())
94    eval.removeFirst();
95  return result;
96}
97
98void
99factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
100                                     int& minFactorsLength, bool& irred,
101                                     const Variable& w)
102{
103  Variable x= Variable (1);
104  minFactorsLength= 0;
105  irred= false;
106  Variable v;
107  CFList factors;
108  for (int j= 0; j < A.level() - 2; j++)
109  {
110    if (!Aeval[j].isEmpty())
111    {
112      v= Variable (Aeval[j].getFirst().level());
113
114      factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
115
116      if (factors.getFirst().inCoeffDomain())
117        factors.removeFirst();
118
119      if (minFactorsLength == 0)
120        minFactorsLength= factors.length();
121      else
122        minFactorsLength= tmin (minFactorsLength, factors.length());
123
124      if (factors.length() == 1)
125      {
126        irred= true;
127        return;
128      }
129      sortList (factors, x);
130      Aeval [j]= factors;
131    }
132  }
133}
134
135int
136testFactors (const CanonicalForm& G, const CFList& uniFactors,
137             CanonicalForm& sqrfPartF, CFList& factors,
138             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF)
139{
140  CanonicalForm tmp;
141  CFListIterator j;
142  for (CFListIterator i= uniFactors; i.hasItem(); i++)
143  {
144    tmp= i.getItem();
145    if (i.hasItem())
146      i++;
147    else
148      break;
149    for (j= i; j.hasItem(); j++)
150    {
151      if (tmp == j.getItem())
152        return 0;
153    }
154  }
155
156  CanonicalForm F= G;
157  CFFList sqrfFactorization= sqrFree (F);
158
159  sqrfPartF= 1;
160  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
161    sqrfPartF *= i.getItem().factor();
162
163  evalSqrfPartF= evaluateAtZero (sqrfPartF);
164
165  CanonicalForm test= evalSqrfPartF.getFirst() (0, 2);
166
167  if (degree (test) != degree (sqrfPartF, 1))
168    return 0;
169
170  CFFList sqrfFactors;
171  CFList tmp2;
172  int k= 0;
173  factors= uniFactors;
174  CFFListIterator iter;
175  for (CFListIterator i= factors; i.hasItem(); i++, k++)
176  {
177    tmp= 1;
178    sqrfFactors= sqrFree (i.getItem());
179
180    for (iter= sqrfFactors; iter.hasItem(); iter++)
181    {
182      tmp2.append (iter.getItem().factor());
183      tmp *= iter.getItem().factor();
184    }
185    i.getItem()= tmp/Lc(tmp);
186    bufSqrfFactors [k]= sqrfFactors;
187  }
188
189  for (int i= 0; i < factors.length() - 1; i++)
190  {
191    for (int k= i + 1; k < factors.length(); k++)
192    {
193      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
194    }
195  }
196
197  factors= CFList();
198  for (int i= 0; i < uniFactors.length(); i++)
199  {
200    if (i == 0)
201    {
202      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
203      {
204        if (iter.getItem().factor().inCoeffDomain())
205          continue;
206        iter.getItem()= CFFactor (iter.getItem().factor()/
207                                  Lc (iter.getItem().factor()),
208                                  iter.getItem().exp());
209        factors.append (iter.getItem().factor());
210      }
211    }
212    else
213    {
214      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
215      {
216        if (iter.getItem().factor().inCoeffDomain())
217          continue;
218        iter.getItem()= CFFactor (iter.getItem().factor()/
219                               Lc (iter.getItem().factor()),
220                               iter.getItem().exp());
221        if (!find (factors, iter.getItem().factor()))
222          factors.append (iter.getItem().factor());
223      }
224    }
225  }
226
227  test= prod (factors);
228  tmp= evalSqrfPartF.getFirst() (0,2);
229  if (test/Lc (test) != tmp/Lc (tmp))
230    return 0;
231  else
232    return 1;
233}
234
235CFList
236precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
237                        const CFList& evaluation,CFList*& differentSecondVarLCs,
238                        int length, Variable& y
239                       )
240{
241  y= Variable (1);
242  if (LCF.inCoeffDomain())
243  {
244    CFList result;
245    for (int i= 1; i <= LCFFactors.length() + 1; i++)
246      result.append (1);
247    return result;
248  }
249
250  CFMap N;
251  CanonicalForm F= compress (LCF, N);
252  if (LCF.isUnivariate())
253  {
254    CFList result;
255    int LCFLevel= LCF.level();
256    bool found= false;
257    if (LCFLevel == 2)
258    {
259    //bivariate leading coefficients are already the true leading coefficients
260      result= LCFFactors;
261      Variable v= Variable (LCF.mvar());
262      CanonicalForm bla= 1;
263      for (CFListIterator i= result; i.hasItem(); i++)
264      {
265        i.getItem()= i.getItem() (v+evaluation.getLast(), v);
266        bla *= Lc (i.getItem());
267      }
268      found= true;
269    }
270    else
271    {
272      CFListIterator j;
273      for (int i= 0; i < length; i++)
274      {
275        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
276        {
277          if (j.getItem().level() == LCFLevel)
278          {
279            found= true;
280            break;
281          }
282        }
283        if (found)
284        {
285          result= differentSecondVarLCs [i];
286          break;
287        }
288      }
289      if (!found)
290        result= LCFFactors;
291    }
292    if (found)
293      result.insert (Lc (LCF));
294    else
295      result.append (LCF);
296    return result;
297  }
298
299  CFList factors= LCFFactors;
300
301  CFMap dummy;
302  for (CFListIterator i= factors; i.hasItem(); i++)
303  {
304    i.getItem()= compress (i.getItem(), dummy);
305    i.getItem()= i.getItem() (Variable (1)+evaluation.getLast(), Variable (1));
306  }
307
308  CanonicalForm sqrfPartF;
309  CFFList * bufSqrfFactors= new CFFList [factors.length()];
310  CFList evalSqrfPartF;
311  CFList bufFactors;
312  //TODO sqrfPartF einmal berechnen nicht stÀndig
313  int pass= testFactors (F, factors, sqrfPartF,
314                         bufFactors, bufSqrfFactors, evalSqrfPartF);
315
316  bool foundDifferent= false;
317  Variable z;
318  Variable x= y;
319  int j= 0;
320  if (!pass)
321  {
322    int lev;
323    for (int i= 1; i <= LCF.level(); i++)
324    {
325      if(degree (LCF, i) > 0)
326      {
327        lev= i - 1;
328        break;
329      }
330    }
331    for (int i= 0; i < length; i++)
332    {
333      CanonicalForm bufF;
334      CFListIterator iter;
335      CFList bufBufFactors;
336      if (!differentSecondVarLCs [i].isEmpty())
337      {
338        bool allConstant= true;
339        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
340        {
341          if (!iter.getItem().inCoeffDomain())
342          {
343            allConstant= false;
344            y= Variable (iter.getItem().level());
345          }
346        }
347        if (allConstant)
348          continue;
349
350        bufFactors= differentSecondVarLCs [i];
351        for (iter= bufFactors; iter.hasItem(); iter++)
352          iter.getItem()= swapvar (iter.getItem(), x, y);
353        bufF= F;
354        z= Variable (y.level() - lev);
355        bufF= swapvar (bufF, x, z);
356        bufBufFactors= bufFactors;
357        pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
358                           bufSqrfFactors, evalSqrfPartF);
359        if (pass)
360        {
361          foundDifferent= true;
362          F= bufF;
363          CFList l= factors;
364          for (iter= l; iter.hasItem(); iter++)
365            iter.getItem()= swapvar (iter.getItem(), x, y);
366          differentSecondVarLCs [i]= l;
367          j= i;
368          break;
369        }
370        if (!pass && i == length - 1)
371        {
372          CFList result;
373          result.append (LCF);
374          for (int j= 1; j <= factors.length(); j++)
375            result.append (LCF);
376          y= Variable (1);
377          delete [] bufSqrfFactors;
378          return result;
379        }
380      }
381    }
382  }
383  if (!pass)
384  {
385    CFList result;
386    result.append (LCF);
387    for (int j= 1; j <= factors.length(); j++)
388      result.append (LCF);
389    y= Variable (1);
390    delete [] bufSqrfFactors;
391    return result;
392  }
393  else
394    factors= bufFactors;
395
396
397  bufFactors= factors;
398
399  if (factors.length() > 1)
400  {
401    CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1);
402
403    CFArray leadingCoeffs= CFArray (factors.length());
404    for (int i= 0; i < factors.length(); i++)
405      leadingCoeffs[i]= LC1;
406    for (CFListIterator i= factors; i.hasItem(); i++)
407      i.getItem() *= LC1 (0,2)/Lc (i.getItem());
408    factors.insert (1);
409
410    CanonicalForm
411    newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
412
413    int liftBound= degree (newSqrfPartF,2) + 1;
414
415    CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
416    CFArray Pi;
417    CFList diophant;
418    henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
419                   leadingCoeffs, false);
420
421    if (sqrfPartF.level() > 2)
422    {
423      int* liftBounds= new int [sqrfPartF.level() - 1];
424      liftBounds [0]= liftBound;
425      bool noOneToOne= false;
426      CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
427      LC1= LC (evalSqrfPartF.getLast(), 1);
428      CFList LCs;
429      for (int i= 0; i < factors.length(); i++)
430        LCs.append (LC1);
431      leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
432      for (int i= sqrfPartF.level() - 1; i > 2; i--)
433      {
434        for (CFListIterator j= LCs; j.hasItem(); j++)
435          j.getItem()= j.getItem() (0, i + 1);
436        leadingCoeffs2 [i - 3]= LCs;
437      }
438      sqrfPartF= sqrfPartF*power (LC1, factors.length()-1);
439
440      int liftBoundsLength= sqrfPartF.level() - 1;
441      for (int i= 1; i < liftBoundsLength; i++)
442        liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
443      evalSqrfPartF= evaluateAtZero (sqrfPartF);
444      evalSqrfPartF.removeFirst();
445      factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
446               diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
447      delete [] leadingCoeffs2;
448      delete [] liftBounds;
449    }
450  }
451  else
452    factors= evalSqrfPartF.getLast();
453
454  CFList interMedResult= recoverFactors (evalSqrfPartF.getLast(), factors);
455
456  CFList result;
457  CFFListIterator k;
458  CanonicalForm tmp;
459  for (int i= 0; i < LCFFactors.length(); i++)
460  {
461    tmp= 1;
462    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
463    {
464      int pos= findItem (bufFactors, k.getItem().factor());
465      if (pos)
466        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
467    }
468    result.append (tmp);
469  }
470
471  for (CFListIterator i= result; i.hasItem(); i++)
472  {
473    F /= i.getItem();
474    if (foundDifferent)
475      i.getItem()= swapvar (i.getItem(), x, z);
476    i.getItem()= N (i.getItem());
477  }
478
479  if (foundDifferent)
480  {
481    CFList l= differentSecondVarLCs [j];
482    for (CFListIterator i= l; i.hasItem(); i++)
483      i.getItem()= swapvar (i.getItem(), y, z);
484    differentSecondVarLCs [j]= l;
485    F= swapvar (F, x, z);
486  }
487
488  result.insert (N (F));
489
490  result= distributeContent (result, differentSecondVarLCs, length);
491
492  if (!result.getFirst().inCoeffDomain())
493  {
494    CFListIterator i= result;
495    CanonicalForm tmp;
496    if (foundDifferent)
497      i.getItem()= swapvar (i.getItem(), Variable (2), y);
498
499    tmp= i.getItem();
500
501    i++;
502    for (; i.hasItem(); i++)
503    {
504      if (foundDifferent)
505        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
506      else
507        i.getItem() *= tmp;
508    }
509  }
510  else
511    y= Variable (1);
512
513  delete [] bufSqrfFactors;
514
515  return result;
516}
517
518
519CFList
520multiFactorize (const CanonicalForm& F, const Variable& v)
521{
522  if (F.inCoeffDomain())
523    return CFList (F);
524
525  // compress and find main Variable
526  CFMap N;
527  CanonicalForm A= myCompress (F, N);
528
529  //univariate case
530  if (F.isUnivariate())
531  {
532    CFList result= conv (factorize (F, v));
533    if (result.getFirst().inCoeffDomain())
534      result.removeFirst();
535    return result;
536  }
537
538  //bivariate case
539  if (A.level() == 2)
540  {
541    CFList buf= biFactorize (F, v);
542    return buf;
543  }
544
545  Variable x= Variable (1);
546  Variable y= Variable (2);
547
548  // remove content
549  CFList contentAi;
550  CanonicalForm lcmCont= lcmContent (A, contentAi);
551  A /= lcmCont;
552
553  // trivial after content removal
554  CFList contentAFactors;
555  if (A.inCoeffDomain())
556  {
557    for (CFListIterator i= contentAi; i.hasItem(); i++)
558    {
559      if (i.getItem().inCoeffDomain())
560        continue;
561      else
562      {
563        lcmCont /= i.getItem();
564        contentAFactors=
565        Union (multiFactorize (lcmCont, v),
566               multiFactorize (i.getItem(), v));
567        break;
568      }
569    }
570    decompress (contentAFactors, N);
571    if (isOn (SW_RATIONAL))
572      normalize (contentAFactors);
573    return contentAFactors;
574  }
575
576  // factorize content
577  contentAFactors= multiFactorize (lcmCont, v);
578
579  // univariate after content removal
580  CFList factors;
581  if (A.isUnivariate ())
582  {
583    factors= conv (factorize (A, v));
584    append (factors, contentAFactors);
585    decompress (factors, N);
586    return factors;
587  }
588
589  // check main variable
590  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
591  int factorNums= 3;
592  CanonicalForm bivarEval;
593  CFList biFactors, bufBiFactors;
594  CanonicalForm evalPoly;
595  int lift, bufLift;
596  CFList* bufAeval2= new CFList [A.level() - 2];
597  CFList* Aeval2= new CFList [A.level() - 2];
598  int counter;
599  int differentSecondVar= 0;
600  CanonicalForm bufA;
601  // several bivariate factorizations
602  REvaluation E (2, A.level(), IntRandom (25));
603  for (int i= 0; i < factorNums; i++)
604  {
605    counter= 0;
606    bufA= A;
607    bufAeval= CFList();
608    bufEvaluation= evalPoints (bufA, bufAeval, E);
609    E.nextpoint();
610    evalPoly= 0;
611
612    bivarEval= bufEvaluation.getLast();
613
614    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
615
616    for (int j= 0; j < A.level() - 1; j++)
617    {
618      if (!bufAeval2[j].isEmpty())
619        counter++;
620    }
621
622    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
623
624    TIMING_START (fac_bi_factorizer);
625    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
626    TIMING_END_AND_PRINT (fac_bi_factorizer,
627                          "time for bivariate factorization: ");
628    bufBiFactors.removeFirst();
629
630    if (bufBiFactors.length() == 1)
631    {
632      factors.append (A);
633      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
634      if (isOn (SW_RATIONAL))
635        normalize (factors);
636      delete [] bufAeval2;
637      delete [] Aeval2;
638      return factors;
639    }
640
641    if (i == 0)
642    {
643      Aeval= bufAeval;
644      evaluation= bufEvaluation;
645      biFactors= bufBiFactors;
646      lift= bufLift;
647      for (int j= 0; j < A.level() - 2; j++)
648        Aeval2 [j]= bufAeval2 [j];
649      differentSecondVar= counter;
650    }
651    else
652    {
653      if (bufBiFactors.length() < biFactors.length() ||
654          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
655          counter > differentSecondVar)
656      {
657        Aeval= bufAeval;
658        evaluation= bufEvaluation;
659        biFactors= bufBiFactors;
660        lift= bufLift;
661        for (int j= 0; j < A.level() - 2; j++)
662          Aeval2 [j]= bufAeval2 [j];
663        differentSecondVar= counter;
664      }
665    }
666    int k= 0;
667    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
668      evalPoly += j.getItem()*power (x, k);
669    list.append (evalPoly);
670  }
671
672  delete [] bufAeval2;
673
674  sortList (biFactors, x);
675
676  int minFactorsLength;
677  bool irred= false;
678  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
679
680  if (irred)
681  {
682    factors.append (A);
683    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
684    if (isOn (SW_RATIONAL))
685      normalize (factors);
686    delete [] Aeval2;
687    return factors;
688  }
689
690  if (minFactorsLength == 0)
691    minFactorsLength= biFactors.length();
692  else if (biFactors.length() > minFactorsLength)
693    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
694
695  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
696
697  CFList * oldAeval= new CFList [A.level() - 2];
698  for (int i= 0; i < A.level() - 2; i++)
699    oldAeval[i]= Aeval2[i];
700
701  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
702
703  CFList biFactorsLCs;
704  for (CFListIterator i= biFactors; i.hasItem(); i++)
705    biFactorsLCs.append (LC (i.getItem(), 1));
706
707
708  //shifting to zero
709  A= shift2Zero (A, Aeval, evaluation);
710
711  CanonicalForm hh= Lc (Aeval.getFirst());
712
713  for (CFListIterator i= Aeval; i.hasItem(); i++)
714    i.getItem() /= hh;
715
716  A /= hh;
717
718  Variable w;
719  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
720                                          evaluation, Aeval2, A.level() - 2, w);
721
722  if (w.level() != 1)
723  {
724    A= swapvar (A, y, w);
725    for (int i= 0; i < A.level() - 2; i++)
726    {
727      if (oldAeval[i].isEmpty())
728        continue;
729      if (oldAeval[i].getFirst().level() == w.level())
730      {
731        biFactors= CFList();
732        for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
733          biFactors.append (swapvar (iter.getItem(), w, y));
734      }
735    }
736    int i= A.level();
737    CanonicalForm evalPoint;
738    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
739    {
740      if (i == w.level())
741      {
742        evalPoint= iter.getItem();
743        iter.getItem()= evaluation.getLast();
744        evaluation.removeLast();
745        evaluation.append (evalPoint);
746        break;
747      }
748    }
749    Aeval= evaluateAtZero (A);
750  }
751
752  CFListIterator iter= biFactors;
753  for (; iter.hasItem(); iter++)
754    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
755
756  CanonicalForm oldA= A;
757  CFList oldBiFactors= biFactors;
758  if (!leadingCoeffs.getFirst().inCoeffDomain())
759  {
760    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
761    A *= tmp;
762    Aeval= evaluateAtZero (A);
763    tmp= leadingCoeffs.getFirst();
764    for (int i= A.level(); i > 2; i--)
765      tmp= tmp (0, i);
766    if (!tmp.inCoeffDomain())
767    {
768      for (CFListIterator i= biFactors; i.hasItem(); i++)
769      {
770        i.getItem() *= tmp/LC (i.getItem(), 1);
771        i.getItem() /= Lc (i.getItem());
772      }
773    }
774    hh= Lc (Aeval.getFirst());
775    for (CFListIterator i= Aeval; i.hasItem(); i++)
776      i.getItem() /= hh;
777
778    A /= hh;
779  }
780
781  leadingCoeffs.removeFirst();
782
783  //prepare leading coefficients
784  CFList* leadingCoeffs2= new CFList [A.level() - 2];
785  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors);
786
787  CFArray Pi;
788  CFList diophant;
789  int* liftBounds= new int [A.level() - 1];
790  int liftBoundsLength= A.level() - 1;
791  for (int i= 0; i < liftBoundsLength; i++)
792    liftBounds [i]= degree (A, i + 2) + 1;
793
794  Aeval.removeFirst();
795  bool noOneToOne= false;
796
797  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
798                               Pi, liftBounds, liftBoundsLength, noOneToOne);
799
800  if (!noOneToOne)
801  {
802    int check= factors.length();
803    factors= recoverFactors (A, factors);
804    if (check != factors.length())
805      noOneToOne= true;
806  }
807  if (noOneToOne)
808  {
809    A= oldA;
810    Aeval= evaluateAtZero (A);
811    biFactors= oldBiFactors;
812    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
813    CanonicalForm yToLift= power (y, lift);
814    CFListIterator i= biFactors;
815    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
816    i++;
817
818    for (; i.hasItem(); i++)
819      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
820
821    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
822
823    i= biFactors;
824    yToLift= power (y, lift);
825    CanonicalForm dummy;
826    for (; i.hasItem(); i++)
827    {
828      LCA= LC (i.getItem(), 1);
829      extgcd (LCA, yToLift, LCA, dummy);
830      i.getItem()= mod (i.getItem()*LCA, yToLift);
831    }
832
833    liftBoundsLength= F.level() - 1;
834    liftBounds= liftingBounds (A, lift);
835
836    CFList MOD;
837    bool earlySuccess;
838    CFList earlyFactors;
839    ExtensionInfo info= ExtensionInfo (false);
840    TIMING_START (fac_hensel_lift);
841    CFList liftedFactors= henselLiftAndEarly
842                          (A, MOD, liftBounds, earlySuccess, earlyFactors,
843                           Aeval, biFactors, evaluation, info);
844    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
845
846    TIMING_START (fac_factor_recombination);
847    factors= factorRecombination (A, liftedFactors, MOD);
848    TIMING_END_AND_PRINT (fac_factor_recombination,
849                          "time for factor recombination: ");
850
851    if (earlySuccess)
852      factors= Union (factors, earlyFactors);
853  }
854
855  for (CFListIterator i= factors; i.hasItem(); i++)
856  {
857    int kk= Aeval.getLast().level();
858    for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
859    {
860      if (i.getItem().level() < kk)
861        continue;
862      i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
863    }
864  }
865
866  if (w.level() != 1)
867  {
868    for (CFListIterator iter= factors; iter.hasItem(); iter++)
869      iter.getItem()= swapvar (iter.getItem(), w, y);
870  }
871
872  swap (factors, 0, 0, x);
873  append (factors, contentAFactors);
874  decompress (factors, N);
875  if (isOn (SW_RATIONAL))
876    normalize (factors);
877
878  delete [] leadingCoeffs2;
879  delete [] oldAeval;
880  delete [] Aeval2;
881  delete[] liftBounds;
882
883  return factors;
884}
Note: See TracBrowser for help on using the repository browser.