My Project
Loading...
Searching...
No Matches
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
39
40#include "kernel/polys.h"
41#include "kernel/ideals.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
61struct matElem
62{
63 int row;
64 number elem;
65};
66
68{
69 int size;
72};
73
75{
76private:
77 int _block;
78 int _max;
79 int _size;
80 int _nfunc;
83 matHeader * grow( int var );
84public:
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
98idealFunctionals::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
136void
138{
139 _size= currentSize[0];
140}
141
142void
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
176matHeader *
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
189void
190idealFunctionals::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
209void
210idealFunctionals::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
241idealFunctionals::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
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{
301public:
302 poly monom;
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
319fglmSelem::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
329void
331{
332 omFreeSize( (ADDRESS)divisors, (numVars+1)*sizeof( int ) );
333}
334
335// The data-structure for the Functional-Finding-Algorithm.
337{
338private:
339 ideal theIdeal;
342
346 polyset basis; //. rem: runs from basis[1]..basis[dimen]
347
351 borderElem * border; //. rem: runs from border[1]..border[dimen]
352
355public:
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
372fglmSdata::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;
388 basisSize= 0;
389 basis= (polyset)omAlloc( basisMax*sizeof( poly ) );
390
391 borderBS= 100;
393 borderSize= 0;
394#ifndef HAVE_EXPLICIT_CONSTR
396#else
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.
423int
425{
426 basisSize++;
427 if ( basisSize == basisMax ) {
428 basis= (polyset)omReallocSize( basis, basisMax*sizeof( poly ), (basisMax + basisBS)*sizeof( poly ) );
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.
440void
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
468{
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
478void
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.)
528int
529fglmSdata::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
578fglmSdata::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
608void
609internalCalculateFunctionals( 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.
672static BOOLEAN
673CalculateFunctionals( const ideal & theIdeal, idealFunctionals & l )
674{
675 fglmSdata data( theIdeal );
676 internalCalculateFunctionals( theIdeal, l, data );
677 return ( data.state() );
678}
679
680static BOOLEAN
681CalculateFunctionals( 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
699fglmDelem::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
712void
714{
715 if ( monom != NULL )
716 {
718 }
719}
720
722{
723public:
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 }
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{
760private:
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
775public:
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 );
787 {
789 return destId;
790 }
791};
792
794{
795 int k;
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
847{
850 return result;
851}
852
853void
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
890void
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
935void
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 }
975 groebnerSize++;
976}
977
978void
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
1045static 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
1117static ideal
1119{
1120 fglmVector v;
1121 fglmVector p;
1122 ideal destIdeal = idInit( (currRing->N), 1 );
1123
1124 int i;
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
1192BOOLEAN
1193fglmzero( 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
1217BOOLEAN
1218fglmquot( 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
1235BOOLEAN
1236FindUnivariateWrapper( 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
#define idMaxIdeal(D)
initialise the maximal ideal (at 0)
Definition: ideals.h:33
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:184
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:3696
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