source: git/factory/facAbsFact.cc @ 8d1432e

spielwiese
Last change on this file since 8d1432e was 53ccafa, checked in by Martin Lee <martinlee84@…>, 10 years ago
exclude points that lead to a content
  • Property mode set to 100644
File size: 26.5 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facAbsFact.cc
5 *
6 * @author Martin Lee
7 *
8 **/
9/*****************************************************************************/
10
11
12#include "config.h"
13
14
15#include "timing.h"
16#include "debug.h"
17
18#include "facAbsBiFact.h"
19#include "facAbsFact.h"
20#include "facFqFactorize.h"
21#include "facFqFactorizeUtil.h"
22#include "facHensel.h"
23#include "facSparseHensel.h"
24#include "facFactorize.h"
25#include "cf_reval.h"
26#include "cf_primes.h"
27#include "cf_algorithm.h"
28#include "cfModResultant.h"
29#include "cfUnivarGcd.h"
30#ifdef HAVE_FLINT
31#include "FLINTconvert.h"
32#endif
33#ifdef HAVE_NTL
34#include "NTLconvert.h"
35#include <NTL/LLL.h>
36#endif
37
38#ifdef HAVE_NTL
39TIMING_DEFINE_PRINT(abs_fac_bi_factorizer)
40TIMING_DEFINE_PRINT(abs_fac_hensel_lift)
41TIMING_DEFINE_PRINT(abs_fac_factor_recombination)
42TIMING_DEFINE_PRINT(abs_fac_shift_to_zero)
43TIMING_DEFINE_PRINT(abs_fac_precompute_leadcoeff)
44TIMING_DEFINE_PRINT(abs_fac_evaluation)
45TIMING_DEFINE_PRINT(abs_fac_recover_factors)
46TIMING_DEFINE_PRINT(abs_fac_bifactor_total)
47TIMING_DEFINE_PRINT(abs_fac_luckswang)
48TIMING_DEFINE_PRINT(abs_fac_lcheuristic)
49TIMING_DEFINE_PRINT(abs_fac_cleardenom)
50TIMING_DEFINE_PRINT(abs_fac_compress)
51
52/// steps 4)-8) of Algorithm B.7.8. from Greuel, Pfister "A Singular
53/// Introduction to Commutative Algebra"
54CFAFList
55RothsteinTragerResultant (const CanonicalForm& F, const CanonicalForm& w, int s,
56                          const CFList& evaluation, const Variable& y)
57{
58  CFList terms;
59  for (CFIterator i= w; i.hasTerms(); i++)
60    terms.append (i.coeff());
61
62  Variable x= Variable (1);
63  CanonicalForm derivF= deriv (F, x);
64  CanonicalForm g, geval, derivFeval, Feval, H, res, sqrfPartRes;
65  CFListIterator iter;
66
67  REvaluation E (1, terms.length(), IntRandom (25));
68
69  do
70  {
71    E.nextpoint();
72    g= 0;
73    iter= terms;
74    for (int i= terms.length(); i >= 1; i--, iter++)
75      g += E[i]*iter.getItem();
76
77    geval= g;
78    Feval= F;
79    derivFeval= derivF;
80    iter= evaluation;
81    for (int i= F.level(); i >= 2; iter++, i--)
82    {
83      Feval= Feval (iter.getItem(), i);
84      geval= geval (iter.getItem(), i);
85      derivFeval= derivFeval (iter.getItem(), i);
86    }
87
88    H= y*derivFeval-geval;
89
90    if (degree (Feval, x) >= 8 || degree (H, x) >= 8)
91      res= resultantZ (Feval, H, x);
92    else
93      res= resultant (Feval, H, x);
94
95    sqrfPartRes= sqrfPart (res); //univariate poly in y
96  }
97  while (degree (sqrfPartRes) != s);
98
99  Variable beta= rootOf (sqrfPartRes);
100
101  CanonicalForm factor= gcd (F, beta*derivF-g);
102
103  return CFAFList (CFAFactor (factor, getMipo (beta), 1));
104}
105
106
107/// Algorithm B.7.8 from Greuel, Pfister "A Singular Introduction to Commutative
108/// Algebra"
109CFAFList
110RothsteinTrager (const CanonicalForm& F, const CFList& factors,
111                 const Variable& alpha, const CFList& evaluation)
112{
113  Variable x= Variable (1);
114  ASSERT (factors.length() == 2, "expected two factors");
115  CanonicalForm G, H;
116  if (totaldegree (factors.getFirst()) > totaldegree (factors.getLast()))
117  {
118    H= factors.getLast();
119    G= factors.getFirst();
120  }
121  else
122  {
123    H= factors.getFirst();
124    G= factors.getLast();
125  }
126  CanonicalForm derivH= deriv (H, x);
127  CanonicalForm w= G*derivH;
128  Variable y= Variable (F.level()+1);
129  w= replacevar (w, alpha, y);
130
131  int s= totaldegree (F)/totaldegree (H);
132
133  return RothsteinTragerResultant (F, w, s, evaluation, y);
134}
135
136CFList
137evalPoints4AbsFact (const CanonicalForm& F, CFList& eval, Evaluation& E,
138                    int& intervalSize)
139{
140  CFList result;
141  Variable x= Variable (1);
142
143  CanonicalForm LCF= LC (F, x);
144  CFList LCFeval= CFList();
145
146  bool found= false;
147  bool allZero= true;
148  bool foundZero= false;
149  CanonicalForm deriv_x, gcd_deriv;
150  CFFList uniFactors;
151  CFListIterator iter;
152  int count= 0;
153  do
154  {
155    count++;
156    if (count==E.max() - E.min() + 1)
157    {
158      count= 1;
159      intervalSize++;
160      E= REvaluation (E.min(), E.max(), IntRandom (intervalSize));
161      E.nextpoint();
162    }
163    eval.insert (F);
164    LCFeval.insert (LCF);
165    bool bad= false;
166    for (int i= E.max(); i >= E.min(); i--)
167    {
168      eval.insert (eval.getFirst()( E [i], i));
169      LCFeval.insert (LCFeval.getFirst()( E [i], i));
170      result.append (E[i]);
171      if (!E[i].isZero())
172        allZero= false;
173      else
174        foundZero= true;
175      if (!allZero && foundZero)
176      {
177        result= CFList();
178        eval= CFList();
179        LCFeval= CFList();
180        bad= true;
181        foundZero= false;
182        break;
183      }
184      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
185      {
186        result= CFList();
187        LCFeval= CFList();
188        eval= CFList();
189        bad= true;
190        break;
191      }
192      if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
193      {
194        result= CFList();
195        LCFeval= CFList();
196        eval= CFList();
197        bad= true;
198        break;
199      }
200    }
201
202    if (bad)
203    {
204      E.nextpoint();
205      continue;
206    }
207
208    if (degree (eval.getFirst()) != degree (F, 1))
209    {
210      result= CFList();
211      eval= CFList();
212      LCFeval= CFList();
213      E.nextpoint();
214      continue;
215    }
216
217    deriv_x= deriv (eval.getFirst(), x);
218    gcd_deriv= gcd (eval.getFirst(), deriv_x);
219    if (degree (gcd_deriv) > 0)
220    {
221      result= CFList();
222      eval= CFList();
223      LCFeval= CFList();
224      E.nextpoint();
225      continue;
226    }
227    uniFactors= factorize (eval.getFirst());
228    if (uniFactors.getFirst().factor().inCoeffDomain())
229      uniFactors.removeFirst();
230    if (uniFactors.length() > 1 || uniFactors.getFirst().exp() > 1)
231    {
232      result= CFList();
233      eval= CFList();
234      LCFeval= CFList();
235      E.nextpoint();
236      continue;
237    }
238    iter= eval;
239    iter++;
240    CanonicalForm contentx= content (iter.getItem(), x);
241    if (degree (contentx) > 0)
242    {
243      result= CFList();
244      eval= CFList();
245      LCFeval= CFList();
246      E.nextpoint();
247      continue;
248    }
249    contentx= content (iter.getItem());
250    if (degree (contentx) > 0)
251    {
252      result= CFList();
253      eval= CFList();
254      LCFeval= CFList();
255      E.nextpoint();
256      continue;
257    }
258    found= true;
259  }
260  while (!found);
261
262  if (!eval.isEmpty())
263    eval.removeFirst();
264  return result;
265}
266
267CFAFList absFactorize (const CanonicalForm& G
268                           )
269{
270  //TODO handle homogeneous input, is already done in LIB interface but still...
271  ASSERT (getCharacteristic() == 0, "expected poly over Q");
272
273  CanonicalForm F= G;
274
275  CanonicalForm LcF= Lc (F);
276  bool isRat= isOn (SW_RATIONAL);
277  if (isRat)
278    F *= bCommonDen (F);
279
280  Off (SW_RATIONAL);
281  F /= icontent (F);
282  if (isRat)
283    On (SW_RATIONAL);
284
285  CFFList rationalFactors= factorize (F);
286
287  CFAFList result, resultBuf;
288
289  CFAFListIterator iter;
290  CFFListIterator i= rationalFactors;
291  i++;
292  for (; i.hasItem(); i++)
293  {
294    resultBuf= absFactorizeMain (i.getItem().factor());
295    for (iter= resultBuf; iter.hasItem(); iter++)
296      iter.getItem()= CFAFactor (iter.getItem().factor(),
297                                 iter.getItem().minpoly(), i.getItem().exp());
298    result= Union (result, resultBuf);
299  }
300
301  if (isRat)
302    normalize (result);
303  result.insert (CFAFactor (LcF, 1, 1));
304
305  return result;
306}
307
308CFAFList absFactorizeMain (const CanonicalForm& G)
309{
310  CanonicalForm F= bCommonDen (G)*G;
311
312  Off (SW_RATIONAL);
313  F /= icontent (F);
314  On (SW_RATIONAL);
315
316  if (F.inCoeffDomain())
317    return CFAFList (CFAFactor (F, 1, 1));
318
319  // compress and find main Variable
320  CFMap N;
321  TIMING_START (abs_fac_compress)
322  CanonicalForm A= myCompress (F, N);
323  TIMING_END_AND_PRINT (abs_fac_compress,
324                        "time to compress poly in abs fact: ")
325
326  //univariate case
327  if (F.isUnivariate())
328  {
329    CFAFList result;
330    result= uniAbsFactorize (F);
331    if (result.getFirst().factor().inCoeffDomain())
332      result.removeFirst();
333    return result;
334  }
335
336  //bivariate case
337  if (A.level() == 2)
338  {
339    CFAFList result= absBiFactorizeMain (A);
340    decompress (result, N);
341    return result; //needs compressed input
342  }
343
344  Variable x= Variable (1);
345  Variable y= Variable (2);
346
347  CFAFList factors;
348  A *= bCommonDen (A);
349  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
350  int factorNums= 1;
351  CFAFList absBiFactors, absBufBiFactors;
352  CanonicalForm evalPoly;
353  int lift, bufLift, lengthAeval2= A.level()-2;
354  CFList* bufAeval2= new CFList [lengthAeval2];
355  CFList* Aeval2= new CFList [lengthAeval2];
356  int counter;
357  int differentSecondVar= 0;
358  CanonicalForm bufA;
359
360  // several bivariate factorizations
361  TIMING_START (abs_fac_bifactor_total);
362  int absValue= 2;
363  REvaluation E (2, A.level(), IntRandom (absValue));
364  for (int i= 0; i < factorNums; i++)
365  {
366    counter= 0;
367    bufA= A;
368    bufAeval= CFList();
369    TIMING_START (abs_fac_evaluation);
370    bufEvaluation= evalPoints4AbsFact (bufA, bufAeval, E, absValue);
371    TIMING_END_AND_PRINT (abs_fac_evaluation,
372                          "time to find evaluation point in abs fact: ");
373    E.nextpoint();
374    evalPoly= 0;
375
376    TIMING_START (abs_fac_evaluation);
377    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
378    TIMING_END_AND_PRINT (abs_fac_evaluation,
379                          "time to eval wrt diff second vars in abs fact: ");
380
381    for (int j= 0; j < lengthAeval2; j++)
382    {
383      if (!bufAeval2[j].isEmpty())
384        counter++;
385    }
386
387    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
388
389    TIMING_START (abs_fac_bi_factorizer);
390    absBufBiFactors= absBiFactorizeMain (bufAeval.getFirst(), true);
391    TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
392                          "time for bivariate factorization in abs fact: ");
393
394    if (absBufBiFactors.length() == 1)
395    {
396      factors.append (CFAFactor (A, 1, 1));
397      decompress (factors, N);
398      if (isOn (SW_RATIONAL))
399        normalize (factors);
400      delete [] bufAeval2;
401      delete [] Aeval2;
402      return factors;
403    }
404
405    if (i == 0)
406    {
407      Aeval= bufAeval;
408      evaluation= bufEvaluation;
409      absBiFactors= absBufBiFactors;
410      lift= bufLift;
411      for (int j= 0; j < lengthAeval2; j++)
412        Aeval2 [j]= bufAeval2 [j];
413      differentSecondVar= counter;
414    }
415    else
416    {
417      if (absBufBiFactors.length() < absBiFactors.length() ||
418          ((bufLift < lift) &&
419          (absBufBiFactors.length() == absBiFactors.length())) ||
420          counter > differentSecondVar)
421      {
422        Aeval= bufAeval;
423        evaluation= bufEvaluation;
424        absBiFactors= absBufBiFactors;
425        lift= bufLift;
426        for (int j= 0; j < lengthAeval2; j++)
427          Aeval2 [j]= bufAeval2 [j];
428        differentSecondVar= counter;
429      }
430    }
431    int k= 0;
432    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
433      evalPoly += j.getItem()*power (x, k);
434    list.append (evalPoly);
435  }
436
437  delete [] bufAeval2;
438
439  CFList rationalFactors;
440  Variable v= mvar (absBiFactors.getFirst().minpoly());
441
442  CFList biFactors;
443  for (CFAFListIterator iter= absBiFactors; iter.hasItem(); iter++)
444    biFactors.append (iter.getItem().factor());
445
446  sortList (biFactors, x);
447
448  int minFactorsLength;
449  bool irred= false;
450
451  TIMING_START (abs_fac_bi_factorizer);
452  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
453  TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
454         "time for bivariate factorization wrt diff second vars in abs fact: ");
455
456  TIMING_END_AND_PRINT (abs_fac_bifactor_total,
457                        "total time for eval and bivar factors in abs fact: ");
458  if (irred)
459  {
460    factors.append (CFAFactor (A, 1, 1));
461    decompress (factors, N);
462    if (isOn (SW_RATIONAL))
463      normalize (factors);
464    delete [] Aeval2;
465    return factors;
466  }
467
468  if (minFactorsLength == 0)
469    minFactorsLength= biFactors.length();
470  else if (biFactors.length() > minFactorsLength)
471    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
472  minFactorsLength= tmin (minFactorsLength, biFactors.length());
473
474  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
475
476  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
477
478  minFactorsLength= tmin (minFactorsLength, biFactors.length());
479
480  if (minFactorsLength == 1)
481  {
482    factors.append (CFAFactor (A, 1, 1));
483    decompress (factors, N);
484    if (isOn (SW_RATIONAL))
485      normalize (factors);
486    delete [] Aeval2;
487    return factors;
488  }
489
490  bool found= false;
491  if (differentSecondVar == lengthAeval2)
492  {
493    bool zeroOccured= false;
494    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
495    {
496      if (iter.getItem().isZero())
497      {
498        zeroOccured= true;
499        break;
500      }
501    }
502    if (!zeroOccured)
503    {
504      rationalFactors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
505                                       minFactorsLength);
506      if (rationalFactors.length() == biFactors.length())
507      {
508        for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
509        {
510          if (totaldegree(iter.getItem())*degree(getMipo(v)) == totaldegree (G))
511          {
512            factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
513            found= true;
514            break;
515          }
516        }
517        // necessary since extension may be too large
518        if (!found)
519          factors= RothsteinTrager (A, rationalFactors, v, evaluation);
520
521        decompress (factors, N);
522        normalize (factors);
523        delete [] Aeval2;
524        return factors;
525      }
526      else
527        rationalFactors= CFList();
528      //TODO case where factors.length() > 0
529    }
530  }
531
532  CFList * oldAeval= new CFList [lengthAeval2];
533  for (int i= 0; i < lengthAeval2; i++)
534    oldAeval[i]= Aeval2[i];
535
536  getLeadingCoeffs (A, Aeval2);
537
538  CFList biFactorsLCs;
539  for (CFListIterator i= biFactors; i.hasItem(); i++)
540    biFactorsLCs.append (LC (i.getItem(), 1));
541
542  Variable w;
543  TIMING_START (abs_fac_precompute_leadcoeff);
544  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
545                                          evaluation, Aeval2, lengthAeval2, w);
546
547  if (w.level() != 1)
548    changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
549                          uniFactors, w);
550
551  CanonicalForm oldA= A;
552  CFList oldBiFactors= biFactors;
553
554  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
555  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
556  leadingCoeffs.removeFirst();
557
558  if (!LCmultiplierIsConst)
559    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation,
560                            LCmultiplier);
561
562  //prepare leading coefficients
563  CFList* leadingCoeffs2= new CFList [lengthAeval2];
564  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
565                        biFactors, evaluation);
566
567  CFListIterator iter;
568  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
569  CFList bufBiFactors= biFactors;
570  bufA= A;
571  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
572  if (!LCmultiplierIsConst)
573  {
574    testVars= Variable (2);
575    for (int i= 0; i < lengthAeval2; i++)
576    {
577      if (!oldAeval[i].isEmpty())
578        testVars *= oldAeval[i].getFirst().mvar();
579    }
580  }
581  TIMING_END_AND_PRINT(abs_fac_precompute_leadcoeff,
582                       "time to precompute LC in abs fact: ");
583
584  TIMING_START (abs_fac_luckswang);
585  CFList bufFactors= CFList();
586  bool LCheuristic= false;
587  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
588                                rationalFactors))
589  {
590    int check= biFactors.length();
591    int * index= new int [factors.length()];
592    CFList oldFactors= rationalFactors;
593    rationalFactors= recoverFactors (A, rationalFactors, index);
594
595    if (check == rationalFactors.length())
596    {
597      if (w.level() != 1)
598      {
599        for (iter= rationalFactors; iter.hasItem(); iter++)
600          iter.getItem()= swapvar (iter.getItem(), w, y);
601      }
602
603      for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
604      {
605        if (totaldegree(iter.getItem())*degree (getMipo (v)) == totaldegree (G))
606        {
607          factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
608          found=true;
609          break;
610        }
611      }
612      // necessary since extension may be too large
613      if (!found)
614        factors= RothsteinTrager (A, rationalFactors, v, evaluation);
615
616      decompress (factors, N);
617      normalize (factors);
618      delete [] index;
619      delete [] Aeval2;
620      TIMING_END_AND_PRINT (abs_fac_luckswang,
621                            "time for successful LucksWang in abs fact: ");
622      return factors;
623    }
624    else if (rationalFactors.length() > 0)
625    {
626      int oneCount= 0;
627      CFList l;
628      for (int i= 0; i < check; i++)
629      {
630        if (index[i] == 1)
631        {
632          iter=biFactors;
633          for (int j=1; j <= i-oneCount; j++)
634            iter++;
635          iter.remove (1);
636          for (int j= 0; j < lengthAeval2; j++)
637          {
638            l= leadingCoeffs2[j];
639            iter= l;
640            for (int k=1; k <= i-oneCount; k++)
641              iter++;
642            iter.remove (1);
643            leadingCoeffs2[j]=l;
644          }
645          oneCount++;
646        }
647      }
648      bufFactors= rationalFactors;
649      rationalFactors= CFList();
650    }
651    else if (!LCmultiplierIsConst && rationalFactors.length() == 0)
652    {
653      LCheuristic= true;
654      rationalFactors= oldFactors;
655      CFList contents, LCs;
656      bool foundTrueMultiplier= false;
657      LCHeuristic2 (LCmultiplier,rationalFactors,leadingCoeffs2[lengthAeval2-1],
658                    contents, LCs, foundTrueMultiplier);
659      if (foundTrueMultiplier)
660      {
661          A= oldA;
662          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
663          for (int i= lengthAeval2-1; i > -1; i--)
664            leadingCoeffs2[i]= CFList();
665          prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
666                                leadingCoeffs, biFactors, evaluation);
667      }
668      else
669      {
670        bool foundMultiplier= false;
671        LCHeuristic3 (LCmultiplier, rationalFactors, oldBiFactors, contents,
672                      oldAeval,A,leadingCoeffs2, lengthAeval2, foundMultiplier);
673        // coming from above: divide out more LCmultiplier if possible
674        if (foundMultiplier)
675        {
676          foundMultiplier= false;
677          LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
678                        testVars, lengthAeval2, leadingCoeffs2, A, LCmultiplier,
679                        foundMultiplier);
680        }
681        else
682        {
683          LCHeuristicCheck (LCs, contents, A, oldA,
684                            leadingCoeffs2[lengthAeval2-1], foundMultiplier);
685          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
686          {
687            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
688                         lengthAeval2, evaluation, oldBiFactors);
689          }
690        }
691
692        // patch everything together again
693        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
694        for (int i= lengthAeval2-1; i > -1; i--)
695          leadingCoeffs2[i]= CFList();
696        prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
697                              biFactors, evaluation);
698      }
699      rationalFactors= CFList();
700      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
701      {
702        LCheuristic= false;
703        A= bufA;
704        biFactors= bufBiFactors;
705        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
706        LCmultiplier= bufLCmultiplier;
707      }
708    }
709    else
710      rationalFactors= CFList();
711    delete [] index;
712  }
713  TIMING_END_AND_PRINT (abs_fac_luckswang, "time for LucksWang in abs fact: ");
714
715  TIMING_START (abs_fac_lcheuristic);
716  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
717      && fdivides (getVars (LCmultiplier), testVars))
718  {
719    LCheuristic= true;
720    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
721                 lengthAeval2, evaluation, oldBiFactors);
722
723    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
724    for (int i= lengthAeval2-1; i > -1; i--)
725      leadingCoeffs2[i]= CFList();
726    prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
727                          biFactors, evaluation);
728
729    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
730    {
731      LCheuristic= false;
732      A= bufA;
733      biFactors= bufBiFactors;
734      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
735      LCmultiplier= bufLCmultiplier;
736    }
737  }
738  TIMING_END_AND_PRINT (abs_fac_lcheuristic,
739                        "time for Lc heuristic in abs fact: ");
740
741tryAgainWithoutHeu:
742  //shifting to zero
743  TIMING_START (abs_fac_shift_to_zero);
744  CanonicalForm denA= bCommonDen (A);
745  A *= denA;
746  A= shift2Zero (A, Aeval, evaluation);
747  A /= denA;
748
749  for (iter= biFactors; iter.hasItem(); iter++)
750    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
751
752  for (int i= 0; i < lengthAeval2-1; i++)
753    leadingCoeffs2[i]= CFList();
754  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
755  {
756    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
757    for (int i= A.level() - 4; i > -1; i--)
758    {
759      if (i + 1 == lengthAeval2-1)
760        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
761      else
762        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
763    }
764  }
765  TIMING_END_AND_PRINT (abs_fac_shift_to_zero,
766                        "time to shift evaluation point to zero in abs fact: ");
767
768  CFArray Pi;
769  CFList diophant;
770  int* liftBounds= new int [A.level() - 1];
771  int liftBoundsLength= A.level() - 1;
772  for (int i= 0; i < liftBoundsLength; i++)
773    liftBounds [i]= degree (A, i + 2) + 1;
774
775  Aeval.removeFirst();
776  bool noOneToOne= false;
777
778  TIMING_START (abs_fac_cleardenom);
779  CFList commonDenominators;
780  for (iter=biFactors; iter.hasItem(); iter++)
781    commonDenominators.append (bCommonDen (iter.getItem()));
782  CanonicalForm tmp1, tmp2, tmp3=1;
783  CFListIterator iter2;
784  for (int i= 0; i < lengthAeval2; i++)
785  {
786    iter2= commonDenominators;
787    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
788    {
789      tmp1= bCommonDen (iter.getItem());
790      Off (SW_RATIONAL);
791      iter2.getItem()= lcm (iter2.getItem(), tmp1);
792      On (SW_RATIONAL);
793    }
794  }
795  tmp1= prod (commonDenominators);
796  for (iter= Aeval; iter.hasItem(); iter++)
797  {
798    tmp2= bCommonDen (iter.getItem()/denA);
799    Off (SW_RATIONAL);
800    tmp3= lcm (tmp2,tmp3);
801    On (SW_RATIONAL);
802  }
803  CanonicalForm multiplier;
804  multiplier= tmp3/tmp1;
805  iter2= commonDenominators;
806  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
807    iter.getItem() *= iter2.getItem()*multiplier;
808
809  for (iter= Aeval; iter.hasItem(); iter++)
810    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
811
812  for (int i= 0; i < lengthAeval2; i++)
813  {
814    iter2= commonDenominators;
815    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
816      iter.getItem() *= iter2.getItem()*multiplier;
817  }
818
819  TIMING_END_AND_PRINT (abs_fac_cleardenom,
820                        "time to clear denominators in abs fact: ");
821
822  TIMING_START (abs_fac_hensel_lift);
823  rationalFactors= nonMonicHenselLift (Aeval, biFactors,leadingCoeffs2,diophant,
824                               Pi, liftBounds, liftBoundsLength, noOneToOne);
825  TIMING_END_AND_PRINT (abs_fac_hensel_lift,
826                        "time for non monic hensel lifting in abs fact: ");
827
828  if (!noOneToOne)
829  {
830    int check= rationalFactors.length();
831    A= oldA;
832    TIMING_START (abs_fac_recover_factors);
833    rationalFactors= recoverFactors (A, rationalFactors, evaluation);
834    TIMING_END_AND_PRINT (abs_fac_recover_factors,
835                          "time to recover factors in abs fact: ");
836    if (check != rationalFactors.length())
837      noOneToOne= true;
838    else
839      rationalFactors= Union (rationalFactors, bufFactors);
840  }
841  if (noOneToOne)
842  {
843    if (!LCmultiplierIsConst && LCheuristic)
844    {
845      A= bufA;
846      biFactors= bufBiFactors;
847      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
848      delete [] liftBounds;
849      LCheuristic= false;
850      goto tryAgainWithoutHeu;
851      //something probably went wrong in the heuristic
852    }
853
854    A= shift2Zero (oldA, Aeval, evaluation);
855    biFactors= oldBiFactors;
856    for (iter= biFactors; iter.hasItem(); iter++)
857      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
858    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
859    CanonicalForm yToLift= power (y, lift);
860    CFListIterator i= biFactors;
861    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
862    i++;
863
864    for (; i.hasItem(); i++)
865      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
866
867    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
868
869    i= biFactors;
870    yToLift= power (y, lift);
871    CanonicalForm dummy;
872    for (; i.hasItem(); i++)
873    {
874      LCA= LC (i.getItem(), 1);
875      extgcd (LCA, yToLift, LCA, dummy);
876      i.getItem()= mod (i.getItem()*LCA, yToLift);
877    }
878
879    liftBoundsLength= F.level() - 1;
880    liftBounds= liftingBounds (A, lift);
881
882    CFList MOD;
883    bool earlySuccess;
884    CFList earlyFactors;
885    ExtensionInfo info= ExtensionInfo (false);
886    CFList liftedFactors;
887    TIMING_START (abs_fac_hensel_lift);
888    liftedFactors= henselLiftAndEarly
889                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
890                    Aeval, biFactors, evaluation, info);
891    TIMING_END_AND_PRINT (abs_fac_hensel_lift,
892                          "time for hensel lifting in abs fact: ");
893
894    TIMING_START (abs_fac_factor_recombination);
895    rationalFactors= factorRecombination (A, liftedFactors, MOD);
896    TIMING_END_AND_PRINT (abs_fac_factor_recombination,
897                          "time for factor recombination in abs fact: ");
898
899    if (earlySuccess)
900      rationalFactors= Union (rationalFactors, earlyFactors);
901
902    for (CFListIterator i= rationalFactors; i.hasItem(); i++)
903    {
904      int kk= Aeval.getLast().level();
905      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
906      {
907        if (i.getItem().level() < kk)
908          continue;
909       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
910      }
911    }
912  }
913
914  if (w.level() != 1)
915  {
916    for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
917      iter.getItem()= swapvar (iter.getItem(), w, y);
918  }
919
920  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
921  {
922    if (totaldegree (iter.getItem())*degree (getMipo (v)) == totaldegree (G))
923    {
924      factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
925      found= true;
926      break;
927    }
928  }
929
930  // necessary since extension may be too large
931  if (!found)
932    factors= RothsteinTrager (A, rationalFactors, v, evaluation);
933
934  decompress (factors, N);
935  if (isOn (SW_RATIONAL))
936    normalize (factors);
937
938  delete [] leadingCoeffs2;
939  delete [] oldAeval;
940  delete [] Aeval2;
941  delete[] liftBounds;
942
943  return factors;
944}
945
946#endif
Note: See TracBrowser for help on using the repository browser.