Loading...
Searching...
No Matches
fglmzero.cc
Go to the documentation of this file.
// emacs edit mode for this file is -*- C++ -*-
/****************************************
* Computer Algebra System SINGULAR *
****************************************/
/*
* ABSTRACT - The FGLM-Algorithm
* Implementation of the fglm algorithm for 0-dimensional ideals,
* based on an idea by Faugere/Gianni/Lazard and Mora.
* The procedure CalculateFunctionals calculates the functionals
* which define the given ideal in the source ring. They build the
* input for GroebnerViaFunctionals, which defines the reduced
* groebner basis for the ideal in the destination ring.
*/
/* Changes:
* o FindUnivariatePolys added
*/
#include "kernel/mod2.h"
// assumes, that NOSTREAMIO is set in factoryconf.h, which is included
// by templates/list.h.
#include "factory/factory.h"
#include "factory/templates/ftmpl_list.h"
#include "factory/templates/ftmpl_list.cc"
#include "misc/options.h"
#include "misc/intvec.h"
#include "polys/monomials/maps.h"
#include "polys/monomials/ring.h"
#include "kernel/polys.h"
#include "kernel/ideals.h"
#include "kernel/GBEngine/kstd1.h"
#include "fglm.h"
#include "fglmvec.h"
#include "fglmgauss.h"
#define PROT(msg)
#define STICKYPROT(msg) if (BTEST1(OPT_PROT)) Print(msg)
#define PROT2(msg,arg)
#define STICKYPROT2(msg,arg) if (BTEST1(OPT_PROT)) Print(msg,arg)
#define fglmASSERT(ignore1,ignore2)
// internal Version: 1.3.1.12
// ============================================================
//! The idealFunctionals
// ============================================================
struct matElem
{
int row;
number elem;
};
struct matHeader
{
int size;
BOOLEAN owner;
matElem * elems;
};
class idealFunctionals
{
private:
int _block;
int _max;
int _size;
int _nfunc;
int * currentSize;
matHeader ** func;
matHeader * grow( int var );
public:
idealFunctionals( int blockSize, int numFuncs );
~idealFunctionals();
int dimen() const { fglmASSERT( _size>0, "called too early"); return _size; }
void endofConstruction();
void map( ring source );
void insertCols( int * divisors, int to );
void insertCols( int * divisors, const fglmVector to );
fglmVector addCols( const int var, int basisSize, const fglmVector v ) const;
fglmVector multiply( const fglmVector v, int var ) const;
};
idealFunctionals::idealFunctionals( int blockSize, int numFuncs )
{
int k;
_block= blockSize;
_max= _block;
_size= 0;
_nfunc= numFuncs;
currentSize= (int *)omAlloc0( _nfunc*sizeof( int ) );
//for ( k= _nfunc-1; k >= 0; k-- )
// currentSize[k]= 0;
func= (matHeader **)omAlloc( _nfunc*sizeof( matHeader * ) );
for ( k= _nfunc-1; k >= 0; k-- )
func[k]= (matHeader *)omAlloc( _max*sizeof( matHeader ) );
}
idealFunctionals::~idealFunctionals()
{
int k;
int l;
int row;
matHeader * colp;
matElem * elemp;
for ( k= _nfunc-1; k >= 0; k-- ) {
for ( l= _size-1, colp= func[k]; l >= 0; l--, colp++ ) {
if ( ( colp->owner == TRUE ) && ( colp->size > 0 ) ) {
for ( row= colp->size-1, elemp= colp->elems; row >= 0; row--, elemp++ )
nDelete( & elemp->elem );
omFreeSize( (ADDRESS)colp->elems, colp->size*sizeof( matElem ) );
}
}
omFreeSize( (ADDRESS)func[k], _max*sizeof( matHeader ) );
}
omFreeSize( (ADDRESS)func, _nfunc*sizeof( matHeader * ) );
omFreeSize( (ADDRESS)currentSize, _nfunc*sizeof( int ) );
}
void
idealFunctionals::endofConstruction()
{
_size= currentSize[0];
}
void
idealFunctionals::map( ring source )
{
// maps from ring source to currentRing.
int var, col, row;
matHeader * colp;
matElem * elemp;
number newelem;
int * perm = (int *)omAlloc0( (_nfunc+1)*sizeof( int ) );
maFindPerm( source->names, source->N, NULL, 0, currRing->names,
currRing->N, NULL, 0, perm, NULL , currRing->cf->type);
nMapFunc nMap=n_SetMap( source->cf, currRing->cf);
matHeader ** temp = (matHeader **)omAlloc( _nfunc*sizeof( matHeader * ));
for ( var= 0; var < _nfunc; var ++ ) {
for ( col= 0, colp= func[var]; col < _size; col++, colp++ ) {
if ( colp->owner == TRUE ) {
for ( row= colp->size-1, elemp= colp->elems; row >= 0;
row--, elemp++ )
{
newelem= nMap( elemp->elem, source->cf, currRing->cf );
nDelete( & elemp->elem );
elemp->elem= newelem;
}
}
}
temp[ perm[var+1]-1 ]= func[var];
}
omFreeSize( (ADDRESS)func, _nfunc*sizeof( matHeader * ) );
omFreeSize( (ADDRESS)perm, (_nfunc+1)*sizeof( int ) );
func= temp;
}
matHeader *
idealFunctionals::grow( int var )
{
if ( currentSize[var-1] == _max ) {
int k;
for ( k= _nfunc; k > 0; k-- )
func[k-1]= (matHeader *)omReallocSize( func[k-1], _max*sizeof( matHeader ), (_max + _block)*sizeof( matHeader ) );
_max+= _block;
}
currentSize[var-1]++;
return func[var-1] + currentSize[var-1] - 1;
}
void
idealFunctionals::insertCols( int * divisors, int to )
{
fglmASSERT( 0 < divisors[0] && divisors[0] <= _nfunc, "wrong number of divisors" );
int k;
BOOLEAN owner = TRUE;
matElem * elems = (matElem *)omAlloc( sizeof( matElem ) );
elems->row= to;
elems->elem= nInit( 1 );
for ( k= divisors[0]; k > 0; k-- ) {
fglmASSERT( 0 < divisors[k] && divisors[k] <= _nfunc, "wrong divisor" );
matHeader * colp = grow( divisors[k] );
colp->size= 1;
colp->elems= elems;
colp->owner= owner;
owner= FALSE;
}
}
void
idealFunctionals::insertCols( int * divisors, const fglmVector to )
{
// divisors runs from divisors[0]..divisors[size-1]
fglmASSERT( 0 < divisors[0] && divisors[0] <= _nfunc, "wrong number of divisors" );
int k, l;
int numElems= to.numNonZeroElems();
matElem * elems;
matElem * elemp;
BOOLEAN owner = TRUE;
if ( numElems > 0 ) {
elems= (matElem *)omAlloc( numElems * sizeof( matElem ) );
for ( k= 1, l= 1, elemp= elems; k <= numElems; k++, elemp++ ) {
while ( nIsZero( to.getconstelem(l) ) ) l++;
elemp->row= l;
elemp->elem= nCopy( to.getconstelem( l ) );
l++; // hochzaehlen, damit wir nicht noch einmal die gleiche Stelle testen
}
}
else
elems= NULL;
for ( k= divisors[0]; k > 0; k-- ) {
fglmASSERT( 0 < divisors[k] && divisors[k] <= _nfunc, "wrong divisor" );
matHeader * colp = grow( divisors[k] );
colp->size= numElems;
colp->elems= elems;
colp->owner= owner;
owner= FALSE;
}
}
fglmVector
idealFunctionals::addCols( const int var, int basisSize, const fglmVector v ) const
{
fglmVector result( basisSize );
matHeader * colp;
matElem * elemp;
number factor, temp;
int k, l;
int vsize = v.size();
fglmASSERT( currentSize[var-1]+1 >= vsize, "wrong v.size()" );
for ( k= 1, colp= func[var-1]; k <= vsize; k++, colp++ ) {
factor= v.getconstelem( k );
if ( ! nIsZero( factor ) ) {
for ( l= colp->size-1, elemp= colp->elems; l >= 0; l--, elemp++ ) {
temp= nMult( factor, elemp->elem );
number newelem= nAdd( result.getconstelem( elemp->row ), temp );
nDelete( & temp );
nNormalize( newelem );
result.setelem( elemp->row, newelem );
}
}
}
return result;
}
fglmVector
idealFunctionals::multiply( const fglmVector v, int var ) const
{
fglmASSERT( v.size() == _size, "multiply: v has wrong size");
fglmVector result( _size );
matHeader * colp;
matElem * elemp;
number factor, temp;
int k, l;
for ( k= 1, colp= func[var-1]; k <= _size; k++, colp++ ) {
factor= v.getconstelem( k );
if ( ! nIsZero( factor ) ) {
for ( l= colp->size-1, elemp= colp->elems; l >= 0; l--, elemp++ ) {
temp= nMult( factor, elemp->elem );
number newelem= nAdd( result.getconstelem( elemp->row ), temp );
nDelete( & temp );
nNormalize( newelem );
result.setelem( elemp->row, newelem );
}
}
}
return result;
}
// ============================================================
//! The old basis
// ============================================================
// Contains the data for a border-monomial, i.e. the monom itself
// ( as a Singular-poly ) and its normal-form, described by an
// fglmVector. The size of the Vector depends on the current size of
// the basis when the normalForm was computed.
// monom gets deleted when borderElem comes out of scope.
class borderElem
{
public:
poly monom;
fglmVector nf;
borderElem() : monom(NULL), nf() {}
borderElem( poly p, fglmVector n ) : monom( p ), nf( n ) {}
~borderElem() { if (monom!=NULL) pLmDelete(&monom); }
#ifndef HAVE_EXPLICIT_CONSTR
void insertElem( poly p, fglmVector n )
{
monom= p;
nf= n;
}
#endif
};
// This class contains the relevant data for the 'candidates'
// The declaration of class fglmSelem is found in fglm.h
fglmSelem::fglmSelem( poly p, int var ) : monom( p ), numVars( 0 )
{
for ( int k = (currRing->N); k > 0; k-- )
if ( pGetExp( monom, k ) > 0 )
numVars++;
divisors= (int *)omAlloc( (numVars+1)*sizeof( int ) );
divisors[0]= 0;
newDivisor( var );
}
void
fglmSelem::cleanup()
{
omFreeSize( (ADDRESS)divisors, (numVars+1)*sizeof( int ) );
}
// The data-structure for the Functional-Finding-Algorithm.
class fglmSdata
{
private:
ideal theIdeal;
int idelems;
int* varpermutation;
int basisBS;
int basisMax;
int basisSize;
polyset basis; //. rem: runs from basis[1]..basis[dimen]
int borderBS;
int borderMax;
int borderSize;
borderElem * border; //. rem: runs from border[1]..border[dimen]
List<fglmSelem> nlist;
BOOLEAN _state;
public:
fglmSdata( const ideal thisIdeal );
~fglmSdata();
BOOLEAN state() const { return _state; };
int getBasisSize() const { return basisSize; };
int newBasisElem( poly & p );
void newBorderElem( poly & m, fglmVector v );
BOOLEAN candidatesLeft() const { return ( nlist.isEmpty() ? FALSE : TRUE ); }
fglmSelem nextCandidate();
void updateCandidates();
int getEdgeNumber( const poly m ) const;
poly getSpanPoly( int number ) const { return pCopy( (theIdeal->m)[number-1] ); }
fglmVector getVectorRep( const poly m );
fglmVector getBorderDiv( const poly m, int & var ) const;
};
fglmSdata::fglmSdata( const ideal thisIdeal )
{
// An dieser Stelle kann die BlockSize ( =BS ) noch sinnvoller berechnet
// werden, jenachdem wie das Ideal aussieht.
theIdeal= thisIdeal;
idelems= IDELEMS( theIdeal );
varpermutation = (int*)omAlloc( ((currRing->N)+1)*sizeof(int) );
// Sort ring variables by increasing values (because of weighted orderings)
ideal perm = idMaxIdeal(1);
intvec *iv = idSort(perm,TRUE);
idDelete(&perm);
for(int i = (currRing->N); i > 0; i--) varpermutation[(currRing->N)+1-i] = (*iv)[i-1];
delete iv;
basisBS= 100;
basisMax= basisBS;
basisSize= 0;
basis= (polyset)omAlloc( basisMax*sizeof( poly ) );
borderBS= 100;
borderMax= borderBS;
borderSize= 0;
#ifndef HAVE_EXPLICIT_CONSTR
border= new borderElem[ borderMax ];
#else
border= (borderElem *)omAlloc( borderMax*sizeof( borderElem ) );
#endif
// rem: the constructors are called in newBorderElem().
_state= TRUE;
}
fglmSdata::~fglmSdata()
{
omFreeSize( (ADDRESS)varpermutation, ((currRing->N)+1)*sizeof(int) );
for ( int k = basisSize; k > 0; k-- )
pLmDelete( basis + k ); //. rem: basis runs from basis[1]..basis[basisSize]
omFreeSize( (ADDRESS)basis, basisMax*sizeof( poly ) );
#ifndef HAVE_EXPLICIT_CONSTR
delete [] border;
#else
for ( int l = borderSize; l > 0; l-- )
// rem: the polys of borderElem are deleted via ~borderElem()
border[l].~borderElem();
omFreeSize( (ADDRESS)border, borderMax*sizeof( borderElem ) );
#endif
}
// Inserts poly p without copying into basis, reAllocs Memory if necessary,
// increases basisSize and returns the new basisSize.
// Remember: The elements of basis are deleted via pDelete in ~fglmSdata!
// Sets m= NULL to indicate that now basis is ow(e?)ing the poly.
int
fglmSdata::newBasisElem( poly & m )
{
basisSize++;
if ( basisSize == basisMax ) {
basis= (polyset)omReallocSize( basis, basisMax*sizeof( poly ), (basisMax + basisBS)*sizeof( poly ) );
basisMax+= basisBS;
}
basis[basisSize]= m;
m= NULL;
return basisSize;
}
// Inserts poly p and fglmvector v without copying into border, reAllocs Memory
// if necessary, and increases borderSize.
// Remember: The poly of border is deleted via ~borderElem in ~fglmSdata!
// Sets m= NULL to indicate that now border is ow(e?)ing the poly.
void
fglmSdata::newBorderElem( poly & m, fglmVector v )
{
borderSize++;
if ( borderSize == borderMax ) {
#ifndef HAVE_EXPLICIT_CONSTR
borderElem * tempborder = new borderElem[ borderMax+borderBS ];
for ( int k = 0; k < borderMax; k++ ) {
tempborder[k]= border[k];
border[k].insertElem( NULL, fglmVector() );
}
delete [] border;
border= tempborder;
#else
border= (borderElem *)omReallocSize( border, borderMax*sizeof( borderElem ), (borderMax + borderBS)*sizeof( borderElem ) );
#endif
borderMax+= borderBS;
}
#ifndef HAVE_EXPLICIT_CONSTR
border[borderSize].insertElem( m, v );
#else
border[borderSize].borderElem( m, v );
#endif
m= NULL;
}
fglmSelem
fglmSdata::nextCandidate()
{
fglmSelem result = nlist.getFirst();
nlist.removeFirst();
return result;
}
// Multiplies basis[basisSize] with all ringvariables and inserts the new monomials
// into the list of candidates, according to the given order. If a monomial already
// exists, then "insertions" and "divisors" are updated.
// Assumes that ringvar(varperm[k]) < ringvar(varperm[l]) for k > l
void
fglmSdata::updateCandidates()
{
ListIterator<fglmSelem> list = nlist;
fglmASSERT( basisSize > 0 && basisSize < basisMax, "Error(1) in fglmSdata::updateCandidates - wrong bassSize" );
poly m = basis[basisSize];
poly newmonom = NULL;
int k = (currRing->N);
BOOLEAN done = FALSE;
int state = 0;
while ( k >= 1 )
{
newmonom = pCopy( m );
pIncrExp( newmonom, varpermutation[k] );
pSetm( newmonom );
done= FALSE;
while ( list.hasItem() && (!done) )
{
if ( (state= pCmp( list.getItem().monom, newmonom )) < 0 )
list++;
else done= TRUE;
}
if ( !done )
{
nlist.append( fglmSelem( newmonom, varpermutation[k] ) );
break;
}
if ( state == 0 )
{
list.getItem().newDivisor( varpermutation[k] );
pLmDelete(&newmonom);
}
else
{
list.insert( fglmSelem( newmonom, varpermutation[k] ) );
}
k--;
}
while ( --k >= 1 )
{
newmonom= pCopy( m ); // HIER
pIncrExp( newmonom, varpermutation[k] );
pSetm( newmonom );
nlist.append( fglmSelem( newmonom, varpermutation[k] ) );
}
}
// if p == pHead( (theIdeal->m)[k] ) return k, 0 otherwise
// (Assumes that pLmEqual just checks the leading monomials without
// coefficients.)
int
fglmSdata::getEdgeNumber( const poly m ) const
{
for ( int k = idelems; k > 0; k-- )
if ( pLmEqual( m, (theIdeal->m)[k-1] ) )
return k;
return 0;
}
// Returns the fglmVector v, s.t.
// p = v[1]*basis(1) + .. + v[basisSize]*basis(basisSize)
// So the size of v depends on the current size of the basis.
// Assumes that such an representation exists, i.e. all monoms in p have to be
// smaller than basis[basisSize] and that basis[k] < basis[l] for k < l.
fglmVector
fglmSdata::getVectorRep( const poly p )
{
fglmVector temp( basisSize );
poly m = p;
int num = basisSize;
while ( m != NULL ) {
int comp = pCmp( m, basis[num] );
if ( comp == 0 ) {
fglmASSERT( num > 0, "Error(1) in fglmSdata::getVectorRep" );
number newelem = nCopy( pGetCoeff( m ) );
temp.setelem( num, newelem );
num--;
pIter( m );
}
else {
if ( comp < 0 ) {
num--;
}
else {
// This is the place where we can detect if the sourceIdeal
// is not reduced. In this case m is not in basis[]. Since basis[]
// is ordered this is the case, if and only if basis[i]<m
// and basis[j]>m for all j>i
_state= FALSE;
return temp;
}
}
}
return temp;
}
// Searches through the border for a monomial bm which divides m and returns
// its normalform in vector representation.
// var contains the number of the variable v, s.t. bm = m * v
fglmVector
fglmSdata::getBorderDiv( const poly m, int & var ) const
{
// int num2 = borderSize;
// while ( num2 > 0 ) {
// poly temp = border[num2].monom;
// if ( pDivisibleBy( temp, m ) ) {
// poly divisor = pDivideM( m, temp );
// int var = pIsPurePower( divisor );
// if ( (var != 0) && (pGetCoeff( divisor, var ) == 1) ) {
// Print( "poly %s divides poly %s", pString( temp ), pString( m ) );
// }
// }
// num2--;
// }
int num = borderSize;
while ( num > 0 ) {
poly temp = border[num].monom;
if ( pDivisibleBy( temp, m ) ) {
var = (currRing->N);
while ( var > 0 ) {
if ( (pGetExp( m, var ) - pGetExp( temp, var )) == 1 )
return border[num].nf;
var--;
}
}
num--;
}
return fglmVector();
}
void
internalCalculateFunctionals( const ideal /*& theIdeal*/, idealFunctionals & l,
fglmSdata & data )
{
// insert pOne() into basis and update the workingList:
poly one = pOne();
data.newBasisElem( one );
data.updateCandidates();
STICKYPROT(".");
while ( data.candidatesLeft() == TRUE ) {
fglmSelem candidate = data.nextCandidate();
if ( candidate.isBasisOrEdge() == TRUE ) {
int edge = data.getEdgeNumber( candidate.monom );
if ( edge != 0 )
{
// now candidate is an edge, i.e. we know its normalform:
// NF(p) = - ( tail(p)/LC(p) )
poly nf = data.getSpanPoly( edge );
pNorm( nf );
pLmDelete(&nf); //. deletes the leadingmonomial
nf= pNeg( nf );
fglmVector nfv = data.getVectorRep( nf );
l.insertCols( candidate.divisors, nfv );
data.newBorderElem( candidate.monom, nfv );
pDelete( &nf );
STICKYPROT( "+" );
}
else
{
int basis= data.newBasisElem( candidate.monom );
data.updateCandidates();
l.insertCols( candidate.divisors, basis );
STICKYPROT( "." );
}
}
else {
int var = 0;
fglmVector temp = data.getBorderDiv( candidate.monom, var );
fglmASSERT( var > 0, "this should never happen" );
fglmVector nfv = l.addCols( var, data.getBasisSize(), temp );
data.newBorderElem( candidate.monom, nfv );
l.insertCols( candidate.divisors, nfv );
STICKYPROT( "-" );
}
candidate.cleanup();
} //. while ( data.candidatesLeft() == TRUE )
l.endofConstruction();
STICKYPROT2( "\nvdim= %i\n", data.getBasisSize() );
return;
}
// Calculates the defining Functionals for the ideal "theIdeal" and
// returns them in "l".
// The ideal has to be zero-dimensional and reduced and has to be a
// real subset of the polynomial ring.
// In any case it has to be zero-dimensional and minimal (check this
// via fglmIdealcheck). Any minimal but not reduced ideal is detected.
// In this case it returns FglmNotReduced.
// If the base domain is Q, the leading coefficients of the polys
// have to be in Z.
// returns TRUE if the result is valid, FALSE if theIdeal
// is not reduced.
static BOOLEAN
CalculateFunctionals( const ideal & theIdeal, idealFunctionals & l )
{
fglmSdata data( theIdeal );
internalCalculateFunctionals( theIdeal, l, data );
return ( data.state() );
}
static BOOLEAN
CalculateFunctionals( const ideal & theIdeal, idealFunctionals & l,
poly & p, fglmVector & v )
{
fglmSdata data( theIdeal );
internalCalculateFunctionals( theIdeal, l, data );
// STICKYPROT("Calculating vector rep\n");
v = data.getVectorRep( p );
// if ( v.isZero() )
// STICKYPROT("vectorrep is 0\n");
return ( data.state() );
}
// ============================================================
//! The new basis
// ============================================================
// The declaration of class fglmDelem is found in fglm.h
fglmDelem::fglmDelem( poly & m, fglmVector mv, int v ) : v( mv ), insertions( 0 ), var( v )
{
monom= m;
m= NULL;
for ( int k = (currRing->N); k > 0; k-- )
if ( pGetExp( monom, k ) > 0 )
insertions++;
// Wir gehen davon aus, dass ein fglmDelem direkt bei der Erzeugung
// auch in eine Liste eingefuegt wird. Daher wird hier automatisch
// newDivisor aufgerufen ( v teilt ja m )
newDivisor();
}
void
fglmDelem::cleanup()
{
if ( monom != NULL )
{
pLmDelete(&monom);
}
}
class oldGaussElem
{
public:
fglmVector v;
fglmVector p;
number pdenom;
number fac;
#ifndef HAVE_EXPLICIT_CONSTR
oldGaussElem() : v(), p(), pdenom( NULL ), fac( NULL ) {}
#endif
oldGaussElem( const fglmVector newv, const fglmVector newp, number & newpdenom, number & newfac ) : v( newv ), p( newp ), pdenom( newpdenom ), fac( newfac )
{
newpdenom= NULL;
newfac= NULL;
}
~oldGaussElem();
#ifndef HAVE_EXPLICIT_CONSTR
void insertElem( const fglmVector newv, const fglmVector newp, number & newpdenom, number & newfac )
{
v= newv;
p= newp;
pdenom= newpdenom;
fac= newfac;
newpdenom= NULL;
newfac= NULL;
}
#endif
};
oldGaussElem::~oldGaussElem()
{
if (fac!=NULL) nDelete( & fac );
if (pdenom!=NULL) nDelete( & pdenom );
}
class fglmDdata
{
private:
int dimen;
oldGaussElem * gauss;
BOOLEAN * isPivot; // [1]..[dimen]
int * perm; // [1]..[dimen]
int basisSize; //. the CURRENT basisSize, i.e. basisSize <= dimen
polyset basis; // [1]..[dimen]. The monoms of the new Vectorspace-basis
int* varpermutation;
int groebnerBS;
int groebnerSize;
ideal destId;
List<fglmDelem> nlist;
public:
fglmDdata( int dimension );
~fglmDdata();
int getBasisSize() const { return basisSize; }
BOOLEAN candidatesLeft() const { return ( nlist.isEmpty() ? FALSE : TRUE ); }
fglmDelem nextCandidate();
void newBasisElem( poly & m, fglmVector v, fglmVector p, number & denom );
void updateCandidates( poly m, const fglmVector v );
void newGroebnerPoly( fglmVector & v, poly & p );
void gaussreduce( fglmVector & v, fglmVector & p, number & denom );
ideal buildIdeal()
{
idSkipZeroes( destId );
return destId;
}
};
fglmDdata::fglmDdata( int dimension )
{
int k;
dimen= dimension;
basisSize= 0;
//. All arrays run from [1]..[dimen], thus omAlloc( dimen + 1 )!
#ifndef HAVE_EXPLICIT_CONSTR
gauss= new oldGaussElem[ dimen+1 ];
#else
gauss= (oldGaussElem *)omAlloc( (dimen+1)*sizeof( oldGaussElem ) );
#endif
isPivot= (BOOLEAN *)omAlloc( (dimen+1)*sizeof( BOOLEAN ) );
for ( k= dimen; k > 0; k-- ) isPivot[k]= FALSE;
perm= (int *)omAlloc( (dimen+1)*sizeof( int ) );
basis= (polyset)omAlloc( (dimen+1)*sizeof( poly ) );
varpermutation = (int*)omAlloc( ((currRing->N)+1)*sizeof(int) );
// Sort ring variables by increasing values (because of weighted orderings)
ideal perm_id = idMaxIdeal(1);
intvec *iv = idSort(perm_id,TRUE);
idDelete(&perm_id);
for(int i = (currRing->N); i > 0; i--) varpermutation[(currRing->N)+1-i] = (*iv)[i-1];
delete iv;
groebnerBS= 16;
groebnerSize= 0;
destId= idInit( groebnerBS, 1 );
}
fglmDdata::~fglmDdata()
{
// STICKYPROT2("dimen= %i", dimen);
// STICKYPROT2("basisSize= %i", basisSize);
// fglmASSERT( dimen == basisSize, "Es wurden nicht alle BasisElemente gefunden!" );
int k;
#ifndef HAVE_EXPLICIT_CONSTR
delete [] gauss;
#else
// use basisSize instead of dimen because of fglmquot!
for ( k= basisSize; k > 0; k-- )
gauss[k].~oldGaussElem();
omFreeSize( (ADDRESS)gauss, (dimen+1)*sizeof( oldGaussElem ) );
#endif
omFreeSize( (ADDRESS)isPivot, (dimen+1)*sizeof( BOOLEAN ) );
omFreeSize( (ADDRESS)perm, (dimen+1)*sizeof( int ) );
// use basisSize instead of dimen because of fglmquot!
//. Remember: There is no poly in basis[0], thus k > 0
for ( k= basisSize; k > 0; k-- )
pLmDelete( basis[k]);
omFreeSize( (ADDRESS)basis, (dimen+1)*sizeof( poly ) );
omFreeSize( (ADDRESS)varpermutation, ((currRing->N)+1)*sizeof(int) );
}
fglmDelem
fglmDdata::nextCandidate()
{
fglmDelem result = nlist.getFirst();
nlist.removeFirst();
return result;
}
void
fglmDdata::newBasisElem( poly & m, fglmVector v, fglmVector p, number & denom )
{
// inserts m as a new basis monom. m is NOT copied but directly inserted.
// returns m=NULL to indicate, that now basis is oweing m.
basisSize++;
basis[basisSize]= m;
m= NULL;
int k= 1;
while ( nIsZero(v.getconstelem(k)) || isPivot[k] ) {
k++;
}
fglmASSERT( k <= dimen, "Error(1) in fglmDdata::pivot-search");
number pivot= v.getconstelem( k );
int pivotcol = k;
k++;
while ( k <= dimen ) {
if ( ! nIsZero( v.getconstelem(k) ) && ! isPivot[k] ) {
if ( nGreater( v.getconstelem( k ), pivot ) ) {
pivot= v.getconstelem( k );
pivotcol= k;
}
}
k++;
}
fglmASSERT( ! nIsZero( pivot ), "Error(2) fglmDdata::Pivotelement ist Null" );
isPivot[ pivotcol ]= TRUE;
perm[basisSize]= pivotcol;
pivot= nCopy( v.getconstelem( pivotcol ) );
#ifndef HAVE_EXPLICIT_CONSTR
gauss[basisSize].insertElem( v, p, denom, pivot );
#else
gauss[basisSize].oldGaussElem( v, p, denom, pivot );
#endif
}
void
fglmDdata::updateCandidates( poly m, const fglmVector v )
{
ListIterator<fglmDelem> list = nlist;
poly newmonom = NULL;
int k = (currRing->N);
BOOLEAN done = FALSE;
int state = 0;
while ( k >= 1 )
{
newmonom = pCopy( m );
pIncrExp( newmonom, varpermutation[k] );
pSetm( newmonom );
done= FALSE;
while ( list.hasItem() && (!done) )
{
if ( (state= pCmp( list.getItem().monom, newmonom )) < 0 )
list++;
else done= TRUE;
}
if ( !done )
{
nlist.append( fglmDelem( newmonom, v, k ) );
break;
}
if ( state == 0 )
{
list.getItem().newDivisor();
pLmDelete( & newmonom );
}
else
{
list.insert( fglmDelem( newmonom, v, k ) );
}
k--;
}
while ( --k >= 1 )
{
newmonom= pCopy( m );
pIncrExp( newmonom, varpermutation[k] );
pSetm( newmonom );
nlist.append( fglmDelem( newmonom, v, k ) );
}
}
void
fglmDdata::newGroebnerPoly( fglmVector & p, poly & m )
// Inserts gp = p[1]*basis(1)+..+p[basisSize]*basis(basisSize)+p[basisSize+1]*m as
// a new groebner polynomial for the ideal.
// All elements (monomials and coefficients) of gp are copied, instead of m.
// Assumes that p.length() == basisSize+1.
{
//. Baue das Polynom von oben nach unten:
fglmASSERT( p.size() == basisSize+1, "GP::newGroebnerPoly: p has wrong size" );
int k;
poly result = m;
poly temp = result;
m= NULL;
if ( nGetChar() > 0 ) {
number lead = nCopy( p.getconstelem( basisSize+1 ) );
p /= lead;
nDelete( & lead );
}
if ( nGetChar() == 0 ) {
number gcd= p.gcd();
fglmASSERT( ! nIsZero( gcd ), "FATAL: gcd and thus p is zero" );
if ( ! nIsOne( gcd ) )
p /= gcd;
nDelete( & gcd );
}
pSetCoeff( result, nCopy( p.getconstelem( basisSize+1 ) ) );
for ( k= basisSize; k > 0; k-- ) {
if ( ! nIsZero( p.getconstelem( k ) ) ) {
temp->next= pCopy( basis[k] );
pIter( temp );
pSetCoeff( temp, nCopy( p.getconstelem( k ) ) );
}
}
pSetm( result );
if ( ! nGreaterZero( pGetCoeff( result ) ) ) result= pNeg( result );
if ( groebnerSize == IDELEMS( destId ) ) {
pEnlargeSet( & destId->m, IDELEMS( destId ), groebnerBS );
IDELEMS( destId )+= groebnerBS;
}
(destId->m)[groebnerSize]= result;
groebnerSize++;
}
void
fglmDdata::gaussreduce( fglmVector & v, fglmVector & p, number & pdenom )
{
int k;
number fac1, fac2;
number temp;
fglmASSERT( pdenom == NULL, "pdenom in gaussreduce should be NULL" );
pdenom= nInit( 1 );
number vdenom = v.clearDenom();
if ( ! nIsZero( vdenom ) && ! nIsOne( vdenom ) ) {
p.setelem( p.size(), vdenom );
}
else {
nDelete( &vdenom );
}
number gcd = v.gcd();
if ( ! nIsZero( gcd ) && ! nIsOne( gcd ) ) {
v /= gcd;
number temp= nMult( pdenom, gcd );
nDelete( &pdenom );
pdenom= temp;
}
nDelete( & gcd );
for ( k= 1; k <= basisSize; k++ ) {
if ( ! v.elemIsZero( perm[k] ) ) {
fac1= gauss[k].fac;
fac2= nCopy( v.getconstelem( perm[k] ) );
v.nihilate( fac1, fac2, gauss[k].v );
fac1= nMult( fac1, gauss[k].pdenom );
temp= nMult( fac2, pdenom );
nDelete( &fac2 );
fac2= temp;
p.nihilate( fac1, fac2, gauss[k].p );
temp= nMult( pdenom, gauss[k].pdenom );
nDelete( &pdenom );
pdenom= temp;
nDelete( & fac1 );
nDelete( & fac2 );
number gcd = v.gcd();
if ( ! nIsZero( gcd ) && ! nIsOne( gcd ) )
{
v /= gcd;
number temp= nMult( pdenom, gcd );
nDelete( &pdenom );
pdenom= temp;
}
nDelete( & gcd );
gcd= p.gcd();
temp= n_SubringGcd( pdenom, gcd, currRing->cf );
nDelete( &gcd );
gcd= temp;
if ( ! nIsZero( gcd ) && ! nIsOne( gcd ) )
{
p /= gcd;
temp= nDiv( pdenom, gcd );
nDelete( & pdenom );
pdenom= temp;
nNormalize( pdenom );
}
nDelete( & gcd );
}
}
}
static ideal
GroebnerViaFunctionals( const idealFunctionals & l,
fglmVector iv = fglmVector() )
// If iv is zero, calculates the groebnerBasis for the ideal which is
// defined by l.
// If iv is not zero, then the groebnerBasis if i:p is calculated where
// i is defined by l and iv is the vector-representation of nf(p) wrt. i
// The dimension of l has to be finite.
// The result is in reduced form.
{
fglmDdata data( l.dimen() );
// insert pOne() and update workinglist according to iv:
fglmVector initv;
if ( iv.isZero() ) {
// STICKYPROT("initv is zero\n");
initv = fglmVector( l.dimen(), 1 );
}
else {
// STICKYPROT("initv is not zero\n");
initv = iv;
}
poly one = pOne();
data.updateCandidates( one, initv );
number nOne = nInit( 1 );
data.newBasisElem( one, initv, fglmVector( 1, 1 ), nOne );
STICKYPROT( "." );
while ( data.candidatesLeft() == TRUE ) {
fglmDelem candidate = data.nextCandidate();
if ( candidate.isBasisOrEdge() == TRUE ) {
// Now we have the chance to find a new groebner polynomial
// v is the vector-representation of candidate.monom
// some elements of v are zeroed in data.gaussreduce(). Which
// ones and how this was done is stored in p.
// originalV contains the unchanged v, which is later inserted
// into the working list (via data.updateCandidates().
fglmVector v = l.multiply( candidate.v, candidate.var );
fglmVector originalV = v;
fglmVector p( data.getBasisSize()+1, data.getBasisSize()+1 );
number pdenom = NULL;
data.gaussreduce( v, p, pdenom );
if ( v.isZero() ) {
// Now v is linear dependent to the already found basis elements.
// This means that v (resp. candidate.monom) is the leading
// monomial of the next groebner-basis polynomial.
data.newGroebnerPoly( p, candidate.monom );
nDelete( & pdenom );
STICKYPROT( "+" );
}
else {
// no linear dependence could be found, so v ( rsp. monom )
// is a basis monomial. We store the zeroed version ( i.e. v
// and not originalV ) as well as p, the denomiator and all
// the other stuff.
// erst updateCandidates, dann newBasisELem!!!
data.updateCandidates( candidate.monom, originalV );
data.newBasisElem( candidate.monom, v, p, pdenom );
STICKYPROT( "." );
}
}
else {
STICKYPROT( "-" );
candidate.cleanup();
}
} //. while data.candidatesLeft()
STICKYPROT( "\n" );
return ( data.buildIdeal() );
}
//<-
static ideal
FindUnivariatePolys( const idealFunctionals & l )
{
fglmVector v;
fglmVector p;
ideal destIdeal = idInit( (currRing->N), 1 );
int i;
BOOLEAN isZero;
int *varpermutation = (int*)omAlloc( ((currRing->N)+1)*sizeof(int) );
ideal perm = idMaxIdeal(1);
intvec *iv = idSort(perm,TRUE);
idDelete(&perm);
for(i = (currRing->N); i > 0; i--) varpermutation[(currRing->N)+1-i] = (*iv)[i-1];
delete iv;
for (i= 1; i <= (currRing->N); i++ )
{
// main loop
STICKYPROT2( "(%i)", i /*varpermutation[i]*/);
gaussReducer gauss( l.dimen() );
isZero= FALSE;
v= fglmVector( l.dimen(), 1 );
while ( !isZero )
{
if ( (isZero= gauss.reduce( v )))
{
STICKYPROT( "+" );
p= gauss.getDependence();
number gcd= p.gcd();
if ( ! nIsOne( gcd ) )
{
p /= gcd;
}
nDelete( & gcd );
int k;
poly temp = NULL;
poly result=NULL;
for ( k= p.size(); k > 0; k-- )
{
number n = p.getconstelem( k );
if ( ! nIsZero( n ) )
{
if ( temp == NULL )
{
result= p_Init(currRing);
temp= result;
}
else
{
temp->next= p_Init(currRing);
pIter( temp );
}
pSetCoeff0( temp, nCopy(n) );
pSetExp( temp, i /*varpermutation[i]*/, k-1 );
pSetm( temp );
}
}
if ( ! nGreaterZero( pGetCoeff( result ) ) ) result= pNeg( result );
(destIdeal->m)[i-1]= result;
}
else
{
STICKYPROT( "." );
gauss.store();
v= l.multiply( v, i /*varpermutation[i]*/ );
}
}
}
STICKYPROT( "\n" );
omFreeSize( (ADDRESS)varpermutation, ((currRing->N)+1)*sizeof(int) );
return destIdeal;
}
// for a description of the parameters see fglm.h
BOOLEAN
fglmzero( ring sourceRing, ideal & sourceIdeal, ring destRing, ideal & destIdeal, BOOLEAN switchBack, BOOLEAN deleteIdeal )
{
ring initialRing = currRing;
BOOLEAN fglmok;
if ( currRing != sourceRing )
{
rChangeCurrRing( sourceRing );
}
idealFunctionals L( 100, rVar(currRing) );
fglmok = CalculateFunctionals( sourceIdeal, L );
if ( deleteIdeal == TRUE )
idDelete( & sourceIdeal );
rChangeCurrRing( destRing );
if ( fglmok == TRUE )
{
L.map( sourceRing );
destIdeal= GroebnerViaFunctionals( L );
}
if ( (switchBack) && (currRing != initialRing) )
rChangeCurrRing( initialRing );
return fglmok;
}
BOOLEAN
fglmquot( ideal sourceIdeal, poly quot, ideal & destIdeal)
{
BOOLEAN fglmok;
fglmVector v;
idealFunctionals L( 100, (currRing->N) );
// STICKYPROT("calculating normal form\n");
// poly p = kNF( sourceIdeal, currRing->qideal, quot );
// STICKYPROT("calculating functionals\n");
fglmok = CalculateFunctionals( sourceIdeal, L, quot, v );
if ( fglmok == TRUE ) {
// STICKYPROT("calculating groebner basis\n");
destIdeal= GroebnerViaFunctionals( L, v );
}
return fglmok;
}
BOOLEAN
FindUnivariateWrapper( ideal source, ideal & destIdeal )
{
BOOLEAN fglmok;
idealFunctionals L( 100, (currRing->N) );
fglmok = CalculateFunctionals( source, L );
if ( fglmok == TRUE ) {
destIdeal= FindUnivariatePolys( L );
return TRUE;
}
else
return FALSE;
}
// ----------------------------------------------------------------------------
// Local Variables: ***
// compile-command: "make Singular" ***
// page-delimiter: "^\\‍(␌\\|//!\\‍)" ***
// fold-internal-margins: nil ***
// End: ***
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
dimension
BOOLEAN dimension(leftv res, leftv args)
Definition bbcone.cc:757
num
CanonicalForm num(const CanonicalForm &f)
Definition canonicalform.h:337
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
ListIterator
Definition ftmpl_list.h:87
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
ListIterator::insert
void insert(const T &)
Definition ftmpl_list.cc:492
List
Definition ftmpl_list.h:52
borderElem
The old basis.
Definition fglmzero.cc:300
borderElem::monom
poly monom
Definition fglmzero.cc:302
borderElem::borderElem
borderElem(poly p, fglmVector n)
Definition fglmzero.cc:305
borderElem::nf
fglmVector nf
Definition fglmzero.cc:303
borderElem::~borderElem
~borderElem()
Definition fglmzero.cc:306
borderElem::borderElem
borderElem()
Definition fglmzero.cc:304
fglmDdata
Definition fglmzero.cc:759
fglmDdata::getBasisSize
int getBasisSize() const
Definition fglmzero.cc:779
fglmDdata::isPivot
BOOLEAN * isPivot
Definition fglmzero.cc:763
fglmDdata::nextCandidate
fglmDelem nextCandidate()
Definition fglmzero.cc:846
fglmDdata::dimen
int dimen
Definition fglmzero.cc:761
fglmDdata::nlist
List< fglmDelem > nlist
Definition fglmzero.cc:774
fglmDdata::varpermutation
int * varpermutation
Definition fglmzero.cc:768
fglmDdata::gauss
oldGaussElem * gauss
Definition fglmzero.cc:762
fglmDdata::buildIdeal
ideal buildIdeal()
Definition fglmzero.cc:786
fglmDdata::groebnerSize
int groebnerSize
Definition fglmzero.cc:771
fglmDdata::newGroebnerPoly
void newGroebnerPoly(fglmVector &v, poly &p)
Definition fglmzero.cc:936
fglmDdata::basisSize
int basisSize
Definition fglmzero.cc:765
fglmDdata::basis
polyset basis
Definition fglmzero.cc:766
fglmDdata::~fglmDdata
~fglmDdata()
Definition fglmzero.cc:821
fglmDdata::groebnerBS
int groebnerBS
Definition fglmzero.cc:770
fglmDdata::candidatesLeft
BOOLEAN candidatesLeft() const
Definition fglmzero.cc:780
fglmDdata::updateCandidates
void updateCandidates(poly m, const fglmVector v)
Definition fglmzero.cc:891
fglmDdata::gaussreduce
void gaussreduce(fglmVector &v, fglmVector &p, number &denom)
Definition fglmzero.cc:979
fglmDdata::newBasisElem
void newBasisElem(poly &m, fglmVector v, fglmVector p, number &denom)
Definition fglmzero.cc:854
fglmDdata::destId
ideal destId
Definition fglmzero.cc:772
fglmDdata::perm
int * perm
Definition fglmzero.cc:764
fglmDdata::fglmDdata
fglmDdata(int dimension)
Definition fglmzero.cc:793
fglmDelem
Definition fglm.h:47
fglmDelem::insertions
int insertions
Definition fglm.h:51
fglmDelem::v
fglmVector v
Definition fglm.h:50
fglmDelem::monom
poly monom
Definition fglm.h:49
fglmDelem::var
int var
Definition fglm.h:52
fglmDelem::cleanup
void cleanup()
Definition fglmzero.cc:713
fglmDelem::newDivisor
void newDivisor()
Definition fglm.h:57
fglmDelem::isBasisOrEdge
BOOLEAN isBasisOrEdge() const
Definition fglm.h:56
fglmDelem::fglmDelem
fglmDelem(poly &m, fglmVector mv, int v)
The new basis.
Definition fglmzero.cc:699
fglmSdata
Definition fglmzero.cc:337
fglmSdata::basis
polyset basis
Definition fglmzero.cc:346
fglmSdata::candidatesLeft
BOOLEAN candidatesLeft() const
Definition fglmzero.cc:363
fglmSdata::basisMax
int basisMax
Definition fglmzero.cc:344
fglmSdata::fglmSdata
fglmSdata(const ideal thisIdeal)
Definition fglmzero.cc:372
fglmSdata::basisBS
int basisBS
Definition fglmzero.cc:343
fglmSdata::idelems
int idelems
Definition fglmzero.cc:340
fglmSdata::theIdeal
ideal theIdeal
Definition fglmzero.cc:339
fglmSdata::basisSize
int basisSize
Definition fglmzero.cc:345
fglmSdata::~fglmSdata
~fglmSdata()
Definition fglmzero.cc:403
fglmSdata::borderMax
int borderMax
Definition fglmzero.cc:349
fglmSdata::varpermutation
int * varpermutation
Definition fglmzero.cc:341
fglmSdata::newBorderElem
void newBorderElem(poly &m, fglmVector v)
Definition fglmzero.cc:441
fglmSdata::getSpanPoly
poly getSpanPoly(int number) const
Definition fglmzero.cc:367
fglmSdata::_state
BOOLEAN _state
Definition fglmzero.cc:354
fglmSdata::border
borderElem * border
Definition fglmzero.cc:351
fglmSdata::borderSize
int borderSize
Definition fglmzero.cc:350
fglmSdata::newBasisElem
int newBasisElem(poly &p)
Definition fglmzero.cc:424
fglmSdata::borderBS
int borderBS
Definition fglmzero.cc:348
fglmSdata::getVectorRep
fglmVector getVectorRep(const poly m)
Definition fglmzero.cc:543
fglmSdata::nlist
List< fglmSelem > nlist
Definition fglmzero.cc:353
fglmSdata::nextCandidate
fglmSelem nextCandidate()
Definition fglmzero.cc:467
fglmSdata::getBorderDiv
fglmVector getBorderDiv(const poly m, int &var) const
Definition fglmzero.cc:578
fglmSdata::state
BOOLEAN state() const
Definition fglmzero.cc:359
fglmSdata::getBasisSize
int getBasisSize() const
Definition fglmzero.cc:360
fglmSdata::getEdgeNumber
int getEdgeNumber(const poly m) const
Definition fglmzero.cc:529
fglmSdata::updateCandidates
void updateCandidates()
Definition fglmzero.cc:479
fglmSelem
Definition fglm.h:28
fglmSelem::monom
poly monom
Definition fglm.h:31
fglmSelem::fglmSelem
fglmSelem(poly p, int var)
Definition fglmzero.cc:319
fglmSelem::cleanup
void cleanup()
Definition fglmzero.cc:330
fglmSelem::divisors
int * divisors
Definition fglm.h:30
fglmSelem::numVars
int numVars
Definition fglm.h:32
fglmSelem::newDivisor
void newDivisor(int var)
Definition fglm.h:37
fglmSelem::isBasisOrEdge
BOOLEAN isBasisOrEdge() const
Definition fglm.h:36
fglmVector
Definition fglmvec.h:19
fglmVector::numNonZeroElems
int numNonZeroElems() const
Definition fglmvec.cc:212
fglmVector::getconstelem
number getconstelem(int i) const
Definition fglmvec.cc:446
fglmVector::setelem
void setelem(int i, number &n)
Definition fglmvec.cc:451
gaussReducer
Definition fglmgauss.h:19
gaussReducer::reduce
BOOLEAN reduce(fglmVector v)
Definition fglmgauss.cc:89
gaussReducer::store
void store()
Definition fglmgauss.cc:159
gaussReducer::getDependence
fglmVector getDependence()
Definition fglmgauss.cc:196
idealFunctionals
Definition fglmzero.cc:75
idealFunctionals::idealFunctionals
idealFunctionals(int blockSize, int numFuncs)
Definition fglmzero.cc:98
idealFunctionals::~idealFunctionals
~idealFunctionals()
Definition fglmzero.cc:115
idealFunctionals::insertCols
void insertCols(int *divisors, int to)
Definition fglmzero.cc:190
idealFunctionals::multiply
fglmVector multiply(const fglmVector v, int var) const
Definition fglmzero.cc:267
idealFunctionals::currentSize
int * currentSize
Definition fglmzero.cc:81
idealFunctionals::_size
int _size
Definition fglmzero.cc:79
idealFunctionals::endofConstruction
void endofConstruction()
Definition fglmzero.cc:137
idealFunctionals::_block
int _block
Definition fglmzero.cc:77
idealFunctionals::func
matHeader ** func
Definition fglmzero.cc:82
idealFunctionals::addCols
fglmVector addCols(const int var, int basisSize, const fglmVector v) const
Definition fglmzero.cc:241
idealFunctionals::map
void map(ring source)
Definition fglmzero.cc:143
idealFunctionals::_max
int _max
Definition fglmzero.cc:78
idealFunctionals::dimen
int dimen() const
Definition fglmzero.cc:88
idealFunctionals::_nfunc
int _nfunc
Definition fglmzero.cc:80
idealFunctionals::grow
matHeader * grow(int var)
Definition fglmzero.cc:177
intvec
Definition intvec.h:24
oldGaussElem
Definition fglmzero.cc:722
oldGaussElem::v
fglmVector v
Definition fglmzero.cc:724
oldGaussElem::~oldGaussElem
~oldGaussElem()
Definition fglmzero.cc:751
oldGaussElem::fac
number fac
Definition fglmzero.cc:727
oldGaussElem::pdenom
number pdenom
Definition fglmzero.cc:726
oldGaussElem::p
fglmVector p
Definition fglmzero.cc:725
oldGaussElem::oldGaussElem
oldGaussElem(const fglmVector newv, const fglmVector newp, number &newpdenom, number &newfac)
Definition fglmzero.cc:732
n_SetMap
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition coeffs.h:703
n_SubringGcd
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition coeffs.h:669
nMapFunc
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition coeffs.h:80
result
return result
Definition facAbsBiFact.cc:76
factor
CanonicalForm factor
Definition facAbsFact.cc:97
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition facSparseHensel.h:25
factory.h
factory.h' is the user interface to Factory.
if
if(!FE_OPT_NO_SHELL_FLAG)
Definition fehelp.cc:1000
fglmgauss.h
fglmvec.h
FindUnivariatePolys
static ideal FindUnivariatePolys(const idealFunctionals &l)
Definition fglmzero.cc:1118
matElem::row
int row
Definition fglmzero.cc:63
matHeader::elems
matElem * elems
Definition fglmzero.cc:71
fglmASSERT
#define fglmASSERT(ignore1, ignore2)
Definition fglmzero.cc:52
STICKYPROT2
#define STICKYPROT2(msg, arg)
Definition fglmzero.cc:51
fglmzero
BOOLEAN fglmzero(ring sourceRing, ideal &sourceIdeal, ring destRing, ideal &destIdeal, BOOLEAN switchBack, BOOLEAN deleteIdeal)
Definition fglmzero.cc:1193
STICKYPROT
#define STICKYPROT(msg)
Definition fglmzero.cc:49
CalculateFunctionals
static BOOLEAN CalculateFunctionals(const ideal &theIdeal, idealFunctionals &l)
Definition fglmzero.cc:673
fglmquot
BOOLEAN fglmquot(ideal sourceIdeal, poly quot, ideal &destIdeal)
Definition fglmzero.cc:1218
GroebnerViaFunctionals
static ideal GroebnerViaFunctionals(const idealFunctionals &l, fglmVector iv=fglmVector())
Definition fglmzero.cc:1046
FindUnivariateWrapper
BOOLEAN FindUnivariateWrapper(ideal source, ideal &destIdeal)
Definition fglmzero.cc:1236
matHeader::owner
BOOLEAN owner
Definition fglmzero.cc:70
matElem::elem
number elem
Definition fglmzero.cc:64
matHeader::size
int size
Definition fglmzero.cc:69
internalCalculateFunctionals
void internalCalculateFunctionals(const ideal, idealFunctionals &l, fglmSdata &data)
Definition fglmzero.cc:609
matElem
The idealFunctionals.
Definition fglmzero.cc:62
matHeader
Definition fglmzero.cc:68
ftmpl_list.cc
ftmpl_list.h
ideals.h
idDelete
#define idDelete(H)
delete an ideal
Definition ideals.h:29
idMaxIdeal
#define idMaxIdeal(D)
initialise the maximal ideal (at 0)
Definition ideals.h:33
idSort
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition ideals.h:188
intvec.h
fglm.h
kstd1.h
pivot
bool pivot(const matrix aMat, const int r1, const int r2, const int c1, const int c2, int *bestR, int *bestC, const ring R)
This code computes a score for each non-zero matrix entry in aMat[r1..r2, c1..c2].
Definition linearAlgebra.cc:68
maFindPerm
void maFindPerm(char const *const *const preim_names, int preim_n, char const *const *const preim_par, int preim_p, char const *const *const names, int n, char const *const *const par, int nop, int *perm, int *par_perm, n_coeffType ch)
Definition maps.cc:155
maps.h
mod2.h
pIter
#define pIter(p)
Definition monomials.h:37
pSetCoeff0
#define pSetCoeff0(p, n)
Definition monomials.h:59
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
nDiv
#define nDiv(a, b)
Definition numbers.h:32
nDelete
#define nDelete(n)
Definition numbers.h:16
nIsZero
#define nIsZero(n)
Definition numbers.h:19
nCopy
#define nCopy(n)
Definition numbers.h:15
nGreater
#define nGreater(a, b)
Definition numbers.h:28
nAdd
#define nAdd(n1, n2)
Definition numbers.h:18
nGetChar
#define nGetChar()
Definition numbers.h:23
nGreaterZero
#define nGreaterZero(n)
Definition numbers.h:27
nIsOne
#define nIsOne(n)
Definition numbers.h:25
nNormalize
#define nNormalize(n)
Definition numbers.h:30
nInit
#define nInit(i)
Definition numbers.h:24
nMult
#define nMult(n1, n2)
Definition numbers.h:17
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
omAlloc0
#define omAlloc0(size)
Definition omAllocDecl.h:211
NULL
#define NULL
Definition omList.c:12
options.h
pEnlargeSet
void pEnlargeSet(poly **p, int l, int increment)
Definition p_polys.cc:3821
p_Init
static poly p_Init(const ring r, omBin bin)
Definition p_polys.h:1341
rChangeCurrRing
void rChangeCurrRing(ring r)
Definition polys.cc:16
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
polys.h
Compatibility layer for legacy polynomial operations (over currRing).
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pSetm
#define pSetm(p)
Definition polys.h:272
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
pNorm
void pNorm(poly p)
Definition polys.h:363
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
pLmDelete
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition polys.h:77
pIncrExp
#define pIncrExp(p, i)
Definition polys.h:44
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
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
pOne
#define pOne()
Definition polys.h:316
polyset
poly * polyset
Definition polys.h:260
ring.h
rVar
static short rVar(const ring r)
define rVar(r) (r->N)
Definition ring.h:598
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition simpleideals.cc:201
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23
nf
Definition gnumpfl.cc:25
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836