source: git/factory/facFactorize.cc @ 5df7d0

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