Changeset ef9d6b in git


Ignore:
Timestamp:
Jan 22, 2008, 10:30:32 AM (15 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
Children:
35cfa3461f55f0fe3760bcefda25c627641368c7
Parents:
c6d3744af7f072c74673ab0aef31dfe80c1c9ae9
Message:
*hannes sqrFree


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

Legend:

Unmodified
Added
Removed

  • factory/cf_algorithm.h

    rc6d3744 ref9d6b  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_algorithm.h,v 1.16 2007-10-25 14:45:41 Singular Exp $ */
     2/* $Id: cf_algorithm.h,v 1.17 2008-01-22 09:30:31 Singular Exp $ */
    33
    44#ifndef INCL_CF_ALGORITHM_H
    … …  
    6464CFFList factorize ( const CanonicalForm & f, const Variable & alpha );
    6565
    66 CFFList sqrFree ( const CanonicalForm & f, bool sort = false );
     66CFFList sqrFree ( const CanonicalForm & f,  const CanonicalForm & mipo, bool sort=false );
    6767
    6868bool isSqrFree ( const CanonicalForm & f );

  • factory/fac_multivar.h

    rc6d3744 ref9d6b  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: fac_multivar.h,v 1.2 1997-06-19 12:23:22 schmidt Exp $ */
     2/* $Id: fac_multivar.h,v 1.3 2008-01-22 09:30:31 Singular Exp $ */
    33
    44#ifndef INCL_FAC_MULTIVAR_H
    … …  
    1010
    1111CFFList ZFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree );
     12CFFList FpFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree );
    1213
    1314#endif /* ! INCL_FAC_MULTIVAR_H */

  • factory/fac_sqrfree.cc

    rc6d3744 ref9d6b  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: fac_sqrfree.cc,v 1.7 1997-12-08 18:24:32 schmidt Exp $ */
     2/* $Id: fac_sqrfree.cc,v 1.8 2008-01-22 09:30:31 Singular Exp $ */
    33
    44#include <config.h>
    … …  
    77
    88#include "cf_defs.h"
     9#include "cf_map.h"
    910#include "canonicalform.h"
     11#include "fac_sqrfree.h"
    1012
    1113static int divexp = 1;
    … …  
    1618}
    1719
    18 static int
    19 compareFactors( const CFFactor & f, const CFFactor & g )
     20static int compareFactors( const CFFactor & f, const CFFactor & g )
    2021{
    2122    return f.exp() > g.exp();
    2223}
    2324
    24 CFFList
    25 sortCFFList( CFFList & F )
     25CFFList sortCFFList( CFFList & F )
    2626{
    2727    F.sort( compareFactors );
    … …  
    3333
    3434    // join elements with the same degree
    35     while ( I.hasItem() ) {
    36         f = I.getItem().factor();
    37         exp = I.getItem().exp();
    38         I++;
    39         while ( I.hasItem() && I.getItem().exp() == exp ) {
    40             f *= I.getItem().factor();
    41             I++;
    42         }
    43         result.append( CFFactor( f, exp ) );
     35    while ( I.hasItem() )
     36    {
     37        f = I.getItem().factor();
     38        exp = I.getItem().exp();
     39        I++;
     40        while ( I.hasItem() && I.getItem().exp() == exp )
     41        {
     42            f *= I.getItem().factor();
     43            I++;
     44        }
     45        result.append( CFFactor( f, exp ) );
    4446    }
    4547
    … …  
    4749}
    4850
    49 CFFList sqrFreeFp ( const CanonicalForm & f )
    50 {
     51CFFList appendCFFL( const CFFList & Inputlist, const CFFactor & TheFactor)
     52{
     53  CFFList Outputlist ;
     54  CFFactor copy;
     55  CFFListIterator i;
     56  int exp=0;
     57
     58  for ( i=Inputlist ; i.hasItem() ; i++ )
     59  {
     60    copy = i.getItem();
     61    if ( copy.factor() == TheFactor.factor() )
     62      exp += copy.exp();
     63    else
     64      Outputlist.append(copy);
     65  }
     66  Outputlist.append( CFFactor(TheFactor.factor(), exp + TheFactor.exp()));
     67  return Outputlist;
     68}
     69
     70CFFList UnionCFFL(const CFFList & Inputlist1,const CFFList & Inputlist2)
     71{
     72  CFFList Outputlist;
     73  CFFListIterator i;
     74
     75  for ( i=Inputlist1 ; i.hasItem() ; i++ )
     76    Outputlist = appendCFFL(Outputlist, i.getItem() );
     77  for ( i=Inputlist2 ; i.hasItem() ; i++ )
     78    Outputlist = appendCFFL(Outputlist, i.getItem() );
     79
     80  return Outputlist;
     81}
     82
     83CFFList sqrFreeFp_univ ( const CanonicalForm & f )
     84{
     85    if (getNumVars(f) == 0) return CFFactor(f,1);
    5186    CanonicalForm t0 = f, t, v, w, h;
    5287    CanonicalForm leadcf = t0.lc();
    … …  
    5792
    5893    if ( ! leadcf.isOne() )
    59         t0 /= leadcf;
     94        t0 /= leadcf;
    6095
    6196    divexp = p;
    62     while ( t0.degree(x) > 0 ) {
    63         t = gcd( t0, t0.deriv() );
    64         v = t0 / t;
    65         k = 0;
    66         while ( v.degree(x) > 0 ) {
    67             k = k+1;
    68             if ( k % p == 0 ) {
    69                 t /= v;
    70                 k = k+1;
    71             }
    72             w = gcd( t, v );
    73             h = v / w;
    74             v = w;
    75             t /= v;
    76             if ( h.degree(x) > 0 )
    77                 F.append( CFFactor( h/h.lc(), e*k ) );
    78         }
    79         t0 = apply( t, divexpfunc );
    80         e = p * e;
    81     }
    82     if ( ! leadcf.isOne() ) {
    83         if ( F.getFirst().exp() == 1 ) {
    84             leadcf = F.getFirst().factor() * leadcf;
    85             F.removeFirst();
    86         }
    87         F.insert( CFFactor( leadcf, 1 ) );
     97    while ( t0.degree(x) > 0 )
     98    {
     99        t = gcd( t0, t0.deriv() );
     100        v = t0 / t;
     101        k = 0;
     102        while ( v.degree(x) > 0 )
     103        {
     104            k = k+1;
     105            if ( k % p == 0 )
     106            {
     107                t /= v;
     108                k = k+1;
     109            }
     110            w = gcd( t, v );
     111            h = v / w;
     112            v = w;
     113            t /= v;
     114            if ( h.degree(x) > 0 )
     115                F.append( CFFactor( h/h.lc(), e*k ) );
     116        }
     117        t0 = apply( t, divexpfunc );
     118        e = p * e;
     119    }
     120    if ( ! leadcf.isOne() )
     121    {
     122        if ( F.getFirst().exp() == 1 )
     123        {
     124            leadcf = F.getFirst().factor() * leadcf;
     125            F.removeFirst();
     126        }
     127        F.insert( CFFactor( leadcf, 1 ) );
    88128    }
    89129    return F;
     130}
     131static inline CFFactor Powerup( const CFFactor & F , int exp=1)
     132{
     133  return CFFactor(F.factor(), exp*F.exp()) ;
     134}
     135
     136static CFFList Powerup( const CFFList & Inputlist , int exp=1 )
     137{
     138  CFFList Outputlist;
     139
     140  for ( CFFListIterator i=Inputlist; i.hasItem(); i++ )
     141    Outputlist.append(Powerup(i.getItem(), exp));
     142  return Outputlist ;
     143}
     144int Powerup( const int base , const int exp)
     145{
     146  int retvalue=1;
     147  if ( exp == 0 )  return retvalue ;
     148  else for ( int i=1 ; i <= exp; i++ ) retvalue *= base ;
     149   
     150  return retvalue;
     151}
     152
     153///////////////////////////////////////////////////////////////
     154// Compute the Pth root of a polynomial in characteristic p  //
     155// f must be a polynomial which we can take the Pth root of. //
     156// Domain is q=p^m , f a uni/multivariate polynomial         //
     157///////////////////////////////////////////////////////////////
     158static CanonicalForm PthRoot( const CanonicalForm & f )
     159{
     160  CanonicalForm RES, R = f;
     161  int n= getNumVars(R), p= getCharacteristic();
     162
     163  if (level(R)>n) n=level(R);
     164
     165  if (n==0)
     166  { // constant
     167    if (R.inExtension()) // not in prime field; f over |F(q=p^k)
     168    {
     169      R = power(R,Powerup(p,getGFDegree() - 1)) ;
     170    } 
     171    // if f in prime field, do nothing
     172    return R;
     173  }
     174  // we assume R is a Pth power here
     175  RES = R.genZero();
     176  Variable x(n);
     177  for (int i=0; i<= (int) (degree(R,level(R))/p) ; i++)
     178    RES += PthRoot( R[i*p] ) * power(x,i);
     179  return RES;
     180}
     181
     182///////////////////////////////////////////////////////////////
     183// Compute the Pth root of a polynomial in characteristic p  //
     184// f must be a polynomial which we can take the Pth root of. //
     185// Domain is q=p^m , f a uni/multivariate polynomial         //
     186///////////////////////////////////////////////////////////////
     187static CanonicalForm PthRoot( const CanonicalForm & f ,const CanonicalForm & mipo)
     188{
     189  CanonicalForm RES, R = f;
     190  int n= getNumVars(R), p= getCharacteristic();
     191  int mipodeg=-1;
     192
     193  if (level(R)>n) n=level(R);
     194
     195  if (f.level()==mipo.level()) mipodeg=mipo.degree();
     196  else if ((f.level()==1) &&(mipo.level()!=LEVELBASE))
     197  {
     198    Variable t;
     199    CanonicalForm tt=getMipo(mipo.mvar(),t);
     200    mipodeg=degree(tt,t);
     201  }
     202
     203  if ((n==0)
     204  ||(mipodeg!=-1))
     205  { // constant
     206    if (R.inExtension()) // not in prime field; f over |F(q=p^k)
     207    {
     208      R = power(R,Powerup(p,getGFDegree() - 1)) ;
     209    } 
     210    else if ((f.level()==mipo.level())
     211    ||((f.level()==1) &&(mipo.level()!=LEVELBASE)))
     212    {
     213      R = power(R,Powerup(p,mipodeg - 1)) ;
     214      R=mod(R, mipo);
     215    }
     216    // if f in prime field, do nothing
     217    return R;
     218  }
     219  // we assume R is a Pth power here
     220  RES = R.genZero();
     221  Variable x(n);
     222  for (int i=0; i<= (int) (degree(R,level(R))/p) ; i++)
     223    RES += PthRoot( R[i*p], mipo ) * power(x,i);
     224  return RES;
     225}
     226CFFList sqrFreeFp ( const CanonicalForm & r, const CanonicalForm &mipo )
     227{
     228///////////////////////////////////////////////////////////////
     229// A uni/multivariate SqrFree routine.Works for polynomials  //
     230// which don\'t have a constant as the content.              //
     231// Works for charcteristic 0 and q=p^m                       //
     232// returns a list of polys each of sqrfree, but gcd(f_i,f_j) //
     233// needs not to be 1 !!!!!                                   //
     234///////////////////////////////////////////////////////////////
     235  CanonicalForm h, g, f = r;
     236  CFFList Outputlist;
     237  int n = level(f);
     238
     239  if (getNumVars(f)==0 )
     240  { // just a constant; return it
     241    Outputlist= CFFactor(f,1);
     242    return Outputlist ;
     243  }
     244
     245// We look if we do have a content; if so, SqrFreed the content
     246// and continue computations with pp(f)
     247  for (int k=1; k<=n; k++)
     248  {
     249    if ((mipo.level()==LEVELBASE)||(k!=1))
     250    {
     251      g = swapvar(f,k,n); g = content(g);
     252      if ( ! (g.isOne() || (-g).isOne() || degree(g)==0 ))
     253      {
     254        g = swapvar(g,k,n);
     255        Outputlist = UnionCFFL(sqrFreeFp(g,mipo),Outputlist); // should we add a
     256                                                // SqrFreeTest(g) first ?
     257        f /=g;
     258      }
     259    } 
     260  }
     261
     262// Now f is primitive; Let`s look if f is univariate
     263  if ( f.isUnivariate() )
     264  {
     265    g = content(g);
     266    if ( ! (g.isOne() || (-g).isOne() ) )
     267    {
     268      Outputlist= appendCFFL(Outputlist,CFFactor(g,1)) ;
     269      f /= g;
     270    }
     271    Outputlist = Union(sqrFreeFp_univ(f),Outputlist) ;
     272    return Outputlist ;
     273  }
     274
     275// Linear?
     276  if ( totaldegree(f) <= 1 )
     277  {
     278    Outputlist= appendCFFL(Outputlist,CFFactor(f,1)) ;
     279    return Outputlist ;
     280  }
     281
     282// is it Pth root?
     283  n=level(f); // maybe less indeterminants
     284  g= f.deriv();
     285  if ( /*getCharacteristic() > 0 &&*/ g.isZero() )
     286  {  // Pth roots only apply to char > 0
     287    for (int k=1; k<=n; k++)
     288    {
     289      if ((mipo.level()==LEVELBASE)||(k!=1))
     290      {
     291        g=swapvar(f,k,n) ;
     292        g = g.deriv();
     293
     294        if ( ! g.isZero() )
     295        { // can`t be Pth root
     296          CFFList Outputlist2= sqrFreeFp(swapvar(f,k,n));
     297          for (CFFListIterator inter=Outputlist2; inter.hasItem(); inter++)
     298          {
     299            Outputlist=appendCFFL(Outputlist,
     300               CFFactor(swapvar(inter.getItem().factor(),k,n), inter.getItem().exp()));
     301          }
     302          return Outputlist;
     303        }
     304      }
     305      if ( k==n )
     306      { // really is Pth power
     307        CFMap m;
     308        g = compress(f,m);
     309        if (mipo.isZero())
     310          f = m(PthRoot(g));
     311        else
     312          f = m(PthRoot(g,mipo));
     313        // now : Outputlist union ( SqrFreed(f) )^getCharacteristic()
     314        Outputlist=UnionCFFL(Powerup(sqrFreeFp(f),getCharacteristic()),Outputlist);
     315        return Outputlist ;
     316      }
     317    }
     318  }
     319  g = f.deriv();
     320  h = gcd(f,pp(g));  h /= lc(h);
     321  if ( (h.isOne()) || ( h==f) || ((-h).isOne()) || getNumVars(h)==0 )
     322  { // no common factor
     323    Outputlist=appendCFFL(Outputlist,CFFactor(f,1)) ;
     324    return Outputlist ;
     325  }
     326  else  // we can split into two nontrivial pieces
     327  {
     328    f /= h; // Now we have split the poly into f and h
     329    g = lc(f);
     330    if ( (!g.isOne()) && getNumVars(g) == 0 )
     331    {
     332       Outputlist=appendCFFL(Outputlist,CFFactor(g,1)) ;
     333       f /= g;
     334    }
     335    // For char > 0 the polys f and h can have Pth roots; so we need a test
     336    // Test is disabled because timing is the same
     337   
     338    Outputlist=UnionCFFL(Outputlist, sqrFreeFp(f,mipo));
     339    Outputlist=UnionCFFL(Outputlist,sqrFreeFp(h,mipo));
     340    return Outputlist ;
     341  }
     342  return Outputlist; // for safety purpose
    90343}
    91344
    … …  
    111364
    112365    while ( ! c.degree() == 0 ) {
    113         y = gcd( w, c ); z = w / y;
    114         if ( degree( z ) > 0 )
    115             if ( lc( z ).sign() < 0 )
    116                 F.append( CFFactor( -z, i ) );
    117             else
    118                 F.append( CFFactor( z, i ) );
    119         i++;
    120         w = y; c = c / y;
     366        y = gcd( w, c ); z = w / y;
     367        if ( degree( z ) > 0 )
     368            if ( lc( z ).sign() < 0 )
     369                F.append( CFFactor( -z, i ) );
     370            else
     371                F.append( CFFactor( z, i ) );
     372        i++;
     373        w = y; c = c / y;
    121374    }
    122375    if ( degree( w ) > 0 )
    123         if ( lc( w ).sign() < 0 )
    124             F.append( CFFactor( -w, i ) );
    125         else
    126             F.append( CFFactor( w, i ) );
     376        if ( lc( w ).sign() < 0 )
     377            F.append( CFFactor( -w, i ) );
     378        else
     379            F.append( CFFactor( w, i ) );
    127380    return F;
    128381}
    129382*/
    130383
    131 CFFList sqrFreeZ ( const CanonicalForm & a )
     384CFFList sqrFreeZ ( const CanonicalForm & a, const CanonicalForm & mipo )
    132385{
    133386    if ( a.inCoeffDomain() )
    134         return CFFactor( a, 1 );
     387        return CFFactor( a, 1 );
    135388    CanonicalForm cont = content( a );
    136389    CanonicalForm aa = a / cont;
    … …  
    140393    CFFList F;
    141394    Variable v = aa.mvar();
    142     while ( ! c.degree(v) == 0 ) {
    143         y = gcd( w, c ); z = w / y;
    144         if ( degree( z, v ) > 0 )
    145             if ( lc( z ).sign() < 0 )
    146                 F.append( CFFactor( -z, i ) );
    147             else
    148                 F.append( CFFactor( z, i ) );
    149         i++;
    150         w = y; c = c / y;
     395    while ( ! c.degree(v) == 0 )
     396    {
     397        y = gcd( w, c ); z = w / y;
     398        if ( degree( z, v ) > 0 )
     399            if ( lc( z ).sign() < 0 )
     400                F.append( CFFactor( -z, i ) );
     401            else
     402                F.append( CFFactor( z, i ) );
     403        i++;
     404        w = y; c = c / y;
    151405    }
    152406    if ( degree( w,v ) > 0 )
    153         if ( lc( w ).sign() < 0 )
    154             F.append( CFFactor( -w, i ) );
    155         else
    156             F.append( CFFactor( w, i ) );
     407        if ( lc( w ).sign() < 0 )
     408            F.append( CFFactor( -w, i ) );
     409        else
     410            F.append( CFFactor( w, i ) );
    157411    if ( ! cont.isOne() )
    158         F = Union( F, sqrFreeZ( cont ) );
     412        F = Union( F, sqrFreeZ( cont ) );
    159413    if ( lc( a ).sign() < 0 ) {
    160         if ( F.getFirst().exp() == 1 ) {
    161             CanonicalForm f = F.getFirst().factor();
    162             CFFListIterator(F).getItem() = CFFactor( -f, 1 );
    163         }
    164         else
    165             F.insert( CFFactor( -1, 1 ) );
     414        if ( F.getFirst().exp() == 1 )
     415        {
     416            CanonicalForm f = F.getFirst().factor();
     417            CFFListIterator(F).getItem() = CFFactor( -f, 1 );
     418        }
     419        else
     420            F.insert( CFFactor( -1, 1 ) );
    166421    }
    167422    return F;

  • factory/fac_sqrfree.h

    rc6d3744 ref9d6b  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: fac_sqrfree.h,v 1.3 1997-06-19 12:23:18 schmidt Exp $ */
     2/* $Id: fac_sqrfree.h,v 1.4 2008-01-22 09:30:31 Singular Exp $ */
    33
    44#ifndef INCL_FAC_SQRFREE_H
    … …  
    99#include "canonicalform.h"
    1010
     11/*BEGINPUBLIC*/
     12
     13int Powerup( const int base , const int exp);
     14CFFList appendCFFL( const CFFList & Inputlist, const CFFactor & TheFactor);
     15CFFList UnionCFFL(const CFFList & Inputlist1,const CFFList & Inputlist2);
     16
     17
     18/*ENDPUBLIC*/
     19
    1120CFFList sortCFFList ( CFFList & F );
    1221
    13 CFFList sqrFreeFp ( const CanonicalForm & f );
     22//CFFList sqrFreeFp ( const CanonicalForm & f );
     23CFFList sqrFreeFp ( const CanonicalForm & r, const CanonicalForm &mipo=0 );
    1424
    1525bool isSqrFreeFp ( const CanonicalForm & f );
    1626
    17 CFFList sqrFreeZ ( const CanonicalForm & f );
     27CFFList sqrFreeZ ( const CanonicalForm & f, const CanonicalForm &mipo=0 );
    1828
    1929bool isSqrFreeZ ( const CanonicalForm & f );

  • factory/fac_univar.cc

    rc6d3744 ref9d6b  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: fac_univar.cc,v 1.19 1998-04-07 08:10:58 pohl Exp $ */
     2/* $Id: fac_univar.cc,v 1.20 2008-01-22 09:30:31 Singular Exp $ */
    33
    44#include <config.h>
    … …  
    389389        H.append( CFFactor( g, 1 ) );
    390390    else
    391         H = sqrFree( g );
     391        H = sqrFree( g, 0, false );
    392392
    393393    DEBOUTLN( cerr, "H = " << H );

  • factory/factory.template

    rc6d3744 ref9d6b  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: factory.template,v 1.18 2006-05-15 09:03:04 Singular Exp $ */
     2/* $Id: factory.template,v 1.19 2008-01-22 09:30:32 Singular Exp $ */
    33
    44#ifndef INCL_FACTORY_H
    … …  
    9999#include "cf_reval.h"
    100100
     101/*MAKEHEADER PUBLIC ONLY*/
     102#include "fac_sqrfree.h"
     103
    101104#ifdef SINGULAR
    102105
Note: See TracChangeset for help on using the changeset viewer.