source: git/factory/facFactorize.cc @ 91788c0

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