Loading...
Searching...
No Matches
fglmcomb.cc File Reference
`#include "kernel/mod2.h"`
`#include "factory/factory.h"`
`#include "misc/options.h"`
`#include "kernel/polys.h"`
`#include "kernel/ideals.h"`
`#include "polys/monomials/ring.h"`
`#include "polys/monomials/maps.h"`
`#include "fglmvec.h"`
`#include "fglmgauss.h"`
`#include "kernel/GBEngine/kstd1.h"`
`#include "fglm.h"`
`#include <iostream>`

Go to the source code of this file.

## Functions

static void | fglmEliminateMonomials (poly *pptr, fglmVector &v, polyset monomials, int numMonoms)
static BOOLEAN | fglmReductionStep (poly *pptr, ideal source, int *w)
static void | fglmReduce (poly *pptr, fglmVector &v, polyset m, int numMonoms, ideal source, int *w)
poly | fglmNewLinearCombination (ideal source, poly monset)
poly | fglmLinearCombination (ideal source, poly monset)

## Function Documentation

## fglmEliminateMonomials()

void fglmEliminateMonomials | ( | poly * | pptr,
|  | fglmVector & | v,
|  | polyset | monomials,
|  | int | numMonoms )

static

Definition at line 36 of file fglmcomb.cc.

{
poly temp = *pptr;
poly pretemp = NULL;
int point = 0;
int state;
while ( (temp != NULL) && (point < numMonoms) ) {
state= pCmp( temp, monomials[point] );
if ( state == 0 ) {
// Eliminate this monomial
poly todelete;
if ( pretemp == NULL ) {
todelete = temp;
pIter( *pptr );
temp= *pptr;
}
else {
todelete= temp;
pIter( temp );
pretemp->next= temp;
}
pGetCoeff( todelete )= nInpNeg( pGetCoeff( todelete ) );
number newelem = nAdd( pGetCoeff( todelete ), v.getconstelem( point+1 ) );
v.setelem( point+1, newelem );
nDelete( & pGetCoeff( todelete ) );
pLmFree( todelete );
point++;
}
else if ( state < 0 )
point++;
else {
pretemp= temp;
pIter( temp );
}
}
}
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
pIter
#define pIter(p)
Definition monomials.h:37
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition monomials.h:44
nDelete
#define nDelete(n)
Definition numbers.h:16
nInpNeg
#define nInpNeg(n)
Definition numbers.h:21
nAdd
#define nAdd(n1, n2)
Definition numbers.h:18
NULL
#define NULL
Definition omList.c:12
pCmp
#define pCmp(p1, p2)
pCmp: args may be NULL returns: (p2==NULL ? 1 : (p1 == NULL ? -1 : p_LmCmp(p1, p2)))
Definition polys.h:116
pLmFree
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition polys.h:71

## fglmLinearCombination()

poly fglmLinearCombination | ( | ideal | source,
|  | poly | monset )

Definition at line 415 of file fglmcomb.cc.

