Changeset 639047e in git


Ignore:
Timestamp:
Aug 19, 2002, 1:11:34 PM (22 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')
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
Files:
13 edited

Legend:

Unmodified
Added
Removed

  • libfac/charset/alg_factor.cc

    rb1476d0 r639047e  
    33// emacs edit mode for this file is -*- C++ -*-
    44////////////////////////////////////////////////////////////
    5 static char * rcsid = "$Id: alg_factor.cc,v 1.9 2002-07-30 15:16:19 Singular Exp $";
     5static char * rcsid = "$Id: alg_factor.cc,v 1.10 2002-08-19 11:11:29 Singular Exp $";
    66////////////////////////////////////////////////////////////
    77// FACTORY - Includes
    … …  
    1919// some CC's need this:
    2020#include "alg_factor.h"
     21
     22//void out_cf(char *s1,const CanonicalForm &f,char *s2);
    2123
    2224#ifdef ALGFACTORDEBUG
    … …  
    360362}
    361363
     364CanonicalForm alg_lc(const CanonicalForm &f)
     365{
     366  if (f.inCoeffDomain()) return f;
     367  if (f.level()>0)
     368  {
     369    return alg_lc(f.LC());
     370  }
     371} 
     372
    362373// the heart of the algorithm: the one from Trager
    363374static CFFList
    … …  
    369380  DEBINCLEVEL(cout,"alg_factor");
    370381  DEBOUTLN(cout, "alg_factor: f= ", f);
     382  //out_cf("start alg_factor:",f,"\n");
    371383  substlist= simpleextension(Astar, vminpoly, Rstar);
    372384  DEBOUTLN(cout, "alg_factor: substlist= ", substlist);
    … …  
    375387
    376388  sqrf_norm(f, Rstar, vminpoly, s, g, R );
     389  //out_cf("sqrf_norm R:",R,"\n");
     390  //out_cf("sqrf_norm s:",s,"\n");
     391  //out_cf("sqrf_norm g:",g,"\n");
    377392  DEBOUTLN(cout, "alg_factor: g= ", g);
    378393  DEBOUTLN(cout, "alg_factor: s= ", s);
    … …  
    429444        // undo linear transformation!!!! and then gcd!
    430445        //cout << "algcd(" << g << "," << fnew << ",as" << as << ")" << endl;
    431         h= algcd(g,fnew, as, oldord);
     446        //out_cf("algcd g=",g,"\n");
     447        //out_cf("algcd fnew=",fnew,"\n");
     448        //h= algcd(g,fnew, as, oldord);
     449        //if (as.length() >1)
     450        //  h= algcd(g,fnew, as, oldord);
     451        //else
     452          h=alg_gcd(g,fnew,as);
     453        //out_cf(" -> algcd=",algcd(g,fnew, as, oldord),"\n");
     454        //out_cf(" -> alg_gcd=",alg_gcd(g,fnew,as),"\n");
    432455        //cout << "algcd result:" << h << endl;
    433456        DEBOUTLN(cout, "  alg_factor: h= ", h);
    … …  
    446469    if (degree(g, f.mvar())>0){ L.append(CFFactor(g,1)); }
    447470  }
    448   DEBOUTLN(cout, "alg_factor: L= ", L);
     471  CFFList LL;
     472  if (getCharacteristic()>0)
     473  {
     474    CFFListIterator i=L;
     475    CanonicalForm c_fac=1;
     476    CanonicalForm c;
     477    for(;i.hasItem(); i++ )
     478    {
     479      CanonicalForm ff=i.getItem().factor();
     480      c=alg_lc(ff);
     481      int e=i.getItem().exp();
     482      ff/=c;
     483      if (!ff.isOne()) LL.append(CFFactor(ff,e));
     484      while (e>0) { c_fac*=c;e--; }
     485    }
     486    if (!c_fac.isOne()) LL.insert(CFFactor(c_fac,1));
     487  }
     488  else
     489  {
     490    LL=L;
     491  }
     492  //CFFListIterator i=LL;
     493  //for(;i.hasItem(); i++ )
     494  //  out_cf("end alg_f:",i.getItem().factor(),"\n");
     495  //printf("end alg_factor\n");
     496  DEBOUTLN(cout, "alg_factor: L= ", LL);
    449497  DEBDECLEVEL(cout,"alg_factor");
    450   return L;
     498  return LL;
    451499}
    452500
    … …  
    597645  // This is for now. we need alg_sqrfree implemented!
    598646  //cout << "algcd(" << f << "," << f.deriv() << " as:" << Astar <<endl;
    599   CanonicalForm Fgcd= algcd(f,f.deriv(),Astar,gcdord);
     647  //CanonicalForm Fgcd= algcd(f,f.deriv(),Astar,gcdord);
     648  CanonicalForm Fgcd;
     649        //if (Astar.length() >1)
     650        //  Fgcd= algcd(f,f.deriv(),Astar,gcdord);
     651        //else
     652          Fgcd= alg_gcd(f,f.deriv(),Astar);
     653        //out_cf("algcd:",algcd(f,f.deriv(),Astar,gcdord),"\n");
     654        //out_cf("alg_gcd:",alg_gcd(f,f.deriv(),Astar),"\n");
    600655 // cout << "algcd result:"  << Fgcd << endl;
    601656  if ( Fgcd == 0 ) DEBOUTMSG(cerr, "WARNING: p'th root ?");
    … …  
    683738/*
    684739$Log: not supported by cvs2svn $
     740Revision 1.9  2002/07/30 15:16:19  Singular
     741*hannes: fix for alg. extension
     742
    685743Revision 1.8  2001/08/06 08:32:53  Singular
    686744* hannes: code cleanup

  • libfac/charset/algfactor.cc

    rb1476d0 r639047e  
    33// emacs edit mode for this file is -*- C++ -*-
    44////////////////////////////////////////////////////////////
    5 static char * rcsid = "$Id: algfactor.cc,v 1.5 2001-06-27 13:58:05 Singular Exp $";
     5static char * rcsid = "$Id: algfactor.cc,v 1.6 2002-08-19 11:11:30 Singular Exp $";
    66////////////////////////////////////////////////////////////
    77// FACTORY - Includes
    … …  
    354354    DEBOUT(cout, ",", fp(substback,vf));
    355355    DEBOUT(cout, ") over K_r wrt ", vf);
    356     fp= algcd(g,fp(substback,vf), as, oldord);
     356    fp=alg_gcd(g,fp(substback,vf), as);
     357    //fp= algcd(g,fp(substback,vf), as, oldord);
    357358    DEBOUTLN(cout, " = ", fp);
    358359    if ( degree(fp,vf) > 0 ){ //otherwise it's a constant
    … …  
    372373    DEBOUT(cout, ",", fp(substback,vf));
    373374    DEBOUT(cout, ") over K_r wrt ", vf);
    374     fp= algcd(g,fp(substback,vf), as, oldord);
     375    fp= alg_gcd(g,fp(substback,vf), as);
     376    //fp= algcd(g,fp(substback,vf), as, oldord);
    375377    DEBOUTLN(cout, " = ", fp);
    376378    if ( degree(fp,vf) > 0 ){ //otherwise it's a constant
    … …  
    448450/*
    449451$Log: not supported by cvs2svn $
     452Revision 1.5  2001/06/27 13:58:05  Singular
     453*hannes/GP: debug newfactoras, char_series, ...
     454
    450455Revision 1.4  2001/06/21 14:57:04  Singular
    451456*hannes/GP: Factorize, newfactoras, ...

  • libfac/charset/algfactor.h

    rb1476d0 r639047e  
    33// emacs edit mode for this file is -*- C++ -*-
    44////////////////////////////////////////////////////////////
    5 // $Id: algfactor.h,v 1.2 1997-09-12 07:19:39 Singular Exp $
     5// $Id: algfactor.h,v 1.3 2002-08-19 11:11:30 Singular Exp $
    66////////////////////////////////////////////////////////////
    77
    … …  
    1616CFFList cfactor(const CanonicalForm & f, const CFList & as, int success );
    1717/*BEGINPUBLIC*/
     18int hasVar(const CanonicalForm &f, const Variable &v);
    1819/*ENDPUBLIC*/
    1920

  • libfac/charset/charset.cc

    rb1476d0 r639047e  
    22////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 static char * rcsid = "$Id: charset.cc,v 1.9 2001-08-08 14:26:54 Singular Exp $";
     4static char * rcsid = "$Id: charset.cc,v 1.10 2002-08-19 11:11:31 Singular Exp $";
    55/////////////////////////////////////////////////////////////
    66// FACTORY - Includes
    … …  
    540540    DEBOUT(cout, "irras: factoring: ", elem);
    541541    if ( degree(elem) > 1 ) // linear poly's are irreduzible
     542    {
    542543      qs = Factorize(elem);
     544    }
    543545    else{
    544546      qs=(CFFactor(elem,1));
    … …  
    581583            break;
    582584          }
    583           else
    584           {
    585 #ifdef HAVE_SINGULAR_ERROR
    586             WarnS("libfac: Factoring over algebraic function field required!");
    587 #else
    588 #ifndef NOSTREAMIO
    589             cerr << "libfac: Factoring over algebraic function field!" << endl;
    590 #endif
    591 #endif
    592           }
    593585        }
    594586      }
    … …  
    602594/*
    603595$Log: not supported by cvs2svn $
     596Revision 1.9  2001/08/08 14:26:54  Singular
     597*hannes: Dan's HAVE_SINGULAR_ERROR
     598
    604599Revision 1.8  2001/08/06 08:32:53  Singular
    605600* hannes: code cleanup

  • libfac/charset/csutil.cc

    rb1476d0 r639047e  
    22////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 static char * rcsid = "$Id: csutil.cc,v 1.6 2002-01-21 09:11:07 Singular Exp $";
     4static char * rcsid = "$Id: csutil.cc,v 1.7 2002-08-19 11:11:31 Singular Exp $";
    55/////////////////////////////////////////////////////////////
    66// FACTORY - Includes
    … …  
    1414// Charset - Includes
    1515#include "csutil.h"
     16//extern void out_cf(char *s1,const CanonicalForm &f,char *s2);
     17extern CanonicalForm alg_lc(const CanonicalForm &f);
     18extern int hasAlgVar(const CanonicalForm &f);
    1619
    1720static bool
    … …  
    651654}
    652655
     656#if 0
     657static CanonicalForm alg_lc(const CanonicalForm &f, const CFList as)
     658{
     659  for(CFListIterator i=as; i.hasItem(); i++)
     660  {
     661    if (f.mvar()==i.getItem().mvar()) return f;
     662  } 
     663  if (f.level()>0)
     664  {
     665    return alg_lc(f.LC(),as);
     666  }
     667  return CanonicalForm(1);
     668}
     669#endif
     670
     671CanonicalForm alg_gcd(const CanonicalForm & fff, const CanonicalForm &ggg,
     672                      const CFList &as)
     673{
     674  //out_cf("alg_gcd(",fff," , ");
     675  //out_cf("",ggg,")\n");
     676  CanonicalForm f=fff;
     677  CanonicalForm g=ggg;
     678  CanonicalForm res;
     679  // does as appear in f and g ?
     680  bool has_alg_var=false;
     681  for ( CFListIterator j=as;j.hasItem(); j++ )
     682  {
     683    Variable v=j.getItem().mvar();
     684    if (hasVar(f,v)) {has_alg_var=true; break;}
     685    if (hasVar(g,v)) {has_alg_var=true; break;}
     686  } 
     687  if (!has_alg_var)
     688  {
     689    if ((hasAlgVar(f))
     690    || (hasAlgVar(g)))
     691    {
     692      Varlist ord;
     693      for ( CFListIterator j=as;j.hasItem(); j++ )
     694        ord.append(j.getItem().mvar());
     695      res=algcd(f,g,as,ord);
     696    }
     697    else
     698      res=gcd(f,g);
     699    //out_cf("gcd=",res,"\n");
     700    return res;
     701  } 
     702
     703  int mvf=f.level();
     704  int mvg=g.level();
     705  if (mvg > mvf)
     706  {
     707    CanonicalForm tmp=f; f=g; g=tmp;
     708    int tmp2=mvf; mvf=mvg; mvg=tmp2;
     709  } 
     710  if (g.inBaseDomain() || f.inBaseDomain())
     711  {
     712    //printf("const\n");
     713    return CanonicalForm(1);
     714  } 
     715 
     716  // gcd of all coefficients:
     717  CFIterator i=f;
     718  CanonicalForm c_gcd=i.coeff(); i++;
     719  while( i.hasTerms())
     720  {
     721    c_gcd=alg_gcd(i.coeff(),c_gcd,as);
     722    if (c_gcd.inBaseDomain()) break;
     723    i++;
     724  }
     725  //printf("f.mvar=%d (%d), g.mvar=%d (%d)\n",f.level(),mvf,g.level(),mvg);
     726  if (mvf!=mvg) // => mvf > mvg
     727  {
     728    res=alg_gcd(g,c_gcd,as);
     729    //out_cf("alg_gcd1=",res,"\n");
     730    return res;
     731  }
     732  if (!c_gcd.inBaseDomain())
     733  {
     734    i=g;
     735    while( i.hasTerms())
     736    {
     737      c_gcd=alg_gcd(i.coeff(),c_gcd,as);
     738      if (c_gcd.inBaseDomain()) break;
     739      i++;
     740    }
     741  } 
     742
     743  f/=c_gcd;
     744  g/=c_gcd;
     745
     746  CanonicalForm r=1;
     747  CFList gg;
     748  while (!(r.isZero()))
     749  {
     750    //printf("f.mvar=%d, g.mvar=%d\n",f.level(),g.level());
     751    gg=as;
     752    gg.append(g);
     753    //out_cf("Prem(",f," , ");
     754    //out_cf("",g,")\n");
     755    if (g.inCoeffDomain()) r=0;
     756    else if (g.level()==f.level()) r=Prem(f,gg);
     757    else
     758    {
     759      // g and f have different levels
     760      return c_gcd;     
     761    }
     762    //out_cf("->",r,"\n");
     763    f=g;
     764    g=r;
     765  }
     766  if (degree(f,Variable(mvg))==0)
     767  {
     768  // remark: mvf == mvg == f.level() ==g.level()
     769    //out_cf("c_gcd=",c_gcd,"\n");
     770    return c_gcd;
     771  } 
     772  //out_cf("f=",f,"\n");
     773  i=f;
     774  CanonicalForm k=i.coeff(); i++;
     775  //out_cf("k=",k,"\n");
     776  while( i.hasTerms())
     777  {
     778    if (k.inCoeffDomain()) break;
     779    k=alg_gcd(i.coeff(),k,as);
     780    //out_cf("k=",k,"\n");
     781    i++;
     782  }
     783  f/=k;
     784  res=c_gcd*f;
     785  CanonicalForm r_lc=alg_lc(res);
     786  res/=r_lc;
     787  //CanonicalForm r_lc=alg_lc(res,as);
     788  //res/=r_lc;
     789  //out_cf("alg_gcd2=",res,"\n");
     790  return res;
     791}
     792
    653793/*
    654794$Log: not supported by cvs2svn $
     795Revision 1.6  2002/01/21 09:11:07  Singular
     796* hannes: handle empty set in removecontent
     797
    655798Revision 1.5  2001/06/21 14:57:04  Singular
    656799*hannes/GP: Factorize, newfactoras, ...

  • libfac/charset/csutil.h

    rb1476d0 r639047e  
    22////////////////////////////////////////////////////////////
    33// emacs edit mode for this file is -*- C++ -*-
    4 // $Id: csutil.h,v 1.3 1997-09-12 07:19:42 Singular Exp $
     4// $Id: csutil.h,v 1.4 2002-08-19 11:11:32 Singular Exp $
    55////////////////////////////////////////////////////////////
    66
    … …  
    99
    1010#include <factory.h>
     11#include "algfactor.h"
    1112#include <tmpl_inst.h>
    1213
    … …  
    5354CanonicalForm  Prem( const CanonicalForm &f, const CFList &L );
    5455CFList         Prem( const CFList &AS, const CFList &L );
     56CanonicalForm alg_gcd(const CanonicalForm &, const CanonicalForm &, const CFList &);
    5557/*ENDPUBLIC*/
    5658CanonicalForm  divide( const CanonicalForm & ff, const CanonicalForm & f, const CFList & as);
    … …  
    7981/*
    8082$Log: not supported by cvs2svn $
     83Revision 1.3  1997/09/12 07:19:42  Singular
     84* hannes/michael: libfac-0.3.0
     85
    8186Revision 1.3  1997/04/25 22:51:48  michael
    8287Version for libfac-0.2.1

  • libfac/factor.h

    rb1476d0 r639047e  
    1818//// Note: second argument for Factorize is for internal use only.
    1919CFFList Factorize( const CanonicalForm & F, int is_SqrFree=0 ) ;
    20 CFFList Factorize( const CanonicalForm & F, Variable mipo, int is_SqrFree=0 ) ;
     20CFFList Factorize( const CanonicalForm & F, const CanonicalForm & mipo, int is_SqrFree=0 ) ;
    2121CFFList newfactoras( const CanonicalForm & f, const CFList & as, int success);
    2222

  • 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.