cf_map.h File Reference

map polynomials More...

#include <iostream>
#include "variable.h"
#include "canonicalform.h"
#include "factory/templates/ftmpl_list.h"

Go to the source code of this file.

Data Structures
class	MapPair
	class MapPair More...
class	CFMap
	class CFMap More...

Macros
#define	OSTREAM   std::ostream

Typedefs
typedef List< MapPair >	MPList
typedef ListIterator< MapPair >	MPListIterator

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

map polynomials

Definition in file cf_map.h.

Macro Definition Documentation

OSTREAM

#define OSTREAM   std::ostream

Definition at line 18 of file cf_map.h.

Typedef Documentation

MPList

typedef List<MapPair> MPList

Definition at line 68 of file cf_map.h.

MPListIterator

typedef ListIterator<MapPair> MPListIterator

Definition at line 69 of file cf_map.h.

Function Documentation

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