source: git/factory/fac_sqrfree.cc @ ef9d6b

spielwiese
Last change on this file since ef9d6b was ef9d6b, checked in by Hans Schönemann <hannes@…>, 16 years ago
*hannes sqrFree git-svn-id: file:///usr/local/Singular/svn/trunk@10518 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 10.9 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id: fac_sqrfree.cc,v 1.8 2008-01-22 09:30:31 Singular Exp $ */
3
4#include <config.h>
5
6#include "assert.h"
7
8#include "cf_defs.h"
9#include "cf_map.h"
10#include "canonicalform.h"
11#include "fac_sqrfree.h"
12
13static int divexp = 1;
14
15static void divexpfunc ( CanonicalForm &, int & e )
16{
17    e /= divexp;
18}
19
20static int compareFactors( const CFFactor & f, const CFFactor & g )
21{
22    return f.exp() > g.exp();
23}
24
25CFFList sortCFFList( CFFList & F )
26{
27    F.sort( compareFactors );
28
29    int exp;
30    CanonicalForm f;
31    CFFListIterator I = F;
32    CFFList result;
33
34    // join elements with the same degree
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 ) );
46    }
47
48    return result;
49}
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); 
86    CanonicalForm t0 = f, t, v, w, h;
87    CanonicalForm leadcf = t0.lc();
88    Variable x = f.mvar();
89    CFFList F;
90    int p = getCharacteristic();
91    int k, e = 1;
92
93    if ( ! leadcf.isOne() )
94        t0 /= leadcf;
95
96    divexp = p;
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 ) );
128    }
129    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
343}
344
345bool isSqrFreeFp( const CanonicalForm & f )
346{
347  CFFList F = sqrFreeFp( f );
348  return ( F.length() == 1 && F.getFirst().exp() == 1 );
349}
350
351bool isSqrFreeZ ( const CanonicalForm & f )
352{
353    return gcd( f, f.deriv() ).degree() == 0;
354}
355
356/*
357
358CFFList sqrFreeZ ( const CanonicalForm & a )
359{
360    CanonicalForm b = a.deriv(), c = gcd( a, b );
361    CanonicalForm y, z, w = a / c;
362    int i = 1;
363    CFFList F;
364
365    while ( ! c.degree() == 0 ) {
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;
374    }
375    if ( degree( w ) > 0 )
376        if ( lc( w ).sign() < 0 )
377            F.append( CFFactor( -w, i ) );
378        else
379            F.append( CFFactor( w, i ) );
380    return F;
381}
382*/
383
384CFFList sqrFreeZ ( const CanonicalForm & a, const CanonicalForm & mipo )
385{
386    if ( a.inCoeffDomain() )
387        return CFFactor( a, 1 );
388    CanonicalForm cont = content( a );
389    CanonicalForm aa = a / cont;
390    CanonicalForm b = aa.deriv(), c = gcd( aa, b );
391    CanonicalForm y, z, w = aa / c;
392    int i = 1;
393    CFFList F;
394    Variable v = aa.mvar();
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;
405    }
406    if ( degree( w,v ) > 0 )
407        if ( lc( w ).sign() < 0 )
408            F.append( CFFactor( -w, i ) );
409        else
410            F.append( CFFactor( w, i ) );
411    if ( ! cont.isOne() )
412        F = Union( F, sqrFreeZ( cont ) );
413    if ( lc( a ).sign() < 0 ) {
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 ) );
421    }
422    return F;
423}
Note: See TracBrowser for help on using the repository browser.