source: git/factory/facFactorize.cc @ 72bfc8

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