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 "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

◆ matElem

struct matElem

The idealFunctionals.

Definition at line 61 of file fglmzero.cc.

Data Fields
number elem
int row

◆ matHeader

struct matHeader

Definition at line 67 of file fglmzero.cc.

Data Fields
matElem * elems
BOOLEAN owner
int size

Macro Definition Documentation

◆ fglmASSERT

#define fglmASSERT (   ignore1,
  ignore2 
)

Definition at line 52 of file fglmzero.cc.

◆ PROT

#define PROT (   msg)

Definition at line 48 of file fglmzero.cc.

◆ PROT2

#define PROT2 (   msg,
  arg 
)

Definition at line 50 of file fglmzero.cc.

◆ STICKYPROT

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

Definition at line 49 of file fglmzero.cc.

◆ STICKYPROT2

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

Definition at line 51 of file fglmzero.cc.

Function Documentation

◆ CalculateFunctionals() [1/2]

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

Definition at line 673 of file fglmzero.cc.

674 {
675  fglmSdata data( theIdeal );
676  internalCalculateFunctionals( theIdeal, l, data );
677  return ( data.state() );
678 }
void internalCalculateFunctionals(const ideal, idealFunctionals &l, fglmSdata &data)
Definition: fglmzero.cc:609

◆ CalculateFunctionals() [2/2]

static BOOLEAN CalculateFunctionals ( const ideal &  theIdeal,
idealFunctionals l,
poly &  p,
fglmVector v 
)
static

Definition at line 681 of file fglmzero.cc.

683 {
684  fglmSdata data( theIdeal );
685  internalCalculateFunctionals( theIdeal, l, data );
686  // STICKYPROT("Calculating vector rep\n");
687  v = data.getVectorRep( p );
688  // if ( v.isZero() )
689  // STICKYPROT("vectorrep is 0\n");
690  return ( data.state() );
691 }
void internalCalculateFunctionals(const ideal, idealFunctionals &l, fglmSdata &data)
Definition: fglmzero.cc:609
int p
Definition: cfModGcd.cc:4019

◆ fglmquot()

BOOLEAN fglmquot ( ideal  sourceIdeal,
poly  quot,
ideal &  destIdeal 
)

Definition at line 1218 of file fglmzero.cc.

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

◆ fglmzero()

BOOLEAN fglmzero ( ring  sourceRing,
ideal &  sourceIdeal,
ring  destRing,
ideal &  destIdeal,
BOOLEAN  switchBack,
BOOLEAN  deleteIdeal 
)

Definition at line 1193 of file fglmzero.cc.

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

◆ FindUnivariatePolys()

static ideal FindUnivariatePolys ( const idealFunctionals l)
static

Definition at line 1118 of file fglmzero.cc.

