source: git/factory/facFactorize.cc @ eefc3a

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