source: git/factory/facFactorize.cc @ 8256fd

jengelh-datetimespielwiese
Last change on this file since 8256fd was 8256fd, checked in by Martin Lee <martinlee84@…>, 11 years ago
fix: possible hang in multivariate factorization
  • Property mode set to 100644
File size: 27.0 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(fac_bi_factorize)
32TIMING_DEFINE_PRINT(fac_hensel_lift)
33TIMING_DEFINE_PRINT(fac_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, M;
270  CFArray dummy= CFArray (1);
271  dummy [0]= LCF;
272  compress (dummy, M, N);
273  CanonicalForm F= M (LCF);
274  if (LCF.isUnivariate())
275  {
276    CFList result;
277    int LCFLevel= LCF.level();
278    bool found= false;
279    if (LCFLevel == 2)
280    {
281    //bivariate leading coefficients are already the true leading coefficients
282      result= LCFFactors;
283      found= true;
284    }
285    else
286    {
287      CFListIterator j;
288      for (int i= 0; i < length; i++)
289      {
290        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
291        {
292          if (j.getItem().level() == LCFLevel)
293          {
294            found= true;
295            break;
296          }
297        }
298        if (found)
299        {
300          result= differentSecondVarLCs [i];
301          break;
302        }
303      }
304      if (!found)
305        result= LCFFactors;
306    }
307    if (found)
308      result.insert (Lc (LCF));
309    else
310      result.append (LCF);
311    return result;
312  }
313
314  CFList factors= LCFFactors;
315
316  for (CFListIterator i= factors; i.hasItem(); i++)
317    i.getItem()= M (i.getItem());
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= 0; i < length; i++)
338    {
339      CanonicalForm bufF, swap;
340      CFList bufBufFactors;
341      CFArray buf;
342      if (!differentSecondVarLCs [i].isEmpty())
343      {
344        bool allConstant= true;
345        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
346        {
347          if (!iter.getItem().inCoeffDomain())
348          {
349            allConstant= false;
350            y= Variable (iter.getItem().level());
351            lev= M(y).level();
352          }
353        }
354        if (allConstant)
355          continue;
356
357        bufFactors= differentSecondVarLCs [i];
358        for (iter= bufFactors; iter.hasItem(); iter++)
359          iter.getItem()= swapvar (iter.getItem(), x, y);
360        bufF= F;
361        z= Variable (lev);
362        bufF= swapvar (bufF, x, z);
363        bufBufFactors= bufFactors;
364        evalPoint= CFArray (evaluation.length() - 1);
365        buf= CFArray (evaluation.length());
366        iter= evaluation;
367        int k= evaluation.length() - 1;
368        for (; iter.hasItem(); iter++, k--)
369          buf[k]= iter.getItem();
370        swap= buf[z.level() - 1];
371        buf[z.level() - 1]= buf[0];
372        buf[0]= 0;
373        int l= 0;
374        for (k= 0; k < evaluation.length(); k++)
375        {
376          if (buf[k].isZero())
377            continue;
378          evalPoint[l]= buf[k];
379          l++;
380        }
381        pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
382                           bufSqrfFactors, evalSqrfPartF, evalPoint);
383        if (pass)
384        {
385          foundDifferent= true;
386          F= bufF;
387          CFList l= factors;
388          for (iter= l; iter.hasItem(); iter++)
389            iter.getItem()= swapvar (iter.getItem(), x, y);
390          differentSecondVarLCs [i]= l;
391          j= i;
392          break;
393        }
394        if (!pass && i == length - 1)
395        {
396          CFList result;
397          result.append (LCF);
398          for (int j= 1; j <= factors.length(); j++)
399            result.append (LCF);
400          y= Variable (1);
401          delete [] bufSqrfFactors;
402          return result;
403        }
404      }
405    }
406  }
407  if (!pass)
408  {
409    CFList result;
410    result.append (LCF);
411    for (int j= 1; j <= factors.length(); j++)
412      result.append (LCF);
413    y= Variable (1);
414    delete [] bufSqrfFactors;
415    return result;
416  }
417  else
418    factors= bufFactors;
419
420
421  bufFactors= factors;
422  CFList evaluation2;
423  if (y == x)
424    evaluation2= evaluation;
425  else
426  {
427    CanonicalForm tmp;
428    evaluation2= evaluation;
429    int i= evaluation.length() + 1;
430    for (CFListIterator iter= evaluation2; iter.hasItem(); iter++, i--)
431    {
432      if (i == y.level())
433      {
434        tmp= iter.getItem();
435        iter.getItem()= evaluation2.getLast();
436        evaluation2.removeLast();
437        evaluation2.append (tmp);
438        break;
439      }
440    }
441  }
442
443  CFList interMedResult;
444  CanonicalForm oldSqrfPartF= sqrfPartF;
445  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
446  if (factors.length() > 1)
447  {
448    CanonicalForm LC1= LC (oldSqrfPartF, 1);
449    CFList leadingCoeffs;
450    for (int i= 0; i < factors.length(); i++)
451      leadingCoeffs.append (LC1);
452
453    CFList LC1eval= evaluateAtEval (LC1, evaluation2, 1);
454    CFList oldFactors= factors;
455    for (CFListIterator i= oldFactors; i.hasItem(); i++)
456      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
457
458    bool success= false;
459    CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
460    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
461        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
462                                  oldFactors, 1, leadingCoeffs, factors))
463    {
464      interMedResult= recoverFactors (oldSqrfPartF, factors);
465      if (oldFactors.length() == interMedResult.length())
466        success= true;
467    }
468    if (!success)
469    {
470      LC1= LC (evalSqrfPartF.getFirst(), 1);
471
472      CFArray leadingCoeffs= CFArray (factors.length());
473      for (int i= 0; i < factors.length(); i++)
474        leadingCoeffs[i]= LC1;
475
476      for (CFListIterator i= factors; i.hasItem(); i++)
477      {
478        i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
479        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
480      }
481      factors.insert (1);
482
483      CanonicalForm
484      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
485
486      int liftBound= degree (newSqrfPartF,2) + 1;
487
488      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
489      CFArray Pi;
490      CFList diophant;
491      nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
492                            leadingCoeffs, false);
493
494      if (sqrfPartF.level() > 2)
495      {
496        int* liftBounds= new int [sqrfPartF.level() - 1];
497        liftBounds [0]= liftBound;
498        bool noOneToOne= false;
499        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
500        LC1= LC (evalSqrfPartF.getLast(), 1);
501        CFList LCs;
502        for (int i= 0; i < factors.length(); i++)
503          LCs.append (LC1);
504        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
505        for (int i= sqrfPartF.level() - 1; i > 2; i--)
506        {
507          for (CFListIterator j= LCs; j.hasItem(); j++)
508            j.getItem()= j.getItem() (0, i + 1);
509          leadingCoeffs2 [i - 3]= LCs;
510        }
511        sqrfPartF *= power (LC1, factors.length()-1);
512
513        int liftBoundsLength= sqrfPartF.level() - 1;
514        for (int i= 1; i < liftBoundsLength; i++)
515          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
516        evalSqrfPartF= evaluateAtZero (sqrfPartF);
517        evalSqrfPartF.removeFirst();
518        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
519                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
520        delete [] leadingCoeffs2;
521        delete [] liftBounds;
522      }
523      for (CFListIterator iter= factors; iter.hasItem(); iter++)
524        iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
525
526      interMedResult=
527      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1),
528                      factors);
529    }
530  }
531  else
532  {
533    CanonicalForm contF=content (oldSqrfPartF,1);
534    factors= CFList (oldSqrfPartF/contF);
535    interMedResult= recoverFactors (oldSqrfPartF, factors);
536  }
537
538  CFList result;
539  CFFListIterator k;
540  CanonicalForm tmp;
541  for (int i= 0; i < LCFFactors.length(); i++)
542  {
543    tmp= 1;
544    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
545    {
546      int pos= findItem (bufFactors, k.getItem().factor());
547      if (pos)
548        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
549    }
550    result.append (tmp);
551  }
552
553  for (CFListIterator i= result; i.hasItem(); i++)
554  {
555    F /= i.getItem();
556    if (foundDifferent)
557      i.getItem()= swapvar (i.getItem(), x, z);
558    i.getItem()= N (i.getItem());
559  }
560
561  if (foundDifferent)
562  {
563    CFList l= differentSecondVarLCs [j];
564    for (CFListIterator i= l; i.hasItem(); i++)
565      i.getItem()= swapvar (i.getItem(), y, z);
566    differentSecondVarLCs [j]= l;
567    F= swapvar (F, x, z);
568  }
569
570  result.insert (N (F));
571
572  result= distributeContent (result, differentSecondVarLCs, length);
573
574  if (!result.getFirst().inCoeffDomain())
575  {
576    CFListIterator i= result;
577    CanonicalForm tmp;
578    if (foundDifferent)
579      i.getItem()= swapvar (i.getItem(), Variable (2), y);
580
581    tmp= i.getItem();
582
583    i++;
584    for (; i.hasItem(); i++)
585    {
586      if (foundDifferent)
587        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
588      else
589        i.getItem() *= tmp;
590    }
591  }
592  else
593    y= Variable (1);
594
595  delete [] bufSqrfFactors;
596
597  return result;
598}
599
600
601CFList
602multiFactorize (const CanonicalForm& F, const Variable& v)
603{
604  if (F.inCoeffDomain())
605    return CFList (F);
606
607  // compress and find main Variable
608  CFMap N;
609  CanonicalForm A= myCompress (F, N);
610
611  //univariate case
612  if (F.isUnivariate())
613  {
614    CFList result;
615    if (v.level() != 1)
616      result= conv (factorize (F, v));
617    else
618      result= conv (factorize (F,true));
619    if (result.getFirst().inCoeffDomain())
620      result.removeFirst();
621    return result;
622  }
623
624  //bivariate case
625  if (A.level() == 2)
626  {
627    CFList buf= biFactorize (F, v);
628    return buf;
629  }
630
631  Variable x= Variable (1);
632  Variable y= Variable (2);
633
634  // remove content
635  CFList contentAi;
636  CanonicalForm lcmCont= lcmContent (A, contentAi);
637  A /= lcmCont;
638
639  // trivial after content removal
640  CFList contentAFactors;
641  if (A.inCoeffDomain())
642  {
643    for (CFListIterator i= contentAi; i.hasItem(); i++)
644    {
645      if (i.getItem().inCoeffDomain())
646        continue;
647      else
648      {
649        lcmCont /= i.getItem();
650        contentAFactors=
651        Union (multiFactorize (lcmCont, v),
652               multiFactorize (i.getItem(), v));
653        break;
654      }
655    }
656    decompress (contentAFactors, N);
657    if (isOn (SW_RATIONAL))
658      normalize (contentAFactors);
659    return contentAFactors;
660  }
661
662  // factorize content
663  contentAFactors= multiFactorize (lcmCont, v);
664
665  // univariate after content removal
666  CFList factors;
667  if (A.isUnivariate ())
668  {
669    if (v.level() != 1)
670      factors= conv (factorize (A, v));
671    else
672      factors= conv (factorize (A,true));
673    append (factors, contentAFactors);
674    decompress (factors, N);
675    return factors;
676  }
677
678  // check main variable
679  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
680  int factorNums= 3;
681  CanonicalForm bivarEval;
682  CFList biFactors, bufBiFactors;
683  CanonicalForm evalPoly;
684  int lift, bufLift;
685  CFList* bufAeval2= new CFList [A.level() - 2];
686  CFList* Aeval2= new CFList [A.level() - 2];
687  int counter;
688  int differentSecondVar= 0;
689  CanonicalForm bufA;
690  // several bivariate factorizations
691  REvaluation E (2, A.level(), IntRandom (25));
692  for (int i= 0; i < factorNums; i++)
693  {
694    counter= 0;
695    bufA= A;
696    bufAeval= CFList();
697    bufEvaluation= evalPoints (bufA, bufAeval, E);
698    E.nextpoint();
699    evalPoly= 0;
700
701    bivarEval= bufEvaluation.getLast();
702
703    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
704
705    for (int j= 0; j < A.level() - 1; j++)
706    {
707      if (!bufAeval2[j].isEmpty())
708        counter++;
709    }
710
711    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
712
713    TIMING_START (fac_bi_factorize);
714    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
715    TIMING_END_AND_PRINT (fac_bi_factorize,
716                          "time for bivariate factorization: ");
717    bufBiFactors.removeFirst();
718
719    if (bufBiFactors.length() == 1)
720    {
721      factors.append (A);
722      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
723      if (isOn (SW_RATIONAL))
724        normalize (factors);
725      delete [] bufAeval2;
726      delete [] Aeval2;
727      return factors;
728    }
729
730    if (i == 0)
731    {
732      Aeval= bufAeval;
733      evaluation= bufEvaluation;
734      biFactors= bufBiFactors;
735      lift= bufLift;
736      for (int j= 0; j < A.level() - 2; j++)
737        Aeval2 [j]= bufAeval2 [j];
738      differentSecondVar= counter;
739    }
740    else
741    {
742      if (bufBiFactors.length() < biFactors.length() ||
743          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
744          counter > differentSecondVar)
745      {
746        Aeval= bufAeval;
747        evaluation= bufEvaluation;
748        biFactors= bufBiFactors;
749        lift= bufLift;
750        for (int j= 0; j < A.level() - 2; j++)
751          Aeval2 [j]= bufAeval2 [j];
752        differentSecondVar= counter;
753      }
754    }
755    int k= 0;
756    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
757      evalPoly += j.getItem()*power (x, k);
758    list.append (evalPoly);
759  }
760
761  delete [] bufAeval2;
762
763  sortList (biFactors, x);
764
765  int minFactorsLength;
766  bool irred= false;
767  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
768
769  if (irred)
770  {
771    factors.append (A);
772    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
773    if (isOn (SW_RATIONAL))
774      normalize (factors);
775    delete [] Aeval2;
776    return factors;
777  }
778
779  if (minFactorsLength == 0)
780    minFactorsLength= biFactors.length();
781  else if (biFactors.length() > minFactorsLength)
782    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
783
784  if (differentSecondVar == A.level() - 2)
785  {
786    bool zeroOccured= false;
787    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
788    {
789      if (iter.getItem().isZero())
790      {
791        zeroOccured= true;
792        break;
793      }
794    }
795    if (!zeroOccured)
796    {
797      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
798                                minFactorsLength);
799      if (factors.length() == biFactors.length())
800      {
801        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
802        normalize (factors);
803        delete [] Aeval2;
804        return factors;
805      }
806      else
807        factors= CFList();
808      //TODO case where factors.length() > 0
809    }
810  }
811
812  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
813
814  CFList * oldAeval= new CFList [A.level() - 2];
815  for (int i= 0; i < A.level() - 2; i++)
816    oldAeval[i]= Aeval2[i];
817
818  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
819
820  CFList biFactorsLCs;
821  for (CFListIterator i= biFactors; i.hasItem(); i++)
822    biFactorsLCs.append (LC (i.getItem(), 1));
823
824  Variable w;
825  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
826                                          evaluation, Aeval2, A.level() - 2, w);
827
828  if (w.level() != 1)
829  {
830    A= swapvar (A, y, w);
831    int i= A.level();
832    CanonicalForm evalPoint;
833    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
834    {
835      if (i == w.level())
836      {
837        evalPoint= iter.getItem();
838        iter.getItem()= evaluation.getLast();
839        evaluation.removeLast();
840        evaluation.append (evalPoint);
841        break;
842      }
843    }
844    for (i= 0; i < A.level() - 2; i++)
845    {
846      if (oldAeval[i].isEmpty())
847        continue;
848      if (oldAeval[i].getFirst().level() == w.level())
849      {
850        CFArray tmp= copy (oldAeval[i]);
851        for (int ii= 0; ii < tmp.size(); ii++)
852          tmp[ii]= swapvar (tmp[ii], w, y);
853        CFArray tmp2= CFArray (tmp.size());
854        CanonicalForm buf;
855        for (int ii= 0; ii < tmp.size(); ii++)
856        {
857          buf= tmp[ii] (evaluation.getLast(),y);
858          buf /= Lc (buf);
859          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
860        }
861        biFactors= CFList();
862        for (int j= 0; j < tmp2.size(); j++)
863          biFactors.append (tmp2[j]);
864      }
865    }
866  }
867
868  CFListIterator iter;
869  CanonicalForm oldA= A;
870  CFList oldBiFactors= biFactors;
871  if (!leadingCoeffs.getFirst().inCoeffDomain())
872  {
873    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
874    A *= tmp;
875    Aeval= evaluateAtZero (A);
876    tmp= leadingCoeffs.getFirst();
877    iter= evaluation;
878    for (int i= A.level(); i > 2; i--, iter++)
879      tmp= tmp (iter.getItem(), i);
880    if (!tmp.inCoeffDomain())
881    {
882      for (CFListIterator i= biFactors; i.hasItem(); i++)
883      {
884        i.getItem() *= tmp/LC (i.getItem(), 1);
885        i.getItem() /= Lc (i.getItem());
886      }
887    }
888  }
889
890  leadingCoeffs.removeFirst();
891
892  //prepare leading coefficients
893  CFList* leadingCoeffs2= new CFList [A.level() - 2];
894  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
895                        evaluation);
896
897
898  Aeval= evaluateAtEval (A, evaluation, 2);
899
900  CanonicalForm hh= Lc (Aeval.getFirst());
901
902  for (CFListIterator i= Aeval; i.hasItem(); i++)
903    i.getItem() /= hh;
904
905  A /= hh;
906
907  if (size (A)/getNumVars (A) < 500 &&
908      LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2 [A.level() - 3],
909                                factors))
910  {
911    int check= factors.length();
912    factors= recoverFactors (A, factors);
913
914    if (check == factors.length())
915    {
916
917      if (w.level() != 1)
918      {
919        for (CFListIterator iter= factors; iter.hasItem(); iter++)
920          iter.getItem()= swapvar (iter.getItem(), w, y);
921      }
922
923      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
924      normalize (factors);
925      delete [] Aeval2;
926      return factors;
927    }
928    else
929      factors= CFList();
930  }
931
932
933  //shifting to zero
934  A= shift2Zero (A, Aeval, evaluation);
935
936  for (iter= biFactors; iter.hasItem(); iter++)
937    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
938
939  for (int i= 0; i < A.level() - 2; i++)
940  {
941    if (i != A.level() - 3)
942      leadingCoeffs2[i]= CFList();
943  }
944  for (iter= leadingCoeffs2[A.level() - 3]; iter.hasItem(); iter++)
945  {
946    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
947    for (int i= A.level() - 4; i > -1; i--)
948    {
949      if (i + 1 == A.level() - 3)
950        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
951      else
952        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
953    }
954  }
955
956  CFArray Pi;
957  CFList diophant;
958  int* liftBounds= new int [A.level() - 1];
959  int liftBoundsLength= A.level() - 1;
960  for (int i= 0; i < liftBoundsLength; i++)
961    liftBounds [i]= degree (A, i + 2) + 1;
962
963  Aeval.removeFirst();
964  bool noOneToOne= false;
965
966  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
967                               Pi, liftBounds, liftBoundsLength, noOneToOne);
968
969  if (!noOneToOne)
970  {
971    int check= factors.length();
972    A= oldA;
973    factors= recoverFactors (A, factors, evaluation);
974    if (check != factors.length())
975      noOneToOne= true;
976  }
977  if (noOneToOne)
978  {
979    A= shift2Zero (oldA, Aeval, evaluation);
980    biFactors= oldBiFactors;
981    for (iter= biFactors; iter.hasItem(); iter++)
982      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
983    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
984    CanonicalForm yToLift= power (y, lift);
985    CFListIterator i= biFactors;
986    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
987    i++;
988
989    for (; i.hasItem(); i++)
990      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
991
992    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
993
994    i= biFactors;
995    yToLift= power (y, lift);
996    CanonicalForm dummy;
997    for (; i.hasItem(); i++)
998    {
999      LCA= LC (i.getItem(), 1);
1000      extgcd (LCA, yToLift, LCA, dummy);
1001      i.getItem()= mod (i.getItem()*LCA, yToLift);
1002    }
1003
1004    liftBoundsLength= F.level() - 1;
1005    liftBounds= liftingBounds (A, lift);
1006
1007    CFList MOD;
1008    bool earlySuccess;
1009    CFList earlyFactors;
1010    ExtensionInfo info= ExtensionInfo (false);
1011    CFList liftedFactors;
1012    TIMING_START (fac_hensel_lift);
1013    liftedFactors= henselLiftAndEarly
1014                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
1015                    Aeval, biFactors, evaluation, info);
1016    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
1017
1018    TIMING_START (fac_factor_recombination);
1019    factors= factorRecombination (A, liftedFactors, MOD);
1020    TIMING_END_AND_PRINT (fac_factor_recombination,
1021                          "time for factor recombination: ");
1022
1023    if (earlySuccess)
1024      factors= Union (factors, earlyFactors);
1025
1026    for (CFListIterator i= factors; i.hasItem(); i++)
1027    {
1028      int kk= Aeval.getLast().level();
1029      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
1030      {
1031        if (i.getItem().level() < kk)
1032          continue;
1033       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
1034      }
1035    }
1036  }
1037
1038  if (w.level() != 1)
1039  {
1040    for (CFListIterator iter= factors; iter.hasItem(); iter++)
1041      iter.getItem()= swapvar (iter.getItem(), w, y);
1042  }
1043
1044  swap (factors, 0, 0, x);
1045  append (factors, contentAFactors);
1046  decompress (factors, N);
1047  if (isOn (SW_RATIONAL))
1048    normalize (factors);
1049
1050  delete [] leadingCoeffs2;
1051  delete [] oldAeval;
1052  delete [] Aeval2;
1053  delete[] liftBounds;
1054
1055  return factors;
1056}
1057
1058#endif
Note: See TracBrowser for help on using the repository browser.