source: git/factory/facFactorize.cc @ afb6a6

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