source: git/factory/facAbsFact.cc @ 767da0

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