{
int k;
poly temp;
polyset m;
polyset nf;
fglmVector * v;
polyset basis;
int basisSize = 0;
int basisBS = 16;
int basisMax;
// get number of monomials in monset
int numMonoms = 0;
temp = monset;
while ( temp != NULL ) {
numMonoms++;
pIter( temp );
}
// Allocate Memory
m= (polyset)omAlloc( numMonoms * sizeof( poly ) );
nf= (polyset)omAlloc( numMonoms * sizeof( poly ) );
// Warning: The fglmVectors in v are yet not initialized
v= (fglmVector *)omAlloc( numMonoms * sizeof( fglmVector ) );
basisMax= basisBS;
basis= (polyset)omAlloc( basisMax * sizeof( poly ) );
// get the NormalForm and the basis monomials
temp= monset;
for ( k= 0; k < numMonoms; k++ ) {
poly mon= pHead( temp );
if ( ! nIsOne( pGetCoeff( mon ) ) ) {
nDelete( & pGetCoeff( mon ) );
pSetCoeff( mon, nInit( 1 ) );
}
STICKYPROT( "(" );
nf[k]= kNF( source, currRing->qideal, mon );
STICKYPROT( ")" );
// search through basis
STICKYPROT( "[" );
poly sm = nf[k];
while ( sm != NULL ) {
BOOLEAN found = FALSE;
int b;
for ( b= 0; (b < basisSize) && (found == FALSE); b++ )
if ( pLmEqual( sm, basis[b] ) ) found= TRUE;
if ( found == FALSE ) {
// Expand the basis
if ( basisSize == basisMax ) {
basis= (polyset)omReallocSize( basis, basisMax * sizeof( poly ), (basisMax + basisBS ) * sizeof( poly ) );
basisMax+= basisBS;
}
basis[basisSize]= pHead( sm );
nDelete( & pGetCoeff( basis[basisSize] ) );
pSetCoeff( basis[basisSize], nInit( 1 ) );
basisSize++;
}
pIter( sm );
}
STICKYPROT( "]" );
m[k]= mon;
pIter( temp );
}
// get the vector representation
STICKYPROT2( "(%i)", basisSize );
for ( k= 0; k < numMonoms; k++ ) {
#ifndef HAVE_EXPLICIT_CONSTR
v[k].mac_constr_i( basisSize );
#else
v[k].fglmVector( basisSize );
#endif
STICKYPROT( "(+" );
poly mon= nf[k];
while ( mon != NULL ) {
BOOLEAN found = FALSE;
int b= 0;
while ( found == FALSE ) {
if ( pLmEqual( mon, basis[b] ) )
found= TRUE;
else
b++;
}
number coeff = nCopy( pGetCoeff( mon ) );
v[k].setelem( b+1, coeff );
pIter( mon );
}
STICKYPROT( ")" );
}
// gauss reduce
gaussReducer gauss( basisSize );
BOOLEAN isZero = FALSE;
fglmVector p;
for ( k= 0; (k < numMonoms) && (isZero == FALSE); k++ ) {
STICKYPROT( "(-" );
if ( ( isZero= gauss.reduce( v[k] )) == TRUE )
p= gauss.getDependence();
else
gauss.store();
STICKYPROT( ")" );
}
poly comb = NULL;
if ( isZero == TRUE ) {
number gcd = p.gcd();
if ( ! nIsZero( gcd ) && ! ( nIsOne( gcd ) ) )
p/= gcd;
nDelete( & gcd );
for ( k= 1; k <= p.size(); k++ ) {
if ( ! p.elemIsZero( k ) ) {
poly temp = pCopy( m[k-1] );
pSetCoeff( temp, nCopy( p.getconstelem( k ) ) );
comb= pAdd( comb, temp );
}
}
if ( ! nGreaterZero( pGetCoeff( comb ) ) ) comb= pNeg( comb );
}
// Free Memory
for ( k= 0; k < numMonoms; k++ ) {
pDelete( m + k );
pDelete( nf + k );
}
omFreeSize( (ADDRESS)m, numMonoms * sizeof( poly ) );
omFreeSize( (ADDRESS)nf, numMonoms * sizeof( poly ) );
// Warning: At this point all Vectors in v have to be initialized
for ( k= numMonoms - 1; k >= 0; k-- ) v[k].~fglmVector();
omFreeSize( (ADDRESS)v, numMonoms * sizeof( fglmVector ) );
for ( k= 0; k < basisSize; k++ )
pDelete( basis + k );
omFreeSize( (ADDRESS)basis, basisMax * sizeof( poly ) );
STICKYPROT( "\n" );
return comb;
}
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
ADDRESS
void * ADDRESS
Definition auxiliary.h:120
m
int m
Definition cfEzgcd.cc:128
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
b
CanonicalForm b
Definition cfModGcd.cc:4111
fglmVector
Definition fglmvec.h:19
gaussReducer
Definition fglmgauss.h:19
found
bool found
Definition facFactorize.cc:55
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468
STICKYPROT2
#define STICKYPROT2(msg, arg)
Definition fglm.h:22
STICKYPROT
#define STICKYPROT(msg)
Definition fglm.h:20
kNF
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3229
nIsZero
#define nIsZero(n)
Definition numbers.h:19
nCopy
#define nCopy(n)
Definition numbers.h:15
nGreaterZero
#define nGreaterZero(n)
Definition numbers.h:27
nIsOne
#define nIsOne(n)
Definition numbers.h:25
nInit
#define nInit(i)
Definition numbers.h:24
omFreeSize
#define omFreeSize(addr, size)
Definition omAllocDecl.h:260
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omReallocSize
#define omReallocSize(addr, o_size, size)
Definition omAllocDecl.h:220
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
pAdd
#define pAdd(p, q)
Definition polys.h:204
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pHead
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:68
pNeg
#define pNeg(p)
Definition polys.h:199
pLmEqual
#define pLmEqual(p1, p2)
Definition polys.h:112
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition polys.h:32
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
polyset
poly * polyset
Definition polys.h:260
nf
Definition gnumpfl.cc:25
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## fglmNewLinearCombination()

