Changeset 639047e in git for libfac/factor


Ignore:
Timestamp:
Aug 19, 2002, 1:11:34 PM (22 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
6acb298d347b4b82e942caa7518a2625dc747c1e
Parents:
b1476d0550d3e358e0fcafec0719ae421300980e
Message:
* hannes/pfister: alg_gcd etc.


git-svn-id: file:///usr/local/Singular/svn/trunk@6237 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
libfac/factor
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • libfac/factor/Factor.cc

    rb1476d0 r639047e  
    11/* Copyright 1996 Michael Messollen. All rights reserved. */
    22///////////////////////////////////////////////////////////////////////////////
    3 static char * rcsid = "$Id: Factor.cc,v 1.13 2002-07-30 17:06:47 Singular Exp $ ";
     3static char * rcsid = "$Id: Factor.cc,v 1.14 2002-08-19 11:11:32 Singular Exp $ ";
    44static 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.";
    55///////////////////////////////////////////////////////////////////////////////
    … …  
    465465      {
    466466        unilist = factorize(g,Extension);
    467       } 
     467      }       
    468468      if (unilist.length() <= minfactors ) {
    469469        minfactors=unilist.length();
    … …  
    521521///////////////////////////////////////////////////////////////
    522522CFFList
    523 Factorized( const CanonicalForm & F, const Variable & alpha, int Mainvar){
     523Factorized( const CanonicalForm & F, const CanonicalForm & alpha, int Mainvar){
    524524  CanonicalForm f,lt,ff,ffuni;
    525   Variable Extension=alpha;
     525  Variable Extension=alpha.mvar();
    526526  CFFList Outputlist,UnivariateFactorlist,Outputlist2;
    527527  SFormList Substitutionlist, Evaluationpoint;
    … …  
    546546      TIMING_START(evaluate_time);
    547547     #if 1
    548       Outputlist = factorize(F,Extension);
     548      if (Extension.level() <0)
     549        Outputlist = factorize(F,Extension);
     550      else
     551      {
     552        Variable X=rootOf(alpha);
     553        CFFList L=factorize(F,X);
     554        CFFListIterator i=L;
     555        for(;i.hasItem(); i++ )
     556        {
     557          Outputlist.append(CFFactor(
     558            replacevar(i.getItem().factor(),X,Extension),
     559            i.getItem().exp()));
     560        }   
     561      }
    549562     #else
    550563      Variable X;
    … …  
    853866    swapvar(F,Variable(mv),F.mvar());
    854867  }
    855                                                                                        
     868                                                                                       
    856869  DEBDECLEVEL(cout, "Factorize");
    857870  TIMING_END(factorize_time);
    … …  
    874887///////////////////////////////////////////////////////////////
    875888CFFList
    876 Factorize(const CanonicalForm & F, Variable minpoly, int is_SqrFree ){
     889Factorize(const CanonicalForm & F, const CanonicalForm & minpoly, int is_SqrFree ){
    877890  CFFList Outputlist,SqrFreeList,Intermediatelist,Outputlist2;
    878891  ListIterator<CFFactor> i,j;
    … …  
    889902  DEBOUTMSG(cout, rcsid);
    890903  DEBOUTLN(cout, "Called with F= ", F);
    891   if ( getCharacteristic() == 0 ) { // char == 0
     904  if ( getCharacteristic() == 0 )
     905  { // char == 0
    892906    TIMING_START(factorize_time);
    893907    //cout << "Factoring in char=0 of " << F << " = " << Outputlist << endl;
     908    #if 0
    894909    // SHOULD: Outputlist= factorize(F,minpoly);
    895910    Outputlist= factorize(F);
     911    #else
     912    if (minpoly!=0)
     913    {
     914      CFList as(minpoly);
     915      Outputlist = newfactoras( F, as, 1);
     916    }
     917    else
     918      Outputlist=factorize(F);
     919    #endif
    896920    // Factorization in char=0 doesn't sometimes return at least two elements!!!
    897921    if ( getNumVars(Outputlist.getFirst().factor()) != 0 )
    … …  
    922946  if ( ! is_SqrFree ){
    923947    TIMING_START(sqrfree_time);
    924     SqrFreeList = InternalSqrFree(F) ; // first sqrfree the polynomial
     948    SqrFreeList = InternalSqrFree(F, minpoly) ; // first sqrfree the polynomial
    925949    // don't use sqrFree(F), factory's internal sqrFree for multiv.
    926950    // Polynomials; it's wrong!! Ex.: char=p   f= x^p*(y+1);
    … …  
    945969    else// a real polynomial
    946970      if ( g.isUnivariate() ){
    947         Intermediatelist=factorize(g,minpoly); // poly is sqr-free!
     971        Variable alpha=rootOf(minpoly);
     972        Intermediatelist=factorize(g,alpha); // poly is sqr-free!
    948973        for ( j=Intermediatelist; j.hasItem(); j++ )
    949974          //Normally j.getItem().exp() should be 1
    950           Outputlist.append( CFFactor( m(j.getItem().factor()),exp*j.getItem().exp()));
     975          Outputlist.append(
     976           CFFactor( m(replacevar(j.getItem().factor(),alpha,minpoly.mvar())),
     977             exp*j.getItem().exp()));
    951978      }
    952979      else{ // multivariate polynomial
    … …  
    9971024    swapvar(F,Variable(mv),F.mvar());
    9981025  }
    999                                                                                        
     1026                                                                                       
    10001027  DEBDECLEVEL(cout, "Factorize");
    10011028  TIMING_END(factorize_time);
    … …  
    10121039/*
    10131040$Log: not supported by cvs2svn $
     1041Revision 1.13  2002/07/30 17:06:47  Singular
     1042*hannes: uuh - factorize in Q(a)[x] is missing, use Q[a][x].
     1043
    10141044Revision 1.12  2002/07/30 15:10:22  Singular
    10151045*hannes: added Factorize for alg. ext.

  • libfac/factor/Factor.h

    rb1476d0 r639047e  
    22////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 // $Id: Factor.h,v 1.4 2002-07-30 15:05:38 Singular Exp $
     4// $Id: Factor.h,v 1.5 2002-08-19 11:11:33 Singular Exp $
    55///////////////////////////////////////////////////////////////////////////////
    66#ifndef FACTOR_H
    77#define FACTOR_H
    88CanonicalForm generate_mipo( int degree_of_Extension , const Variable & Extension );
    9 CFFList Factorized( const CanonicalForm & F, const Variable & alpha, int Mainvar=0);
     9CFFList Factorized( const CanonicalForm & F, const CanonicalForm & mipo, int Mainvar=0);
    1010/*BEGINPUBLIC*/
    1111CFFList Factorize( const CanonicalForm & F, int is_SqrFree=0 ) ;
    12 CFFList Factorize( const CanonicalForm & F, Variable mi, int is_SqrFree=0 ) ;
     12CFFList Factorize( const CanonicalForm & F, const CanonicalForm & mi, int is_SqrFree=0 ) ;
    1313/*ENDPUBLIC*/
    1414
    … …  
    1818/*
    1919$Log: not supported by cvs2svn $
     20Revision 1.4  2002/07/30 15:05:38  Singular
     21*hannes: added Factorize for alg. ext.
     22
    2023Revision 1.3  1997/09/12 07:19:47  Singular
    2124* hannes/michael: libfac-0.3.0

  • libfac/factor/SqrFree.cc

    rb1476d0 r639047e  
    22///////////////////////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 static char * rcsid = "$Id: SqrFree.cc,v 1.7 2001-08-08 14:27:38 Singular Exp $";
     4static char * rcsid = "$Id: SqrFree.cc,v 1.8 2002-08-19 11:11:33 Singular Exp $";
    55static char * errmsg = "\nYou found a bug!\nPlease inform (Michael Messollen) michael@math.uni-sb.de .\n Please include above information and your input (the ideal/polynomial and characteristic) in your bug-report.\nThank you.";
    66///////////////////////////////////////////////////////////////////////////////
    … …  
    3535TIMING_DEFINE_PRINT(gcd_time);
    3636
    37 
    3837static inline CFFactor
    3938Powerup( const CFFactor & F , int exp=1){
    … …  
    6261  if (n==0){ // constant
    6362    if (R.inExtension()) // not in prime field; f over |F(q=p^k)
     63    {
    6464      R = power(R,Powerup(p,getGFDegree() - 1)) ;
     65    } 
    6566    // if f in prime field, do nothing
    6667    return R;
    … …  
    7172  for (int i=0; i<= (int) (degree(R,level(R))/p) ; i++)
    7273    RES += PthRoot( R[i*p] ) * power(x,i);
     74  return RES;
     75}
     76
     77///////////////////////////////////////////////////////////////
     78// Compute the Pth root of a polynomial in characteristic p  //
     79// f must be a polynomial which we can take the Pth root of. //
     80// Domain is q=p^m , f a uni/multivariate polynomial         //
     81///////////////////////////////////////////////////////////////
     82static CanonicalForm
     83PthRoot( const CanonicalForm & f ,const CanonicalForm & mipo){
     84  CanonicalForm RES, R = f;
     85  int n= max(level(R),getNumVars(R)), p= getCharacteristic();
     86  int mipodeg=-1;
     87  if (f.level()==mipo.level()) mipodeg=mipo.degree();
     88  else if ((f.level()==1) &&(mipo.level()!=-1000000))
     89  {
     90    Variable t;
     91    CanonicalForm tt=getMipo(mipo.mvar(),t);
     92    mipodeg=degree(tt,t);
     93  }
     94
     95  if ((n==0)
     96  ||(mipodeg!=-1))
     97  { // constant
     98    if (R.inExtension()) // not in prime field; f over |F(q=p^k)
     99    {
     100      R = power(R,Powerup(p,getGFDegree() - 1)) ;
     101    } 
     102    else if ((f.level()==mipo.level())
     103    ||((f.level()==1) &&(mipo.level()!=-1000000)))
     104    {
     105      R = power(R,Powerup(p,mipodeg - 1)) ;
     106      R=mod(R, mipo);
     107    }
     108    // if f in prime field, do nothing
     109    return R;
     110  }
     111  // we assume R is a Pth power here
     112  RES = R.genZero();
     113  Variable x(n);
     114  for (int i=0; i<= (int) (degree(R,level(R))/p) ; i++)
     115    RES += PthRoot( R[i*p], mipo ) * power(x,i);
    73116  return RES;
    74117}
    … …  
    150193///////////////////////////////////////////////////////////////
    151194static CFFList
    152 SqrFreed( const CanonicalForm & r ){
     195SqrFreed( const CanonicalForm & r , const CanonicalForm &mipo=0){
    153196  CanonicalForm h, g, f = r;
    154197  CFFList Outputlist;
    … …  
    165208// and continue computations with pp(f)
    166209  for (int k=1; k<=n; k++) {
    167     g = swapvar(f,k,n); g = content(g);
    168     if ( ! (g.isOne() || (-g).isOne() || degree(g)==0 )) {
    169       g = swapvar(g,k,n);
    170       DEBOUTLN(cout, "We have a content: ", g);
    171       Outputlist = myUnion(InternalSqrFree(g),Outputlist); // should we add a
     210    if ((mipo.level()==-1000000)||(k!=1))
     211    {
     212      g = swapvar(f,k,n); g = content(g);
     213      if ( ! (g.isOne() || (-g).isOne() || degree(g)==0 )) {
     214        g = swapvar(g,k,n);
     215        DEBOUTLN(cout, "We have a content: ", g);
     216        Outputlist = myUnion(InternalSqrFree(g,mipo),Outputlist); // should we add a
    172217                                                // SqrFreeTest(g) first ?
    173       DEBOUTLN(cout, "Outputlist is now: ", Outputlist);
    174       f /=g;
    175       DEBOUTLN(cout, "f is now: ", f);
    176     }
     218        DEBOUTLN(cout, "Outputlist is now: ", Outputlist);
     219        f /=g;
     220        DEBOUTLN(cout, "f is now: ", f);
     221      }
     222    } 
    177223  }
    178224
    … …  
    202248  g= f.deriv();
    203249  if ( getCharacteristic() > 0 && g.isZero() ){  // Pth roots only apply to char > 0
    204     for (int k=1; k<=n; k++) {
    205       g=swapvar(f,k,n) ; g = g.deriv();
    206       if ( ! g.isZero() ){ // can`t be Pth root
    207         CFFList Outputlist2= SqrFreed(swapvar(f,k,n));
    208         for (CFFListIterator inter=Outputlist2; inter.hasItem(); inter++){
    209           Outputlist= myappend(Outputlist, CFFactor(swapvar(inter.getItem().factor(),k,n), inter.getItem().exp()));
     250    for (int k=1; k<=n; k++)
     251    {
     252      if ((mipo.level()==-1000000)||(k!=1))
     253      {
     254        g=swapvar(f,k,n) ;
     255        g = g.deriv();
     256
     257        if ( ! g.isZero() )
     258        { // can`t be Pth root
     259          CFFList Outputlist2= SqrFreed(swapvar(f,k,n));
     260          for (CFFListIterator inter=Outputlist2; inter.hasItem(); inter++){
     261            Outputlist= myappend(Outputlist, CFFactor(swapvar(inter.getItem().factor(),k,n), inter.getItem().exp()));
     262          }
     263          return Outputlist;
    210264        }
    211         return Outputlist;
     265      }
     266      if ( k==n )
     267      { // really is Pth power
     268        DEBOUTLN(cout, "f is a p'th root: ", f);
     269        CFMap m;
     270        g = compress(f,m);
     271        if (mipo==0)
     272          f = m(PthRoot(g));
     273        else
     274          f = m(PthRoot(g,mipo));
     275        DEBOUTLN(cout, "  that is       : ", f);
     276        // now : Outputlist union ( SqrFreed(f) )^getCharacteristic()
     277        Outputlist=myUnion(Powerup(InternalSqrFree(f),getCharacteristic()),Outputlist);
     278        DEBDECLEVEL(cout, "SqrFreed");
     279        return Outputlist ;
    212280      }
    213       else
    214         if ( k==n ) { // really is Pth power
    215           DEBOUTLN(cout, "f is a p'th root: ", f);
    216           CFMap m;
    217           g = compress(f,m);
    218           f = m(PthRoot(g));
    219           DEBOUTLN(cout, "  that is       : ", f);
    220           // now : Outputlist union ( SqrFreed(f) )^getCharacteristic()
    221           Outputlist=myUnion(Powerup(InternalSqrFree(f),getCharacteristic()),Outputlist);
    222           DEBDECLEVEL(cout, "SqrFreed");
    223           return Outputlist ;
    224         }
    225281    }
    226282  }
    … …  
    247303    // For char > 0 the polys f and h can have Pth roots; so we need a test
    248304    // Test is disabled because timing is the same
     305   
    249306//    if ( SqrFreeTest(f,0) )
    250307//      Outputlist= myappend(Outputlist,CFFactor(f,1)) ;
    … …  
    276333///////////////////////////////////////////////////////////////
    277334CFFList
    278 InternalSqrFree( const CanonicalForm & r ){
     335InternalSqrFree( const CanonicalForm & r , const CanonicalForm & mipo ){
    279336  CanonicalForm g=icontent(r), f = r;
    280337  CFFList Outputlist, Outputlist2;
    … …  
    295352      f /= g;
    296353      if ( getNumVars(f) != 0 ) // a real polynomial
    297         Outputlist=myUnion(SqrFreed(f),Outputlist) ;
     354      {
     355        if (mipo!=0)
     356          Outputlist=myUnion(SqrFreed(f,mipo),Outputlist) ;
     357        else 
     358          Outputlist=myUnion(SqrFreed(f),Outputlist) ;
     359      }
    298360  }
    299361  DEBOUTLN(cout,"Outputlist = ", Outputlist);
    … …  
    341403/*
    342404$Log: not supported by cvs2svn $
     405Revision 1.7  2001/08/08 14:27:38  Singular
     406*hannes: Dan's HAVE_SINGULAR_ERROR
     407
    343408Revision 1.6  2001/08/08 14:26:56  Singular
    344409*hannes: Dan's HAVE_SINGULAR_ERROR

  • libfac/factor/SqrFree.h

    rb1476d0 r639047e  
    22////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 // $Id: SqrFree.h,v 1.3 1997-09-12 07:19:51 Singular Exp $
     4// $Id: SqrFree.h,v 1.4 2002-08-19 11:11:34 Singular Exp $
    55///////////////////////////////////////////////////////////////////////////////
    66#ifndef SQRFREE_H
    … …  
    1010// CFFList SqrFree( const CanonicalForm & f ) ;
    1111/*ENDPUBLIC*/
    12 CFFList InternalSqrFree( const CanonicalForm & f ) ;
     12CFFList InternalSqrFree( const CanonicalForm & f , const CanonicalForm & mipo=0) ;
    1313int     SqrFreeTest( const CanonicalForm & r, int opt=1) ;
    1414CFFList SqrFree( const CanonicalForm & f ) ;
    … …  
    1818/*
    1919$Log: not supported by cvs2svn $
     20Revision 1.3  1997/09/12 07:19:51  Singular
     21* hannes/michael: libfac-0.3.0
     22
    2023Revision 1.2  1997/04/25 22:13:03  michael
    2124Version for libfac-0.2.1

  • libfac/factor/homogfactor.cc

    rb1476d0 r639047e  
    11/* Copyright 1997 Michael Messollen. All rights reserved. */
    22////////////////////////////////////////////////////////////
    3 // static char * rcsid = "$Id: homogfactor.cc,v 1.3 1997-09-12 07:19:57 Singular Exp $ ";
     3// static char * rcsid = "$Id: homogfactor.cc,v 1.4 2002-08-19 11:11:34 Singular Exp $ ";
    44////////////////////////////////////////////////////////////
    55// FACTORY - Includes
    … …  
    111111// we assume g is square-free
    112112CFFList
    113 HomogFactor( const CanonicalForm & g, const Variable  & minpoly, const int Mainvar ){
     113HomogFactor( const CanonicalForm & g, const CanonicalForm  & minpoly, const int Mainvar ){
    114114  DEBINCLEVEL(cout, "HomogFactor");
    115115  Variable xn = get_max_degree_Variable(g);
    … …  
    154154/*
    155155$Log: not supported by cvs2svn $
     156Revision 1.3  1997/09/12 07:19:57  Singular
     157* hannes/michael: libfac-0.3.0
     158
    156159Revision 1.2  1997/04/25 22:35:20  michael
    157160changed cerr and cout messages for use with Singular

  • libfac/factor/homogfactor.h

    rb1476d0 r639047e  
    22///////////////////////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 // $Id: homogfactor.h,v 1.3 1997-09-12 07:19:58 Singular Exp $
     4// $Id: homogfactor.h,v 1.4 2002-08-19 11:11:34 Singular Exp $
    55///////////////////////////////////////////////////////////////////////////////
    66#ifndef HFACTOR_H
    … …  
    88CFList  get_Terms( const CanonicalForm & f );
    99bool    is_homogeneous( const CanonicalForm & f);
    10 CFFList HomogFactor( const CanonicalForm & g, const Variable  & minpoly, const int Mainvar );
     10CFFList HomogFactor( const CanonicalForm & g, const CanonicalForm  & minpoly, const int Mainvar );
    1111#endif /* HFACTOR_H */
    1212
    … …  
    1414/*
    1515$Log: not supported by cvs2svn $
     16Revision 1.3  1997/09/12 07:19:58  Singular
     17* hannes/michael: libfac-0.3.0
     18
    1619Revision 1.2  1997/04/25 22:14:46  michael
    1720Version for libfac-0.2.1
Note: See TracChangeset for help on using the changeset viewer.