Functions
cf_map.cc File Reference

definition of class CFMap. More...

#include "config.h"
#include "canonicalform.h"
#include "cf_map.h"
#include "cf_iter.h"
#include "templates/ftmpl_functions.h"

Go to the source code of this file.

Functions

OSTREAMoperator<< (OSTREAM &s, const MapPair &p)
 OSTREAM & operator << ( OSTREAM & s, const MapPair & p ) More...
 
static int cmpfunc (const MapPair &p1, const MapPair &p2)
 static int cmpfunc ( const MapPair & p1, const MapPair & p2 ) More...
 
static void insfunc (MapPair &orgp, const MapPair &newp)
 static void insfunc ( MapPair & orgp, const MapPair & newp ) More...
 
static CanonicalForm subsrec (const CanonicalForm &f, const MPListIterator &i)
 static CanonicalForm subsrec ( const CanonicalForm & f, const MPListIterator & i ) More...
 
OSTREAMoperator<< (OSTREAM &s, const CFMap &m)
 OSTREAM & operator << ( OSTREAM & s, const CFMap & m ) More...
 
CanonicalForm compress (const CanonicalForm &f, CFMap &m)
 CanonicalForm compress ( const CanonicalForm & f, CFMap & m ) More...
 
void compress (const CFArray &a, CFMap &M, CFMap &N)
 void compress ( const CFArray & a, CFMap & M, CFMap & N ) More...
 
static void optvalues (const int *df, const int *dg, const int n, int &p1, int &pe)
 
void compress (const CanonicalForm &f, const CanonicalForm &g, CFMap &M, CFMap &N)
 void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N ) More...
 

Detailed Description

definition of class CFMap.

Used by: cf_gcd.cc, fac_multivar.cc

Definition in file cf_map.cc.

Function Documentation

static int cmpfunc ( const MapPair p1,
const MapPair p2 
)
static

static int cmpfunc ( const MapPair & p1, const MapPair & p2 )

cmpfunc() - compare two map pairs.

Return -1 if p2's variable is less than p1's, 0 if they are equal, 1 if p2's level is greater than p1's.

Definition at line 93 of file cf_map.cc.

94 {
95  if ( p1.var() > p2.var() ) return -1;
96  else if ( p1.var() == p2.var() ) return 0;
97  else return 1;
98 }
Variable var() const
Definition: cf_map.h:60
CanonicalForm compress ( const CanonicalForm f,
CFMap m 
)

CanonicalForm compress ( const CanonicalForm & f, CFMap & m )

compress() - compress the canonical form f.

Compress the polynomial f such that the levels of its polynomial variables are ordered without any gaps starting from level 1. Return the compressed polynomial and a map m to undo the compression. That is, if f' = compress(f, m), than f = m(f').

Definition at line 210 of file cf_map.cc.

211 {
213  int i, n;
214  int * degs = degrees( f );
215 
216  m = CFMap();
217  n = i = 1;
218  while ( i <= level( f ) ) {
219  while( degs[i] == 0 ) i++;
220  if ( i != n ) {
221  // swap variables and remember the swap in the map
222  m.newpair( Variable( n ), Variable( i ) );
223  result = swapvar( result, Variable( i ), Variable( n ) );
224  }
225  n++; i++;
226  }
227  delete [] degs;
228  return result;
229 }
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: variable.h:32
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
class CFMap
Definition: cf_map.h:84
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition: cf_map.cc:120
return result
Definition: facAbsBiFact.cc:76
void compress ( const CFArray a,
CFMap M,
CFMap N 
)

void compress ( const CFArray & a, CFMap & M, CFMap & N )

compress() - compress the variables occuring in an a.

Compress the polynomial variables occuring in a so that their levels are ordered without any gaps starting from level 1. Return the CFMap M to realize the compression and its inverse, the CFMap N. Note that if you compress a member of a using M the result of the compression is not necessarily compressed, since the map is constructed using all variables occuring in a.

Definition at line 245 of file cf_map.cc.

