source: git/factory/facFactorize.cc @ c770dc

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