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