246 {
247  M = N = CFMap();
248  if ( a.size() == 0 )
249  return;
250  int maxlevel = level( a[a.min()] );
251  int i, j;
252 
253  // get the maximum of levels in a
254  for ( i = a.min() + 1; i <= a.max(); i++ )
255  if ( level( a[i] ) > maxlevel )
256  maxlevel = level( a[i] );
257  if ( maxlevel <= 0 )
258  return;
259 
260  int * degs = new int[maxlevel+1];
261  int * tmp = new int[maxlevel+1];
262  for ( i = 1; i <= maxlevel; i++ )
263  degs[i] = 0;
264 
265  // calculate the union of all levels occuring in a
266  for ( i = a.min(); i <= a.max(); i++ ) {
267  tmp = degrees( a[i], tmp );
268  for ( j = 1; j <= level( a[i] ); j++ )
269  if ( tmp[j] != 0 )
270  degs[j] = 1;
271  }
272 
273  // create the maps
274  i = 1; j = 1;
275  while ( i <= maxlevel ) {
276  if ( degs[i] != 0 ) {
277  M.newpair( Variable(i), Variable(j) );
278  N.newpair( Variable(j), Variable(i) );
279  j++;
280  }
281  i++;
282  }
283  delete [] tmp;
284  delete [] degs;
285 }
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: variable.h:32
int size() const
Definition: ftmpl_array.cc:92
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
class CFMap
Definition: cf_map.h:84
int min() const
Definition: ftmpl_array.cc:98
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition: cf_map.cc:120
int max() const
Definition: ftmpl_array.cc:104
void compress ( const CanonicalForm f,
const CanonicalForm g,
CFMap M,
CFMap N 
)

void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )

compress() - compress the variables occurring in f and g with respect to optimal variables

Compress the polynomial variables occurring in f and g so that the levels of variables common to f and g are ordered without any gaps starting from level 1, whereas the variables occuring in only one of f or g are moved to levels higher than the levels of the common variables. Return the CFMap M to realize the compression and its inverse, the CFMap N. N needs only variables common to f and g.

Definition at line 346 of file cf_map.cc.

347 {
348  int n = tmax( f.level(), g.level() );
349  int i, k, p1, pe;
350  int * degsf = new int[n+1];
351  int * degsg = new int[n+1];
352 
353  for ( i = 0; i <= n; i++ )
354  {
355  degsf[i] = degsg[i] = 0;
356  }
357 
358  degsf = degrees( f, degsf );
359  degsg = degrees( g, degsg );
360  optvalues( degsf, degsg, n, p1, pe );
361 
362  i = 1; k = 1;
363  if ( pe > 1 )
364  {
365  M.newpair( Variable(pe), Variable(k) );
366  N.newpair( Variable(k), Variable(pe) );
367  k++;
368  }
369  while ( i <= n )
370  {
371  if ( degsf[i] > 0 && degsg[i] > 0 )
372  {
373  if ( ( i != k ) && ( i != pe ) && ( i != p1 ) )
374  {
375  M.newpair( Variable(i), Variable(k) );
376  N.newpair( Variable(k), Variable(i) );
377  }
378  k++;
379  }
380  i++;
381  }
382  if ( p1 != pe )
383  {
384  M.newpair( Variable(p1), Variable(k) );
385  N.newpair( Variable(k), Variable(p1) );
386  k++;
387  }
388  i = 1;
389  while ( i <= n )
390  {
391  if ( degsf[i] > 0 && degsg[i] == 0 ) {
392  if ( i != k )
393  {
394  M.newpair( Variable(i), Variable(k) );
395  k++;
396  }
397  }
398  else if ( degsf[i] == 0 && degsg[i] > 0 )
399  {
400  if ( i != k )
401  {
402  M.newpair( Variable(i), Variable(k) );
403  k++;
404  }
405  }
406  i++;
407  }
408 
409  delete [] degsf;
410  delete [] degsg;
411 }
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: variable.h:32
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
int * degsg
Definition: cfEzgcd.cc:54
int k
Definition: cfEzgcd.cc:93
int level() const
level() returns the level of CO.
int i
Definition: cfEzgcd.cc:123
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
Definition: cf_map.cc:293
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition: cf_map.cc:120
int * degsf
Definition: cfEzgcd.cc:53
static void insfunc ( MapPair orgp,
const MapPair newp 
)
static

static void insfunc ( MapPair & orgp, const MapPair & newp )

insfunc() - assign newp to orgp.

cmpfunc() and insfunc() are used as functions for inserting a map pair into a map by CFMap::newpair().

Definition at line 109 of file cf_map.cc.

