Data Structures | Macros | Functions
fglmzero.cc File Reference
#include <kernel/mod2.h>
#include <factory/factory.h>
#include <factory/templates/ftmpl_list.h>
#include <factory/templates/ftmpl_list.cc>
#include <omalloc/omalloc.h>
#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"

Go to the source code of this file.

Data Structures

struct  matElem
 The idealFunctionals. More...
 
struct  matHeader
 
class  idealFunctionals
 
class  borderElem
 The old basis. More...
 
class  fglmSdata
 
class  oldGaussElem
 
class  fglmDdata
 

Macros

#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)
 

Functions

void internalCalculateFunctionals (const ideal, idealFunctionals &l, fglmSdata &data)
 
static BOOLEAN CalculateFunctionals (const ideal &theIdeal, idealFunctionals &l)
 
static BOOLEAN CalculateFunctionals (const ideal &theIdeal, idealFunctionals &l, poly &p, fglmVector &v)
 
static ideal GroebnerViaFunctionals (const idealFunctionals &l, fglmVector iv=fglmVector())
 
static ideal FindUnivariatePolys (const idealFunctionals &l)
 
BOOLEAN fglmzero (ring sourceRing, ideal &sourceIdeal, ring destRing, ideal &destIdeal, BOOLEAN switchBack, BOOLEAN deleteIdeal)
 
BOOLEAN fglmquot (ideal sourceIdeal, poly quot, ideal &destIdeal)
 
BOOLEAN FindUnivariateWrapper (ideal source, ideal &destIdeal)
 

Data Structure Documentation

struct matElem

The idealFunctionals.

Definition at line 63 of file fglmzero.cc.

Data Fields
number elem
int row
struct matHeader

Definition at line 69 of file fglmzero.cc.

Data Fields
matElem * elems
BOOLEAN owner
int size

Macro Definition Documentation

#define fglmASSERT (   ignore1,
  ignore2 
)

Definition at line 54 of file fglmzero.cc.

#define PROT (   msg)

Definition at line 50 of file fglmzero.cc.

#define PROT2 (   msg,
  arg 
)

Definition at line 52 of file fglmzero.cc.

#define STICKYPROT (   msg)    if (BTEST1(OPT_PROT)) Print(msg)

Definition at line 51 of file fglmzero.cc.

#define STICKYPROT2 (   msg,
  arg 
)    if (BTEST1(OPT_PROT)) Print(msg,arg)

Definition at line 53 of file fglmzero.cc.

Function Documentation

static BOOLEAN CalculateFunctionals ( const ideal &  theIdeal,
idealFunctionals l 
)
static

Definition at line 675 of file fglmzero.cc.

676 {
677  fglmSdata data( theIdeal );
678  internalCalculateFunctionals( theIdeal, l, data );
679  return ( data.state() );
680 }
void internalCalculateFunctionals(const ideal, idealFunctionals &l, fglmSdata &data)
Definition: fglmzero.cc:611
static BOOLEAN CalculateFunctionals ( const ideal &  theIdeal,
idealFunctionals l,
poly p,
fglmVector v 
)
static

Definition at line 683 of file fglmzero.cc.

685 {
686  fglmSdata data( theIdeal );
687  internalCalculateFunctionals( theIdeal, l, data );
688  // STICKYPROT("Calculating vector rep\n");
689  v = data.getVectorRep( p );
690  // if ( v.isZero() )
691  // STICKYPROT("vectorrep is 0\n");
692  return ( data.state() );
693 }
void internalCalculateFunctionals(const ideal, idealFunctionals &l, fglmSdata &data)
Definition: fglmzero.cc:611
return P p
Definition: myNF.cc:203
BOOLEAN fglmquot ( ideal  sourceIdeal,
poly  quot,
ideal &  destIdeal 
)

Definition at line 1215 of file fglmzero.cc.

