My Project
Loading...
Searching...
No Matches
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

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

◆ cmpfunc()

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

◆ compress() [1/3]

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_ARRAY(degs);
228 return result;
229}
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level(const CanonicalForm &f)
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
FILE * f
Definition: checklibs.c:9
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
factory's class for variables
Definition: variable.h:33
return result
Definition: facAbsBiFact.cc:75

◆ compress() [2/3]

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 349 of file cf_map.cc.

350{
351 int n = tmax( f.level(), g.level() );
352 int i, k, p1, pe;
353 int * degsf = NEW_ARRAY(int,n+1);
354 int * degsg = NEW_ARRAY(int,n+1);
355
356 for ( i = 0; i <= n; i++ )
357 {
358 degsf[i] = degsg[i] = 0;
359 }
360
361 degsf = degrees( f, degsf );
362 degsg = degrees( g, degsg );
363 optvalues( degsf, degsg, n, p1, pe );
364
365 i = 1; k = 1;
366 if ( pe > 1 )
367 {
368 M.newpair( Variable(pe), Variable(k) );
369 N.newpair( Variable(k), Variable(pe) );
370 k++;
371 }
372 while ( i <= n )
373 {
374 if ( degsf[i] > 0 && degsg[i] > 0 )
375 {
376 if ( ( i != k ) && ( i != pe ) && ( i != p1 ) )
377 {
378 M.newpair( Variable(i), Variable(k) );
379 N.newpair( Variable(k), Variable(i) );
380 }
381 k++;
382 }
383 i++;
384 }
385 if ( p1 != pe )
386 {
387 M.newpair( Variable(p1), Variable(k) );
388 N.newpair( Variable(k), Variable(p1) );
389 k++;
390 }
391 i = 1;
392 while ( i <= n )
393 {
394 if ( degsf[i] > 0 && degsg[i] == 0 ) {
395 if ( i != k )
396 {
397 M.newpair( Variable(i), Variable(k) );
398 k++;
399 }
400 }
401 else if ( degsf[i] == 0 && degsg[i] > 0 )
402 {
403 if ( i != k )
404 {
405 M.newpair( Variable(i), Variable(k) );
406 k++;
407 }
408 }
409 i++;
410 }
411
414}
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int * degsf
Definition: cfEzgcd.cc:59
int k
Definition: cfEzgcd.cc:99
int * degsg
Definition: cfEzgcd.cc:60
g
Definition: cfModGcd.cc:4090
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
Definition: cf_map.cc:296
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
#define M
Definition: sirandom.c:25

◆ compress() [3/3]

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_ARRAY(int,maxlevel+1);
261 int * tmp = NEW_ARRAY(int,maxlevel+1);
262 for ( i = maxlevel; i >= 1; 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 {
268 tmp = degrees( a[i], tmp );
269 for ( j = 1; j <= level( a[i] ); j++ )
270 if ( tmp[j] != 0 )
271 degs[j] = 1;
272 }
273
274 // create the maps
275 i = 1; j = 1;
276 while ( i <= maxlevel )
277 {
278 if ( degs[i] != 0 )
279 {
280 M.newpair( Variable(i), Variable(j) );
281 N.newpair( Variable(j), Variable(i) );
282 j++;
283 }
284 i++;
285 }
286 DELETE_ARRAY(degs);
287 DELETE_ARRAY(tmp);
288}
int size() const
Definition: ftmpl_array.cc:92
int max() const
Definition: ftmpl_array.cc:104
int min() const
Definition: ftmpl_array.cc:98
int j
Definition: facHensel.cc:110

◆ insfunc()

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}

◆ optvalues()

static void optvalues ( const int *  df,
const int *  dg,
const int  n,
int &  p1,
int &  pe 
)
static

Definition at line 296 of file cf_map.cc.

297{
298 int i, o1, oe;
299 i = p1 = pe = 0;
300 do
301 {
302 i++;
303 if ( i > n ) return;
304 } while ( ( df[i] == 0 ) || ( dg[i] == 0 ) );
305 p1 = pe = i;
306 if ( df[i] > dg[i] )
307 {
308 o1 = df[i]; oe = dg[i];
309 }
310 else
311 {
312 o1 = dg[i]; oe = df[i];
313 }
314 while ( i < n )
315 {
316 i++;
317 if ( ( df[i] != 0 ) && ( dg[i] != 0 ) )
318 {
319 if ( df[i] > dg[i] )
320 {
321 if ( o1 >= df[i]) { o1 = df[i]; p1 = i; }
322 if ( oe < dg[i]) { oe = dg[i]; pe = i; }
323 }
324 else
325 {
326 if ( o1 >= dg[i]) { o1 = dg[i]; p1 = i; }
327 if ( oe < df[i]) { oe = df[i]; pe = i; }
328 }
329 }
330 }
331}

◆ subsrec()

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;
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
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
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
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CF_NO_INLINE int exp() const
get the current exponent
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
const CanonicalForm int s
Definition: facAbsFact.cc:51