110 {
111  orgp = newp;
112 }
OSTREAM& operator<< ( OSTREAM s,
const MapPair p 
)

OSTREAM & operator << ( OSTREAM & s, const MapPair & p )

operator << - print a map pair ("V -> S").

Definition at line 44 of file cf_map.cc.

45 {
46  s << p.var() << " -> " << p.subst();
47  return s;
48 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
Variable var() const
Definition: cf_map.h:60
CanonicalForm subst() const
Definition: cf_map.h:61
OSTREAM& operator<< ( OSTREAM s,
const CFMap m 
)

OSTREAM & operator << ( OSTREAM & s, const CFMap & m )

operator << - print a CFMap ("( V[1] -> S[1], ..., V[n] -> * S[n] )".

Definition at line 191 of file cf_map.cc.

192 {
193  m.P.print(s);
194  return s;
195 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
MPList P
Definition: cf_map.h:87
void print(OSTREAM &) const
Definition: ftmpl_list.cc:366
static void optvalues ( const int *  df,
const int *  dg,
const int  n,
int &  p1,
int &  pe 
)
static

Definition at line 293 of file cf_map.cc.

294 {
295  int i, o1, oe;
296  i = p1 = pe = 0;
297  do
298  {
299  i++;
300  if ( i > n ) return;
301  } while ( ( df[i] == 0 ) || ( dg[i] == 0 ) );
302  p1 = pe = i;
303  if ( df[i] > dg[i] )
304  {
305  o1 = df[i]; oe = dg[i];
306  }
307  else
308  {
309  o1 = dg[i]; oe = df[i];
310  }
311  while ( i < n )
312  {
313  i++;
314  if ( ( df[i] != 0 ) && ( dg[i] != 0 ) )
315  {
316  if ( df[i] > dg[i] )
317  {
318  if ( o1 >= df[i]) { o1 = df[i]; p1 = i; }
319  if ( oe < dg[i]) { oe = dg[i]; pe = i; }
320  }
321  else
322  {
323  if ( o1 >= dg[i]) { o1 = dg[i]; p1 = i; }
324  if ( oe < df[i]) { oe = df[i]; pe = i; }
325  }
326  }
327  }
328 }
int i
Definition: cfEzgcd.cc:123
static CanonicalForm subsrec ( const CanonicalForm f,
const MPListIterator i 
)
static

static CanonicalForm subsrec ( const CanonicalForm & f, const MPListIterator & i )

subsrec() - recursively apply the substitutions in i to f.

Substitutes algebraic variables, too. The substituted expression are not subject to further substitutions.

Used by: CFMap::operator ()().

Definition at line 136 of file cf_map.cc.

137 {
138  if ( f.inBaseDomain() ) return f;
139  MPListIterator j = i;
140 
141  // skip MapPairs larger than the main variable of f
142  while ( j.hasItem() && j.getItem().var() > f.mvar() ) j++;
143 
144  if ( j.hasItem() )
145  if ( j.getItem().var() != f.mvar() ) {
146  // simply descend if the current MapPair variable is
147  // not the main variable of f
148  CanonicalForm result = 0;
149  CFIterator I;
150  for ( I = f; I.hasTerms(); I++ )
151  result += power( f.mvar(), I.exp() ) * subsrec( I.coeff(), j );
152  return result;
153  }
154  else {
155  // replace the main variable of f with the image of
156  // the current variable under MapPair
157  CanonicalForm result = 0;
158  CanonicalForm s = j.getItem().subst();
159  CFIterator I;
160  // move on to the next MapPair
161  j++;
162  for ( I = f; I.hasTerms(); I++ )
163  result += subsrec( I.coeff(), j ) * power( s, I.exp() );
164  return result;
165  }
166  else
167  return f;
168 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
static CanonicalForm subsrec(const CanonicalForm &f, const MPListIterator &i)
static CanonicalForm subsrec ( const CanonicalForm & f, const MPListIterator & i ) ...
Definition: cf_map.cc:136
const CanonicalForm int s
Definition: facAbsFact.cc:55
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
factory&#39;s main class
Definition: canonicalform.h:75
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int j
Definition: myNF.cc:70
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int exp() const
get the current exponent
T & getItem() const
Definition: ftmpl_list.cc:431
bool inBaseDomain() const
return result
Definition: facAbsBiFact.cc:76