source: git/factory/facAbsFact.cc

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