source: git/factory/facAbsFact.cc @ bebd13f

fieker-DuValspielwiese
Last change on this file since bebd13f was 252584, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: handling of constant factor
  • 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
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
463  bool found= false;
464  if (differentSecondVar == lengthAeval2)
465  {
466    bool zeroOccured= false;
467    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
468    {
469      if (iter.getItem().isZero())
470      {
471        zeroOccured= true;
472        break;
473      }
474    }
475    if (!zeroOccured)
476    {
477      rationalFactors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
478                                       minFactorsLength);
479      if (rationalFactors.length() == biFactors.length())
480      {
481        for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
482        {
483          if (totaldegree(iter.getItem())*degree(getMipo(v)) == totaldegree (G))
484          {
485            factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
486            found= true;
487            break;
488          }
489        }
490        // necessary since extension may be too large
491        if (!found)
492          factors= RothsteinTrager (A, rationalFactors, v, evaluation);
493
494        decompress (factors, N);
495        normalize (factors);
496        delete [] Aeval2;
497        return factors;
498      }
499      else
500        rationalFactors= CFList();
501      //TODO case where factors.length() > 0
502    }
503  }
504
505  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
506
507  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
508
509  CFList * oldAeval= new CFList [lengthAeval2];
510  for (int i= 0; i < lengthAeval2; i++)
511    oldAeval[i]= Aeval2[i];
512
513  getLeadingCoeffs (A, Aeval2);
514
515  CFList biFactorsLCs;
516  for (CFListIterator i= biFactors; i.hasItem(); i++)
517    biFactorsLCs.append (LC (i.getItem(), 1));
518
519  Variable w;
520  TIMING_START (abs_fac_precompute_leadcoeff);
521  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
522                                          evaluation, Aeval2, lengthAeval2, w);
523
524  if (w.level() != 1)
525    changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
526                          uniFactors, w);
527
528  CanonicalForm oldA= A;
529  CFList oldBiFactors= biFactors;
530
531  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
532  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
533  leadingCoeffs.removeFirst();
534
535  if (!LCmultiplierIsConst)
536    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation,
537                            LCmultiplier);
538
539  //prepare leading coefficients
540  CFList* leadingCoeffs2= new CFList [lengthAeval2];
541  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
542                        biFactors, evaluation);
543
544  CFListIterator iter;
545  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
546  CFList bufBiFactors= biFactors;
547  bufA= A;
548  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
549  if (!LCmultiplierIsConst)
550  {
551    testVars= Variable (2);
552    for (int i= 0; i < lengthAeval2; i++)
553    {
554      if (!oldAeval[i].isEmpty())
555        testVars *= oldAeval[i].getFirst().mvar();
556    }
557  }
558  TIMING_END_AND_PRINT(abs_fac_precompute_leadcoeff,
559                       "time to precompute LC in abs fact: ");
560
561  TIMING_START (abs_fac_luckswang);
562  CFList bufFactors= CFList();
563  bool LCheuristic= false;
564  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
565                                rationalFactors))
566  {
567    int check= biFactors.length();
568    int * index= new int [factors.length()];
569    CFList oldFactors= rationalFactors;
570    rationalFactors= recoverFactors (A, rationalFactors, index);
571
572    if (check == rationalFactors.length())
573    {
574      if (w.level() != 1)
575      {
576        for (iter= rationalFactors; iter.hasItem(); iter++)
577          iter.getItem()= swapvar (iter.getItem(), w, y);
578      }
579
580      for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
581      {
582        if (totaldegree(iter.getItem())*degree (getMipo (v)) == totaldegree (G))
583        {
584          factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
585          found=true;
586          break;
587        }
588      }
589      // necessary since extension may be too large
590      if (!found)
591        factors= RothsteinTrager (A, rationalFactors, v, evaluation);
592
593      decompress (factors, N);
594      normalize (factors);
595      delete [] index;
596      delete [] Aeval2;
597      TIMING_END_AND_PRINT (abs_fac_luckswang,
598                            "time for successful LucksWang in abs fact: ");
599      return factors;
600    }
601    else if (rationalFactors.length() > 0)
602    {
603      int oneCount= 0;
604      CFList l;
605      for (int i= 0; i < check; i++)
606      {
607        if (index[i] == 1)
608        {
609          iter=biFactors;
610          for (int j=1; j <= i-oneCount; j++)
611            iter++;
612          iter.remove (1);
613          for (int j= 0; j < lengthAeval2; j++)
614          {
615            l= leadingCoeffs2[j];
616            iter= l;
617            for (int k=1; k <= i-oneCount; k++)
618              iter++;
619            iter.remove (1);
620            leadingCoeffs2[j]=l;
621          }
622          oneCount++;
623        }
624      }
625      bufFactors= rationalFactors;
626      rationalFactors= CFList();
627    }
628    else if (!LCmultiplierIsConst && rationalFactors.length() == 0)
629    {
630      LCheuristic= true;
631      rationalFactors= oldFactors;
632      CFList contents, LCs;
633      bool foundTrueMultiplier= false;
634      LCHeuristic2 (LCmultiplier,rationalFactors,leadingCoeffs2[lengthAeval2-1],
635                    contents, LCs, foundTrueMultiplier);
636      if (foundTrueMultiplier)
637      {
638          A= oldA;
639          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
640          for (int i= lengthAeval2-1; i > -1; i--)
641            leadingCoeffs2[i]= CFList();
642          prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
643                                leadingCoeffs, biFactors, evaluation);
644      }
645      else
646      {
647        bool foundMultiplier= false;
648        LCHeuristic3 (LCmultiplier, rationalFactors, oldBiFactors, contents,
649                      oldAeval,A,leadingCoeffs2, lengthAeval2, foundMultiplier);
650        // coming from above: divide out more LCmultiplier if possible
651        if (foundMultiplier)
652        {
653          foundMultiplier= false;
654          LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
655                        testVars, lengthAeval2, leadingCoeffs2, A, LCmultiplier,
656                        foundMultiplier);
657        }
658        else
659        {
660          LCHeuristicCheck (LCs, contents, A, oldA,
661                            leadingCoeffs2[lengthAeval2-1], foundMultiplier);
662          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
663          {
664            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
665                         lengthAeval2, evaluation, oldBiFactors);
666          }
667        }
668
669        // patch everything together again
670        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
671        for (int i= lengthAeval2-1; i > -1; i--)
672          leadingCoeffs2[i]= CFList();
673        prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
674                              biFactors, evaluation);
675      }
676      rationalFactors= CFList();
677      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
678      {
679        LCheuristic= false;
680        A= bufA;
681        biFactors= bufBiFactors;
682        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
683        LCmultiplier= bufLCmultiplier;
684      }
685    }
686    else
687      rationalFactors= CFList();
688    delete [] index;
689  }
690  TIMING_END_AND_PRINT (abs_fac_luckswang, "time for LucksWang in abs fact: ");
691
692  TIMING_START (abs_fac_lcheuristic);
693  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
694      && fdivides (getVars (LCmultiplier), testVars))
695  {
696    LCheuristic= true;
697    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
698                 lengthAeval2, evaluation, oldBiFactors);
699
700    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
701    for (int i= lengthAeval2-1; i > -1; i--)
702      leadingCoeffs2[i]= CFList();
703    prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
704                          biFactors, evaluation);
705
706    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
707    {
708      LCheuristic= false;
709      A= bufA;
710      biFactors= bufBiFactors;
711      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
712      LCmultiplier= bufLCmultiplier;
713    }
714  }
715  TIMING_END_AND_PRINT (abs_fac_lcheuristic,
716                        "time for Lc heuristic in abs fact: ");
717
718tryAgainWithoutHeu:
719  //shifting to zero
720  TIMING_START (abs_fac_shift_to_zero);
721  CanonicalForm denA= bCommonDen (A);
722  A *= denA;
723  A= shift2Zero (A, Aeval, evaluation);
724  A /= denA;
725
726  for (iter= biFactors; iter.hasItem(); iter++)
727    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
728
729  for (int i= 0; i < lengthAeval2-1; i++)
730    leadingCoeffs2[i]= CFList();
731  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
732  {
733    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
734    for (int i= A.level() - 4; i > -1; i--)
735    {
736      if (i + 1 == lengthAeval2-1)
737        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
738      else
739        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
740    }
741  }
742  TIMING_END_AND_PRINT (abs_fac_shift_to_zero,
743                        "time to shift evaluation point to zero in abs fact: ");
744
745  CFArray Pi;
746  CFList diophant;
747  int* liftBounds= new int [A.level() - 1];
748  int liftBoundsLength= A.level() - 1;
749  for (int i= 0; i < liftBoundsLength; i++)
750    liftBounds [i]= degree (A, i + 2) + 1;
751
752  Aeval.removeFirst();
753  bool noOneToOne= false;
754
755  TIMING_START (abs_fac_cleardenom);
756  CFList commonDenominators;
757  for (iter=biFactors; iter.hasItem(); iter++)
758    commonDenominators.append (bCommonDen (iter.getItem()));
759  CanonicalForm tmp1, tmp2, tmp3=1;
760  CFListIterator iter2;
761  for (int i= 0; i < lengthAeval2; i++)
762  {
763    iter2= commonDenominators;
764    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
765    {
766      tmp1= bCommonDen (iter.getItem());
767      Off (SW_RATIONAL);
768      iter2.getItem()= lcm (iter2.getItem(), tmp1);
769      On (SW_RATIONAL);
770    }
771  }
772  tmp1= prod (commonDenominators);
773  for (iter= Aeval; iter.hasItem(); iter++)
774  {
775    tmp2= bCommonDen (iter.getItem()/denA);
776    Off (SW_RATIONAL);
777    tmp3= lcm (tmp2,tmp3);
778    On (SW_RATIONAL);
779  }
780  CanonicalForm multiplier;
781  multiplier= tmp3/tmp1;
782  iter2= commonDenominators;
783  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
784    iter.getItem() *= iter2.getItem()*multiplier;
785
786  for (iter= Aeval; iter.hasItem(); iter++)
787    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
788
789  for (int i= 0; i < lengthAeval2; i++)
790  {
791    iter2= commonDenominators;
792    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
793      iter.getItem() *= iter2.getItem()*multiplier;
794  }
795
796  TIMING_END_AND_PRINT (abs_fac_cleardenom,
797                        "time to clear denominators in abs fact: ");
798
799  TIMING_START (abs_fac_hensel_lift);
800  rationalFactors= nonMonicHenselLift (Aeval, biFactors,leadingCoeffs2,diophant,
801                               Pi, liftBounds, liftBoundsLength, noOneToOne);
802  TIMING_END_AND_PRINT (abs_fac_hensel_lift,
803                        "time for non monic hensel lifting in abs fact: ");
804
805  if (!noOneToOne)
806  {
807    int check= rationalFactors.length();
808    A= oldA;
809    TIMING_START (abs_fac_recover_factors);
810    rationalFactors= recoverFactors (A, rationalFactors, evaluation);
811    TIMING_END_AND_PRINT (abs_fac_recover_factors,
812                          "time to recover factors in abs fact: ");
813    if (check != rationalFactors.length())
814      noOneToOne= true;
815    else
816      rationalFactors= Union (rationalFactors, bufFactors);
817  }
818  if (noOneToOne)
819  {
820    if (!LCmultiplierIsConst && LCheuristic)
821    {
822      A= bufA;
823      biFactors= bufBiFactors;
824      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
825      delete [] liftBounds;
826      LCheuristic= false;
827      goto tryAgainWithoutHeu;
828      //something probably went wrong in the heuristic
829    }
830
831    A= shift2Zero (oldA, Aeval, evaluation);
832    biFactors= oldBiFactors;
833    for (iter= biFactors; iter.hasItem(); iter++)
834      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
835    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
836    CanonicalForm yToLift= power (y, lift);
837    CFListIterator i= biFactors;
838    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
839    i++;
840
841    for (; i.hasItem(); i++)
842      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
843
844    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
845
846    i= biFactors;
847    yToLift= power (y, lift);
848    CanonicalForm dummy;
849    for (; i.hasItem(); i++)
850    {
851      LCA= LC (i.getItem(), 1);
852      extgcd (LCA, yToLift, LCA, dummy);
853      i.getItem()= mod (i.getItem()*LCA, yToLift);
854    }
855
856    liftBoundsLength= F.level() - 1;
857    liftBounds= liftingBounds (A, lift);
858
859    CFList MOD;
860    bool earlySuccess;
861    CFList earlyFactors;
862    ExtensionInfo info= ExtensionInfo (false);
863    CFList liftedFactors;
864    TIMING_START (abs_fac_hensel_lift);
865    liftedFactors= henselLiftAndEarly
866                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
867                    Aeval, biFactors, evaluation, info);
868    TIMING_END_AND_PRINT (abs_fac_hensel_lift,
869                          "time for hensel lifting in abs fact: ");
870
871    TIMING_START (abs_fac_factor_recombination);
872    rationalFactors= factorRecombination (A, liftedFactors, MOD);
873    TIMING_END_AND_PRINT (abs_fac_factor_recombination,
874                          "time for factor recombination in abs fact: ");
875
876    if (earlySuccess)
877      rationalFactors= Union (rationalFactors, earlyFactors);
878
879    for (CFListIterator i= rationalFactors; i.hasItem(); i++)
880    {
881      int kk= Aeval.getLast().level();
882      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
883      {
884        if (i.getItem().level() < kk)
885          continue;
886       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
887      }
888    }
889  }
890
891  if (w.level() != 1)
892  {
893    for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
894      iter.getItem()= swapvar (iter.getItem(), w, y);
895  }
896
897  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
898  {
899    if (totaldegree (iter.getItem())*degree (getMipo (v)) == totaldegree (G))
900    {
901      factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
902      found= true;
903      break;
904    }
905  }
906
907  // necessary since extension may be too large
908  if (!found)
909    factors= RothsteinTrager (A, rationalFactors, v, evaluation);
910
911  decompress (factors, N);
912  if (isOn (SW_RATIONAL))
913    normalize (factors);
914
915  delete [] leadingCoeffs2;
916  delete [] oldAeval;
917  delete [] Aeval2;
918  delete[] liftBounds;
919
920  return factors;
921}
922
923#endif
Note: See TracBrowser for help on using the repository browser.