source: git/libfac/factor/Factor.cc @ 341696

spielwiese
Last change on this file since 341696 was 341696, checked in by Hans Schönemann <hannes@…>, 14 years ago
Adding Id property to all files git-svn-id: file:///usr/local/Singular/svn/trunk@12231 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 47.0 KB
Line 
1///////////////////////////////////////////////////////////////////////////////
2/* $Id$ */
3static const char * errmsg = "\nYou found a bug!\nPlease inform singular@mathematik.uni-kl.de\nPlease include above information and your input (the ideal/polynomial and characteristic) in your bug-report.\nThank you.";
4///////////////////////////////////////////////////////////////////////////////
5// FACTORY - Includes
6#include <factory.h>
7#ifndef NOSTREAMIO
8#ifdef HAVE_IOSTREAM
9#include <iostream>
10#define CERR std::cerr
11#define CIN std::cin
12#elif defined(HAVE_IOSTREAM_H)
13#include <iostream.h>
14#define CERR cerr
15#define CIN cin
16#endif
17#endif
18// Factor - Includes
19#include "tmpl_inst.h"
20#include "SqrFree.h"
21#include "helpstuff.h"
22#include "MVMultiHensel.h"
23#include "Truefactor.h"
24#include "homogfactor.h"
25#include "interrupt.h"
26// some CC's need this:
27#include "Factor.h"
28
29#include "alg_factor.h"
30void out_cf(char *s1,const CanonicalForm &f,char *s2);
31void out_cff(CFFList &L);
32
33
34#ifdef SINGULAR
35#define HAVE_SINGULAR_ERROR
36#endif
37
38#ifdef HAVE_SINGULAR_ERROR
39   extern "C" { void WerrorS(const char *); }
40   extern "C" { void WarnS(const char *); }
41#endif
42
43#ifdef FACTORDEBUG
44#  define DEBUGOUTPUT
45#else
46#  undef DEBUGOUTPUT
47#endif
48
49#include "debug.h"
50#include "timing.h"
51TIMING_DEFINE_PRINT(factorize_time);
52TIMING_DEFINE_PRINT(sqrfree_time);
53TIMING_DEFINE_PRINT(discr_time);
54TIMING_DEFINE_PRINT(evaluate_time);
55TIMING_DEFINE_PRINT(hensel_time);
56TIMING_DEFINE_PRINT(truefactor_time);
57
58/*
59* a wrapper for factorize over algebraic extensions:
60* does a sanity check and, if nec., a conversion
61* before calling factorize(f,alpha)
62* ( in factorize, alpha.level() must be < 0 )
63*/
64CFFList factorize2 ( const CanonicalForm & f,
65                     const Variable & alpha, const CanonicalForm & mipo )
66{
67  if (alpha.level() <0)
68  {
69    if (f.isUnivariate())
70      return factorize(f,alpha);
71    else
72    {
73      return Factorize(f,mipo);
74    }
75  }
76  else
77  {
78    bool repl=(f.mvar() != alpha);
79    //out_cf("f2 - factor:",f,"\n");
80    //out_cf("f2 - ext:",alpha,"\n");
81    //out_cf("f2 - mipo:",mipo,"\n");
82    Variable X=rootOf(mipo);
83    CanonicalForm F=f;
84    if (repl) F=replacevar(f,alpha,X);
85    //out_cf("call - factor:",F,"\n");
86    //out_cf("call - ext:",X,"\n");
87    //out_cf("call - mipo:",getMipo(X,'A'),"\n");
88    CFFList L=factorize(F,X);
89    CFFListIterator i=L;
90    if (repl)
91    {
92      CFFList Outputlist;
93      for(;i.hasItem(); i++ )
94      {
95        Outputlist.append(CFFactor(
96        replacevar(i.getItem().factor(),X,alpha),
97        i.getItem().exp()));
98      }
99      return Outputlist;
100    }
101    else return L;
102  }
103}
104///////////////////////////////////////////////////////////////
105// Choose a main variable if the user didn`t wish a          //
106// special one. Returns level of main variable.              //
107///////////////////////////////////////////////////////////////
108static int
109choose_main_variable( const CanonicalForm & f, int Mainvar=0){
110  CanonicalForm remlc, newlc;
111  int n= level(f), mainvar= Mainvar;
112
113  if (mainvar != 0) return mainvar ; // We force use of the wished mainvar
114  remlc= LC(f,n); mainvar = n;
115  if ( totaldegree(remlc)==0 ){ remlc=f.genOne() ; }
116  DEBOUTLN(CERR, "remlc= " , remlc);
117  for ( int i=n-1; i>=1; i-- )
118  {
119    newlc= LC(f,i);
120    if ( totaldegree(newlc)==0 ){ newlc=f.genOne() ; }
121    DEBOUTLN(CERR, "newlc= " , newlc);
122    if ( (remlc.isOne()) && (newlc.isOne()) ){ // take care of the degrees
123      if ( degree(f,i) < degree(f,mainvar) ){
124        remlc= newlc;
125        mainvar= i;
126      }
127    }
128    else  if ( (! remlc.isOne() ) && ( newlc.isOne() ) ){
129      remlc= newlc;
130      mainvar= i;
131    }
132  }
133  return mainvar;
134}
135
136///////////////////////////////////////////////////////////////
137// Check if the derivative is nonzero for oldmainvar.        //
138// Returns the level of the choosen main variable.           //
139///////////////////////////////////////////////////////////////
140static int
141necessary_condition( const CanonicalForm & F, int oldmainvar){
142  CanonicalForm g;
143  int n=level(F);
144
145  g= swapvar(F,oldmainvar,n);
146  g= g.deriv();
147  if ( g.isZero() )
148  {
149    for ( int i=n; i>=1; i-- )
150    {
151      g= swapvar(F,i,n);
152      g= g.deriv();
153      if ( ! g.isZero() ) return i;
154    }
155  }
156  return oldmainvar;
157}
158
159///////////////////////////////////////////////////////////////
160// Make F monic. Return monic polynomial.                    //
161///////////////////////////////////////////////////////////////
162static CanonicalForm
163make_monic( const CanonicalForm & F, const CanonicalForm & lt)
164{
165  CanonicalForm intermediatpoly,f;
166  Variable x(level(F));
167
168  if ( degree(lt) == 0 ) f= 1/lt * F ;
169  else
170  {
171    intermediatpoly= power(lt,degree(F)-1);
172    for ( int i=0; i<=degree(F); i++ )
173      if ( ! F[i].isZero())
174        f+= (F[i] * intermediatpoly*power(x,i))/power(lt,i);
175  }
176  return f;
177}
178
179///////////////////////////////////////////////////////////////
180// Decide whether num/denum (num,denum both from the         //
181// FiniteFielddomain)  lies in the RationalDomain.           //
182// If false, return num/denum else return the zero poly from //
183// the FiniteFielddomain.                                    //
184///////////////////////////////////////////////////////////////
185static CanonicalForm
186is_rational( const CanonicalForm & num, const CanonicalForm & denum ){
187  CanonicalForm a, b;
188  int retvalue;
189
190  retvalue= mydivremt(num,denum,a,b);
191  if ( retvalue && b == num.genZero() ) // num/denum from FFdomain
192    return a;
193  else // num/denum is rational
194    return num.genZero();
195}
196
197///////////////////////////////////////////////////////////////
198// lt_is_product returns 1 iff lt is a product, 0 iff lt is  //
199// a sum.                                                    //
200///////////////////////////////////////////////////////////////
201static int
202lt_is_product( const CanonicalForm & lt ){
203  CFList result;
204
205  result= get_Terms(lt);
206  if ( result.length() > 1 ) return 0;
207  else return 1;
208}
209
210///////////////////////////////////////////////////////////////
211// Reverse the make_monic transformation.                    //
212// Return the list of factors.                               //
213///////////////////////////////////////////////////////////////
214static CFFList
215not_monic( const CFFList & TheList, const CanonicalForm & ltt, const CanonicalForm & F, int levelF)
216{
217  CFFList Returnlist,IntermediateList;
218  CFFListIterator i;
219  CanonicalForm intermediate,lt= ltt,savelc;
220  CanonicalForm numerator,denumerator,test,a,b;
221  Variable x(level(F));
222  int test1;
223
224  if ( lt.isOne() ) return TheList; // the poly was already monic
225  if ( TheList.length() <= 1 ) // only one factor to substitute back
226  {
227    if ( totaldegree(lt) == 0 ) // lt is type numeric
228      Returnlist.append( CFFactor(lt*TheList.getFirst().factor(),
229                                  TheList.getFirst().exp()) );
230    else
231    {
232      intermediate = F(x*lt, levelF)/power(lt,degree(F,levelF)-1);
233      Returnlist.append(CFFactor(intermediate,TheList.getFirst().exp()));
234    }
235  }
236  else // more then one factor
237  {
238    IntermediateList= TheList;
239    if ( totaldegree(lt) == 0 ){ // lt is type numeric;(SqrFree-use, see above)
240      Returnlist.append( CFFactor(lt*IntermediateList.getFirst().factor()
241                                  , IntermediateList.getFirst().exp()) );
242      IntermediateList.removeFirst();
243      Returnlist= Union(Returnlist,IntermediateList);
244    }
245    else // lt is a) a product or b) a sum of terms
246    {
247      if ( lt_is_product(lt) ) // case a)
248      {
249        DEBOUTLN(CERR, "lt_is_product: ", lt);
250        savelc= content(lt) ; // can we simplify to savelc= lc(lt); ?
251        while ( getNumVars(savelc) != 0 )
252          savelc= content(savelc);
253        for ( i=TheList; i.hasItem();i++ )
254        {
255          numerator= i.getItem().factor();
256          numerator= numerator(x*lt,levelF); // x <- x*lt
257          denumerator= power(lt,degree(F,levelF)-1); // == lt^(1-degree(F,x)
258          while (numerator.genZero() == is_rational(numerator, denumerator))
259            numerator*= lt;
260          intermediate= is_rational(numerator,denumerator);
261
262          Returnlist.append( CFFactor(lc(content(intermediate))*intermediate/content(intermediate), i.getItem().exp() ) );
263        }
264        // Now we add a test. If product(factors)/F is a multiple of
265        // savelc, we have to add 1/multiplicity to the factors
266        IntermediateList= Returnlist;
267        intermediate= 1;
268        for ( CFFListIterator j=IntermediateList; j.hasItem(); j++)
269          intermediate*= j.getItem().factor();
270        test1= mydivremt( intermediate,F,a,b);
271        if ( test1 && b == intermediate.genZero() ) // Yupp!
272        {
273          IntermediateList.append(CFFactor(1/a,1));
274          Returnlist= IntermediateList;
275        }
276        else { Returnlist= IntermediateList; }
277      }
278      else // case b)
279      {
280        DEBOUTLN(CERR, "lt_is_sum: ", lt);
281        CanonicalForm save_denumerator= 1;
282        for ( i=TheList; i.hasItem(); i++ )
283        {
284          numerator= i.getItem().factor();
285          numerator= numerator(x*lt,levelF); // x <- x*lt
286          denumerator= power(lt,degree(numerator,levelF)); // == lt^(-degree(numerator,x)
287          test= content(numerator,x);
288          test1= mydivremt(denumerator,test,a,b);
289          if ( test1 && b == numerator.genZero() ) // Yupp!
290          {
291            save_denumerator*= a;
292            Returnlist.append(CFFactor(numerator/test ,1));
293          }
294          else
295          {
296#ifdef HAVE_SINGULAR_ERROR
297            WerrorS("libfac: ERROR: not_monic1: case lt is a sum.");
298#else
299#ifndef NOSTREAMIO
300            CERR << "libfac: ERROR: not_monic1: case lt is a sum.\n"
301                 << errmsg << "\n";
302#endif
303#endif
304          }
305        }
306        // Now we add a test if we did the right thing:
307        // save_denumerator should be a multiple of the leading coeff
308        test1= mydivremt(save_denumerator,lt,a,b);
309        if ( test1 && b == save_denumerator.genZero() ) // Yupp!
310          // We have to multiply one of the factors with
311          // the multiplicity of the save_denumerator <-> lc
312          // the following will do what we want
313          Returnlist= myUnion( CFFList(CFFactor(1/a,1)),Returnlist) ;
314        else
315        {
316#ifdef HAVE_SINGULAR_ERROR
317          WerrorS("libfac: ERROR: not_monic2: case lt is a sum.");
318#else
319#ifndef NOSTREAMIO
320          CERR << "libfac: ERROR: not_monic2: case lt is a sum.\n"
321               << errmsg << "\n";
322#endif
323#endif
324        }
325      }
326    }
327  }
328  DEBOUTLN(CERR,"Returnlist: ", Returnlist);
329  return Returnlist;
330}
331
332///////////////////////////////////////////////////////////////
333// Substitute the (Variable,Value)-Pair(s) from Substitution-//
334// list into the polynomial F. Returns the resulting poly.   //
335///////////////////////////////////////////////////////////////
336static CanonicalForm
337substitutePoly( const CanonicalForm & F, const SFormList & Substitutionlist){
338  CanonicalForm f= F;
339
340  for ( SFormListIterator i=Substitutionlist; i.hasItem(); i++ )
341    f= f(i.getItem().exp(),level(i.getItem().factor()));
342  return f;
343}
344
345///////////////////////////////////////////////////////////////
346// Find specialization values for the poly F. Returns 0 if   //
347// procedure failed, 1 otherwise. On success Substitutionlist//
348// holds (Variable,Value)-pairs. On failure we only have a   //
349// partitial list.                                           //
350///////////////////////////////////////////////////////////////
351//      *** This is the version with extensions ***          //
352///////////////////////////////////////////////////////////////
353
354///////////////////////////////////////////////////////////////
355// is CF g ok?                                               //
356///////////////////////////////////////////////////////////////
357static int
358various_tests( const CanonicalForm & g, int deg, int vars_left)
359{
360  CFMap m;
361
362  if ( degree(g) == deg ) // degrees match
363    if ( level(compress(g,m)) == (vars_left) ) // exactly one variable less
364      if ( SqrFreeTest(g,1) ) // poly is sqrfree
365        if ( gcd(g,g.deriv()).isOne() ) // Discriminante != 0
366           return 1;
367  return 0;
368}
369
370///////////////////////////////////////////////////////////////
371// specialize one variable over the given field.             //
372///////////////////////////////////////////////////////////////
373// substitutes in poly f of degree deg with former
374// former_nr_of_variables variables the variable nr_of_variable ;
375// this is done in the field of Char getCharacteristic() and
376// Extension given by Extgenerator.
377///////////////////////////////////////////////////////////////
378static int
379specialize_variable( CanonicalForm & f, int deg, SFormList & Substitutionlist, int nr_of_variable,
380                     int former_nr_of_variables, CFGenerator & Extgenerator ){
381  CanonicalForm g;
382  Variable x(nr_of_variable);
383
384  DEBOUTLN(CERR, "specialize_variable: called with: ", f);
385  for ( Extgenerator.reset(); Extgenerator.hasItems(); Extgenerator.next() ){
386    DEBOUTLN(CERR, "  specialize_variable: trying:  ", Extgenerator.item());
387    g= f( Extgenerator.item(), x );
388    DEBOUTLN(CERR, "  specialize_variable: resulting g= ", g);
389    if ( various_tests(g,deg,former_nr_of_variables - nr_of_variable ) ){
390      Substitutionlist.insert(SForm(x,Extgenerator.item())); // append (Var,value) pair
391      f= g;
392      return 1;
393    }
394  }
395  return 0;
396}
397static int
398specialize_agvariable( CanonicalForm & f, int deg, SFormList & Substitutionlist, int nr_of_variable,
399                     int former_nr_of_variables, AlgExtGenerator & Extgenerator ){
400  CanonicalForm g;
401  Variable x(nr_of_variable);
402
403  DEBOUTLN(CERR, "specialize_variable: called with: ", f);
404  for ( Extgenerator.reset(); Extgenerator.hasItems(); Extgenerator.next() ){
405    DEBOUTLN(CERR, "  specialize_variable: trying:  ", Extgenerator.item());
406    g= f( Extgenerator.item(), x );
407    DEBOUTLN(CERR, "  specialize_variable: resulting g= ", g);
408    if ( various_tests(g,deg,former_nr_of_variables - nr_of_variable ) ){
409      Substitutionlist.insert(SForm(x,Extgenerator.item())); // append (Var,value) pair
410      f= g;
411      return 1;
412    }
413  }
414  return 0;
415}
416
417///////////////////////////////////////////////////////////////
418// generate a minpoly of degree degree_of_Extension in the   //
419// field getCharacteristik()^Extension.                      //
420///////////////////////////////////////////////////////////////
421CanonicalForm
422generate_mipo( int degree_of_Extension , const Variable & Extension ){
423  FFRandom gen;
424  if ( degree(Extension) > 0 ) GFRandom gen;
425  else {
426    if ( degree(Extension) == 0 ) FFRandom gen;
427    else {
428#ifdef HAVE_SINGULAR_ERROR
429    WerrorS("libfac: evaluate: Extension not inFF() or inGF() !");
430#else
431#ifndef NOSTREAMIO
432    CERR << "libfac: evaluate: " << Extension << " not inFF() or inGF() !"
433         << "\n";
434#endif
435#endif
436    FFRandom gen;
437    }
438  }
439  return find_irreducible( degree_of_Extension, gen, Variable(1) );
440}
441
442///////////////////////////////////////////////////////////////
443// Try to find a specialization for f over the field of char //
444// f.getCharacteristic() and (possible) extension defined by //
445// the variable Extension .                                  //
446// Returns 1 iff specialisation was found, 0 otherwise.      //
447// If 0 is returned there are variables left to substitute.  //
448// We check if Substitutionlist.length() > 0, i.e. we        //
449// previously tried to find specialization values for some   //
450// values. We take them and work with the resulting poly.    //
451///////////////////////////////////////////////////////////////
452static int
453try_specializePoly(const CanonicalForm & f, const Variable & Extension, int deg, SFormList & Substitutionlist, int ii,int j)
454{
455  int ok,i= ii;
456  CanonicalForm ff= f;
457
458  if ( Substitutionlist.length() > 0 ){ // we formerly tried to specialize
459    ff= substitutePoly(f,Substitutionlist); // substitute found values
460    i= Substitutionlist.length() + 1;
461  }
462
463  if ( degree(Extension) > 0 )
464  { // working over Extensions
465    DEBOUTLN(CERR, "try_specializePoly: working over Extensions: ", Extension);
466    if (Extension.level() > 0)
467    {
468    //  AlgExtGenerator g(Extension,minpoly );
469    //  for ( int k=i ; k<j ; k++ ) // try to find specialization for all
470    //  {                           // variables (# = k ) beginning with the
471    //                             // starting value i
472    //    ok= specialize_agvariable( ff, deg, Substitutionlist, k, j, g );
473    //    if ( ! ok ) return 0; // we failed
474    //  }
475      #ifndef NDEBUG
476        //printf("libfac: try_specializePoly: extension level >0\n");
477      #endif
478      return 0; // we failed
479    }
480    else
481    {
482      AlgExtGenerator g(Extension);
483      for ( int k=i ; k<j ; k++ ) // try to find specialization for all
484      {                           // variables (# = k ) beginning with the
485                                 // starting value i
486        ok= specialize_agvariable( ff, deg, Substitutionlist, k, j, g );
487        if ( ! ok ) return 0; // we failed
488      }
489    }
490  }
491  else{ // working over the ground-field
492    FFGenerator g;
493    DEBOUTMSG(CERR, "try_specializePoly: working over the ground-field.");
494    for ( int k=i ; k<j ; k++ ){
495      ok= specialize_variable( ff, deg, Substitutionlist, k, j, g );
496      if ( ! ok ) return 0; // we failed
497    }
498  }
499  return 1;
500}
501
502static int
503specializePoly(const CanonicalForm & f, Variable & Extension, int deg, SFormList & Substitutionlist, int i,int j){
504  Variable minpoly= Extension;
505  int ok,extended= degree(Extension), working_over_extension;
506
507  // Remember if we are working over an extension-field
508  if ( extended >= 2 )    { working_over_extension = 1; }
509  else                    { working_over_extension = 0; extended = 1; }
510  // First try:
511  ok = try_specializePoly(f,minpoly,deg,Substitutionlist,i,j);
512  while ( ! ok ){ // we have to extend!
513    extended+= 1;
514    if ( ! working_over_extension ){
515      minpoly= rootOf(generate_mipo( extended,Extension ));
516      Extension= minpoly;
517      ok= try_specializePoly(f,minpoly,deg,Substitutionlist,i,j);
518    }
519    else {
520#ifdef HAVE_SINGULAR_ERROR
521      WerrorS("libfac: spezializePoly ERROR: Working over given extension-field not yet implemented!");
522#else
523#ifndef NOSTREAMIO
524      CERR << "libfac: spezializePoly ERROR: Working over given extension-field not yet implemented!\n"
525           << errmsg << "\n";
526#endif
527#endif
528      return 0;
529    }
530  }
531  return 1;
532}
533
534
535// This is a procedure to play with: lot's of parameters!
536// returns: 0  iff no success (possibly because Extension isn't great enough
537//          >0 iff g (univariate) splits into n factors;
538// if n>0 BestEvaluationpoint contains the choice of values for the variables
539//
540// tries to find at least maxtries evaluation points
541// if g factored sametries into the same number of poly's the procedure stops
542// if we tried failtries evaluations not found valid, we stop. Perhaps
543// Extension isn't big enough!
544static int
545evaluate( int maxtries, int sametries, int failtries, const CanonicalForm &f , const Variable & Extension, const CanonicalForm &mipo, SFormList & BestEvaluationpoint, CFFList & BestFactorisation ){
546  int minfactors=degree(f),degf=degree(f),n=level(f.mvar())-1;
547  SFormList minEvaluation;
548  CFFList minFactorisation;
549  int samefactors=0, failedfactor=0, tried=0;
550  FFRandom gen;
551  CFFList unilist;
552
553  if ( degree(Extension) >0 ) GFRandom gen;
554  else { if ( degree(Extension) == 0 ) FFRandom gen;
555  else {
556#ifdef HAVE_SINGULAR_ERROR
557    WerrorS("libfac: evaluate: Extension not inFF() or inGF() !");
558#else
559#ifndef NOSTREAMIO
560    CERR << "libfac: evaluate: " << Extension << " not inFF() or inGF() !"
561         << "\n";
562#endif
563#endif
564    FFRandom gen; }}
565  REvaluation k(1,n,gen);
566  k.nextpoint();
567  for ( int i=1; i<=maxtries ; i++){
568    // k.nextpoint();
569    SFormList Substitutionlist;
570    for ( int j=1; j<=n; j++ )
571     Substitutionlist.insert(SForm(Variable(j),k[j]));
572    k.nextpoint();
573    CanonicalForm g=substitutePoly(f,Substitutionlist);
574    if ( various_tests(g, degf,1) ){ // found a valid point
575      failedfactor = 0; tried += 1;
576      if ( degree(Extension) == 0   )
577        unilist = factorize(g,1); // poly is sqr-free!
578      else
579      {
580        unilist = factorize2(g,Extension,mipo);
581      }
582      if (unilist.length() <= minfactors )
583      {
584        minfactors=unilist.length();
585        minEvaluation=Substitutionlist;
586        minFactorisation=unilist;
587      }
588      else samefactors +=1;
589
590      if (unilist.length() == 1 ) // wow! we found f is irreducible!
591      {
592        BestEvaluationpoint=minEvaluation;
593        BestFactorisation=minFactorisation;
594        return 1;
595      }
596
597      if ( samefactors >= sametries ) // now we stop ( maybe polynomial *has*
598                                      // minfactors factors? )
599      {
600        BestEvaluationpoint=minEvaluation;
601        BestFactorisation=minFactorisation;
602        return minfactors;
603      }
604
605    }
606    else
607      failedfactor += 1;
608
609    if ( failedfactor >= failtries ) // now we stop ( perhaps Extension isn't
610                                     // big enough )
611    {
612      if ( tried == 0 )
613        return 0;
614      else
615      {
616        BestEvaluationpoint=minEvaluation;
617        BestFactorisation=minFactorisation;
618        return minfactors;
619      }
620    }
621  }
622  BestEvaluationpoint=minEvaluation;
623  BestFactorisation=minFactorisation;
624  return minfactors;
625}
626
627#ifdef EXPERIMENTAL
628static int
629find_evaluation(int maxtries, int sametries, int failtries, const CanonicalForm &f , const Variable & Extension, SFormList & BestEvaluationpoint, CFFList & BestFactorisation ){
630  int success;
631
632  success=evaluate( maxtries, sametries, failtries, f , Extension, BestEvaluationpoint, BestFactorisation );
633  return success;
634}
635#endif
636
637///////////////////////////////////////////////////////////////
638// A factorization routine for a sqrfree polynomial.         //
639// Returns the list of factors.                              //
640///////////////////////////////////////////////////////////////
641CFFList
642Factorized( const CanonicalForm & F, const CanonicalForm & alpha, int Mainvar)
643{
644  CanonicalForm f,lt,ff,ffuni;
645  Variable Extension=alpha.mvar();
646  CFFList Outputlist,UnivariateFactorlist,Outputlist2;
647  SFormList Substitutionlist, Evaluationpoint;
648  CFFactor copy;
649  int mainvar=Mainvar,success,oldmainvar;
650  CFMap m;
651
652  // INTERRUPTHANDLER
653  if ( interrupt_handle() ) return CFFList() ;
654  // INTERRUPTHANDLER
655
656  if ( F.isUnivariate() ) // could have lost one Variable elsewhere
657  {
658    if ( degree(Extension) == 0 )
659    {
660      TIMING_START(evaluate_time);
661      Outputlist = factorize(F,1); // poly is sqr-free
662      TIMING_END(evaluate_time);
663      return Outputlist;
664    }
665    else
666    {
667      if (Extension.level()<0)
668      DEBOUTLN(CERR, "Univ. Factorization over extension of degree ",
669               degree(getMipo(Extension,'x')) );
670      else
671      DEBOUTLN(CERR, "Univ. Factorization over extension of level ??",
672                Extension.level());
673      TIMING_START(evaluate_time);
674     #if 1
675     Outputlist = factorize2(F,Extension,alpha);
676     #else
677      Variable X;
678      CanonicalForm mipo=getMipo(Extension,X);
679      CFList as(mipo);
680      Outputlist = newfactoras( F, as, 1);
681     #endif
682      TIMING_END(evaluate_time);
683      return Outputlist;
684    }
685  }
686
687  if ( Mainvar ) oldmainvar=Mainvar; else oldmainvar=level(F);
688  // First choose a main variable; this may be revisted in the next step
689  mainvar = choose_main_variable(F);
690  // Let`s look if @f/@mainvar is nonzero
691  mainvar = necessary_condition(F,mainvar);
692  // Now we have definetly choosen a main variable
693  // swap poly such that the mainvar has highest level
694  f=swapvar(F,mainvar,level(F));
695
696  // INTERRUPTHANDLER
697  if ( interrupt_handle() ) return CFFList() ;
698  // INTERRUPTHANDLER
699
700  if ( oldmainvar != mainvar ){
701    DEBOUTSL(CERR); DEBOUT(CERR,"Swapped poly ", F);
702    DEBOUT(CERR, " in ", f); DEBOUTNL(CERR);
703    DEBOUTSL(CERR); DEBOUT(CERR,"Swapped  ", oldmainvar );
704    DEBOUT(CERR, " <-- ", mainvar ); DEBOUT(CERR, "  Mainvar= ", f.mvar());
705    DEBOUTNL(CERR);
706    ff = f.deriv();
707    TIMING_START(discr_time);
708    ffuni = gcd(f,ff);
709    TIMING_END(discr_time);
710    if ( !(ffuni.isOne()) ){ //discriminante nonzero: split poly
711      DEBOUTLN(CERR,"Nontrivial GCD of f= ", f);
712      DEBOUTLN(CERR,"             and @f= ", ff);
713      DEBOUTLN(CERR,"          GCD(f,@f)= ", ffuni);
714      ff=f/ffuni;
715      CFFList Outputlist_a, Outputlist_b;
716      Outputlist_a = Factorized(ff,alpha);
717      DEBOUTLN(CERR, "Outputlist_a = ", Outputlist_a);
718      Outputlist_b = Factorized(ffuni,alpha);
719      DEBOUTLN(CERR, "Outputlist_b = ", Outputlist_b);
720      Outputlist = myUnion(Outputlist_a, Outputlist_b);
721      // have to back-swapvar the factors....
722      for ( CFFListIterator i=Outputlist; i.hasItem(); i++ ){
723        copy=i.getItem();
724        Outputlist2.append(CFFactor(swapvar(copy.factor(),oldmainvar,mainvar),copy.exp()));
725      }
726      DEBOUTLN(CERR, "Outputlist2 (a+b swapped) (to return) = ", Outputlist2);
727      return Outputlist2;
728    }
729  }
730
731  // Check special cases
732  for ( int i=1; i<=level(F); i++)
733  {
734    if ( degree(f,Variable(i) ) == 1 )
735    //test trivial case; only true iff F is primitiv w.r.t every variable; else check (if F=ax+b) gcd(a,b)=1 ?
736    {
737      DEBOUTLN(CERR, "Trivial case: ", F);
738      Outputlist.append(CFFactor(F,1));
739      return Outputlist;
740    }
741  }
742
743  // Look at the leading term:
744  lt = LC(f);
745  DEBOUTLN(CERR, "Leading term: ", lt);
746  //if ( lt != f.genOne() )
747  if ( !lt.isOne() )
748  {
749    // make the polynomial monic in the main variable
750    ff = make_monic(f,lt); ffuni = ff;
751    DEBOUTLN(CERR, "make_monic returned: ", ff);
752  }
753  else{ ff= f; ffuni= ff; }
754
755  TIMING_START(evaluate_time);
756  success=evaluate(min(10,max(degree(ff), 5)), min(degree(ff),3), min(degree(ff),3), ff, Extension, alpha, Substitutionlist,UnivariateFactorlist);
757  DEBOUTLN(CERR,  "Returned from evaluate: success: ", success);
758  for ( SFormListIterator ii=Substitutionlist; ii.hasItem(); ii++ )
759  {
760    DEBOUTLN(CERR, "Substituting ", ii.getItem().factor());
761    DEBOUTLN(CERR, "       with value: ", ii.getItem().exp());
762  }
763
764  if ( success==0 ) // evalute wasn't successfull
765  {
766    success= specializePoly(ffuni,Extension,degree(ff),Substitutionlist,1,getNumVars(compress(ff,m)));
767    DEBOUTLN(CERR,  "Returned from specializePoly: success: ", success);
768    if (success == 0 ) // No spezialisation could be found
769    {
770#ifdef HAVE_SINGULAR_ERROR
771      WarnS("libfac: Factorize: ERROR: Not able to find a valid specialization!");
772#else
773#ifndef NOSTREAMIO
774      CERR << "libfac: Factorize: ERROR: Not able to find a valid specialization!\n"
775           << errmsg << "\n";
776#else
777       ;
778#endif
779#endif
780      Outputlist.append(CFFactor(F,1));
781      return Outputlist;
782    }
783
784    // INTERRUPTHANDLER
785    if ( interrupt_handle() ) return CFFList() ;
786    // INTERRUPTHANDLER
787
788    ffuni = substitutePoly(ff,Substitutionlist);
789    // We now have an univariat poly; factorize that
790    if ( degree(Extension) == 0   )
791    {
792      DEBOUTMSG(CERR, "Univ. Factorization over the ground field");
793      UnivariateFactorlist = factorize(ffuni,1); // univ. poly is sqr-free!
794    }
795    else
796    {
797      DEBOUTLN(CERR, "Univ. Factorization over extension of degree ",
798               degree(getMipo(Extension,'x')) );
799     #if 1
800      UnivariateFactorlist = factorize2(ffuni,Extension,alpha);
801     #else
802      Variable X;
803      CanonicalForm mipo=getMipo(Extension,X);
804      CFList as(mipo);
805      UnivariateFactorlist = newfactoras( ffuni, as, 1);
806     #endif
807    }
808  }
809  else
810  {
811    ffuni = substitutePoly(ff,Substitutionlist);
812  }
813    TIMING_END(evaluate_time);
814  if (UnivariateFactorlist.length() == 1)
815  { // poly is irreduzibel
816    DEBOUTLN(CERR, "Univ. poly is irreduzible: ", UnivariateFactorlist);
817    Outputlist.append(CFFactor(F,1));
818    return Outputlist;
819  }
820  else
821  { // we have factors
822    DEBOUTSL(CERR);
823    DEBOUT(CERR, "Univariate poly has " , UnivariateFactorlist.length());
824    DEBOUT(CERR, " factors:  ", ffuni);
825    DEBOUT(CERR, " = ", UnivariateFactorlist); DEBOUTNL(CERR);
826
827    // INTERRUPTHANDLER
828    if ( interrupt_handle() ) return CFFList() ;
829    // INTERRUPTHANDLER
830
831    TIMING_START(hensel_time);
832    Outputlist = MultiHensel(ff,UnivariateFactorlist,Substitutionlist, alpha);
833    DEBOUTLN(CERR, "Outputlist after MultiHensel: ", Outputlist);
834    TIMING_END(hensel_time);
835
836    // INTERRUPTHANDLER
837    if ( interrupt_handle() ) return CFFList() ;
838    // INTERRUPTHANDLER
839
840    TIMING_START(truefactor_time);
841    Outputlist = Truefactors(ff, level(ff), Substitutionlist, Outputlist);
842    DEBOUTLN(CERR, "Outputlist after Truefactors: ", Outputlist);
843    TIMING_END(truefactor_time);
844
845    // INTERRUPTHANDLER
846    if ( interrupt_handle() ) return CFFList() ;
847    // INTERRUPTHANDLER
848
849    //if ( lt != f.genOne() )
850    if ( !lt.isOne() )
851    {
852      Outputlist = not_monic(Outputlist,lt,ff,level(ff));
853      DEBOUTLN(CERR, "not_monic returned: ", Outputlist);
854    }
855
856    // have to back-swapvar the factors....
857    for ( CFFListIterator i=Outputlist; i.hasItem(); i++ )
858    {
859      copy=i.getItem();
860      Outputlist2.append(CFFactor(swapvar(copy.factor(),oldmainvar,mainvar),copy.exp()));
861    }
862
863    return Outputlist2;
864  }
865}
866
867// for debuggig:
868int cmpCF( const CFFactor & f, const CFFactor & g );
869
870///////////////////////////////////////////////////////////////
871// The user front-end for a uni/multivariate factorization   //
872// routine. F needs not to be SqrFree.                       //
873// Option of * choosing a  main variable (n.y.i.)            //
874//           * choosing an algebraic extension (n.y.u.)      //
875//           * ensuring poly is sqrfree (n.y.i.)             //
876// use Factorize(F,alpha,is_SqrFree) if not over Zp[x]/Q[x]  //
877///////////////////////////////////////////////////////////////
878int find_mvar(const CanonicalForm &f);
879CFFList Factorize(const CanonicalForm & F, int is_SqrFree )
880{
881  //out_cf("Factorize ",F,"\n");
882  CFFList Outputlist,SqrFreeList,Intermediatelist,Outputlist2;
883  ListIterator<CFFactor> i,j;
884  CanonicalForm g=1,unit=1,r=1;
885  Variable minpoly; // dummy
886  int exp;
887  CFMap m;
888
889  // INTERRUPTHANDLER
890  if ( interrupt_handle() ) return CFFList() ;
891  // INTERRUPTHANDLER
892
893  DEBINCLEVEL(CERR, "Factorize");
894  DEBOUTLN(CERR, "Called with F= ", F);
895  if (( getCharacteristic() == 0 ) || (F.isUnivariate()))
896  { // char == 0
897    TIMING_START(factorize_time);
898    //CERR << "Factoring in char=0 of " << F << " = " << Outputlist << "\n";
899    Outputlist= factorize(F);
900    // Factorization in char=0 doesn't sometimes return at least two elements!!!
901    if ( getNumVars(Outputlist.getFirst().factor()) != 0 )
902      Outputlist.insert(CFFactor(1,1));
903    //CERR << "  Factorize in char=0: returning with: " << Outputlist << "\n";
904    TIMING_END(factorize_time);
905    DEBDECLEVEL(CERR, "Factorize");
906    TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
907    return Outputlist;
908  }
909  TIMING_START(factorize_time);
910  // search an "optimal" main variavble
911  int mv=F.level();
912  if ((mv != LEVELBASE) /* && (! F.isUnivariate()) */)
913  {
914     mv=find_mvar(F);
915     if (mv!=F.level())
916     {
917       swapvar(F,Variable(mv),F.mvar());
918     }
919  }
920
921  ///////
922  // Maybe it`s better to add a sqrfree-test before?
923  // (If gcd is fast...)
924  ///////
925  //  if ( ! SqrFreeTest(F) ){
926  if ( ! is_SqrFree )
927  {
928    TIMING_START(sqrfree_time);
929    SqrFreeList = SqrFreeMV(F) ; // first sqrfree the polynomial
930    // don't use sqrFree(F), factory's internal sqrFree for multiv.
931    // Polynomials; it's wrong!! Ex.: char=p   f= x^p*(y+1);
932    // SqrFreeMV(f)= ( y+1, (x)^p ), sqrFree(f)= ( y+1 ) .
933    TIMING_END(sqrfree_time);
934
935    // INTERRUPTHANDLER
936    if ( interrupt_handle() ) return CFFList() ;
937    // INTERRUPTHANDLER
938
939  }
940  else
941    SqrFreeList.append(CFFactor(F,1));
942
943  DEBOUTLN(CERR, "SqrFreeMV= ", SqrFreeList);
944  for ( i=SqrFreeList; i.hasItem(); i++ )
945  {
946    DEBOUTLN(CERR, "Factor under consideration: ", i.getItem().factor());
947    // We need a compress on each list item ! Maybe we have less variables!
948    g =compress(i.getItem().factor(),m);
949    exp = i.getItem().exp();
950    if ( getNumVars(g) ==0 ) // a constant; Exp==1
951      Outputlist.append( CFFactor(g,1) ) ;
952    else// a real polynomial
953      if ( g.isUnivariate() )
954      {
955        //out_cf("univ. poly: ",g,"\n");
956        Intermediatelist=factorize(g,1); // poly is sqr-free!
957        for ( j=Intermediatelist; j.hasItem(); j++ )
958          //Normally j.getItem().exp() should be 1
959          Outputlist.append( CFFactor( m(j.getItem().factor()),exp*j.getItem().exp()));
960      }
961      else
962      { // multivariate polynomial
963        if ( g.isHomogeneous() )
964        {
965          DEBOUTLN(CERR, "Poly is homogeneous! : ", g);
966          // Now we can substitute one variable to 1, factorize and then
967          // look on the resulting factors and their monomials for
968          // backsubstitution of the substituted variable.
969          Intermediatelist = HomogFactor(g, minpoly, 0);
970        }
971        else // not homogeneous
972          Intermediatelist = Factorized(g, minpoly, 0);
973
974        // INTERRUPTHANDLER
975        if ( interrupt_handle() ) return CFFList() ;
976        // INTERRUPTHANDLER
977
978        for ( j=Intermediatelist; j.hasItem(); j++ )
979          //Normally j.getItem().exp() should be 1
980          Outputlist= myappend( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
981      }
982  }
983  g=1; unit=1;
984  DEBOUTLN(CERR, "Outputlist is ", Outputlist);
985  for ( i=Outputlist; i.hasItem(); i++ )
986    if ( level(i.getItem().factor()) > 0 )
987    {
988      unit = lc(i.getItem().factor());
989      if ( getNumVars(unit) == 0 )
990      { // a constant; possibly 1
991        Outputlist2.append(CFFactor(i.getItem().factor()/unit , i.getItem().exp()));
992        g *=power(i.getItem().factor()/unit,i.getItem().exp());
993      }
994      else
995      {
996        Outputlist2.append(i.getItem());
997        g *=power(i.getItem().factor(),i.getItem().exp());
998      }
999    }
1000
1001  r=F/g;
1002  Outputlist2.insert(CFFactor(r,1));
1003
1004  if ((mv!=F.level()) && (! F.isUnivariate() ))
1005  {
1006    CFFListIterator J=Outputlist2;
1007    for ( ; J.hasItem(); J++)
1008    {
1009      swapvar(J.getItem().factor(),Variable(mv),F.mvar());
1010    }
1011    swapvar(F,Variable(mv),F.mvar());
1012  }
1013  DEBDECLEVEL(CERR, "Factorize");
1014  TIMING_END(factorize_time);
1015
1016  TIMING_PRINT(sqrfree_time, "\ntime used for sqrfree   : ");
1017  TIMING_PRINT(discr_time, "time used for discriminante   : ");
1018  TIMING_PRINT(evaluate_time, "time used for evaluation and univ. factorization  : ");
1019  TIMING_PRINT(hensel_time, "time used for hensel-lift   : ");
1020  TIMING_PRINT(truefactor_time, "time used for truefactors   : ");
1021  TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1022
1023  if(isOn(SW_USE_NTL_SORT)) Outputlist2.sort(cmpCF);
1024
1025  return Outputlist2;
1026}
1027
1028///////////////////////////////////////////////////////////////
1029// The user front-end for a uni/multivariate factorization   //
1030// routine. F needs not to be SqrFree.                       //
1031// Option of * choosing a  main variable (n.y.i.)            //
1032//           * choosing an algebraic extension (n.y.u.)      //
1033//           * ensuring poly is sqrfree (n.y.i.)             //
1034///////////////////////////////////////////////////////////////
1035static bool fdivides2(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &minpoly)
1036{
1037  if (!minpoly.isZero())
1038  {
1039  #if 0
1040    Variable Alpha=minpoly.mvar();
1041    Variable X=rootOf(minpoly);
1042    CanonicalForm rF=replacevar(F,Alpha,X);
1043    CanonicalForm rG=replacevar(G,Alpha,X);
1044    return fdivides(rF,rG);;
1045  #else
1046    if (degree(F,F.mvar()) > degree(G,F.mvar())) return false;
1047    return true;
1048    //CanonicalForm a,b;
1049    //mydivrem(G,F,a,b);
1050    //if (b.isZero()) return true;
1051    //else return false;
1052  #endif
1053  }
1054  else
1055   return fdivides(F,G);
1056}
1057CFFList Factorize2(CanonicalForm F, const CanonicalForm & minpoly )
1058{
1059#ifndef NDEBUG
1060  //printf("start Factorize2(int_flag=%d)\n",libfac_interruptflag);
1061#endif
1062  CFFList G,H;
1063  CanonicalForm fac;
1064  int d,e;
1065  ListIterator<CFFactor> i,k;
1066  libfac_interruptflag=0;
1067  CFFList iF=Factorize(F,minpoly);
1068  if ((libfac_interruptflag==0)&&(!iF.isEmpty()))
1069    H=iF;
1070  else
1071  {
1072#ifndef NDEBUG
1073    //printf("variant 2(int_flag=%d)\n",libfac_interruptflag);
1074#endif
1075    libfac_interruptflag=0;
1076    iF=Factorize(F);
1077    if (libfac_interruptflag==0)
1078    {
1079      i = iF;
1080      while( i.hasItem())
1081      {
1082        d = i.getItem().exp();
1083        fac = i.getItem().factor();
1084        if (fdivides(fac,F))
1085        {
1086          if ((getNumVars(fac)==0)||(fac.degree()<=1))
1087          {
1088#ifndef NOSTREAMIO
1089#ifndef NDEBUG
1090            //printf("append trivial factor\n");
1091#endif
1092#endif
1093            H.append( CFFactor( fac, d));
1094            do {F/=fac; d--; } while (d>0);
1095          }
1096          else
1097          {
1098            G = Factorize( fac, minpoly);
1099            if (libfac_interruptflag!=0)
1100            {
1101              libfac_interruptflag=0;
1102              k = G;
1103              while( k.hasItem())
1104              {
1105                fac = k.getItem().factor();
1106                int dd = k.getItem().exp()*d;
1107                e=0;
1108                while ((!fac.isZero())&& fdivides2(fac,F,minpoly) && (dd>0))
1109                {
1110#ifndef NOSTREAMIO
1111#ifndef NDEBUG
1112                  //out_cf("factor:",fac,"\n");
1113#endif
1114#endif
1115                  e++;dd--;
1116                  F/=fac;
1117                }
1118                if (e>0) H.append( CFFactor( fac , e ) );
1119                ++k;
1120              }
1121            }
1122          }
1123        }
1124        ++i;
1125      }
1126    }
1127  }
1128  //Outputlist = newfactoras( F, as, 1);
1129  if((isOn(SW_USE_NTL_SORT))&&(!H.isEmpty())) H.sort(cmpCF);
1130#ifndef NDEBUG
1131  //printf("end Factorize2(%d)\n",libfac_interruptflag);
1132#endif
1133  return H;
1134}
1135
1136CFFList
1137Factorize(const CanonicalForm & F, const CanonicalForm & minpoly, int is_SqrFree )
1138{
1139  //out_cf("Factorize: F=",F,"\n");
1140  //out_cf("           minpoly:",minpoly,"\n");
1141  CFFList Outputlist,SqrFreeList,Intermediatelist,Outputlist2;
1142  ListIterator<CFFactor> i,j;
1143  CanonicalForm g=1,unit=1,r=1;
1144  //Variable minpoly; // reserved (-> Factorisation over algebraic Extensions)
1145  int exp;
1146  CFMap m;
1147
1148  // INTERRUPTHANDLER
1149  if ( interrupt_handle() ) return CFFList() ;
1150  // INTERRUPTHANDLER
1151
1152  DEBINCLEVEL(CERR, "Factorize");
1153  DEBOUTLN(CERR, "Called with F= ", F);
1154  if ( getCharacteristic() == 0 )
1155  { // char == 0
1156    TIMING_START(factorize_time);
1157    //CERR << "Factoring in char=0 of " << F << " = " << Outputlist << "\n";
1158    #if 0
1159    // SHOULD: Outputlist= factorize(F,minpoly);
1160    Outputlist= factorize(F);
1161    #else
1162    if (!minpoly.isZero())
1163    {
1164      if ( F.isHomogeneous() )
1165      {
1166        DEBOUTLN(CERR, "Poly is homogeneous! : ", F);
1167        // Now we can substitute one variable to 1, factorize and then
1168        // look on the resulting factors and their monomials for
1169        // backsubstitution of the substituted variable.
1170        Outputlist=HomogFactor(F, minpoly, 0);
1171      }
1172      else
1173      {
1174        CFList as(minpoly);
1175        //CFFList sqF=sqrFree(F); // sqrFreeZ
1176        CFFList sqF=SqrFreeMV(F,minpoly);
1177        if (sqF.isEmpty()) sqF=sqrFree(F);
1178        CFFList G,H;
1179        CanonicalForm fac;
1180        int d;
1181        ListIterator<CFFactor> i,k;
1182        for ( i = sqF; i.hasItem(); ++i )
1183        {
1184          d = i.getItem().exp();
1185          fac = i.getItem().factor();
1186          int success=1;
1187          G = newfactoras( fac, as, success);
1188          for ( k = G; k.hasItem(); ++k )
1189          {
1190            fac = k.getItem().factor();
1191            int dd = k.getItem().exp();
1192            H.append( CFFactor( fac , d*dd ) );
1193          }
1194        }
1195        //Outputlist = newfactoras( F, as, 1);
1196        Outputlist = H;
1197      }
1198    }
1199    else // minpoly==0
1200      Outputlist=factorize(F);
1201    #endif
1202    // Factorization in char=0 doesn't sometimes return at least two elements!!!
1203    if ( getNumVars(Outputlist.getFirst().factor()) != 0 )
1204      Outputlist.insert(CFFactor(1,1));
1205    //CERR << "  Factorize in char=0: returning with: " << Outputlist << "\n";
1206    TIMING_END(factorize_time);
1207    DEBDECLEVEL(CERR, "Factorize");
1208    TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1209    //out_cff(Outputlist);
1210    return Outputlist;
1211  }
1212  TIMING_START(factorize_time);
1213  // search an "optimal" main variavble
1214  int mv=F.level();
1215  if (mv != LEVELBASE && ! F.isUnivariate() )
1216  {
1217     mv=find_mvar(F);
1218     if (mv!=F.level())
1219     {
1220       swapvar(F,Variable(mv),F.mvar());
1221     }
1222  }
1223
1224  ///////
1225  // Maybe it`s better to add a sqrfree-test before?
1226  // (If gcd is fast...)
1227  ///////
1228  //  if ( ! SqrFreeTest(F) ){
1229  if ( ! is_SqrFree )
1230  {
1231    TIMING_START(sqrfree_time);
1232    SqrFreeList = SqrFreeMV(F, minpoly) ; // first sqrfree the polynomial
1233    // don't use sqrFree(F), factory's internal sqrFree for multiv.
1234    // Polynomials; it's wrong!! Ex.: char=p   f= x^p*(y+1);
1235    // SqrFreeMV(f)= ( y+1, (x)^p ), sqrFree(f)= ( y+1 ) .
1236    TIMING_END(sqrfree_time);
1237
1238    // INTERRUPTHANDLER
1239    if ( interrupt_handle() ) return CFFList() ;
1240    // INTERRUPTHANDLER
1241
1242  }
1243  else
1244    SqrFreeList.append(CFFactor(F,1));
1245  DEBOUTLN(CERR, "SqrFreeMV= ", SqrFreeList);
1246  for ( i=SqrFreeList; i.hasItem(); i++ )
1247  {
1248    DEBOUTLN(CERR, "Factor under consideration: ", i.getItem().factor());
1249    // We need a compress on each list item ! Maybe we have less variables!
1250    g =compress(i.getItem().factor(),m);
1251    exp = i.getItem().exp();
1252    if ( getNumVars(g) ==0 ) // a constant; Exp==1
1253      Outputlist.append( CFFactor(g,1) ) ;
1254    else// a real polynomial
1255    {
1256      if ( g.isUnivariate() )
1257      {
1258        Variable alpha=rootOf(minpoly);
1259        Intermediatelist=factorize2(g,alpha,minpoly); // poly is sqr-free!
1260        for ( j=Intermediatelist; j.hasItem(); j++ )
1261          //Normally j.getItem().exp() should be 1
1262          Outputlist.append(
1263           CFFactor( m(replacevar(j.getItem().factor(),alpha,minpoly.mvar())),
1264             exp*j.getItem().exp()));
1265      }
1266      else // multivariate polynomial
1267      {
1268        if ( g.isHomogeneous() )
1269        {
1270          DEBOUTLN(CERR, "Poly is homogeneous! : ", g);
1271          // Now we can substitute one variable to 1, factorize and then
1272          // look on the resulting factors and their monomials for
1273          // backsubstitution of the substituted variable.
1274          Intermediatelist = HomogFactor(g, minpoly, 0);
1275        }
1276        else // not homogeneous
1277          Intermediatelist = Factorized(g, minpoly, 0);
1278
1279        // INTERRUPTHANDLER
1280        if ( interrupt_handle() ) return CFFList() ;
1281        // INTERRUPTHANDLER
1282
1283        for ( j=Intermediatelist; j.hasItem(); j++ )
1284          //Normally j.getItem().exp() should be 1
1285          Outputlist= myappend( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
1286      }
1287    }
1288  }
1289  g=1; unit=1;
1290  DEBOUTLN(CERR, "Outputlist is ", Outputlist);
1291  for ( i=Outputlist; i.hasItem(); i++ )
1292    if ( level(i.getItem().factor()) > 0 )
1293    {
1294      unit = lc(i.getItem().factor());
1295      if ( getNumVars(unit) == 0 ){ // a constant; possibly 1
1296        Outputlist2.append(CFFactor(i.getItem().factor()/unit , i.getItem().exp()));
1297        g *=power(i.getItem().factor()/unit,i.getItem().exp());
1298      }
1299      else
1300      {
1301        Outputlist2.append(i.getItem());
1302        g *=power(i.getItem().factor(),i.getItem().exp());
1303      }
1304    }
1305
1306  r=F/g;
1307  Outputlist2.insert(CFFactor(r,1));
1308
1309  if ((mv!=F.level()) && (! F.isUnivariate() ))
1310  {
1311    CFFListIterator J=Outputlist2;
1312    for ( ; J.hasItem(); J++)
1313    {
1314      swapvar(J.getItem().factor(),Variable(mv),F.mvar());
1315    }
1316    swapvar(F,Variable(mv),F.mvar());
1317  }
1318
1319  DEBDECLEVEL(CERR, "Factorize");
1320  TIMING_END(factorize_time);
1321
1322  TIMING_PRINT(sqrfree_time, "\ntime used for sqrfree   : ");
1323  TIMING_PRINT(discr_time, "time used for discriminante   : ");
1324  TIMING_PRINT(evaluate_time, "time used for evaluation and univ. factorization  : ");
1325  TIMING_PRINT(hensel_time, "time used for hensel-lift   : ");
1326  TIMING_PRINT(truefactor_time, "time used for truefactors   : ");
1327  TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1328
1329  if(isOn(SW_USE_NTL_SORT)) Outputlist2.sort(cmpCF);
1330
1331  //out_cff(Outputlist2);
1332  return Outputlist2;
1333}
1334
1335/*
1336$Log: not supported by cvs2svn $
1337Revision 1.48  2008/06/10 14:49:15  Singular
1338*hannes: licence stuff
1339
1340Revision 1.47  2008/06/01 17:48:14  Singular
1341*hannes: sqrfree etc
1342
1343Revision 1.46  2008/05/31 17:20:10  Singular
1344hannes: minor irras changes
1345
1346Revision 1.45  2008/04/08 16:19:10  Singular
1347*hannes: removed rcsid
1348
1349Revision 1.44  2008/03/18 17:46:15  Singular
1350*hannes: gcc 4.2
1351
1352Revision 1.43  2008/03/18 10:12:21  Singular
1353*hannes: format
1354
1355Revision 1.42  2008/03/17 17:44:16  Singular
1356*hannes: fact.tst
1357
1358Revision 1.38  2008/01/07 13:34:56  Singular
1359*hannes: omse optiomzations(isOne)
1360
1361Revision 1.37  2007/10/25 14:45:41  Singular
1362*hannes: homgfactor for alg.ext of Q
1363
1364Revision 1.36  2007/10/15 18:03:11  Singular
1365*hannes: // debug stuff
1366
1367Revision 1.35  2007/06/14 14:16:35  Singular
1368*hannes: Factorize2 etc.
1369
1370Revision 1.34  2007/06/02 10:21:57  Singular
1371*hannes: fdivides2 again
1372
1373Revision 1.33  2007/05/25 16:02:01  Singular
1374*hannes: removed diophant_error, format
1375
1376Revision 1.32  2007/05/25 12:59:05  Singular
1377*hannes: fdivides2
1378
1379Revision 1.31  2007/05/22 14:49:52  Singular
1380*hannes: format
1381
1382Revision 1.30  2007/05/22 14:30:53  Singular
1383*hannes: diophant_error
1384
1385Revision 1.29  2007/05/22 13:18:57  Singular
1386*hannes: Factorize2: div test, sort etc.
1387
1388Revision 1.28  2007/05/21 17:56:55  Singular
1389*hannes: fixed exp.
1390
1391Revision 1.27  2007/05/21 16:50:56  Singular
1392*hannes: fix fdivide test
1393
1394Revision 1.26  2007/05/21 16:40:12  Singular
1395*hannes: Factorize2
1396
1397Revision 1.25  2007/05/15 15:50:42  Singular
1398*hannes: Factorize2
1399
1400Revision 1.24  2007/05/15 14:46:48  Singular
1401*hannes: factorize in Zp(a)[x...]
1402
1403Revision 1.23  2006/05/16 14:46:49  Singular
1404*hannes: gcc 4.1 fixes
1405
1406Revision 1.22  2006/04/28 13:46:29  Singular
1407*hannes: better tests for 0, 1
1408
1409Revision 1.21  2005/12/12 18:02:03  Singular
1410*hannes: use sorting option in Factorize
1411
1412Revision 1.20  2005/12/05 15:47:32  Singular
1413*hannes: is_homogeneous -> factory: isHomogeneous
1414
1415Revision 1.19  2005/10/17 13:18:44  Singular
1416*hannes: apply sqrFree before newfactoras (Factorize in Q(a))
1417
1418Revision 1.18  2005/10/17 13:17:39  Singular
1419*hannes: aplly sqrFree before newfactoras (Factorize in Q(a))
1420
1421Revision 1.17  2004/12/10 10:15:06  Singular
1422*pohl: AlgExtGenerator etc.
1423
1424Revision 1.16  2003/05/28 11:52:52  Singular
1425*pfister/hannes: newfactoras, alg_gcd, divide (see bug_33)
1426
1427Revision 1.15  2003/02/14 15:51:15  Singular
1428* hannes: bugfix
1429          could not factorize x2+xy+y2 in Fp(a)[x,y], a2+a+1=0
1430          (factorize2 does nor sanity checks)
1431
1432Revision 1.14  2002/08/19 11:11:32  Singular
1433* hannes/pfister: alg_gcd etc.
1434
1435Revision 1.13  2002/07/30 17:06:47  Singular
1436*hannes: uuh - factorize in Q(a)[x] is missing, use Q[a][x].
1437
1438Revision 1.12  2002/07/30 15:10:22  Singular
1439*hannes: added Factorize for alg. ext.
1440
1441Revision 1.11  2001/08/22 14:21:16  Singular
1442*hannes: added search for main var to Factorize
1443
1444Revision 1.10  2001/08/08 14:26:55  Singular
1445*hannes: Dan's HAVE_SINGULAR_ERROR
1446
1447Revision 1.9  2001/08/08 11:59:12  Singular
1448*hannes: Dan's NOSTREAMIO changes
1449
1450Revision 1.8  2001/08/06 08:32:54  Singular
1451* hannes: code cleanup
1452
1453Revision 1.7  2001/06/21 14:57:05  Singular
1454*hannes/GP: Factorize, newfactoras, ...
1455
1456Revision 1.6  2001/06/18 08:44:41  pfister
1457* hannes/GP/michael: factory debug, Factorize
1458
1459Revision 1.5  1999/06/15 12:54:55  Singular
1460* hannes: debug fixes for Singular-interface
1461
1462Revision 1.4  1997/11/18 16:39:04  Singular
1463* hannes: moved WerrorS from C++ to C
1464     (Factor.cc MVMultiHensel.cc SqrFree.cc Truefactor.cc)
1465
1466Revision 1.3  1997/09/12 07:19:46  Singular
1467* hannes/michael: libfac-0.3.0
1468
1469Revision 1.6  1997/04/25 22:18:40  michael
1470changed lc == 1 to lc == unit in choose_mainvar
1471changed cerr and cout messages for use with Singular
1472Version for libfac-0.2.1
1473
1474Revision 1.5  1997/01/17 05:04:03  michael
1475* added support for homogenous polynomials
1476* exported functions to homogfactor.cc
1477
1478*/
Note: See TracBrowser for help on using the repository browser.