1216 {
1217  BOOLEAN fglmok;
1218  fglmVector v;
1219 
1220  idealFunctionals L( 100, (currRing->N) );
1221  // STICKYPROT("calculating normal form\n");
1222  // poly p = kNF( sourceIdeal, currRing->qideal, quot );
1223  // STICKYPROT("calculating functionals\n");
1224  fglmok = CalculateFunctionals( sourceIdeal, L, quot, v );
1225  if ( fglmok == TRUE ) {
1226  // STICKYPROT("calculating groebner basis\n");
1227  destIdeal= GroebnerViaFunctionals( L, v );
1228  }
1229  return fglmok;
1230 }
#define TRUE
Definition: auxiliary.h:144
static ideal GroebnerViaFunctionals(const idealFunctionals &l, fglmVector iv=fglmVector())
Definition: fglmzero.cc:1048
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
static BOOLEAN CalculateFunctionals(const ideal &theIdeal, idealFunctionals &l)
Definition: fglmzero.cc:675
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int BOOLEAN
Definition: auxiliary.h:131
BOOLEAN fglmzero ( ring  sourceRing,
ideal &  sourceIdeal,
ring  destRing,
ideal &  destIdeal,
BOOLEAN  switchBack,
BOOLEAN  deleteIdeal 
)

Definition at line 1190 of file fglmzero.cc.

1191 {
1192  ring initialRing = currRing;
1193  BOOLEAN fglmok;
1194 
1195  if ( currRing != sourceRing )
1196  {
1197  rChangeCurrRing( sourceRing );
1198  }
1199  idealFunctionals L( 100, rVar(currRing) );
1200  fglmok = CalculateFunctionals( sourceIdeal, L );
1201  if ( deleteIdeal == TRUE )
1202  idDelete( & sourceIdeal );
1203  rChangeCurrRing( destRing );
1204  if ( fglmok == TRUE )
1205  {
1206  L.map( sourceRing );
1207  destIdeal= GroebnerViaFunctionals( L );
1208  }
1209  if ( (switchBack) && (currRing != initialRing) )
1210  rChangeCurrRing( initialRing );
1211  return fglmok;
1212 }
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:537
#define TRUE
Definition: auxiliary.h:144
static ideal GroebnerViaFunctionals(const idealFunctionals &l, fglmVector iv=fglmVector())
Definition: fglmzero.cc:1048
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
static BOOLEAN CalculateFunctionals(const ideal &theIdeal, idealFunctionals &l)
Definition: fglmzero.cc:675
void rChangeCurrRing(ring r)
Definition: polys.cc:14
int BOOLEAN
Definition: auxiliary.h:131
static ideal FindUnivariatePolys ( const idealFunctionals l)
static

Definition at line 1120 of file fglmzero.cc.

