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

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