1119 {
1120  fglmVector v;
1121  fglmVector p;
1122  ideal destIdeal = idInit( (currRing->N), 1 );
1123 
1124  int i;
1125  BOOLEAN isZero;
1126  int *varpermutation = (int*)omAlloc( ((currRing->N)+1)*sizeof(int) );
1127  ideal perm = idMaxIdeal(1);
1128  intvec *iv = idSort(perm,TRUE);
1129  idDelete(&perm);
1130  for(i = (currRing->N); i > 0; i--) varpermutation[(currRing->N)+1-i] = (*iv)[i-1];
1131  delete iv;
1132 
1133  for (i= 1; i <= (currRing->N); i++ )
1134  {
1135  // main loop
1136  STICKYPROT2( "(%i)", i /*varpermutation[i]*/);
1137  gaussReducer gauss( l.dimen() );
1138  isZero= FALSE;
1139  v= fglmVector( l.dimen(), 1 );
1140  while ( !isZero )
1141  {
1142  if ( (isZero= gauss.reduce( v )))
1143  {
1144  STICKYPROT( "+" );
1145  p= gauss.getDependence();
1146  number gcd= p.gcd();
1147  if ( ! nIsOne( gcd ) )
1148  {
1149  p /= gcd;
1150  }
1151  nDelete( & gcd );
1152  int k;
1153  poly temp = NULL;
1154  poly result=NULL;
1155  for ( k= p.size(); k > 0; k-- )
1156  {
1157  number n = nCopy( p.getconstelem( k ) );
1158  if ( ! nIsZero( n ) )
1159  {
1160  if ( temp == NULL )
1161  {
1162  result= pOne();
1163  temp= result;
1164  }
1165  else
1166  {
1167  temp->next= pOne();
1168  pIter( temp );
1169  }
1170  pSetCoeff( temp, n );
1171  pSetExp( temp, i /*varpermutation[i]*/, k-1 );
1172  pSetm( temp );
1173  }
1174  }
1175  if ( ! nGreaterZero( pGetCoeff( result ) ) ) result= pNeg( result );
1176  (destIdeal->m)[i-1]= result;
1177  }
1178  else
1179  {
1180  STICKYPROT( "." );
1181  gauss.store();
1182  v= l.multiply( v, i /*varpermutation[i]*/ );
1183  }
1184  }
1185  }
1186  STICKYPROT( "\n" );
1187  omFreeSize( (ADDRESS)varpermutation, ((currRing->N)+1)*sizeof(int) );
1188  return destIdeal;
1189 }
#define idMaxIdeal(D)
initialise the maximal ideal (at 0)
Definition: ideals.h:33
#define pSetm(p)
Definition: polys.h:267
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define pSetExp(p, i, v)
Definition: polys.h:42
#define FALSE
Definition: auxiliary.h:96
int size() const
Definition: fglmvec.cc:207
number getconstelem(int i) const
Definition: fglmvec.cc:446
number gcd() const
Definition: fglmvec.cc:458
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
int dimen() const
Definition: fglmzero.cc:88
#define pNeg(p)
Definition: polys.h:194
#define TRUE
Definition: auxiliary.h:100
#define nIsOne(n)
Definition: numbers.h:25
void * ADDRESS
Definition: auxiliary.h:135
int k
Definition: cfEzgcd.cc:92
#define STICKYPROT2(msg, arg)
Definition: fglmzero.cc:51
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:186
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
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define pIter(p)
Definition: monomials.h:37
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Definition: intvec.h:19
#define nGreaterZero(n)
Definition: numbers.h:27
int i
Definition: cfEzgcd.cc:125
#define pOne()
Definition: polys.h:311
#define nDelete(n)
Definition: numbers.h:16
#define STICKYPROT(msg)
Definition: fglmzero.cc:49
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define nIsZero(n)
Definition: numbers.h:19
#define NULL
Definition: omList.c:12
int gcd(int a, int b)
Definition: walkSupport.cc:836
#define nCopy(n)
Definition: numbers.h:15
bool isZero(const CFArray &A)
checks if entries of A are zero
int p
Definition: cfModGcd.cc:4019
int BOOLEAN
Definition: auxiliary.h:87
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
return result
Definition: facAbsBiFact.cc:76
fglmVector multiply(const fglmVector v, int var) const
Definition: fglmzero.cc:267

◆ FindUnivariateWrapper()

BOOLEAN FindUnivariateWrapper ( ideal  source,
ideal &  destIdeal 
)

Definition at line 1236 of file fglmzero.cc.

1237 {
1238  BOOLEAN fglmok;
1239 
1240  idealFunctionals L( 100, (currRing->N) );
1241  fglmok = CalculateFunctionals( source, L );
1242  if ( fglmok == TRUE ) {
1243  destIdeal= FindUnivariatePolys( L );
1244  return TRUE;
1245  }
1246  else
1247  return FALSE;
1248 }
#define FALSE
Definition: auxiliary.h:96
#define TRUE
Definition: auxiliary.h:100
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
static ideal FindUnivariatePolys(const idealFunctionals &l)
Definition: fglmzero.cc:1118
static BOOLEAN CalculateFunctionals(const ideal &theIdeal, idealFunctionals &l)
Definition: fglmzero.cc:673
int BOOLEAN
Definition: auxiliary.h:87

◆ GroebnerViaFunctionals()