1121 {
1122  fglmVector v;
1123  fglmVector p;
1124  ideal destIdeal = idInit( (currRing->N), 1 );
1125 
1126  int i;
1127  BOOLEAN isZero;
1128  int *varpermutation = (int*)omAlloc( ((currRing->N)+1)*sizeof(int) );
1129  ideal perm = idMaxIdeal(1);
1130  intvec *iv = idSort(perm,TRUE);
1131  idDelete(&perm);
1132  for(i = (currRing->N); i > 0; i--) varpermutation[(currRing->N)+1-i] = (*iv)[i-1];
1133  delete iv;
1134 
1135  for (i= 1; i <= (currRing->N); i++ )
1136  {
1137  // main loop
1138  STICKYPROT2( "(%i)", i /*varpermutation[i]*/);
1139  gaussReducer gauss( l.dimen() );
1140  isZero= FALSE;
1141  v= fglmVector( l.dimen(), 1 );
1142  while ( !isZero )
1143  {
1144  if ( (isZero= gauss.reduce( v )))
1145  {
1146  STICKYPROT( "+" );
1147  p= gauss.getDependence();
1148  number gcd= p.gcd();
1149  if ( ! nIsOne( gcd ) )
1150  {
1151  p /= gcd;
1152  }
1153  nDelete( & gcd );
1154  int k;
1155  poly temp = NULL;
1156  poly result;
1157  for ( k= p.size(); k > 0; k-- ) {
1158  number n = nCopy( p.getconstelem( k ) );
1159  if ( ! nIsZero( n ) ) {
1160  if ( temp == NULL ) {
1161  result= pOne();
1162  temp= result;
1163  }
1164  else {
1165  temp->next= pOne();
1166  pIter( temp );
1167  }
1168  pSetCoeff( temp, n );
1169  pSetExp( temp, i /*varpermutation[i]*/, k-1 );
1170  pSetm( temp );
1171  }
1172  }
1173  if ( ! nGreaterZero( pGetCoeff( result ) ) ) result= pNeg( result );
1174  (destIdeal->m)[i-1]= result;
1175  }
1176  else {
1177  STICKYPROT( "." );
1178  gauss.store();
1179  v= l.multiply( v, i /*varpermutation[i]*/ );
1180  }
1181  }
1182  }
1183  STICKYPROT( "\n" );
1184  omFreeSize( (ADDRESS)varpermutation, ((currRing->N)+1)*sizeof(int) );
1185  return destIdeal;
1186 }
#define idMaxIdeal(D)
initialise the maximal ideal (at 0)
Definition: ideals.h:35
number gcd() const
Definition: fglmvec.cc:455
#define pSetm(p)
Definition: polys.h:241
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
#define pSetExp(p, i, v)
Definition: polys.h:42
#define FALSE
Definition: auxiliary.h:140
return P p
Definition: myNF.cc:203
int size() const
Definition: fglmvec.cc:204
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define pNeg(p)
Definition: polys.h:169
#define TRUE
Definition: auxiliary.h:144
#define nIsOne(n)
Definition: numbers.h:25
void * ADDRESS
Definition: auxiliary.h:161
number getconstelem(int i) const
Definition: fglmvec.cc:443
int k
Definition: cfEzgcd.cc:93
#define STICKYPROT2(msg, arg)
Definition: fglmzero.cc:53
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:181
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:51
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define pIter(p)
Definition: monomials.h:44
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
Definition: intvec.h:14
#define nGreaterZero(n)
Definition: numbers.h:27
fglmVector multiply(const fglmVector v, int var) const
Definition: fglmzero.cc:269
int i
Definition: cfEzgcd.cc:123
#define pOne()
Definition: polys.h:286
#define nDelete(n)
Definition: numbers.h:16
int dimen() const
Definition: fglmzero.cc:90
#define STICKYPROT(msg)
Definition: fglmzero.cc:51
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define nIsZero(n)
Definition: numbers.h:19
#define NULL
Definition: omList.c:10
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define nCopy(n)
Definition: numbers.h:15
bool isZero(const CFArray &A)
checks if entries of A are zero
polyrec * poly
Definition: hilb.h:10
int perm[100]
int BOOLEAN
Definition: auxiliary.h:131
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
return result
Definition: facAbsBiFact.cc:76
BOOLEAN FindUnivariateWrapper ( ideal  source,
ideal &  destIdeal 
)

Definition at line 1233 of file fglmzero.cc.

1234 {
1235  BOOLEAN fglmok;
1236 
1237  idealFunctionals L( 100, (currRing->N) );
1238  fglmok = CalculateFunctionals( source, L );
1239  if ( fglmok == TRUE ) {
1240  destIdeal= FindUnivariatePolys( L );
1241  return TRUE;
1242  }
1243  else
1244  return FALSE;
1245 }
#define FALSE
Definition: auxiliary.h:140
#define TRUE
Definition: auxiliary.h:144
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
static ideal FindUnivariatePolys(const idealFunctionals &l)
Definition: fglmzero.cc:1120
static BOOLEAN CalculateFunctionals(const ideal &theIdeal, idealFunctionals &l)
Definition: fglmzero.cc:675
int BOOLEAN
Definition: auxiliary.h:131
static ideal GroebnerViaFunctionals ( const idealFunctionals l,
fglmVector  iv = fglmVector() 
)
static