poly fglmNewLinearCombination | ( | ideal | source,
|  | poly | monset )

Definition at line 153 of file fglmcomb.cc.

{
polyset m = NULL;
polyset nf = NULL;
fglmVector * mv = NULL;
fglmVector * v = NULL;
polyset basis = NULL;
int basisSize = 0;
int basisBS = 16;
int basisMax = basisBS;
int * weights = NULL;
int * lengths = NULL;
int * order = NULL;
int numMonoms = 0;
int k;
// get number of monoms
numMonoms= pLength( monset );
STICKYPROT2( "%i monoms\n", numMonoms );
// Allocate Memory and initialize sets
m= (polyset)omAlloc( numMonoms * sizeof( poly ) );
poly temp= monset;
for ( k= 0; k < numMonoms; k++ ) {
// m[k]= pOne();
// pSetExpV( m[k], temp->exp );
// pSetm( m[k] );
m[k]=pLmInit(temp);
pSetCoeff( m[k], nInit(1) );
pIter( temp );
}
nf= (polyset)omAlloc( numMonoms * sizeof( poly ) );
#ifndef HAVE_EXPLICIT_CONSTR
mv= new fglmVector[ numMonoms ];
#else
mv= (fglmVector *)omAlloc( numMonoms * sizeof( fglmVector ) );
#endif
#ifndef HAVE_EXPLICIT_CONSTR
v= new fglmVector[ numMonoms ];
#else
v= (fglmVector *)omAlloc( numMonoms * sizeof( fglmVector ) );
#endif
basisMax= basisBS;
basis= (polyset)omAlloc( basisMax * sizeof( poly ) );
weights= (int *)omAlloc( IDELEMS( source ) * sizeof( int ) );
STICKYPROT( "weights: " );
for ( k= 0; k < IDELEMS( source ); k++ ) {
poly temp= (source->m)[k];
int w = 0;
while ( temp != NULL ) {
w+= nSize( pGetCoeff( temp ) );
pIter( temp );
}
weights[k]= w;
STICKYPROT2( "%i ", w );
}
STICKYPROT( "\n" );
lengths= (int *)omAlloc( numMonoms * sizeof( int ) );
order= (int *)omAlloc( numMonoms * sizeof( int ) );
// calculate the NormalForm in a special way
for ( k= 0; k < numMonoms; k++ )
{
STICKYPROT( "#" );
poly current = pCopy( m[k] );
fglmVector currV( numMonoms, k+1 );
fglmReduce( & current, currV, m, numMonoms, source, weights );
poly temp = current;
int b;
while ( temp != NULL )
{
BOOLEAN found = FALSE;
for ( b= 0; (b < basisSize) && (found == FALSE); b++ )
{
if ( pLmEqual( temp, basis[b] ) )
{
found= TRUE;
}
}
if ( found == FALSE )
{
if ( basisSize == basisMax )
{
// Expand the basis
basis= (polyset)omReallocSize( basis, basisMax * sizeof( poly ), (basisMax + basisBS ) * sizeof( poly ) );
basisMax+= basisBS;
}
// basis[basisSize]= pOne();
// pSetExpV( basis[basisSize], temp->exp );
// pSetm( basis[basisSize] );
basis[basisSize]=pLmInit(temp);
pSetCoeff( basis[basisSize], nInit(1) );
basisSize++;
}
pIter( temp );
}
nf[k]= current;
#ifndef HAVE_EXPLICIT_CONSTR
mv[k].mac_constr( currV );
#else
mv[k].fglmVector( currV );
#endif
STICKYPROT( "\n" );
}
// get the vector representation
for ( k= 0; k < numMonoms; k++ ) {
STICKYPROT( "." );
#ifndef HAVE_EXPLICIT_CONSTR
v[k].mac_constr_i( basisSize );
#else
v[k].fglmVector( basisSize );
#endif
poly mon= nf[k];
while ( mon != NULL ) {
BOOLEAN found = FALSE;
int b= 0;
while ( found == FALSE ) {
if ( pLmEqual( mon, basis[b] ) ) {
found= TRUE;
}
else {
b++;
}
}
number coeff = nCopy( pGetCoeff( mon ) );
v[k].setelem( b+1, coeff );
pIter( mon );
}
pDelete( nf + k );
}
// Free Memory not needed anymore
omFreeSize( (ADDRESS)nf, numMonoms * sizeof( poly ) );
omFreeSize( (ADDRESS)weights, IDELEMS( source ) * sizeof( int ) );
STICKYPROT2( "\nbasis size: %i\n", basisSize );
STICKYPROT( "(clear basis" );
for ( k= 0; k < basisSize; k++ )
pDelete( basis + k );
STICKYPROT( ")\n" );
// gauss reduce
gaussReducer gauss( basisSize );
BOOLEAN isZero = FALSE;
fglmVector p;
STICKYPROT( "sizes: " );
for ( k= 0; k < numMonoms; k++ ) {
lengths[k]= v[k].numNonZeroElems();
STICKYPROT2( "%i ", lengths[k] );
}
STICKYPROT( "\n" );
int act = 0;
while ( (isZero == FALSE) && (act < numMonoms) ) {
int best = 0;
for ( k= numMonoms - 1; k >= 0; k-- ) {
if ( lengths[k] > 0 ) {
if ( best == 0 ) {
best= k+1;
}
else {
if ( lengths[k] < lengths[best-1] ) {
best= k+1;
}
}
}
}
lengths[best-1]= 0;
order[act]= best-1;
STICKYPROT2( " (%i) ", best );
if ( ( isZero= gauss.reduce( v[best-1] )) == TRUE ) {
p= gauss.getDependence();
}
else {
STICKYPROT( "+" );
gauss.store();
act++;
}
#ifndef HAVE_EXPLICIT_CONSTR
v[best-1].clearelems();
#else
v[best-1].~fglmVector();
#endif
}
poly result = NULL;
if ( isZero == TRUE ) {
number gcd = p.gcd();
if ( ! nIsZero( gcd ) && ! ( nIsOne( gcd ) ) ) {
p/= gcd;
}
nDelete( & gcd );
fglmVector temp( numMonoms );
for ( k= 0; k < p.size(); k++ ) {
if ( ! p.elemIsZero( k+1 ) ) {
temp+= p.getconstelem( k+1 ) * mv[order[k]];
}
}
number denom = temp.clearDenom();
nDelete( & denom );
gcd = temp.gcd();
if ( ! nIsZero( gcd ) && ! nIsOne( gcd ) ) {
temp/= gcd;
}
nDelete( & gcd );
poly sum = NULL;
for ( k= 1; k <= numMonoms; k++ ) {
if ( ! temp.elemIsZero( k ) ) {
if ( result == NULL ) {
result= pCopy( m[k-1] );
sum= result;
}
else {
sum->next= pCopy( m[k-1] );
pIter( sum );
}
pSetCoeff( sum, nCopy( temp.getconstelem( k ) ) );
}
}
p_Cleardenom( result, currRing );
}
// Free Memory
omFreeSize( (ADDRESS)lengths, numMonoms * sizeof( int ) );
omFreeSize( (ADDRESS)order, numMonoms * sizeof( int ) );
// for ( k= 0; k < numMonoms; k++ )
// v[k].~fglmVector();
#ifndef HAVE_EXPLICIT_CONSTR
delete [] v;
#else
omFreeSize( (ADDRESS)v, numMonoms * sizeof( fglmVector ) );
#endif
for ( k= 0; k < basisSize; k++ )
pDelete( basis + k );
omFreeSize( (ADDRESS)basis, basisMax * sizeof( poly ) );
#ifndef HAVE_EXPLICIT_CONSTR
delete [] mv;
#else
for ( k= 0; k < numMonoms; k++ )
mv[k].~fglmVector();
omFreeSize( (ADDRESS)mv, numMonoms * sizeof( fglmVector ) );
#endif
for ( k= 0; k < numMonoms; k++ )
pDelete( m + k );
omFreeSize( (ADDRESS)m, numMonoms * sizeof( poly ) );
STICKYPROT( "\n" );
return result;
}
fglmVector::fglmVector
fglmVector(fglmVectorRep *rep)
Definition fglmvec.cc:152
result
return result
Definition facAbsBiFact.cc:76
w
const CanonicalForm & w
Definition facAbsFact.cc:51
fglmReduce
static void fglmReduce(poly *pptr, fglmVector &v, polyset m, int numMonoms, ideal source, int *w)
Definition fglmcomb.cc:128
act
STATIC_VAR scmon act
Definition hdegree.cc:1139
nSize
#define nSize(n)
Definition numbers.h:39
p_Cleardenom
poly p_Cleardenom(poly p, const ring r)
Definition p_polys.cc:2893
pLength
static int pLength(poly a)
Definition p_polys.h:190
pLmInit
#define pLmInit(p)
like pInit, except that expvector is initialized to that of p, p must be != NULL
Definition polys.h:65
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23

