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.

{
    if ( p1.var() > p2.var() ) return -1;
    else if ( p1.var() == p2.var() ) return 0;
    else return 1;
}

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.

{
    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;
}

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.

{
    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);
}

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.

{
    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);
}

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.

{
    orgp = newp;
}

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.

{
    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; }
            }
        }
    }
}

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.

{
    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;
}