1 | // emacs edit mode for this file is -*- C++ -*- |
---|
2 | // $Id: fglm.cc,v 1.5 1997-03-27 10:32:36 Singular Exp $ |
---|
3 | |
---|
4 | /**************************************** |
---|
5 | * Computer Algebra System SINGULAR * |
---|
6 | ****************************************/ |
---|
7 | /* |
---|
8 | * ABSTRACT - The FGLM-Algorithm |
---|
9 | * Calculate a reduced groebner basis for one ordering, given a |
---|
10 | * reduced groebner basis for another ordering. |
---|
11 | * In this file the input is checked. Furthermore we decide, if |
---|
12 | * the input is 0-dimensional ( then fglmzero.cc is used ) or |
---|
13 | * if the input is homogeneous ( then fglmhom.cc is used. Yet |
---|
14 | * not implemented ). |
---|
15 | */ |
---|
16 | |
---|
17 | #ifndef NOSTREAMIO |
---|
18 | #include <iostream.h> |
---|
19 | #endif |
---|
20 | #include "mod2.h" |
---|
21 | #include "tok.h" |
---|
22 | #include "structs.h" |
---|
23 | #include "polys.h" |
---|
24 | #include "ideals.h" |
---|
25 | #include "ring.h" |
---|
26 | #include "ipid.h" |
---|
27 | #include "ipshell.h" |
---|
28 | #include "febase.h" |
---|
29 | #include "maps.h" |
---|
30 | #include "mmemory.h" |
---|
31 | #include "kstd1.h" |
---|
32 | #include "fglm.h" |
---|
33 | |
---|
34 | // enumeration to handle the various errors to occour. |
---|
35 | enum FglmState{ |
---|
36 | FglmOk, |
---|
37 | FglmHasOne, |
---|
38 | FglmNoIdeal, |
---|
39 | FglmNotReduced, |
---|
40 | FglmNotZeroDim, |
---|
41 | FglmIncompatibleRings |
---|
42 | }; |
---|
43 | |
---|
44 | // Has to be called, if currQuotient != NULL. ( i.e. qring-case ) |
---|
45 | // Then a new ideal is build, consisting of the generators of sourceIdeal |
---|
46 | // and the generators of currQuotient, which are completely reduced by |
---|
47 | // the sourceIdeal. This means: If sourceIdeal is reduced, then the new |
---|
48 | // ideal will be reduced as well. |
---|
49 | // Assumes that currRing == sourceRing |
---|
50 | ideal fglmUpdatesource( const ideal sourceIdeal ) |
---|
51 | { |
---|
52 | int k, l, offset; |
---|
53 | BOOLEAN found; |
---|
54 | ideal newSource= idInit( IDELEMS( sourceIdeal ) + IDELEMS( currQuotient ), 1 ); |
---|
55 | for ( k= IDELEMS( sourceIdeal )-1; k >=0; k-- ) |
---|
56 | (newSource->m)[k]= pCopy( (sourceIdeal->m)[k] ); |
---|
57 | offset= IDELEMS( sourceIdeal ); |
---|
58 | for ( l= IDELEMS( currQuotient )-1; l >= 0; l-- ) { |
---|
59 | found= FALSE; |
---|
60 | for ( k= IDELEMS( sourceIdeal )-1; (k >= 0) && (found == FALSE); k-- ) |
---|
61 | if ( pDivisibleBy( (sourceIdeal->m)[k], (currQuotient->m)[l] ) ) |
---|
62 | found= TRUE; |
---|
63 | if ( ! found ) { |
---|
64 | (newSource->m)[offset]= pCopy( (currQuotient->m)[l] ); |
---|
65 | offset++; |
---|
66 | } |
---|
67 | } |
---|
68 | idSkipZeroes( newSource ); |
---|
69 | return newSource; |
---|
70 | } |
---|
71 | |
---|
72 | // Has to be called, if currQuotient != NULL, i.e. in qring-case. |
---|
73 | // Gets rid of the elements of result which are contained in |
---|
74 | // currQuotient and skips Zeroes. |
---|
75 | // Assumes that currRing == destRing |
---|
76 | void |
---|
77 | fglmUpdateresult( ideal & result ) |
---|
78 | { |
---|
79 | int k, l; |
---|
80 | BOOLEAN found; |
---|
81 | for ( k= IDELEMS( result )-1; k >=0; k-- ) { |
---|
82 | found= FALSE; |
---|
83 | for ( l= IDELEMS( currQuotient )-1; (l >= 0) && ( found == FALSE ); l-- ) |
---|
84 | if ( pDivisibleBy( (currQuotient->m)[l], (result->m)[k] ) ) |
---|
85 | found= TRUE; |
---|
86 | if ( found ) pDelete( &(currQuotient->m)[l] ); |
---|
87 | } |
---|
88 | idSkipZeroes( result ); |
---|
89 | } |
---|
90 | |
---|
91 | // Checks if the two rings sringHdl and dringHdl are compatible enough to |
---|
92 | // be used for the fglm. This means: |
---|
93 | // 1) Same Characteristic, 2) globalOrderings in both rings, |
---|
94 | // 3) Same number of variables, 4) same number of parameters |
---|
95 | // 5) variables in one ring are permutated variables of the other one |
---|
96 | // 6) parameters in one ring are permutated parameters of the other one |
---|
97 | // 7) either both rings are rings or both rings are qrings |
---|
98 | // 8) if they are qrings, the quotientIdeals of both must coincide. |
---|
99 | // vperm must be a vector of length pVariables+1, initialized by 0. |
---|
100 | // If both rings are compatible, it stores the permutation of the |
---|
101 | // variables if mapped from sringHdl to dringHdl. |
---|
102 | // if the rings are compatible, it returns FglmOk. |
---|
103 | // Should be called with currRing= IDRING( sringHdl ); |
---|
104 | FglmState |
---|
105 | fglmConsistency( idhdl sringHdl, idhdl dringHdl, int * vperm ) |
---|
106 | { |
---|
107 | int k; |
---|
108 | FglmState state= FglmOk; |
---|
109 | ring dring = IDRING( dringHdl ); |
---|
110 | ring sring = IDRING( sringHdl ); |
---|
111 | |
---|
112 | if ( sring->ch != dring->ch ) { |
---|
113 | WerrorS( "rings must have same characteristic" ); |
---|
114 | state= FglmIncompatibleRings; |
---|
115 | } |
---|
116 | if ( (sring->OrdSgn != 1) || (dring->OrdSgn != 1) ) { |
---|
117 | WerrorS( "only works for global orderings" ); |
---|
118 | state= FglmIncompatibleRings; |
---|
119 | } |
---|
120 | if ( sring->N != dring->N ) { |
---|
121 | WerrorS( "rings must have same number of variables" ); |
---|
122 | state= FglmIncompatibleRings; |
---|
123 | } |
---|
124 | if ( sring->P != dring->P ) { |
---|
125 | WerrorS( "rings must have same number of parameters" ); |
---|
126 | state= FglmIncompatibleRings; |
---|
127 | } |
---|
128 | if ( state != FglmOk ) return state; |
---|
129 | // now the rings have the same number of variables resp. parameters. |
---|
130 | // check if the names of the variables resp. parameters do agree: |
---|
131 | int nvar = sring->N; |
---|
132 | int npar = sring->P; |
---|
133 | int * pperm; |
---|
134 | if ( npar > 0 ) |
---|
135 | pperm= (int *)Alloc0( (npar+1)*sizeof( int ) ); |
---|
136 | else |
---|
137 | pperm= NULL; |
---|
138 | maFindPerm( sring->names, nvar, sring->parameter, npar, dring->names, nvar, dring->parameter, npar, vperm, pperm ); |
---|
139 | for ( k= nvar; (k > 0) && (state == FglmOk); k-- ) |
---|
140 | if ( vperm[k] <= 0 ) { |
---|
141 | WerrorS( "variable names do not agree" ); |
---|
142 | state= FglmIncompatibleRings; |
---|
143 | } |
---|
144 | for ( k= npar-1; (k >= 0) && (state == FglmOk); k-- ) |
---|
145 | if ( pperm[k] >= 0 ) { |
---|
146 | WerrorS( "paramater names do not agree" ); |
---|
147 | state= FglmIncompatibleRings; |
---|
148 | } |
---|
149 | Free( (ADDRESS)pperm, (npar+1)*sizeof( int ) ); |
---|
150 | if ( state != FglmOk ) return state; |
---|
151 | // check if both rings are qrings or not |
---|
152 | if ( sring->qideal != NULL ) { |
---|
153 | if ( dring->qideal == NULL ) { |
---|
154 | Werror( "%s is a qring, current ring not", sringHdl->id ); |
---|
155 | return FglmIncompatibleRings; |
---|
156 | } |
---|
157 | // both rings are qrings, now check if both quotients define the same ideal. |
---|
158 | // check if sring->qideal is contained in dring->qideal: |
---|
159 | rSetHdl( dringHdl, TRUE ); |
---|
160 | nSetMap( sring->ch, sring->parameter, npar, sring->minpoly ); |
---|
161 | ideal sqind = idInit( IDELEMS( sring->qideal ), 1 ); |
---|
162 | for ( k= IDELEMS( sring->qideal )-1; k >= 0; k-- ) |
---|
163 | (sqind->m)[k]= pPermPoly( (sring->qideal->m)[k], vperm, nvar ); |
---|
164 | ideal sqindred = kNF( dring->qideal, NULL, sqind ); |
---|
165 | if ( ! idIs0( sqindred ) ) { |
---|
166 | WerrorS( "the quotients do not agree" ); |
---|
167 | state= FglmIncompatibleRings; |
---|
168 | } |
---|
169 | idDelete( & sqind ); |
---|
170 | idDelete( & sqindred ); |
---|
171 | rSetHdl( sringHdl, TRUE ); |
---|
172 | if ( state != FglmOk ) return state; |
---|
173 | // check if dring->qideal is contained in sring->qideal: |
---|
174 | int * dsvperm = (int *)Alloc0( (nvar+1)*sizeof( int ) ); |
---|
175 | maFindPerm( dring->names, nvar, NULL, 0, sring->names, nvar, NULL, 0, dsvperm, NULL ); |
---|
176 | nSetMap( dring->ch, dring->parameter, npar, dring->minpoly ); |
---|
177 | ideal dqins = idInit( IDELEMS( dring->qideal ), 1 ); |
---|
178 | for ( k= IDELEMS( dring->qideal )-1; k >= 0; k-- ) |
---|
179 | (dqins->m)[k]= pPermPoly( (dring->qideal->m)[k], dsvperm, nvar ); |
---|
180 | ideal dqinsred = kNF( sring->qideal, NULL, dqins ); |
---|
181 | if ( ! idIs0( dqinsred ) ) { |
---|
182 | WerrorS( "the quotients do not agree" ); |
---|
183 | state= FglmIncompatibleRings; |
---|
184 | } |
---|
185 | idDelete( & dqins ); |
---|
186 | idDelete( & dqinsred ); |
---|
187 | Free( (ADDRESS)dsvperm, (nvar+1)*sizeof( int ) ); |
---|
188 | if ( state != FglmOk ) return state; |
---|
189 | } |
---|
190 | else { |
---|
191 | if ( dring->qideal != NULL ) { |
---|
192 | Werror( "current ring is a qring, %s not", sringHdl->id ); |
---|
193 | return FglmIncompatibleRings; |
---|
194 | } |
---|
195 | } |
---|
196 | return FglmOk; |
---|
197 | } |
---|
198 | |
---|
199 | // Checks if the ideal "theIdeal" is zero-dimensional and minimal. It does |
---|
200 | // not check, if it is reduced. |
---|
201 | // returns FglmOk if we can use theIdeal for CalculateFunctionals (this |
---|
202 | // function reports an error if theIdeal is not reduced, |
---|
203 | // so this need not to be tested here) |
---|
204 | // FglmNotReduced if theIdeal is not minimal |
---|
205 | // FglmNotZeroDim if it is not zero-dimensional |
---|
206 | // FglmHasOne if 1 belongs to theIdeal |
---|
207 | FglmState |
---|
208 | fglmIdealcheck( const ideal theIdeal ) |
---|
209 | { |
---|
210 | FglmState state = FglmOk; |
---|
211 | int power; |
---|
212 | int k; |
---|
213 | BOOLEAN * purePowers = (BOOLEAN *)Alloc( pVariables*sizeof( BOOLEAN ) ); |
---|
214 | for ( k= pVariables-1; k >= 0; k-- ) |
---|
215 | purePowers[k]= FALSE; |
---|
216 | |
---|
217 | for ( k= IDELEMS( theIdeal ) - 1; (state == FglmOk) && (k >= 0); k-- ) { |
---|
218 | poly p = (theIdeal->m)[k]; |
---|
219 | if ( pIsConstant( p ) ) state= FglmHasOne; |
---|
220 | else if ( (power= pIsPurePower( p )) > 0 ) { |
---|
221 | fglmASSERT( 0 < power && power <= pVariables, "illegal power" ); |
---|
222 | if ( purePowers[power-1] == TRUE ) state= FglmNotReduced; |
---|
223 | else purePowers[power-1]= TRUE; |
---|
224 | } |
---|
225 | for ( int l = IDELEMS( theIdeal ) - 1; state == FglmOk && l >= 0; l-- ) |
---|
226 | if ( (k != l) && pDivisibleBy( p, (theIdeal->m)[l] ) ) |
---|
227 | state= FglmNotReduced; |
---|
228 | } |
---|
229 | if ( state == FglmOk ) { |
---|
230 | for ( k= pVariables-1 ; (state == FglmOk) && (k >= 0); k-- ) |
---|
231 | if ( purePowers[k] == FALSE ) state= FglmNotZeroDim; |
---|
232 | } |
---|
233 | Free( (ADDRESS)purePowers, pVariables*sizeof( BOOLEAN ) ); |
---|
234 | return state; |
---|
235 | } |
---|
236 | |
---|
237 | // the main function for the fglm-Algorithm. |
---|
238 | // Checks the input-data, calls CalculateFunctionals, handles change |
---|
239 | // of ring-vars and finaly calls GroebnerViaFunctionals. |
---|
240 | // returns the new groebnerbasis or 0 if an error occoured. |
---|
241 | BOOLEAN |
---|
242 | fglmProc( leftv result, leftv first, leftv second ) |
---|
243 | { |
---|
244 | FglmState state = FglmOk; |
---|
245 | //. array for the permutations of vars in both rings: |
---|
246 | //. counts from perm[1]..perm[pvariables] |
---|
247 | int * vperm = (int *)Alloc0( (pVariables+1)*sizeof( int ) ); |
---|
248 | |
---|
249 | idhdl destRingHdl = currRingHdl; |
---|
250 | ring destRing = currRing; |
---|
251 | ideal destIdeal = NULL; |
---|
252 | idhdl sourceRingHdl = (idhdl)first->data; |
---|
253 | rSetHdl( sourceRingHdl, TRUE ); |
---|
254 | ring sourceRing = currRing; |
---|
255 | state= fglmConsistency( sourceRingHdl, destRingHdl, vperm ); |
---|
256 | |
---|
257 | if ( state == FglmOk ) { |
---|
258 | idhdl ih = currRing->idroot->get( second->Name(), myynest ); |
---|
259 | if ( (ih != NULL) && (IDTYP(ih)==IDEAL_CMD) ) { |
---|
260 | ideal sourceIdeal; |
---|
261 | if ( currQuotient != NULL ) |
---|
262 | sourceIdeal= fglmUpdatesource( IDIDEAL( ih ) ); |
---|
263 | else |
---|
264 | sourceIdeal = IDIDEAL( ih ); |
---|
265 | state= fglmIdealcheck( sourceIdeal ); |
---|
266 | if ( state == FglmOk ) { |
---|
267 | // Now the settings are compatible with FGLM |
---|
268 | assumeStdFlag( (leftv)ih ); |
---|
269 | if ( fglmzero( sourceRingHdl, sourceIdeal, destRingHdl, destIdeal, FALSE, (currQuotient != NULL) ) == FALSE ) |
---|
270 | state= FglmNotReduced; |
---|
271 | } |
---|
272 | } else state= FglmNoIdeal; |
---|
273 | } |
---|
274 | if ( currRingHdl != destRingHdl ) |
---|
275 | rSetHdl( destRingHdl, TRUE ); |
---|
276 | switch (state) { |
---|
277 | case FglmOk: |
---|
278 | if ( currQuotient != NULL ) fglmUpdateresult( destIdeal ); |
---|
279 | break; |
---|
280 | case FglmHasOne: |
---|
281 | destIdeal= idInit(1,1); |
---|
282 | (destIdeal->m)[0]= pOne(); |
---|
283 | state= FglmOk; |
---|
284 | break; |
---|
285 | case FglmIncompatibleRings: |
---|
286 | Werror( "ring %s and current ring are incompatible", first->Name() ); |
---|
287 | destIdeal= idInit(0,0); |
---|
288 | break; |
---|
289 | case FglmNoIdeal: |
---|
290 | Werror( "Can't find ideal %s in ring %s", second->Name(), first->Name() ); |
---|
291 | destIdeal= idInit(0,0); |
---|
292 | break; |
---|
293 | case FglmNotZeroDim: |
---|
294 | Werror( "The ideal %s has to be 0-dimensional", second->Name() ); |
---|
295 | destIdeal= idInit(0,0); |
---|
296 | break; |
---|
297 | case FglmNotReduced: |
---|
298 | Werror( "The ideal %s has to be reduced", second->Name() ); |
---|
299 | destIdeal= idInit(0,0); |
---|
300 | break; |
---|
301 | default: |
---|
302 | destIdeal= idInit(1,1); |
---|
303 | } |
---|
304 | Free( (ADDRESS)vperm, (pVariables+1)*sizeof(int) ); |
---|
305 | |
---|
306 | result->rtyp = IDEAL_CMD; |
---|
307 | result->data= (void *)destIdeal; |
---|
308 | setFlag( result, FLAG_STD ); |
---|
309 | if ( state == FglmOk ) |
---|
310 | return FALSE; |
---|
311 | else |
---|
312 | return TRUE; |
---|
313 | } |
---|
314 | |
---|
315 | // ---------------------------------------------------------------------------- |
---|
316 | // Local Variables: *** |
---|
317 | // compile-command: "make Singular" *** |
---|
318 | // page-delimiter: "^\\(\\|//!\\)" *** |
---|
319 | // fold-internal-margins: nil *** |
---|
320 | // End: *** |
---|