## fglmReduce()

void fglmReduce | ( | poly * | pptr,
|  | fglmVector & | v,
|  | polyset | m,
|  | int | numMonoms,
|  | ideal | source,
|  | int * | w )

static

Definition at line 128 of file fglmcomb.cc.

{
BOOLEAN reduced = FALSE;
reduced= fglmReductionStep( pptr, source, w );
while ( reduced == TRUE ) {
fglmEliminateMonomials( pptr, v, m, numMonoms );
reduced= fglmReductionStep( pptr, source, w );
}
STICKYPROT( "<" );
poly temp = * pptr;
if ( temp != NULL ) {
while ( pNext( temp ) != NULL ) {
STICKYPROT( ">" );
reduced= fglmReductionStep( & pNext( temp ), source, w );
while ( reduced == TRUE ) {
fglmEliminateMonomials( & pNext( temp ), v, m, numMonoms );
reduced= fglmReductionStep( & pNext( temp ), source, w );
}
if ( pNext( temp ) != NULL ) {
pIter( temp );
}
}
}
}
fglmEliminateMonomials
static void fglmEliminateMonomials(poly *pptr, fglmVector &v, polyset monomials, int numMonoms)
Definition fglmcomb.cc:36
fglmReductionStep
static BOOLEAN fglmReductionStep(poly *pptr, ideal source, int *w)
Definition fglmcomb.cc:75
pNext
#define pNext(p)
Definition monomials.h:36

