source: git/factory/facAbsFact.cc @ ae1735

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