static ideal GroebnerViaFunctionals ( const idealFunctionals l,
fglmVector  iv = fglmVector() 
)
static

Definition at line 1046 of file fglmzero.cc.

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

◆ internalCalculateFunctionals()

void internalCalculateFunctionals ( const ideal  ,
idealFunctionals l,
fglmSdata data 
)

Definition at line 609 of file fglmzero.cc.

611 {
612 
613  // insert pOne() into basis and update the workingList:
614  poly one = pOne();
615  data.newBasisElem( one );
616  data.updateCandidates();
617 
618  STICKYPROT(".");
619  while ( data.candidatesLeft() == TRUE ) {
620  fglmSelem candidate = data.nextCandidate();
621  if ( candidate.isBasisOrEdge() == TRUE ) {
622  int edge = data.getEdgeNumber( candidate.monom );
623  if ( edge != 0 )
624  {
625  // now candidate is an edge, i.e. we know its normalform:
626  // NF(p) = - ( tail(p)/LC(p) )
627  poly nf = data.getSpanPoly( edge );
628  pNorm( nf );
629  pLmDelete(&nf); //. deletes the leadingmonomial
630  nf= pNeg( nf );
631  fglmVector nfv = data.getVectorRep( nf );
632  l.insertCols( candidate.divisors, nfv );
633  data.newBorderElem( candidate.monom, nfv );
634  pDelete( &nf );
635  STICKYPROT( "+" );
636  }
637  else
638  {
639  int basis= data.newBasisElem( candidate.monom );
640  data.updateCandidates();
641  l.insertCols( candidate.divisors, basis );
642  STICKYPROT( "." );
643  }
644  }
645  else {
646  int var = 0;
647  fglmVector temp = data.getBorderDiv( candidate.monom, var );
648  fglmASSERT( var > 0, "this should never happen" );
649  fglmVector nfv = l.addCols( var, data.getBasisSize(), temp );
650  data.newBorderElem( candidate.monom, nfv );
651  l.insertCols( candidate.divisors, nfv );
652  STICKYPROT( "-" );
653  }
654  candidate.cleanup();
655  } //. while ( data.candidatesLeft() == TRUE )
656  l.endofConstruction();
657  STICKYPROT2( "\nvdim= %i\n", data.getBasisSize() );
658  return;
659 }
int * divisors
Definition: fglm.h:30
fglmSelem nextCandidate()
Definition: fglmzero.cc:467
#define pNeg(p)
Definition: polys.h:194
void cleanup()
Definition: fglmzero.cc:330
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define TRUE
Definition: auxiliary.h:100
void endofConstruction()
Definition: fglmzero.cc:137
BOOLEAN isBasisOrEdge() const
Definition: fglm.h:36
#define STICKYPROT2(msg, arg)
Definition: fglmzero.cc:51
void insertCols(int *divisors, int to)
Definition: fglmzero.cc:190
BOOLEAN candidatesLeft() const
Definition: fglmzero.cc:363
Definition: gnumpfl.cc:26
poly getSpanPoly(int number) const
Definition: fglmzero.cc:367
int newBasisElem(poly &p)
Definition: fglmzero.cc:424
poly monom
Definition: fglm.h:31
#define pOne()
Definition: polys.h:311
#define fglmASSERT(ignore1, ignore2)
Definition: fglmzero.cc:52
void newBorderElem(poly &m, fglmVector v)
Definition: fglmzero.cc:441
#define STICKYPROT(msg)
Definition: fglmzero.cc:49
int getEdgeNumber(const poly m) const
Definition: fglmzero.cc:529
fglmVector getBorderDiv(const poly m, int &var) const
Definition: fglmzero.cc:578
Definition: fglm.h:27
void updateCandidates()
Definition: fglmzero.cc:479
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:359
#define pDelete(p_ptr)
Definition: polys.h:182
fglmVector getVectorRep(const poly m)
Definition: fglmzero.cc:543
int getBasisSize() const
Definition: fglmzero.cc:360
fglmVector addCols(const int var, int basisSize, const fglmVector v) const
Definition: fglmzero.cc:241