Loading...
Searching...
No Matches
cf_map.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
/**
*
* @file cf_map.cc
*
* definition of class CFMap.
*
* Used by: cf_gcd.cc, fac_multivar.cc
*
**/
#include "config.h"
#include "canonicalform.h"
#include "cf_map.h"
#include "cf_iter.h"
#include "templates/ftmpl_functions.h"
/** MapPair & MapPair::operator = ( const MapPair & p )
*
* MapPair::operator = - assignment operator.
*
**/
MapPair &
MapPair::operator = ( const MapPair & p )
{
if ( this != &p ) {
V = p.V;
S = p.S;
}
return *this;
}
#ifndef NOSTREAMIO
/** OSTREAM & operator << ( OSTREAM & s, const MapPair & p )
*
* operator << - print a map pair ("V -> S").
*
**/
OSTREAM &
operator << ( OSTREAM & s, const MapPair & p )
{
s << p.var() << " -> " << p.subst();
return s;
}
void MapPair::print( OSTREAM&) const
{
}
#endif /* NOSTREAMIO */
/** CFMap::CFMap ( const CFList & L )
*
* CFMap::CFMap() - construct a CFMap from a CFList.
*
* Variable[i] will be mapped to CFList[i] under the resulting
* map.
*
**/
CFMap::CFMap ( const CFList & L )
{
CFListIterator i;
int j;
for ( i = L, j = 1; i.hasItem(); i++, j++ )
P.insert( MapPair( Variable(j), i.getItem() ) );
}
/** CFMap & CFMap::operator = ( const CFMap & m )
*
* CFMap::operator = - assignment operator.
*
**/
CFMap &
CFMap::operator = ( const CFMap & m )
{
if ( this != &m )
P = m.P;
return *this;
}
/** 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.
*
**/
static int
cmpfunc ( const MapPair & p1, const MapPair & p2 )
{
if ( p1.var() > p2.var() ) return -1;
else if ( p1.var() == p2.var() ) return 0;
else return 1;
}
/** 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().
*
**/
static void
insfunc ( MapPair & orgp, const MapPair & newp )
{
orgp = newp;
}
/** void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
*
* CFMap::newpair() - insert a MapPair into a CFMap.
*
**/
void
CFMap::newpair ( const Variable & v, const CanonicalForm & s )
{
P.insert( MapPair( v, s ), cmpfunc, insfunc );
}
/** 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 ()().
*
**/
static CanonicalForm
subsrec ( const CanonicalForm & f, const MPListIterator & i )
{
if ( f.inBaseDomain() ) return f;
MPListIterator j = i;
// skip MapPairs larger than the main variable of f
while ( j.hasItem() && j.getItem().var() > f.mvar() ) j++;
if ( j.hasItem() )
if ( j.getItem().var() != f.mvar() ) {
// simply descend if the current MapPair variable is
// not the main variable of f
CanonicalForm result = 0;
CFIterator I;
for ( I = f; I.hasTerms(); I++ )
result += power( f.mvar(), I.exp() ) * subsrec( I.coeff(), j );
return result;
}
else {
// replace the main variable of f with the image of
// the current variable under MapPair
CanonicalForm result = 0;
CanonicalForm s = j.getItem().subst();
CFIterator I;
// move on to the next MapPair
j++;
for ( I = f; I.hasTerms(); I++ )
result += subsrec( I.coeff(), j ) * power( s, I.exp() );
return result;
}
else
return f;
}
/** CanonicalForm CFMap::operator () ( const CanonicalForm & f ) const
*
* CFMap::operator () - apply CO to f.
*
* See subsrec() for more detailed information.
*
**/
CanonicalForm
CFMap::operator () ( const CanonicalForm & f ) const
{
MPListIterator i = P;
return subsrec( f, i );
}
#ifndef NOSTREAMIO
/** OSTREAM & operator << ( OSTREAM & s, const CFMap & m )
*
* operator << - print a CFMap ("( V[1] -> S[1], ..., V[n] -> * S[n] )".
*
**/
OSTREAM &
operator << ( OSTREAM & s, const CFMap & m )
{
m.P.print(s);
return s;
}
#endif /* NOSTREAMIO */
/** 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').
*
**/
CanonicalForm
compress ( const CanonicalForm & f, CFMap & m )
{
CanonicalForm result = f;
int i, n;
int * degs = degrees( f );
m = CFMap();
n = i = 1;
while ( i <= level( f ) ) {
while( degs[i] == 0 ) i++;
if ( i != n ) {
// swap variables and remember the swap in the map
m.newpair( Variable( n ), Variable( i ) );
result = swapvar( result, Variable( i ), Variable( n ) );
}
n++; i++;
}
DELETE_ARRAY(degs);
return result;
}
/** 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.
*
**/
void
compress ( const CFArray & a, CFMap & M, CFMap & N )
{
M = N = CFMap();
if ( a.size() == 0 )
return;
int maxlevel = level( a[a.min()] );
int i, j;
// get the maximum of levels in a
for ( i = a.min() + 1; i <= a.max(); i++ )
if ( level( a[i] ) > maxlevel )
maxlevel = level( a[i] );
if ( maxlevel <= 0 )
return;
int * degs = NEW_ARRAY(int,maxlevel+1);
int * tmp = NEW_ARRAY(int,maxlevel+1);
for ( i = maxlevel; i >= 1; i-- )
degs[i] = 0;
// calculate the union of all levels occuring in a
for ( i = a.min(); i <= a.max(); i++ )
{
tmp = degrees( a[i], tmp );
for ( j = 1; j <= level( a[i] ); j++ )
if ( tmp[j] != 0 )
degs[j] = 1;
}
// create the maps
i = 1; j = 1;
while ( i <= maxlevel )
{
if ( degs[i] != 0 )
{
M.newpair( Variable(i), Variable(j) );
N.newpair( Variable(j), Variable(i) );
j++;
}
i++;
}
DELETE_ARRAY(degs);
DELETE_ARRAY(tmp);
}
/*
* compute positions p1 and pe of optimal variables:
* pe is used in "ezgcd" and
* p1 in "gcd_poly1"
*/
static
void optvalues ( const int * df, const int * dg, const int n, int & p1, int &pe )
{
int i, o1, oe;
i = p1 = pe = 0;
do
{
i++;
if ( i > n ) return;
} while ( ( df[i] == 0 ) || ( dg[i] == 0 ) );
p1 = pe = i;
if ( df[i] > dg[i] )
{
o1 = df[i]; oe = dg[i];
}
else
{
o1 = dg[i]; oe = df[i];
}
while ( i < n )
{
i++;
if ( ( df[i] != 0 ) && ( dg[i] != 0 ) )
{
if ( df[i] > dg[i] )
{
if ( o1 >= df[i]) { o1 = df[i]; p1 = i; }
if ( oe < dg[i]) { oe = dg[i]; pe = i; }
}
else
{
if ( o1 >= dg[i]) { o1 = dg[i]; p1 = i; }
if ( oe < df[i]) { oe = df[i]; pe = i; }
}
}
}
}
/** 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.
*
**/
void
compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )
{
int n = tmax( f.level(), g.level() );
int i, k, p1, pe;
int * degsf = NEW_ARRAY(int,n+1);
int * degsg = NEW_ARRAY(int,n+1);
for ( i = 0; i <= n; i++ )
{
degsf[i] = degsg[i] = 0;
}
degsf = degrees( f, degsf );
degsg = degrees( g, degsg );
optvalues( degsf, degsg, n, p1, pe );
i = 1; k = 1;
if ( pe > 1 )
{
M.newpair( Variable(pe), Variable(k) );
N.newpair( Variable(k), Variable(pe) );
k++;
}
while ( i <= n )
{
if ( degsf[i] > 0 && degsg[i] > 0 )
{
if ( ( i != k ) && ( i != pe ) && ( i != p1 ) )
{
M.newpair( Variable(i), Variable(k) );
N.newpair( Variable(k), Variable(i) );
}
k++;
}
i++;
}
if ( p1 != pe )
{
M.newpair( Variable(p1), Variable(k) );
N.newpair( Variable(k), Variable(p1) );
k++;
}
i = 1;
while ( i <= n )
{
if ( degsf[i] > 0 && degsg[i] == 0 ) {
if ( i != k )
{
M.newpair( Variable(i), Variable(k) );
k++;
}
}
else if ( degsf[i] == 0 && degsg[i] > 0 )
{
if ( i != k )
{
M.newpair( Variable(i), Variable(k) );
k++;
}
}
i++;
}
DELETE_ARRAY(degsf);
DELETE_ARRAY(degsg);
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
canonicalform.h
Header for factory's main class CanonicalForm.
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
degsf
int * degsf
Definition cfEzgcd.cc:59
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
degsg
int * degsg
Definition cfEzgcd.cc:60
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
cf_iter.h
Iterators for CanonicalForm's.
subsrec
static CanonicalForm subsrec(const CanonicalForm &f, const MPListIterator &i)
static CanonicalForm subsrec ( const CanonicalForm & f, const MPListIterator & i )
Definition cf_map.cc:136
insfunc
static void insfunc(MapPair &orgp, const MapPair &newp)
static void insfunc ( MapPair & orgp, const MapPair & newp )
Definition cf_map.cc:109
operator<<
OSTREAM & operator<<(OSTREAM &s, const MapPair &p)
OSTREAM & operator << ( OSTREAM & s, const MapPair & p ).
Definition cf_map.cc:44
cmpfunc
static int cmpfunc(const MapPair &p1, const MapPair &p2)
static int cmpfunc ( const MapPair & p1, const MapPair & p2 )
Definition cf_map.cc:93
optvalues
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
Definition cf_map.cc:296
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
cf_map.h
map polynomials
MPListIterator
ListIterator< MapPair > MPListIterator
Definition cf_map.h:69
f
FILE * f
Definition checklibs.c:9
Array::size
int size() const
Definition ftmpl_array.cc:92
Array::max
int max() const
Definition ftmpl_array.cc:104
Array::min
int min() const
Definition ftmpl_array.cc:98
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFIterator::exp
CF_NO_INLINE int exp() const
get the current exponent
CFIterator::coeff
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CFIterator::hasTerms
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
CFMap
class CFMap
Definition cf_map.h:85
CFMap::operator()
CanonicalForm operator()(const CanonicalForm &f) const
CanonicalForm CFMap::operator () ( const CanonicalForm & f ) const.
Definition cf_map.cc:178
CFMap::newpair
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition cf_map.cc:120
CFMap::P
MPList P
Definition cf_map.h:87
CFMap::operator=
CFMap & operator=(const CFMap &m)
CFMap & CFMap::operator = ( const CFMap & m ).
Definition cf_map.cc:77
CFMap::CFMap
CFMap()
Definition cf_map.h:89
CanonicalForm
factory's main class
Definition canonicalform.h:86
MapPair
class MapPair
Definition cf_map.h:50
MapPair::var
Variable var() const
Definition cf_map.h:60
MapPair::S
CanonicalForm S
Definition cf_map.h:53
MapPair::print
void print(OSTREAM &) const
Definition cf_map.cc:50
MapPair::MapPair
MapPair(const Variable &v, const CanonicalForm &s)
Definition cf_map.h:55
MapPair::V
Variable V
Definition cf_map.h:52
MapPair::operator=
MapPair & operator=(const MapPair &p)
MapPair & MapPair::operator = ( const MapPair & p ).
Definition cf_map.cc:28
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
s
const CanonicalForm int s
Definition facAbsFact.cc:51
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
j
int j
Definition facHensel.cc:110
ftmpl_functions.h
some useful template functions.
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
OSTREAM
#define OSTREAM
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition factory.h:537
CFList
List< CanonicalForm > CFList
Definition factory.h:536
MPListIterator
ListIterator< MapPair > MPListIterator
Definition factory.h:987
M
#define M
Definition sirandom.c:25