## fglmReductionStep()

BOOLEAN fglmReductionStep | ( | poly * | pptr,
|  | ideal | source,
|  | int * | w )

static

Definition at line 75 of file fglmcomb.cc.

{
// returns TRUE if the leading monomial was reduced
if ( *pptr == NULL ) return FALSE;
int k;
int best = 0;
for ( k= IDELEMS( source ) - 1; k >= 0; k-- ) {
if ( pDivisibleBy( (source->m)[k], *pptr ) ) {
if ( best == 0 ) {
best= k + 1;
}
else {
if ( w[k] < w[best-1] ) {
best= k + 1;
}
}
}
}
if ( best > 0 )
{
// OwnSPoly
poly p2 = (source->m)[best-1];
int i, diff;
poly m = pOne();
for ( i= (currRing->N); i > 0; i-- )
{
diff= pGetExp( *pptr, i ) - pGetExp( p2, i );
pSetExp( m, i, diff );
}
pSetm( m );
number n1 = nCopy( pGetCoeff( *pptr ) );
number n2 = pGetCoeff( p2 );
p2= pCopy( p2 );
pLmDelete(pptr);
pLmDelete( & p2 );
p2= pMult( m, p2 );
number temp = nDiv( n1, n2 );
n_Normalize( temp, currRing->cf );
nDelete( & n1 );
n1= temp;
n1= nInpNeg( n1 );
p2=__p_Mult_nn( p2, n1, currRing );
// pNormalize( p2 );
nDelete( & n1 );
*pptr= pAdd( *pptr, p2 );
}
return ( (best > 0) );
}
i
int i
Definition cfEzgcd.cc:132
n_Normalize
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition coeffs.h:581
diff
STATIC_VAR gmp_float * diff
Definition mpr_complex.cc:45
nDiv
#define nDiv(a, b)
Definition numbers.h:32
__p_Mult_nn
#define __p_Mult_nn(p, n, r)
Definition p_polys.h:973
pSetm
#define pSetm(p)
Definition polys.h:272
pLmDelete
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition polys.h:77
pMult
#define pMult(p, q)
Definition polys.h:208
pGetExp
#define pGetExp(p, i)
Exponent.
Definition polys.h:42
pDivisibleBy
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
Definition polys.h:139
pSetExp
#define pSetExp(p, i, v)
Definition polys.h:43
pOne
#define pOne()
Definition polys.h:316