source: git/factory/facAbsFact.cc @ e6a143

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