fglmzero.cc
Go to the documentation of this file.
1 // emacs edit mode for this file is -*- C++ -*-
2 
3 /****************************************
4 * Computer Algebra System SINGULAR *
5 ****************************************/
6 /*
7 * ABSTRACT - The FGLM-Algorithm
8 * Implementation of the fglm algorithm for 0-dimensional ideals,
9 * based on an idea by Faugere/Gianni/Lazard and Mora.
10 * The procedure CalculateFunctionals calculates the functionals
11 * which define the given ideal in the source ring. They build the
12 * input for GroebnerViaFunctionals, which defines the reduced
13 * groebner basis for the ideal in the destination ring.
14 */
15 
16 /* Changes:
17  * o FindUnivariatePolys added
18  */
19 
20 
21 
22 
23 #include "kernel/mod2.h"
24 
25 
26 // assumes, that NOSTREAMIO is set in factoryconf.h, which is included
27 // by templates/list.h.
28 
29 #include "factory/factory.h"
30 
33 
34 #include "omalloc/omalloc.h"
35 
36 #include "misc/options.h"
37 #include "misc/intvec.h"
38 
39 #include "polys/monomials/maps.h"
40 #include "polys/monomials/ring.h"
41 
42 #include "kernel/polys.h"
43 #include "kernel/ideals.h"
44 #include "kernel/GBEngine/kstd1.h"
45 
46 #include "fglm.h"
47 #include "fglmvec.h"
48 #include "fglmgauss.h"
49 
50 #define PROT(msg)
51 #define STICKYPROT(msg) if (BTEST1(OPT_PROT)) Print(msg)
52 #define PROT2(msg,arg)
53 #define STICKYPROT2(msg,arg) if (BTEST1(OPT_PROT)) Print(msg,arg)
54 #define fglmASSERT(ignore1,ignore2)
55 
56 
57 
58 // internal Version: 1.3.1.12
59 // ============================================================
60 //! The idealFunctionals
61 // ============================================================
62 
63 struct matElem
64 {
65  int row;
66  number elem;
67 };
68 
69 struct matHeader
70 {
71  int size;
74 };
75 
77 {
78 private:
79  int _block;
80  int _max;
81  int _size;
82  int _nfunc;
83  int * currentSize;
85  matHeader * grow( int var );
86 public:
87  idealFunctionals( int blockSize, int numFuncs );
89 
90  int dimen() const { fglmASSERT( _size>0, "called too early"); return _size; }
91  void endofConstruction();
92  void map( ring source );
93  void insertCols( int * divisors, int to );
94  void insertCols( int * divisors, const fglmVector to );
95  fglmVector addCols( const int var, int basisSize, const fglmVector v ) const;
96  fglmVector multiply( const fglmVector v, int var ) const;
97 };
98 
99 
100 idealFunctionals::idealFunctionals( int blockSize, int numFuncs )
101 {
102  int k;
103  _block= blockSize;
104  _max= _block;
105  _size= 0;
106  _nfunc= numFuncs;
107 
108  currentSize= (int *)omAlloc0( _nfunc*sizeof( int ) );
109  //for ( k= _nfunc-1; k >= 0; k-- )
110  // currentSize[k]= 0;
111 
112  func= (matHeader **)omAlloc( _nfunc*sizeof( matHeader * ) );
113  for ( k= _nfunc-1; k >= 0; k-- )
114  func[k]= (matHeader *)omAlloc( _max*sizeof( matHeader ) );
115 }
116 
118 {
119  int k;
120  int l;
121  int row;
122  matHeader * colp;
123  matElem * elemp;
124  for ( k= _nfunc-1; k >= 0; k-- ) {
125  for ( l= _size-1, colp= func[k]; l >= 0; l--, colp++ ) {
126  if ( ( colp->owner == TRUE ) && ( colp->size > 0 ) ) {
127  for ( row= colp->size-1, elemp= colp->elems; row >= 0; row--, elemp++ )
128  nDelete( & elemp->elem );
129  omFreeSize( (ADDRESS)colp->elems, colp->size*sizeof( matElem ) );
130  }
131  }
132  omFreeSize( (ADDRESS)func[k], _max*sizeof( matHeader ) );
133  }
134  omFreeSize( (ADDRESS)func, _nfunc*sizeof( matHeader * ) );
135  omFreeSize( (ADDRESS)currentSize, _nfunc*sizeof( int ) );
136 }
137 
138 void
140 {
141  _size= currentSize[0];
142 }
143 
144 void
145 idealFunctionals::map( ring source )
146 {
147  // maps from ring source to currentRing.
148  int var, col, row;
149  matHeader * colp;
150  matElem * elemp;
151  number newelem;
152 
153  int * perm = (int *)omAlloc0( (_nfunc+1)*sizeof( int ) );
154  maFindPerm( source->names, source->N, NULL, 0, currRing->names,
155  currRing->N, NULL, 0, perm, NULL , currRing->cf->type);
156  nMapFunc nMap=n_SetMap( source->cf, currRing->cf);
157 
158  matHeader ** temp = (matHeader **)omAlloc( _nfunc*sizeof( matHeader * ));
159  for ( var= 0; var < _nfunc; var ++ ) {
160  for ( col= 0, colp= func[var]; col < _size; col++, colp++ ) {
161  if ( colp->owner == TRUE ) {
162  for ( row= colp->size-1, elemp= colp->elems; row >= 0;
163  row--, elemp++ )
164  {
165  newelem= nMap( elemp->elem, source->cf, currRing->cf );
166  nDelete( & elemp->elem );
167  elemp->elem= newelem;
168  }
169  }
170  }
171  temp[ perm[var+1]-1 ]= func[var];
172  }
173  omFreeSize( (ADDRESS)func, _nfunc*sizeof( matHeader * ) );
174  omFreeSize( (ADDRESS)perm, (_nfunc+1)*sizeof( int ) );
175  func= temp;
176 }
177 
178 matHeader *
180 {
181  if ( currentSize[var-1] == _max ) {
182  int k;
183  for ( k= _nfunc; k > 0; k-- )
184  func[k-1]= (matHeader *)omReallocSize( func[k-1], _max*sizeof( matHeader ), (_max + _block)*sizeof( matHeader ) );
185  _max+= _block;
186  }
187  currentSize[var-1]++;
188  return func[var-1] + currentSize[var-1] - 1;
189 }
190 
191 void
192 idealFunctionals::insertCols( int * divisors, int to )
193 {
194  fglmASSERT( 0 < divisors[0] && divisors[0] <= _nfunc, "wrong number of divisors" );
195  int k;
196  BOOLEAN owner = TRUE;
197  matElem * elems = (matElem *)omAlloc( sizeof( matElem ) );
198  elems->row= to;
199  elems->elem= nInit( 1 );
200  for ( k= divisors[0]; k > 0; k-- ) {
201  fglmASSERT( 0 < divisors[k] && divisors[k] <= _nfunc, "wrong divisor" );
202  matHeader * colp = grow( divisors[k] );
203  colp->size= 1;
204  colp->elems= elems;
205  colp->owner= owner;
206  owner= FALSE;
207  }
208 }
209 
210 
211 void
212 idealFunctionals::insertCols( int * divisors, const fglmVector to )
213 {
214  // divisors runs from divisors[0]..divisors[size-1]
215  fglmASSERT( 0 < divisors[0] && divisors[0] <= _nfunc, "wrong number of divisors" );
216  int k, l;
217  int numElems= to.numNonZeroElems();
218  matElem * elems;
219  matElem * elemp;
220  BOOLEAN owner = TRUE;
221  if ( numElems > 0 ) {
222  elems= (matElem *)omAlloc( numElems * sizeof( matElem ) );
223  for ( k= 1, l= 1, elemp= elems; k <= numElems; k++, elemp++ ) {
224  while ( nIsZero( to.getconstelem(l) ) ) l++;
225  elemp->row= l;
226  elemp->elem= nCopy( to.getconstelem( l ) );
227  l++; // hochzaehlen, damit wir nicht noch einmal die gleiche Stelle testen
228  }
229  }
230  else
231  elems= NULL;
232  for ( k= divisors[0]; k > 0; k-- ) {
233  fglmASSERT( 0 < divisors[k] && divisors[k] <= _nfunc, "wrong divisor" );
234  matHeader * colp = grow( divisors[k] );
235  colp->size= numElems;
236  colp->elems= elems;
237  colp->owner= owner;
238  owner= FALSE;
239  }
240 }
241 
243 idealFunctionals::addCols( const int var, int basisSize, const fglmVector v ) const
244 {
245  fglmVector result( basisSize );
246  matHeader * colp;
247  matElem * elemp;
248  number factor, temp;
249  int k, l;
250  int vsize = v.size();
251 
252  fglmASSERT( currentSize[var-1]+1 >= vsize, "wrong v.size()" );
253  for ( k= 1, colp= func[var-1]; k <= vsize; k++, colp++ ) {
254  factor= v.getconstelem( k );
255  if ( ! nIsZero( factor ) ) {
256  for ( l= colp->size-1, elemp= colp->elems; l >= 0; l--, elemp++ ) {
257  temp= nMult( factor, elemp->elem );
258  number newelem= nAdd( result.getconstelem( elemp->row ), temp );
259  nDelete( & temp );
260  nNormalize( newelem );
261  result.setelem( elemp->row, newelem );
262  }
263  }
264  }
265  return result;
266 }
267 
269 idealFunctionals::multiply( const fglmVector v, int var ) const
270 {
271  fglmASSERT( v.size() == _size, "multiply: v has wrong size");
272  fglmVector result( _size );
273  matHeader * colp;
274  matElem * elemp;
275  number factor, temp;
276  int k, l;
277  for ( k= 1, colp= func[var-1]; k <= _size; k++, colp++ ) {
278  factor= v.getconstelem( k );
279  if ( ! nIsZero( factor ) ) {
280  for ( l= colp->size-1, elemp= colp->elems; l >= 0; l--, elemp++ ) {
281  temp= nMult( factor, elemp->elem );
282  number newelem= nAdd( result.getconstelem( elemp->row ), temp );
283  nDelete( & temp );
284  nNormalize( newelem );
285  result.setelem( elemp->row, newelem );
286  }
287  }
288  }
289  return result;
290 }
291 
292 // ============================================================
293 //! The old basis
294 // ============================================================
295 
296 // Contains the data for a border-monomial, i.e. the monom itself
297 // ( as a Singular-poly ) and its normal-form, described by an
298 // fglmVector. The size of the Vector depends on the current size of
299 // the basis when the normalForm was computed.
300 // monom gets deleted when borderElem comes out of scope.
302 {
303 public:
304  poly monom;
306  borderElem() : monom(NULL), nf() {}
307  borderElem( poly p, fglmVector n ) : monom( p ), nf( n ) {}
308  ~borderElem() { if (monom!=NULL) pLmDelete(&monom); }
309 #ifndef HAVE_EXPLICIT_CONSTR
310  void insertElem( poly p, fglmVector n )
311  {
312  monom= p;
313  nf= n;
314  }
315 #endif
316 };
317 
318 // This class contains the relevant data for the 'candidates'
319 // The declaration of class fglmSelem is found in fglm.h
320 
321 fglmSelem::fglmSelem( poly p, int var ) : monom( p ), numVars( 0 )
322 {
323  for ( int k = (currRing->N); k > 0; k-- )
324  if ( pGetExp( monom, k ) > 0 )
325  numVars++;
326  divisors= (int *)omAlloc( (numVars+1)*sizeof( int ) );
327  divisors[0]= 0;
328  newDivisor( var );
329 }
330 
331 void
333 {
334  omFreeSize( (ADDRESS)divisors, (numVars+1)*sizeof( int ) );
335 }
336 
337 // The data-structure for the Functional-Finding-Algorithm.
339 {
340 private:
341  ideal theIdeal;
342  int idelems;
344 
345  int basisBS;
346  int basisMax;
348  polyset basis; //. rem: runs from basis[1]..basis[dimen]
349 
350  int borderBS;
353  borderElem * border; //. rem: runs from border[1]..border[dimen]
354 
357 public:
358  fglmSdata( const ideal thisIdeal );
359  ~fglmSdata();
360 
361  BOOLEAN state() const { return _state; };
362  int getBasisSize() const { return basisSize; };
363  int newBasisElem( poly & p );
364  void newBorderElem( poly & m, fglmVector v );
365  BOOLEAN candidatesLeft() const { return ( nlist.isEmpty() ? FALSE : TRUE ); }
366  fglmSelem nextCandidate();
367  void updateCandidates();
368  int getEdgeNumber( const poly m ) const;
369  poly getSpanPoly( int number ) const { return pCopy( (theIdeal->m)[number-1] ); }
370  fglmVector getVectorRep( const poly m );
371  fglmVector getBorderDiv( const poly m, int & var ) const;
372 };
373 
374 fglmSdata::fglmSdata( const ideal thisIdeal )
375 {
376  // An dieser Stelle kann die BlockSize ( =BS ) noch sinnvoller berechnet
377  // werden, jenachdem wie das Ideal aussieht.
378  theIdeal= thisIdeal;
379  idelems= IDELEMS( theIdeal );
380  varpermutation = (int*)omAlloc( ((currRing->N)+1)*sizeof(int) );
381  // Sort ring variables by increasing values (because of weighted orderings)
382  ideal perm = idMaxIdeal(1);
383  intvec *iv = idSort(perm,TRUE);
384  idDelete(&perm);
385  for(int i = (currRing->N); i > 0; i--) varpermutation[(currRing->N)+1-i] = (*iv)[i-1];
386  delete iv;
387 
388  basisBS= 100;
389  basisMax= basisBS;
390  basisSize= 0;
391  basis= (polyset)omAlloc( basisMax*sizeof( poly ) );
392 
393  borderBS= 100;
394  borderMax= borderBS;
395  borderSize= 0;
396 #ifndef HAVE_EXPLICIT_CONSTR
397  border= new borderElem[ borderMax ];
398 #else
399  border= (borderElem *)omAlloc( borderMax*sizeof( borderElem ) );
400 #endif
401  // rem: the constructors are called in newBorderElem().
402  _state= TRUE;
403 }
404 
406 {
407  omFreeSize( (ADDRESS)varpermutation, ((currRing->N)+1)*sizeof(int) );
408  for ( int k = basisSize; k > 0; k-- )
409  pLmDelete( basis + k ); //. rem: basis runs from basis[1]..basis[basisSize]
410  omFreeSize( (ADDRESS)basis, basisMax*sizeof( poly ) );
411 #ifndef HAVE_EXPLICIT_CONSTR
412  delete [] border;
413 #else
414  for ( int l = borderSize; l > 0; l-- )
415  // rem: the polys of borderElem are deleted via ~borderElem()
416  border[l].~borderElem();
417  omFreeSize( (ADDRESS)border, borderMax*sizeof( borderElem ) );
418 #endif
419 }
420 
421 // Inserts poly p without copying into basis, reAllocs Memory if necessary,
422 // increases basisSize and returns the new basisSize.
423 // Remember: The elements of basis are deleted via pDelete in ~fglmSdata!
424 // Sets m= NULL to indicate that now basis is ow(e?)ing the poly.
425 int
427 {
428  basisSize++;
429  if ( basisSize == basisMax ) {
430  basis= (polyset)omReallocSize( basis, basisMax*sizeof( poly ), (basisMax + basisBS)*sizeof( poly ) );
431  basisMax+= basisBS;
432  }
433  basis[basisSize]= m;
434  m= NULL;
435  return basisSize;
436 }
437 
438 // Inserts poly p and fglmvector v without copying into border, reAllocs Memory
439 // if necessary, and increases borderSize.
440 // Remember: The poly of border is deleted via ~borderElem in ~fglmSdata!
441 // Sets m= NULL to indicate that now border is ow(e?)ing the poly.
442 void
444 {
445  borderSize++;
446  if ( borderSize == borderMax ) {
447 #ifndef HAVE_EXPLICIT_CONSTR
448  borderElem * tempborder = new borderElem[ borderMax+borderBS ];
449  for ( int k = 0; k < borderMax; k++ ) {
450  tempborder[k]= border[k];
451  border[k].insertElem( NULL, fglmVector() );
452  }
453  delete [] border;
454  border= tempborder;
455 #else
456  border= (borderElem *)omReallocSize( border, borderMax*sizeof( borderElem ), (borderMax + borderBS)*sizeof( borderElem ) );
457 #endif
458  borderMax+= borderBS;
459  }
460 #ifndef HAVE_EXPLICIT_CONSTR
461  border[borderSize].insertElem( m, v );
462 #else
463  border[borderSize].borderElem( m, v );
464 #endif
465  m= NULL;
466 }
467 
468 fglmSelem
470 {
471  fglmSelem result = nlist.getFirst();
472  nlist.removeFirst();
473  return result;
474 }
475 
476 // Multiplies basis[basisSize] with all ringvariables and inserts the new monomials
477 // into the list of candidates, according to the given order. If a monomial already
478 // exists, then "insertions" and "divisors" are updated.
479 // Assumes that ringvar(varperm[k]) < ringvar(varperm[l]) for k > l
480 void
482 {
483  ListIterator<fglmSelem> list = nlist;
484  fglmASSERT( basisSize > 0 && basisSize < basisMax, "Error(1) in fglmSdata::updateCandidates - wrong bassSize" );
485  poly m = basis[basisSize];
486  poly newmonom = NULL;
487  int k = (currRing->N);
488  BOOLEAN done = FALSE;
489  int state = 0;
490  while ( k >= 1 )
491  {
492  newmonom = pCopy( m );
493  pIncrExp( newmonom, varpermutation[k] );
494  pSetm( newmonom );
495  done= FALSE;
496  while ( list.hasItem() && (!done) )
497  {
498  if ( (state= pCmp( list.getItem().monom, newmonom )) < 0 )
499  list++;
500  else done= TRUE;
501  }
502  if ( !done )
503  {
504  nlist.append( fglmSelem( newmonom, varpermutation[k] ) );
505  break;
506  }
507  if ( state == 0 )
508  {
509  list.getItem().newDivisor( varpermutation[k] );
510  pLmDelete(&newmonom);
511  }
512  else
513  {
514  list.insert( fglmSelem( newmonom, varpermutation[k] ) );
515  }
516  k--;
517  }
518  while ( --k >= 1 )
519  {
520  newmonom= pCopy( m ); // HIER
521  pIncrExp( newmonom, varpermutation[k] );
522  pSetm( newmonom );
523  nlist.append( fglmSelem( newmonom, varpermutation[k] ) );
524  }
525 }
526 
527 // if p == pHead( (theIdeal->m)[k] ) return k, 0 otherwise
528 // (Assumes that pLmEqual just checks the leading monomials without
529 // coefficients.)
530 int
531 fglmSdata::getEdgeNumber( const poly m ) const
532 {
533  for ( int k = idelems; k > 0; k-- )
534  if ( pLmEqual( m, (theIdeal->m)[k-1] ) )
535  return k;
536  return 0;
537 }
538 
539 // Returns the fglmVector v, s.t.
540 // p = v[1]*basis(1) + .. + v[basisSize]*basis(basisSize)
541 // So the size of v depends on the current size of the basis.
542 // Assumes that such an representation exists, i.e. all monoms in p have to be
543 // smaller than basis[basisSize] and that basis[k] < basis[l] for k < l.
546 {
547  fglmVector temp( basisSize );
548  poly m = p;
549  int num = basisSize;
550  while ( m != NULL ) {
551  int comp = pCmp( m, basis[num] );
552  if ( comp == 0 ) {
553  fglmASSERT( num > 0, "Error(1) in fglmSdata::getVectorRep" );
554  number newelem = nCopy( pGetCoeff( m ) );
555  temp.setelem( num, newelem );
556  num--;
557  pIter( m );
558  }
559  else {
560  if ( comp < 0 ) {
561  num--;
562  }
563  else {
564  // This is the place where we can detect if the sourceIdeal
565  // is not reduced. In this case m is not in basis[]. Since basis[]
566  // is ordered this is the case, if and only if basis[i]<m
567  // and basis[j]>m for all j>i
568  _state= FALSE;
569  return temp;
570  }
571  }
572  }
573  return temp;
574 }
575 
576 // Searches through the border for a monomoial bm which devides m and returns
577 // its normalform in vector representation.
578 // var contains the number of the variable v, s.t. bm = m * v
580 fglmSdata::getBorderDiv( const poly m, int & var ) const
581 {
582 // int num2 = borderSize;
583 // while ( num2 > 0 ) {
584 // poly temp = border[num2].monom;
585 // if ( pDivisibleBy( temp, m ) ) {
586 // poly divisor = pDivideM( m, temp );
587 // int var = pIsPurePower( divisor );
588 // if ( (var != 0) && (pGetCoeff( divisor, var ) == 1) ) {
589 // Print( "poly %s divides poly %s", pString( temp ), pString( m ) );
590 // }
591 // }
592 // num2--;
593 // }
594  int num = borderSize;
595  while ( num > 0 ) {
596  poly temp = border[num].monom;
597  if ( pDivisibleBy( temp, m ) ) {
598  var = (currRing->N);
599  while ( var > 0 ) {
600  if ( (pGetExp( m, var ) - pGetExp( temp, var )) == 1 )
601  return border[num].nf;
602  var--;
603  }
604  }
605  num--;
606  }
607  return fglmVector();
608 }
609 
610 void
611 internalCalculateFunctionals( const ideal /*& theIdeal*/, idealFunctionals & l,
612  fglmSdata & data )
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 }
662 
663 // Calculates the defining Functionals for the ideal "theIdeal" and
664 // returns them in "l".
665 // The ideal has to be zero-dimensional and reduced and has to be a
666 // real subset of the polynomal ring.
667 // In any case it has to be zero-dimensional and minimal (check this
668 // via fglmIdealcheck). Any minimal but not reduced ideal is detected.
669 // In this case it returns FglmNotReduced.
670 // If the base domain is Q, the leading coefficients of the polys
671 // have to be in Z.
672 // returns TRUE if the result is valid, FALSE if theIdeal
673 // is not reduced.
674 static BOOLEAN
675 CalculateFunctionals( const ideal & theIdeal, idealFunctionals & l )
676 {
677  fglmSdata data( theIdeal );
678  internalCalculateFunctionals( theIdeal, l, data );
679  return ( data.state() );
680 }
681 
682 static BOOLEAN
683 CalculateFunctionals( const ideal & theIdeal, idealFunctionals & l,
684  poly & p, fglmVector & v )
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 }
694 
695 // ============================================================
696 //! The new basis
697 // ============================================================
698 
699 // The declaration of class fglmDelem is found in fglm.h
700 
701 fglmDelem::fglmDelem( poly & m, fglmVector mv, int v ) : v( mv ), insertions( 0 ), var( v )
702 {
703  monom= m;
704  m= NULL;
705  for ( int k = (currRing->N); k > 0; k-- )
706  if ( pGetExp( monom, k ) > 0 )
707  insertions++;
708  // Wir gehen davon aus, dass ein fglmDelem direkt bei der Erzeugung
709  // auch in eine Liste eingefuegt wird. Daher wird hier automatisch
710  // newDivisor aufgerufen ( v teilt ja m )
711  newDivisor();
712 }
713 
714 void
716 {
717  if ( monom != NULL )
718  {
719  pLmDelete(&monom);
720  }
721 }
722 
724 {
725 public:
728  number pdenom;
729  number fac;
730 
731 #ifndef HAVE_EXPLICIT_CONSTR
732  oldGaussElem() : v(), p(), pdenom( NULL ), fac( NULL ) {}
733 #endif
734  oldGaussElem( const fglmVector newv, const fglmVector newp, number & newpdenom, number & newfac ) : v( newv ), p( newp ), pdenom( newpdenom ), fac( newfac )
735  {
736  newpdenom= NULL;
737  newfac= NULL;
738  }
739  ~oldGaussElem();
740 #ifndef HAVE_EXPLICIT_CONSTR
741  void insertElem( const fglmVector newv, const fglmVector newp, number & newpdenom, number & newfac )
742  {
743  v= newv;
744  p= newp;
745  pdenom= newpdenom;
746  fac= newfac;
747  newpdenom= NULL;
748  newfac= NULL;
749  }
750 #endif
751 };
752 
754 {
755  if (fac!=NULL) nDelete( & fac );
756  if (pdenom!=NULL) nDelete( & pdenom );
757 }
758 
759 
761 {
762 private:
763  int dimen;
765  BOOLEAN * isPivot; // [1]..[dimen]
766  int * perm; // [1]..[dimen]
767  int basisSize; //. the CURRENT basisSize, i.e. basisSize <= dimen
768  polyset basis; // [1]..[dimen]. The monoms of the new Vectorspace-basis
769 
771 
774  ideal destId;
775 
777 public:
778  fglmDdata( int dimension );
779  ~fglmDdata();
780 
781  int getBasisSize() const { return basisSize; }
782  BOOLEAN candidatesLeft() const { return ( nlist.isEmpty() ? FALSE : TRUE ); }
783  fglmDelem nextCandidate();
784  void newBasisElem( poly & m, fglmVector v, fglmVector p, number & denom );
785  void updateCandidates( poly m, const fglmVector v );
786  void newGroebnerPoly( fglmVector & v, poly & p );
787  void gaussreduce( fglmVector & v, fglmVector & p, number & denom );
788  ideal buildIdeal()
789  {
790  idSkipZeroes( destId );
791  return destId;
792  }
793 };
794 
796 {
797  int k;
798  dimen= dimension;
799  basisSize= 0;
800  //. All arrays run from [1]..[dimen], thus omAlloc( dimen + 1 )!
801 #ifndef HAVE_EXPLICIT_CONSTR
802  gauss= new oldGaussElem[ dimen+1 ];
803 #else
804  gauss= (oldGaussElem *)omAlloc( (dimen+1)*sizeof( oldGaussElem ) );
805 #endif
806  isPivot= (BOOLEAN *)omAlloc( (dimen+1)*sizeof( BOOLEAN ) );
807  for ( k= dimen; k > 0; k-- ) isPivot[k]= FALSE;
808  perm= (int *)omAlloc( (dimen+1)*sizeof( int ) );
809  basis= (polyset)omAlloc( (dimen+1)*sizeof( poly ) );
810  varpermutation = (int*)omAlloc( ((currRing->N)+1)*sizeof(int) );
811  // Sort ring variables by increasing values (because of weighted orderings)
812  ideal perm_id = idMaxIdeal(1);
813  intvec *iv = idSort(perm_id,TRUE);
814  idDelete(&perm_id);
815  for(int i = (currRing->N); i > 0; i--) varpermutation[(currRing->N)+1-i] = (*iv)[i-1];
816  delete iv;
817 
818  groebnerBS= 16;
819  groebnerSize= 0;
820  destId= idInit( groebnerBS, 1 );
821 }
822 
824 {
825  // STICKYPROT2("dimen= %i", dimen);
826  // STICKYPROT2("basisSize= %i", basisSize);
827  // fglmASSERT( dimen == basisSize, "Es wurden nicht alle BasisElemente gefunden!" );
828  int k;
829 #ifndef HAVE_EXPLICIT_CONSTR
830  delete [] gauss;
831 #else
832  // use basisSize instead of dimen because of fglmquot!
833  for ( k= basisSize; k > 0; k-- )
834  gauss[k].~oldGaussElem();
835  omFreeSize( (ADDRESS)gauss, (dimen+1)*sizeof( oldGaussElem ) );
836 #endif
837  omFreeSize( (ADDRESS)isPivot, (dimen+1)*sizeof( BOOLEAN ) );
838  omFreeSize( (ADDRESS)perm, (dimen+1)*sizeof( int ) );
839  // use basisSize instead of dimen because of fglmquot!
840  //. Remember: There is no poly in basis[0], thus k > 0
841  for ( k= basisSize; k > 0; k-- )
842  pLmDelete( basis[k]);
843  omFreeSize( (ADDRESS)basis, (dimen+1)*sizeof( poly ) );
844  omFreeSize( (ADDRESS)varpermutation, ((currRing->N)+1)*sizeof(int) );
845 }
846 
847 fglmDelem
849 {
850  fglmDelem result = nlist.getFirst();
851  nlist.removeFirst();
852  return result;
853 }
854 
855 void
856 fglmDdata::newBasisElem( poly & m, fglmVector v, fglmVector p, number & denom )
857 {
858 // inserts m as a new basis monom. m is NOT copied but directly inserted.
859 // returns m=NULL to indicate, that now basis is oweing m.
860  basisSize++;
861  basis[basisSize]= m;
862  m= NULL;
863  int k= 1;
864  while ( nIsZero(v.getconstelem(k)) || isPivot[k] ) {
865  k++;
866  }
867  fglmASSERT( k <= dimen, "Error(1) in fglmDdata::pivot-search");
868  number pivot= v.getconstelem( k );
869  int pivotcol = k;
870  k++;
871  while ( k <= dimen ) {
872  if ( ! nIsZero( v.getconstelem(k) ) && ! isPivot[k] ) {
873  if ( nGreater( v.getconstelem( k ), pivot ) ) {
874  pivot= v.getconstelem( k );
875  pivotcol= k;
876  }
877  }
878  k++;
879  }
880  fglmASSERT( ! nIsZero( pivot ), "Error(2) fglmDdata::Pivotelement ist Null" );
881  isPivot[ pivotcol ]= TRUE;
882  perm[basisSize]= pivotcol;
883 
884  pivot= nCopy( v.getconstelem( pivotcol ) );
885 #ifndef HAVE_EXPLICIT_CONSTR
886  gauss[basisSize].insertElem( v, p, denom, pivot );
887 #else
888  gauss[basisSize].oldGaussElem( v, p, denom, pivot );
889 #endif
890 }
891 
892 void
894 {
895  ListIterator<fglmDelem> list = nlist;
896  poly newmonom = NULL;
897  int k = (currRing->N);
898  BOOLEAN done = FALSE;
899  int state = 0;
900  while ( k >= 1 )
901  {
902  newmonom = pCopy( m );
903  pIncrExp( newmonom, varpermutation[k] );
904  pSetm( newmonom );
905  done= FALSE;
906  while ( list.hasItem() && (!done) )
907  {
908  if ( (state= pCmp( list.getItem().monom, newmonom )) < 0 )
909  list++;
910  else done= TRUE;
911  }
912  if ( !done )
913  {
914  nlist.append( fglmDelem( newmonom, v, k ) );
915  break;
916  }
917  if ( state == 0 )
918  {
919  list.getItem().newDivisor();
920  pLmDelete( & newmonom );
921  }
922  else
923  {
924  list.insert( fglmDelem( newmonom, v, k ) );
925  }
926  k--;
927  }
928  while ( --k >= 1 )
929  {
930  newmonom= pCopy( m );
931  pIncrExp( newmonom, varpermutation[k] );
932  pSetm( newmonom );
933  nlist.append( fglmDelem( newmonom, v, k ) );
934  }
935 }
936 
937 void
939 // Inserts gp = p[1]*basis(1)+..+p[basisSize]*basis(basisSize)+p[basisSize+1]*m as
940 // a new groebner polynomial for the ideal.
941 // All elements (monomials and coefficients) of gp are copied, instead of m.
942 // Assumes that p.length() == basisSize+1.
943 {
944  //. Baue das Polynom von oben nach unten:
945  fglmASSERT( p.size() == basisSize+1, "GP::newGroebnerPoly: p has wrong size" );
946  int k;
947  poly result = m;
948  poly temp = result;
949  m= NULL;
950  if ( nGetChar() > 0 ) {
951  number lead = nCopy( p.getconstelem( basisSize+1 ) );
952  p /= lead;
953  nDelete( & lead );
954  }
955  if ( nGetChar() == 0 ) {
956  number gcd= p.gcd();
957  fglmASSERT( ! nIsZero( gcd ), "FATAL: gcd and thus p is zero" );
958  if ( ! nIsOne( gcd ) )
959  p /= gcd;
960  nDelete( & gcd );
961  }
962  pSetCoeff( result, nCopy( p.getconstelem( basisSize+1 ) ) );
963  for ( k= basisSize; k > 0; k-- ) {
964  if ( ! nIsZero( p.getconstelem( k ) ) ) {
965  temp->next= pCopy( basis[k] );
966  pIter( temp );
967  pSetCoeff( temp, nCopy( p.getconstelem( k ) ) );
968  }
969  }
970  pSetm( result );
971  if ( ! nGreaterZero( pGetCoeff( result ) ) ) result= pNeg( result );
972  if ( groebnerSize == IDELEMS( destId ) ) {
973  pEnlargeSet( & destId->m, IDELEMS( destId ), groebnerBS );
974  IDELEMS( destId )+= groebnerBS;
975  }
976  (destId->m)[groebnerSize]= result;
977  groebnerSize++;
978 }
979 
980 void
982 {
983  int k;
984  number fac1, fac2;
985  number temp;
986  fglmASSERT( pdenom == NULL, "pdenom in gaussreduce should be NULL" );
987  pdenom= nInit( 1 );
988  number vdenom = v.clearDenom();
989  if ( ! nIsZero( vdenom ) && ! nIsOne( vdenom ) ) {
990  p.setelem( p.size(), vdenom );
991  }
992  else {
993  nDelete( &vdenom );
994  }
995  number gcd = v.gcd();
996  if ( ! nIsZero( gcd ) && ! nIsOne( gcd ) ) {
997  v /= gcd;
998  number temp= nMult( pdenom, gcd );
999  nDelete( &pdenom );
1000  pdenom= temp;
1001  }
1002  nDelete( & gcd );
1003 
1004  for ( k= 1; k <= basisSize; k++ ) {
1005 
1006  if ( ! v.elemIsZero( perm[k] ) ) {
1007  fac1= gauss[k].fac;
1008  fac2= nCopy( v.getconstelem( perm[k] ) );
1009  v.nihilate( fac1, fac2, gauss[k].v );
1010  fac1= nMult( fac1, gauss[k].pdenom );
1011  temp= nMult( fac2, pdenom );
1012  nDelete( &fac2 );
1013  fac2= temp;
1014  p.nihilate( fac1, fac2, gauss[k].p );
1015  temp= nMult( pdenom, gauss[k].pdenom );
1016  nDelete( &pdenom );
1017  pdenom= temp;
1018 
1019  nDelete( & fac1 );
1020  nDelete( & fac2 );
1021  number gcd = v.gcd();
1022  if ( ! nIsZero( gcd ) && ! nIsOne( gcd ) )
1023  {
1024  v /= gcd;
1025  number temp= nMult( pdenom, gcd );
1026  nDelete( &pdenom );
1027  pdenom= temp;
1028  }
1029  nDelete( & gcd );
1030  gcd= p.gcd();
1031  temp= n_SubringGcd( pdenom, gcd, currRing->cf );
1032  nDelete( &gcd );
1033  gcd= temp;
1034  if ( ! nIsZero( gcd ) && ! nIsOne( gcd ) )
1035  {
1036  p /= gcd;
1037  temp= nDiv( pdenom, gcd );
1038  nDelete( & pdenom );
1039  pdenom= temp;
1040  nNormalize( pdenom );
1041  }
1042  nDelete( & gcd );
1043  }
1044  }
1045 }
1046 
1047 static ideal
1049  fglmVector iv = fglmVector() )
1050 // If iv is zero, calculates the groebnerBasis for the ideal which is
1051 // defined by l.
1052 // If iv is not zero, then the groebnerBasis if i:p is calculated where
1053 // i is defined by l and iv is the vector-representation of nf(p) wrt. i
1054 // The dimension of l has to be finite.
1055 // The result is in reduced form.
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 }
1117 //<-
1118 
1119 static ideal
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=NULL;
1157  for ( k= p.size(); k > 0; k-- )
1158  {
1159  number n = nCopy( p.getconstelem( k ) );
1160  if ( ! nIsZero( n ) )
1161  {
1162  if ( temp == NULL )
1163  {
1164  result= pOne();
1165  temp= result;
1166  }
1167  else
1168  {
1169  temp->next= pOne();
1170  pIter( temp );
1171  }
1172  pSetCoeff( temp, n );
1173  pSetExp( temp, i /*varpermutation[i]*/, k-1 );
1174  pSetm( temp );
1175  }
1176  }
1177  if ( ! nGreaterZero( pGetCoeff( result ) ) ) result= pNeg( result );
1178  (destIdeal->m)[i-1]= result;
1179  }
1180  else
1181  {
1182  STICKYPROT( "." );
1183  gauss.store();
1184  v= l.multiply( v, i /*varpermutation[i]*/ );
1185  }
1186  }
1187  }
1188  STICKYPROT( "\n" );
1189  omFreeSize( (ADDRESS)varpermutation, ((currRing->N)+1)*sizeof(int) );
1190  return destIdeal;
1191 }
1192 
1193 // for a descritption of the parameters see fglm.h
1194 BOOLEAN
1195 fglmzero( ring sourceRing, ideal & sourceIdeal, ring destRing, ideal & destIdeal, BOOLEAN switchBack, BOOLEAN deleteIdeal )
1196 {
1197  ring initialRing = currRing;
1198  BOOLEAN fglmok;
1199 
1200  if ( currRing != sourceRing )
1201  {
1202  rChangeCurrRing( sourceRing );
1203  }
1204  idealFunctionals L( 100, rVar(currRing) );
1205  fglmok = CalculateFunctionals( sourceIdeal, L );
1206  if ( deleteIdeal == TRUE )
1207  idDelete( & sourceIdeal );
1208  rChangeCurrRing( destRing );
1209  if ( fglmok == TRUE )
1210  {
1211  L.map( sourceRing );
1212  destIdeal= GroebnerViaFunctionals( L );
1213  }
1214  if ( (switchBack) && (currRing != initialRing) )
1215  rChangeCurrRing( initialRing );
1216  return fglmok;
1217 }
1218 
1219 BOOLEAN
1220 fglmquot( ideal sourceIdeal, poly quot, ideal & destIdeal)
1221 {
1222  BOOLEAN fglmok;
1223  fglmVector v;
1224 
1225  idealFunctionals L( 100, (currRing->N) );
1226  // STICKYPROT("calculating normal form\n");
1227  // poly p = kNF( sourceIdeal, currRing->qideal, quot );
1228  // STICKYPROT("calculating functionals\n");
1229  fglmok = CalculateFunctionals( sourceIdeal, L, quot, v );
1230  if ( fglmok == TRUE ) {
1231  // STICKYPROT("calculating groebner basis\n");
1232  destIdeal= GroebnerViaFunctionals( L, v );
1233  }
1234  return fglmok;
1235 }
1236 
1237 BOOLEAN
1238 FindUnivariateWrapper( ideal source, ideal & destIdeal )
1239 {
1240  BOOLEAN fglmok;
1241 
1242  idealFunctionals L( 100, (currRing->N) );
1243  fglmok = CalculateFunctionals( source, L );
1244  if ( fglmok == TRUE ) {
1245  destIdeal= FindUnivariatePolys( L );
1246  return TRUE;
1247  }
1248  else
1249  return FALSE;
1250 }
1251 
1252 // ----------------------------------------------------------------------------
1253 // Local Variables: ***
1254 // compile-command: "make Singular" ***
1255 // page-delimiter: "^\\( \\|//!\\)" ***
1256 // fold-internal-margins: nil ***
1257 // End: ***
int row
Definition: fglmzero.cc:65
int numNonZeroElems() const
Definition: fglmvec.cc:213
fglmDelem(poly &m, fglmVector mv, int v)
The new basis.
Definition: fglmzero.cc:701
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
Definition: cf_map_ext.cc:400
#define idMaxIdeal(D)
initialise the maximal ideal (at 0)
Definition: ideals.h:33
#define pSetm(p)
Definition: polys.h:257
poly monom
Definition: fglm.h:49
borderElem * border
Definition: fglmzero.cc:353
ideal buildIdeal()
Definition: fglmzero.cc:788
matHeader ** func
Definition: fglmzero.cc:84
int * divisors
Definition: fglm.h:30
int insertions
Definition: fglm.h:51
int isEmpty() const
Definition: ftmpl_list.cc:267
fglmDelem nextCandidate()
Definition: fglmzero.cc:848
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
void internalCalculateFunctionals(const ideal, idealFunctionals &l, fglmSdata &data)
Definition: fglmzero.cc:611
#define nNormalize(n)
Definition: numbers.h:31
CanonicalForm num(const CanonicalForm &f)
int groebnerBS
Definition: fglmzero.cc:772
#define pSetExp(p, i, v)
Definition: polys.h:42
#define FALSE
Definition: auxiliary.h:94
Compatiblity layer for legacy polynomial operations (over currRing)
fglmVector p
Definition: fglmzero.cc:727
int size() const
Definition: fglmvec.cc:208
number getconstelem(int i) const
Definition: fglmvec.cc:447
void newDivisor()
Definition: fglm.h:57
number gcd() const
Definition: fglmvec.cc:459
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
void gaussreduce(fglmVector &v, fglmVector &p, number &denom)
Definition: fglmzero.cc:981
void newBasisElem(poly &m, fglmVector v, fglmVector p, number &denom)
Definition: fglmzero.cc:856
int basisSize
Definition: fglmzero.cc:347
int dimen() const
Definition: fglmzero.cc:90
int borderMax
Definition: fglmzero.cc:351
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:583
fglmSelem nextCandidate()
Definition: fglmzero.cc:469
#define pNeg(p)
Definition: polys.h:185
void cleanup()
Definition: fglmzero.cc:332
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define pCmp(p1, p2)
pCmp: args may be NULL returns: (p2==NULL ? 1 : (p1 == NULL ? -1 : p_LmCmp(p1, p2))) ...
Definition: polys.h:115
#define TRUE
Definition: auxiliary.h:98
#define nIsOne(n)
Definition: numbers.h:26
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].
void newDivisor(int var)
Definition: fglm.h:37
static ideal GroebnerViaFunctionals(const idealFunctionals &l, fglmVector iv=fglmVector())
Definition: fglmzero.cc:1048
void * ADDRESS
Definition: auxiliary.h:133
void endofConstruction()
Definition: fglmzero.cc:139
BOOLEAN isBasisOrEdge() const
Definition: fglm.h:36
int k
Definition: cfEzgcd.cc:92
fglmVector nf
Definition: fglmzero.cc:305
#define STICKYPROT2(msg, arg)
Definition: fglmzero.cc:53
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:186
~fglmSdata()
Definition: fglmzero.cc:405
void insertCols(int *divisors, int to)
Definition: fglmzero.cc:192
fglmSdata(const ideal thisIdeal)
Definition: fglmzero.cc:374
int idelems
Definition: fglmzero.cc:342
fglmDdata(int dimension)
Definition: fglmzero.cc:795
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
Definition: fglm.h:46
poly monom
Definition: fglmzero.cc:304
#define omAlloc(size)
Definition: omAllocDecl.h:210
fglmVector v
Definition: fglm.h:50
BOOLEAN candidatesLeft() const
Definition: fglmzero.cc:365
int dimen
Definition: fglmzero.cc:763
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: gnumpfl.cc:27
#define pIter(p)
Definition: monomials.h:44
#define omReallocSize(addr, o_size, size)
Definition: omAllocDecl.h:220
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
#define pIncrExp(p, i)
Definition: polys.h:43
static ideal FindUnivariatePolys(const idealFunctionals &l)
Definition: fglmzero.cc:1120
int isZero()
Definition: fglmvec.cc:296
int basisSize
Definition: fglmzero.cc:767
int elemIsZero(int i)
Definition: fglmvec.cc:301
poly getSpanPoly(int number) const
Definition: fglmzero.cc:369
idealFunctionals(int blockSize, int numFuncs)
Definition: fglmzero.cc:100
void updateCandidates(poly m, const fglmVector v)
Definition: fglmzero.cc:893
int newBasisElem(poly &p)
Definition: fglmzero.cc:426
void nihilate(const number fac1, const number fac2, const fglmVector v)
Definition: fglmvec.cc:219
Definition: intvec.h:17
BOOLEAN candidatesLeft() const
Definition: fglmzero.cc:782
fglmSelem(poly p, int var)
Definition: fglmzero.cc:321
#define nGreaterZero(n)
Definition: numbers.h:28
int * perm
Definition: fglmzero.cc:766
oldGaussElem(const fglmVector newv, const fglmVector newp, number &newpdenom, number &newfac)
Definition: fglmzero.cc:734
number clearDenom()
Definition: fglmvec.cc:503
int groebnerSize
Definition: fglmzero.cc:773
T & getItem() const
Definition: ftmpl_list.cc:431
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:74
#define nMult(n1, n2)
Definition: numbers.h:18
number elem
Definition: fglmzero.cc:66
BOOLEAN state() const
Definition: fglmzero.cc:361
int borderBS
Definition: fglmzero.cc:350
number fac
Definition: fglmzero.cc:729
matHeader * grow(int var)
Definition: fglmzero.cc:179
int size
Definition: fglmzero.cc:71
int borderSize
Definition: fglmzero.cc:352
static BOOLEAN CalculateFunctionals(const ideal &theIdeal, idealFunctionals &l)
Definition: fglmzero.cc:675
int m
Definition: cfEzgcd.cc:121
int * currentSize
Definition: fglmzero.cc:83
poly monom
Definition: fglm.h:31
borderElem(poly p, fglmVector n)
Definition: fglmzero.cc:307
#define nGetChar()
Definition: numbers.h:24
void newGroebnerPoly(fglmVector &v, poly &p)
Definition: fglmzero.cc:938
poly * polyset
Definition: polys.h:246
int i
Definition: cfEzgcd.cc:125
ideal theIdeal
Definition: fglmzero.cc:341
#define pOne()
Definition: polys.h:301
int * varpermutation
Definition: fglmzero.cc:343
int basisBS
Definition: fglmzero.cc:345
CanonicalForm factor
Definition: facAbsFact.cc:101
#define IDELEMS(i)
Definition: simpleideals.h:24
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:722
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define fglmASSERT(ignore1, ignore2)
Definition: fglmzero.cc:54
#define nDelete(n)
Definition: numbers.h:17
ideal destId
Definition: fglmzero.cc:774
BOOLEAN isBasisOrEdge() const
Definition: fglm.h:56
void rChangeCurrRing(ring r)
Definition: polys.cc:15
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
void insert(const T &)
Definition: ftmpl_list.cc:492
fglmVector getBorderDiv(const poly m, int &var) const
Definition: fglmzero.cc:580
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:37
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define nDiv(a, b)
Definition: numbers.h:33
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:165
BOOLEAN dimension(leftv res, leftv args)
Definition: bbcone.cc:757
#define nIsZero(n)
Definition: numbers.h:20
#define NULL
Definition: omList.c:10
#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:138
oldGaussElem * gauss
Definition: fglmzero.cc:764
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3633
Definition: fglm.h:27
void cleanup()
Definition: fglmzero.cc:715
polyset basis
Definition: fglmzero.cc:348
void setelem(int i, number &n)
Definition: fglmvec.cc:452
BOOLEAN * isPivot
Definition: fglmzero.cc:765
polyset basis
Definition: fglmzero.cc:768
void updateCandidates()
Definition: fglmzero.cc:481
int gcd(int a, int b)
Definition: walkSupport.cc:836
List< fglmSelem > nlist
Definition: fglmzero.cc:355
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:349
#define pDelete(p_ptr)
Definition: polys.h:173
BOOLEAN fglmzero(ring sourceRing, ideal &sourceIdeal, ring destRing, ideal &destIdeal, BOOLEAN switchBack, BOOLEAN deleteIdeal)
Definition: fglmzero.cc:1195
fglmVector getVectorRep(const poly m)
Definition: fglmzero.cc:545
#define nCopy(n)
Definition: numbers.h:16
int * varpermutation
Definition: fglmzero.cc:770
bool isZero(const CFArray &A)
checks if entries of A are zero
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
The idealFunctionals.
Definition: fglmzero.cc:63
BOOLEAN _state
Definition: fglmzero.cc:356
int getBasisSize() const
Definition: fglmzero.cc:362
int var
Definition: fglm.h:52
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:689
void map(ring source)
Definition: fglmzero.cc:145
int getBasisSize() const
Definition: fglmzero.cc:781
List< fglmDelem > nlist
Definition: fglmzero.cc:776
int p
Definition: cfModGcd.cc:4019
BOOLEAN owner
Definition: fglmzero.cc:72
BOOLEAN FindUnivariateWrapper(ideal source, ideal &destIdeal)
Definition: fglmzero.cc:1238
int basisMax
Definition: fglmzero.cc:346
BOOLEAN fglmquot(ideal sourceIdeal, poly quot, ideal &destIdeal)
Definition: fglmzero.cc:1220
#define nInit(i)
Definition: numbers.h:25
int BOOLEAN
Definition: auxiliary.h:85
~fglmDdata()
Definition: fglmzero.cc:823
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
fglmVector addCols(const int var, int basisSize, const fglmVector v) const
Definition: fglmzero.cc:243
fglmVector v
Definition: fglmzero.cc:726
#define nAdd(n1, n2)
Definition: numbers.h:19
#define pLmEqual(p1, p2)
Definition: polys.h:111
The old basis.
Definition: fglmzero.cc:301
#define omAlloc0(size)
Definition: omAllocDecl.h:211
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:93
matElem * elems
Definition: fglmzero.cc:73
fglmVector multiply(const fglmVector v, int var) const
Definition: fglmzero.cc:269
int numVars
Definition: fglm.h:32
#define nGreater(a, b)
Definition: numbers.h:29
#define pCopy(p)
return a copy of the poly
Definition: polys.h:172
number pdenom
Definition: fglmzero.cc:728