Definition at line 1048 of file fglmzero.cc.

1056 {
1057  fglmDdata data( l.dimen() );
1058 
1059  // insert pOne() and update workinglist according to iv:
1060  fglmVector initv;
1061  if ( iv.isZero() ) {
1062  // STICKYPROT("initv is zero\n");
1063  initv = fglmVector( l.dimen(), 1 );
1064  }
1065  else {
1066  // STICKYPROT("initv is not zero\n");
1067  initv = iv;
1068  }
1069 
1070  poly one = pOne();
1071  data.updateCandidates( one, initv );
1072  number nOne = nInit( 1 );
1073  data.newBasisElem( one, initv, fglmVector( 1, 1 ), nOne );
1074  STICKYPROT( "." );
1075  while ( data.candidatesLeft() == TRUE ) {
1076  fglmDelem candidate = data.nextCandidate();
1077  if ( candidate.isBasisOrEdge() == TRUE ) {
1078  // Now we have the chance to find a new groebner polynomial
1079 
1080  // v is the vector-representation of candidate.monom
1081  // some elements of v are zeroed in data.gaussreduce(). Which
1082  // ones and how this was done is stored in p.
1083  // originalV containes the unchanged v, which is later inserted
1084  // into the working list (via data.updateCandidates().
1085  fglmVector v = l.multiply( candidate.v, candidate.var );
1086  fglmVector originalV = v;
1087  fglmVector p( data.getBasisSize()+1, data.getBasisSize()+1 );
1088  number pdenom = NULL;
1089  data.gaussreduce( v, p, pdenom );
1090  if ( v.isZero() ) {
1091  // Now v is linear dependend to the already found basis elements.
1092  // This means that v (rsp. candidate.monom) is the leading
1093  // monomial of the next groebner-basis polynomial.
1094  data.newGroebnerPoly( p, candidate.monom );
1095  nDelete( & pdenom );
1096  STICKYPROT( "+" );
1097  }
1098  else {
1099  // no linear dependence could be found, so v ( rsp. monom )
1100  // is a basis monomial. We store the zeroed version ( i.e. v
1101  // and not originalV ) as well as p, the denomiator and all
1102  // the other stuff.
1103  // erst updateCandidates, dann newBasisELem!!!
1104  data.updateCandidates( candidate.monom, originalV );
1105  data.newBasisElem( candidate.monom, v, p, pdenom );
1106  STICKYPROT( "." );
1107  }
1108  }
1109  else {
1110  STICKYPROT( "-" );
1111  candidate.cleanup();
1112  }
1113  } //. while data.candidatesLeft()
1114  STICKYPROT( "\n" );
1115  return ( data.buildIdeal() );
1116 }
poly monom
Definition: fglm.h:49
return P p
Definition: myNF.cc:203
#define TRUE
Definition: auxiliary.h:144
Definition: fglm.h:46
fglmVector v
Definition: fglm.h:50
int isZero()
Definition: fglmvec.cc:292
BOOLEAN isBasisOrEdge() const
Definition: fglm.h:56
fglmVector multiply(const fglmVector v, int var) const
Definition: fglmzero.cc:269
#define pOne()
Definition: polys.h:286
#define nDelete(n)
Definition: numbers.h:16
int dimen() const
Definition: fglmzero.cc:90
#define STICKYPROT(msg)
Definition: fglmzero.cc:51
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define NULL
Definition: omList.c:10
void cleanup()
Definition: fglmzero.cc:715
int var
Definition: fglm.h:52
polyrec * poly
Definition: hilb.h:10
#define nInit(i)
Definition: numbers.h:24
void internalCalculateFunctionals ( const ideal  ,
idealFunctionals l,
fglmSdata data 
)

