source: git/factory/facAbsFact.cc @ 7766a9

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