source: git/factory/facFactorize.cc @ e699d8

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