Definition at line 611 of file fglmzero.cc.

613 {
614 
615  // insert pOne() into basis and update the workingList:
616  poly one = pOne();
617  data.newBasisElem( one );
618  data.updateCandidates();
619 
620  STICKYPROT(".");
621  while ( data.candidatesLeft() == TRUE ) {
622  fglmSelem candidate = data.nextCandidate();
623  if ( candidate.isBasisOrEdge() == TRUE ) {
624  int edge = data.getEdgeNumber( candidate.monom );
625  if ( edge != 0 )
626  {
627  // now candidate is an edge, i.e. we know its normalform:
628  // NF(p) = - ( tail(p)/LC(p) )
629  poly nf = data.getSpanPoly( edge );
630  pNorm( nf );
631  pLmDelete(&nf); //. deletes the leadingmonomial
632  nf= pNeg( nf );
633  fglmVector nfv = data.getVectorRep( nf );
634  l.insertCols( candidate.divisors, nfv );
635  data.newBorderElem( candidate.monom, nfv );
636  pDelete( &nf );
637  STICKYPROT( "+" );
638  }
639  else
640  {
641  int basis= data.newBasisElem( candidate.monom );
642  data.updateCandidates();
643  l.insertCols( candidate.divisors, basis );
644  STICKYPROT( "." );
645  }
646  }
647  else {
648  int var = 0;
649  fglmVector temp = data.getBorderDiv( candidate.monom, var );
650  fglmASSERT( var > 0, "this should never happen" );
651  fglmVector nfv = l.addCols( var, data.getBasisSize(), temp );
652  data.newBorderElem( candidate.monom, nfv );
653  l.insertCols( candidate.divisors, nfv );
654  STICKYPROT( "-" );
655  }
656  candidate.cleanup();
657  } //. while ( data.candidatesLeft() == TRUE )
658  l.endofConstruction();
659  STICKYPROT2( "\nvdim= %i\n", data.getBasisSize() );
660  return;
661 }
int * divisors
Definition: fglm.h:30
BOOLEAN candidatesLeft() const
Definition: fglmzero.cc:365
fglmSelem nextCandidate()
Definition: fglmzero.cc:469
#define pNeg(p)
Definition: polys.h:169
void cleanup()
Definition: fglmzero.cc:332
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define TRUE
Definition: auxiliary.h:144
void endofConstruction()
Definition: fglmzero.cc:139
#define STICKYPROT2(msg, arg)
Definition: fglmzero.cc:53
void insertCols(int *divisors, int to)
Definition: fglmzero.cc:192
Definition: gnumpfl.cc:60
fglmVector addCols(const int var, int basisSize, const fglmVector v) const
Definition: fglmzero.cc:243
int newBasisElem(poly &p)
Definition: fglmzero.cc:426
poly monom
Definition: fglm.h:31
#define pOne()
Definition: polys.h:286
#define fglmASSERT(ignore1, ignore2)
Definition: fglmzero.cc:54
void newBorderElem(poly &m, fglmVector v)
Definition: fglmzero.cc:443
#define STICKYPROT(msg)
Definition: fglmzero.cc:51
int getEdgeNumber(const poly m) const
Definition: fglmzero.cc:531
Definition: fglm.h:27
poly getSpanPoly(int number) const
Definition: fglmzero.cc:369
void updateCandidates()
Definition: fglmzero.cc:481
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:334
#define pDelete(p_ptr)
Definition: polys.h:157
fglmVector getVectorRep(const poly m)
Definition: fglmzero.cc:545
BOOLEAN isBasisOrEdge() const
Definition: fglm.h:36
int getBasisSize() const
Definition: fglmzero.cc:362
fglmVector getBorderDiv(const poly m, int &var) const
Definition: fglmzero.cc:580
polyrec * poly
Definition: hilb.h:10