1 | // last modified: 10.06.2010 |
---|
2 | ////////////////////////////////////////////////////////////////////////////// |
---|
3 | version = "$Id: monomial.lib$"; |
---|
4 | category = "Commutative algebra"; |
---|
5 | info = " |
---|
6 | LIBRARY: monomial.lib Primary and irreducible decompositions of monomial |
---|
7 | ideals |
---|
8 | AUTHORS: I.Bermejo, ibermejo@ull.es |
---|
9 | @* E.Garcia-Llorente, evgarcia@ull.es |
---|
10 | @* Ph.Gimenez, pgimenez@agt.uva.es |
---|
11 | OVERVIEW: |
---|
12 | A library for computing a primary and the irreducible decompositions of a |
---|
13 | monomial ideal using several methods. |
---|
14 | In this library we also take advantage of the fact that the ideal is |
---|
15 | monomial to make some computations that are Grobner free in this case |
---|
16 | (radical, intersection, quotient...). |
---|
17 | PROCEDURES: |
---|
18 | isMonomial(id); checks whether an ideal id is monomial |
---|
19 | minbaseMon(id); computes the minimal monomial generating set of a |
---|
20 | monomial ideal id |
---|
21 | gcdMon(f,g); computes the gcd of two monomials f, g |
---|
22 | lcmMon(f,g); computes the lcm of two monomials f, g |
---|
23 | membershipMon(f,id); checks whether a polynomial f belongs to a monomial |
---|
24 | ideal id |
---|
25 | intersectMon(id1,id2);intersection of monomial ideals id1 and id2 |
---|
26 | quotientMon(id1,id2); quotient ideal id1:id2 |
---|
27 | radicalMon(id); computes the radical of a monomial ideal id |
---|
28 | isprimeMon(id); checks whether a monomial ideal id is prime |
---|
29 | isprimaryMon(id); checks whether a monomial ideal id is primary |
---|
30 | isirreducibleMon(id); checks whether a monomial ideal id is irreducible |
---|
31 | isartinianMon(id); checks whether a monomial ideal id is artininan |
---|
32 | isgenericMon(id); checks whether a monomial ideal id is generic |
---|
33 | dimMon(id); dimension of a monomial ideal id |
---|
34 | irreddecMon(id,..); computes the irreducible decomposition of a monomial |
---|
35 | ideal id |
---|
36 | primdecMon(id,..); computes a minimal primary decomposition of a monomial |
---|
37 | ideal id |
---|
38 | "; |
---|
39 | LIB "poly.lib"; // Para "maxdeg1" en "isprimeMon" |
---|
40 | //--------------------------------------------------------------------------- |
---|
41 | //----------------------- INTERNOS ------------------------------------- |
---|
42 | //--------------------------------------------------------------------------- |
---|
43 | ///////////////////////////////////////////////////////////////////////////// |
---|
44 | // |
---|
45 | static proc checkIdeal (ideal I) |
---|
46 | " |
---|
47 | USAGE: checkIdeal (I); I ideal. |
---|
48 | RETURN: 1, if ideal is generated by monomials; 0, otherwise. |
---|
49 | " |
---|
50 | // Aqui NO estoy quitando el caso de que el ideal sea el trivial. |
---|
51 | { |
---|
52 | int i,n; |
---|
53 | n = ncols(I); |
---|
54 | for (i = 1 ; i <= n ; i ++) |
---|
55 | { |
---|
56 | if ( size(I[i]) > 1 ) |
---|
57 | { |
---|
58 | return (0); |
---|
59 | } |
---|
60 | } |
---|
61 | return (1); |
---|
62 | } |
---|
63 | ///////////////////////////////////////////////////////////////////////////// |
---|
64 | // |
---|
65 | static proc quotientIdealMon (ideal I,poly f) |
---|
66 | " |
---|
67 | USAGE: quotientIdealMon(I,f); I ideal, f polynomial. |
---|
68 | RETURN: an ideal, the quotient ideal I:(f). |
---|
69 | ASSUME: I is an ideal generated by a list of monomials and f is a monomial |
---|
70 | of the basering. |
---|
71 | " |
---|
72 | { |
---|
73 | // Variables |
---|
74 | int i,j; |
---|
75 | poly g,generator; |
---|
76 | intvec v; |
---|
77 | ideal J; |
---|
78 | J = 0; |
---|
79 | |
---|
80 | int sizI = size(I); |
---|
81 | for (i = 1 ; i <= sizI ; i++) |
---|
82 | { |
---|
83 | g = gcdMon(I[i],f); |
---|
84 | // Cociente de dos monomios: restamos los exponentes, y en el |
---|
85 | // denominador va el mcd |
---|
86 | v = leadexp(I[i]) - leadexp(g); |
---|
87 | generator = monomial (v); |
---|
88 | if (membershipMon(generator,J) == 0) |
---|
89 | { |
---|
90 | J=J,generator; |
---|
91 | } |
---|
92 | } |
---|
93 | // minimal monomial basis |
---|
94 | return ( minbase(J) ); |
---|
95 | } |
---|
96 | ///////////////////////////////////////////////////////////////////////////// |
---|
97 | // |
---|
98 | static proc soporte (poly f) |
---|
99 | " |
---|
100 | USAGE: soporte(f); f polynomial. |
---|
101 | RETURN: 0, if the monomial f is product of more than one variable; |
---|
102 | otherwise, an integer j, 1<=j<=n, if the monomial f is a power of |
---|
103 | x(j). |
---|
104 | ASSUME: f is a monomial of the basering K[x(1)..x(n)]. |
---|
105 | " |
---|
106 | { |
---|
107 | def R = basering; |
---|
108 | // Variables |
---|
109 | int nvar,i,cont,sop; |
---|
110 | intvec expf; |
---|
111 | nvar = nvars(R); |
---|
112 | expf = leadexp(f); |
---|
113 | cont = 0; |
---|
114 | // cont va a contar el numero de componentes del vector no nulas. |
---|
115 | // En sop guardamos el subindice de la componente no nula. |
---|
116 | for (i = 1 ; i <= nvar ; i++) |
---|
117 | { |
---|
118 | if (expf[i] > 0) |
---|
119 | { |
---|
120 | cont ++; |
---|
121 | sop = i; |
---|
122 | // Si cont > 1 ==> aparece mas de una variable, devolvemos 0 |
---|
123 | if (cont > 1) |
---|
124 | { |
---|
125 | return (0); |
---|
126 | } |
---|
127 | } |
---|
128 | } |
---|
129 | return(sop); |
---|
130 | } |
---|
131 | ///////////////////////////////////////////////////////////////////////////// |
---|
132 | // |
---|
133 | static proc irredAux (ideal I) |
---|
134 | " |
---|
135 | USAGE: irredAux (I); I ideal. |
---|
136 | RETURN: 1, if I is irreducible; otherwise, an intvec whose fist entry is |
---|
137 | the position of a generator which is the product of more than one |
---|
138 | variable, the next entries are the indexes of those variables. |
---|
139 | ASSUME: I is a monomial ideal of the basering K[x(1)..x(n)] and it is |
---|
140 | generated by its minimal monomial generators. |
---|
141 | NOTE: This procedure is a modification of isirreducibleMon to give |
---|
142 | more information when ideal is not irreducible. |
---|
143 | " |
---|
144 | { |
---|
145 | def R = basering; |
---|
146 | // Variables |
---|
147 | int sizI,i,nvar,j,sum; |
---|
148 | intvec w,exp; |
---|
149 | sizI = size(I); |
---|
150 | nvar = nvars(R); |
---|
151 | for (i = 1 ; i <= sizI ; i++) |
---|
152 | { |
---|
153 | sum = 0; |
---|
154 | exp = leadexp(I[i]); |
---|
155 | for (j = 1 ; j <= nvar ; j++) |
---|
156 | { |
---|
157 | // Al menos tenemos una variable en cada generador, luego |
---|
158 | // entramos minimo 1 vez, luego sum >= 1. |
---|
159 | if (exp[j] <> 0) |
---|
160 | { |
---|
161 | sum = sum + 1; |
---|
162 | w[sum] = j; |
---|
163 | } |
---|
164 | } |
---|
165 | // Si hay mas de una variable la suma sera mayor que 1; y ya |
---|
166 | // sabemos que I no es irreducible. |
---|
167 | if (sum <> 1) |
---|
168 | { |
---|
169 | return(i,w); |
---|
170 | } |
---|
171 | } |
---|
172 | return(1); |
---|
173 | } |
---|
174 | ////////////////////////////////////////////////////////////////////// |
---|
175 | // |
---|
176 | static proc contents (ideal I,ideal J) |
---|
177 | " |
---|
178 | USAGE: contents (I,J); I,J ideals. |
---|
179 | RETURN: 1, if I is contained in J; 0, otherwise. |
---|
180 | ASSUME: I,J are monomial ideals of the basering. |
---|
181 | " |
---|
182 | { |
---|
183 | // Variables |
---|
184 | poly f; |
---|
185 | int i,resp; |
---|
186 | int n = size(I); |
---|
187 | // Desde que haya un generador que no pertenzca al ideal, ya no se da |
---|
188 | // el contenido y terminamos. |
---|
189 | for (i = 1 ; i <= n ; i++) |
---|
190 | { |
---|
191 | resp = membershipMon(I[i],J); |
---|
192 | if (resp == 0) |
---|
193 | { |
---|
194 | return(0); |
---|
195 | } |
---|
196 | } |
---|
197 | return(1); |
---|
198 | } |
---|
199 | ///////////////////////////////////////////////////////////////////////////// |
---|
200 | // |
---|
201 | static proc equal (ideal I,ideal J) |
---|
202 | " |
---|
203 | USAGE: equal (I,J); I,J ideals. |
---|
204 | RETURN: 1, if I and J are the same ideal; 0, otherwise. |
---|
205 | ASSUME: I,J are monomial ideals of the basering and are defined by their |
---|
206 | minimal monomial generators. |
---|
207 | " |
---|
208 | { |
---|
209 | // Variables |
---|
210 | int n,i,j; |
---|
211 | intvec resps; |
---|
212 | // Si no tienen el mismo numero de generadores, no pueden ser iguales; ya |
---|
213 | // que vienen dados por el sistema minimal de generadores. |
---|
214 | if (size(I) <> size(J)) |
---|
215 | { |
---|
216 | return(0); |
---|
217 | } |
---|
218 | n = size(I); |
---|
219 | // Como ambos ideales vienen dados por la base minimal, no vamos a |
---|
220 | // tener problemas con que comparemos uno de I con otro de J, pues |
---|
221 | // no puede haber generadores iguales en el mismo ideal. |
---|
222 | // Si los ordenamos, se puede comparar uno a uno |
---|
223 | I = sort(I)[1]; |
---|
224 | J = sort(J)[1]; |
---|
225 | for (i = 1 ; i <= n ; i++) |
---|
226 | { |
---|
227 | if (I[i] <> J[i]) |
---|
228 | { |
---|
229 | return(0); |
---|
230 | } |
---|
231 | } |
---|
232 | return(1); |
---|
233 | } |
---|
234 | ///////////////////////////////////////////////////////////////////////////// |
---|
235 | // |
---|
236 | static proc radicalAux (ideal I) |
---|
237 | " |
---|
238 | USAGE: radicalAux (I); I ideal. |
---|
239 | RETURN: an ideal, the radical ideal of I |
---|
240 | ASSUME: I is an irreducible monomial ideal of the basering given by its |
---|
241 | minimal monomial generators. |
---|
242 | " |
---|
243 | { |
---|
244 | // Cambiamos de anillo |
---|
245 | def R = basering; |
---|
246 | int nvar = nvars(R); |
---|
247 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
248 | execute(s); |
---|
249 | // Variables |
---|
250 | int i,cont; |
---|
251 | intvec exp; |
---|
252 | ideal rad; |
---|
253 | ideal I = fetch(R,I); |
---|
254 | // Como en cada generador aparece solo una variable, y ademas la |
---|
255 | // la misma variable no va a aparecer dos veces, es suficiente |
---|
256 | // con sumar los exponentes de todos los generadores para saber que |
---|
257 | // variables aparecen. |
---|
258 | int n = size(I); |
---|
259 | for (i = 1 ; i <= n ; i++) |
---|
260 | { |
---|
261 | exp = exp + leadexp (I[i]); |
---|
262 | } |
---|
263 | cont = 1; |
---|
264 | for (i = 1 ; i <= nvar ; i++) |
---|
265 | { |
---|
266 | if (exp[i] <> 0) |
---|
267 | { |
---|
268 | rad[cont] = x(i); |
---|
269 | cont ++; |
---|
270 | } |
---|
271 | } |
---|
272 | setring R; |
---|
273 | ideal rad = fetch(R1,rad); |
---|
274 | kill R1; |
---|
275 | return (rad); |
---|
276 | } |
---|
277 | ///////////////////////////////////////////////////////////////////////////// |
---|
278 | // |
---|
279 | static proc primAux (ideal I) |
---|
280 | " |
---|
281 | USAGE: primAux (I); I ideal. |
---|
282 | RETURN: 1, if I is primary; otherwise, an intvec, whose first element is |
---|
283 | 0, the second is the index of one variable such that a power of it |
---|
284 | does not appear as a generator of I, the rest of the elements are |
---|
285 | the situation in the ideal of that elements of I which |
---|
286 | are product of more than one variable. |
---|
287 | ASSUME: I is a monomial ideal of the basering K[x(1)..x(n)]. |
---|
288 | NOTE: This procedure detects if the ideal is primary, when the |
---|
289 | ideal is not primary, it gives some additional information. |
---|
290 | " |
---|
291 | { |
---|
292 | def R = basering; |
---|
293 | // Variables |
---|
294 | int control,nvar,i,sub_in,l,j; |
---|
295 | intvec v,w,exp_gen; |
---|
296 | // El ideal ya entra generado por el sistema minimal |
---|
297 | nvar = nvars(R); |
---|
298 | int sizI = size(I); |
---|
299 | v[nvar] = 0; |
---|
300 | int cont = 1; |
---|
301 | // v = 1 en la posicion en el ideal de variables sueltas, que son |
---|
302 | // las que no hay que tocar, 0 en las demas. w = posiciones de los |
---|
303 | // generadores de I que hay que comprobar. |
---|
304 | for (i = 1 ; i <= sizI ; i++ ) |
---|
305 | { |
---|
306 | sub_in = soporte(I[i]); |
---|
307 | if ( sub_in <> 0) |
---|
308 | { |
---|
309 | v[sub_in] = 1; |
---|
310 | } |
---|
311 | else |
---|
312 | { |
---|
313 | w[cont] = i; |
---|
314 | cont ++; |
---|
315 | } |
---|
316 | } |
---|
317 | l = size(w); |
---|
318 | // No hay ningun generador que tenga productos de variables, luego |
---|
319 | // este ideal ya es primario. |
---|
320 | if (l == 1 && w[1] == 0) |
---|
321 | { |
---|
322 | return (1); |
---|
323 | } |
---|
324 | for (i = 1 ; i <= l ; i++) |
---|
325 | { |
---|
326 | exp_gen = leadexp(I[w[i]]); |
---|
327 | // Ahora hay que ver que valor tiene el exponente de los |
---|
328 | // generadores oportunos en la posicion que es cero dentro del |
---|
329 | // vector v. |
---|
330 | for (j = 1 ; j <= nvar ; j++) |
---|
331 | { |
---|
332 | if (v[j] == 0) |
---|
333 | { |
---|
334 | if (exp_gen[j] <> 0) |
---|
335 | { |
---|
336 | return (0,j,w); |
---|
337 | } |
---|
338 | } |
---|
339 | } |
---|
340 | } |
---|
341 | // Si hemos llegado hasta aqui hemos recorrido todo el ideal y por tanto |
---|
342 | // es primario. |
---|
343 | return (1); |
---|
344 | } |
---|
345 | ///////////////////////////////////////////////////////////////////////////// |
---|
346 | // |
---|
347 | static proc maxExp (ideal I,intvec v) |
---|
348 | " |
---|
349 | USAGE: maxExp (I,v); I ideal, v integer vector. |
---|
350 | RETURN: an integer, the greatest power of a variable in the minimal |
---|
351 | monomial set of generators of I. |
---|
352 | ASSUME: I is a monomial ideal of the basering, v=primAux(I) and the |
---|
353 | variable considered is v[2]. |
---|
354 | If the ideal I is primary, it returns 0. |
---|
355 | NOTE: The elements of the vector shows what variable and what |
---|
356 | generators we must consider to look for the greatest power |
---|
357 | of this variable. |
---|
358 | " |
---|
359 | { |
---|
360 | // Variables |
---|
361 | int n,i,max; |
---|
362 | intvec exp; |
---|
363 | // Ponemos el tama?o de v menos 2 porque en el vector v a partir de |
---|
364 | // la tercera componente es donde tenemos la posicion de los |
---|
365 | // generadores que tenemos que estudiar. |
---|
366 | n = size(v)-2; |
---|
367 | // Buscamos el maximo de la variable que no aparece "sola" en los |
---|
368 | // generadores del ideal (donde nos indica v). |
---|
369 | max = 0; |
---|
370 | for (i = 1 ; i <= n ; i++) |
---|
371 | { |
---|
372 | exp = leadexp (I[v[i+2]]); |
---|
373 | if (exp[v[2]] > max) |
---|
374 | { |
---|
375 | max = exp[v[2]]; |
---|
376 | } |
---|
377 | } |
---|
378 | return (max); |
---|
379 | } |
---|
380 | ///////////////////////////////////////////////////////////////////////////// |
---|
381 | // |
---|
382 | static proc irredundant (list l) |
---|
383 | " |
---|
384 | USAGE: irredundant (l); l, list. |
---|
385 | RETURN: a list such that the intersection of the elements in that list has |
---|
386 | no redundant component. |
---|
387 | ASSUME: elements of l are monomial ideals of the basering. |
---|
388 | " |
---|
389 | { |
---|
390 | // Variables |
---|
391 | int i,j,resp; |
---|
392 | ideal J; |
---|
393 | // Recalculamos el tamano de l cuando modificamos la lista (sizl) |
---|
394 | int sizl = size(l); |
---|
395 | for (i = 1 ; i <= sizl ; i++) |
---|
396 | { |
---|
397 | J = 1; |
---|
398 | for (j = 1 ; j <= sizl ; j++) |
---|
399 | { |
---|
400 | // Hacemos la interseccion de todos los ideales menos uno y |
---|
401 | // luego se estudia el contenido. |
---|
402 | if (j <> i) |
---|
403 | { |
---|
404 | J = intersect (J,l[j]); |
---|
405 | } |
---|
406 | } |
---|
407 | J = minbase(J); |
---|
408 | resp = contents(J,l[i]); |
---|
409 | if (resp == 1) |
---|
410 | { |
---|
411 | l = delete (l,i); |
---|
412 | i--; |
---|
413 | sizl = size(l); |
---|
414 | } |
---|
415 | } |
---|
416 | return (l); |
---|
417 | } |
---|
418 | ///////////////////////////////////////////////////////////////////////////// |
---|
419 | // |
---|
420 | static proc alexDif (intvec v,ideal I) |
---|
421 | " |
---|
422 | USAGE: alexDif (v,I); v, intvec; I, ideal. |
---|
423 | RETURN: a list, irreducible monomial ideals whose intersection is the |
---|
424 | Alexander dual of I with respect to v. |
---|
425 | ASSUME: I is a monomial ideal of the basering K[x(1),...,x(n)] given by |
---|
426 | its minimal monomial generators and v is an integer vector with |
---|
427 | n entries s.t.monomial(v) is a multiple of all minimal monomial |
---|
428 | generators of I. |
---|
429 | " |
---|
430 | { |
---|
431 | // Cambiamos de anillo |
---|
432 | def R = basering; |
---|
433 | int nvar = nvars(R); |
---|
434 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
435 | execute(s); |
---|
436 | // Variables |
---|
437 | int i,j; |
---|
438 | intvec exp_I,exp; |
---|
439 | list l; |
---|
440 | ideal J; |
---|
441 | ideal I = fetch (R,I); |
---|
442 | int sizI = size(I); |
---|
443 | // Vamos a tener tantas componentes como generadores minimales tiene el |
---|
444 | // ideal, por eso el bucle es de 1 a size(I). |
---|
445 | for (i = 1 ; i <= sizI ; i++) |
---|
446 | { |
---|
447 | J = 0; |
---|
448 | exp_I = leadexp (I[i]); |
---|
449 | for (j = 1 ; j <= nvar ; j++) |
---|
450 | { |
---|
451 | if (exp_I[j] <> 0) |
---|
452 | { |
---|
453 | exp[j] = v[j] + 1 - exp_I[j]; |
---|
454 | J = J, x(j)^exp[j]; |
---|
455 | } |
---|
456 | } |
---|
457 | // Tenemos siempre un cero por la inicializacion de J, entonces |
---|
458 | // lo quitamos. |
---|
459 | J = simplify (J,2); |
---|
460 | l = insert (l,J); |
---|
461 | } |
---|
462 | setring R; |
---|
463 | list l = fetch (R1,l); |
---|
464 | kill R1; |
---|
465 | return (l); |
---|
466 | } |
---|
467 | ///////////////////////////////////////////////////////////////////////////// |
---|
468 | // |
---|
469 | static proc irredPrimary (list l1) |
---|
470 | " |
---|
471 | USAGE: irredPrimary (l1); l1, list of ideals. |
---|
472 | RETURN: a list, primary monomial ideals whose intersection is an |
---|
473 | irredundant primary decomposition. |
---|
474 | ASSUME: list l1 is the list of the irredundant irreducible components of a |
---|
475 | monomial ideal I of the basering. |
---|
476 | " |
---|
477 | { |
---|
478 | // Variables |
---|
479 | int i,sizl1,sizl2,j; |
---|
480 | ideal J,K; |
---|
481 | list l2,l3; |
---|
482 | //----- irredundant primary decomposition |
---|
483 | sizl1 = size(l1); |
---|
484 | for (i = 1 ; i <= sizl1 ; i++) |
---|
485 | { |
---|
486 | l2[i] = radicalAux (l1[i]); |
---|
487 | } |
---|
488 | sizl2 = size(l2); |
---|
489 | int sizl2i, sizl2j; |
---|
490 | // Looking for irreducible components whose radicals are equal. |
---|
491 | // l1 = irreducible components list |
---|
492 | // l2 = radical of irreducible components list |
---|
493 | // l3 = primary components list |
---|
494 | for (i = 1 ; i <= sizl1 ; i++) |
---|
495 | { |
---|
496 | J = l2[i]; |
---|
497 | sizl2i = size(l2[i]); |
---|
498 | K = l1[i]; |
---|
499 | for (j = i+1 ; j <= sizl2 ; j++) |
---|
500 | { |
---|
501 | sizl2j = size(l2[j]); |
---|
502 | if (sizl2i == sizl2j) |
---|
503 | { |
---|
504 | if (equal (J,l2[j]) == 1) |
---|
505 | { |
---|
506 | K = minbase(intersect (K,l1[j])); |
---|
507 | l1 = delete (l1,j); |
---|
508 | sizl1 = size(l1); |
---|
509 | l2 = delete (l2,j); |
---|
510 | sizl2 = size(l2); |
---|
511 | j--; |
---|
512 | } |
---|
513 | } |
---|
514 | } |
---|
515 | l3 = insert (l3,K); |
---|
516 | } |
---|
517 | return (l3); |
---|
518 | } |
---|
519 | ///////////////////////////////////////////////////////////////////////////// |
---|
520 | // |
---|
521 | static proc isMinimal (ideal I) |
---|
522 | " |
---|
523 | USAGE: isMinimal (I); I ideal. |
---|
524 | RETURN: 1, if the generators of I are the minimal ones; |
---|
525 | 0 & minimal generators of I, otherwise. |
---|
526 | ASSUME: I is an ideal of the basering generated by monomials. |
---|
527 | " |
---|
528 | { |
---|
529 | // VARIABLES |
---|
530 | int i; |
---|
531 | ideal J; |
---|
532 | // Quitamos los ceros del sistema de generadores. |
---|
533 | I = simplify(I,2); |
---|
534 | int resp = 1; |
---|
535 | int sizI = size(I); |
---|
536 | // Cambiamos el tamano de I cuando eliminamos generadores |
---|
537 | for (i = 1 ; i <= sizI ; i++) |
---|
538 | { |
---|
539 | if (sizI <> 1) |
---|
540 | { |
---|
541 | if (i == 1) |
---|
542 | { |
---|
543 | J = I[2..sizI]; |
---|
544 | } |
---|
545 | else |
---|
546 | { |
---|
547 | if (i > 1 && i < sizI) |
---|
548 | { |
---|
549 | J = I[1..i-1], I[i+1..sizI]; |
---|
550 | } |
---|
551 | else |
---|
552 | { |
---|
553 | J = I[1..sizI-1]; |
---|
554 | } |
---|
555 | } |
---|
556 | // Si quitamos el generador del lugar "i", luego el que |
---|
557 | // ocupa ahora el lugar "i" es el "i+1", de ahi que restemos |
---|
558 | // 1 al i para volver al for de manera que recorramos los |
---|
559 | // generadores como debemos. |
---|
560 | if (membershipMon(I[i],J) == 1) |
---|
561 | { |
---|
562 | resp = 0; |
---|
563 | I = J; |
---|
564 | i--; |
---|
565 | sizI = size(I); |
---|
566 | } |
---|
567 | } |
---|
568 | } |
---|
569 | if (resp == 1) |
---|
570 | { |
---|
571 | return (1); |
---|
572 | } |
---|
573 | else |
---|
574 | { |
---|
575 | return (0,I); |
---|
576 | } |
---|
577 | } |
---|
578 | ///////////////////////////////////////////////////////////////////////////// |
---|
579 | // |
---|
580 | static proc isMonomialGB (ideal I) |
---|
581 | " |
---|
582 | USAGE: isMonomialGB (I); I ideal. |
---|
583 | RETURN: a list, 1 & the minimal generators of I, if I is a monomial ideal; |
---|
584 | 0, otherwise. |
---|
585 | ASSUME: I is an ideal of the basering which is not generated by |
---|
586 | monomials. |
---|
587 | NOTE: this procedure is NOT Grobner free and should be used only if the |
---|
588 | ideal has non-monomial generators (use first checkIdeal) |
---|
589 | " |
---|
590 | { |
---|
591 | // Cambiamos de anillo |
---|
592 | def R = basering; |
---|
593 | int nvar = nvars(R); |
---|
594 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
595 | execute(s); |
---|
596 | |
---|
597 | // Variables |
---|
598 | int resp,m,k; |
---|
599 | // Queremos la base de Grobner reducida, para uncidad. |
---|
600 | ideal I = fetch(R,I); |
---|
601 | option(redSB); |
---|
602 | // Si el ideal es cero, no es monomial. |
---|
603 | if ( size(I) == 0) |
---|
604 | { |
---|
605 | return(0); |
---|
606 | } |
---|
607 | // Base de Grobner |
---|
608 | I = std(I); |
---|
609 | // Una vez que tenemos la GB, no es mas que comprobar que el ideal |
---|
610 | // esta generado por monomios. |
---|
611 | resp = checkIdeal(I); |
---|
612 | if (resp == 0) |
---|
613 | { |
---|
614 | setring R; |
---|
615 | kill R1; |
---|
616 | return (0); |
---|
617 | } |
---|
618 | else |
---|
619 | { |
---|
620 | setring R; |
---|
621 | I = fetch (R1,I); |
---|
622 | kill R1; |
---|
623 | return (1,I); |
---|
624 | } |
---|
625 | } |
---|
626 | ///////////////////////////////////////////////////////////////////////////// |
---|
627 | // |
---|
628 | // Comparing irreducible decompsitions |
---|
629 | // WARNING: this is not a test, when the answer is 1 and the decompositions |
---|
630 | // may not coincide but it is fast and easy and when the answer is |
---|
631 | // 0 the decomposition do not coincide. |
---|
632 | // |
---|
633 | proc areEqual(list l1,list l2) |
---|
634 | { |
---|
635 | def R = basering; |
---|
636 | l1 = fetch(R,l1); |
---|
637 | l2 = fetch(R,l2); |
---|
638 | int i,j,sizIdeal; |
---|
639 | poly generator; |
---|
640 | ideal l1Ideal,l2Ideal; |
---|
641 | int sizl1 = size(l1); |
---|
642 | for (i = 1 ; i <= sizl1 ; i ++) |
---|
643 | { |
---|
644 | sizIdeal = size(l1[i]); |
---|
645 | generator = 1; |
---|
646 | for (j = 1 ; j <= sizIdeal ; j ++) |
---|
647 | { |
---|
648 | generator = generator*l1[i][j]; |
---|
649 | } |
---|
650 | l1Ideal[i] = generator; |
---|
651 | } |
---|
652 | int sizl2 = size(l2); |
---|
653 | for (i = 1 ; i <= sizl2 ; i ++) |
---|
654 | { |
---|
655 | sizIdeal = size(l2[i]); |
---|
656 | generator = 1; |
---|
657 | for (j = 1 ; j <= sizIdeal ; j ++) |
---|
658 | { |
---|
659 | generator = generator*l2[i][j]; |
---|
660 | } |
---|
661 | l2Ideal[i] = generator; |
---|
662 | } |
---|
663 | return (equal(l1Ideal,l2Ideal)); |
---|
664 | } |
---|
665 | ///////////////////////////////////////////////////////////////////////////// |
---|
666 | //-------------------------------------------------------------------------// |
---|
667 | //----------------------- EXTERNOS ------------------------------------// |
---|
668 | //-------------------------------------------------------------------------// |
---|
669 | ///////////////////////////////////////////////////////////////////////////// |
---|
670 | // |
---|
671 | proc isMonomial (ideal I) |
---|
672 | "USAGE: isMonomial (I); I ideal. |
---|
673 | RETURN: 1, if I is monomial ideal; 0, otherwise. |
---|
674 | ASSUME: I is an ideal of the basering. |
---|
675 | EXAMPLE: example isMonomial; shows some examples. |
---|
676 | " |
---|
677 | { |
---|
678 | // Cambiamos de anillo |
---|
679 | def R = basering; |
---|
680 | int nvar = nvars(R); |
---|
681 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
682 | execute(s); |
---|
683 | // Variables |
---|
684 | int resp,m,k; |
---|
685 | // Queremos la base de Grobner reducida, para uncidad. |
---|
686 | ideal I = fetch(R,I); |
---|
687 | option(redSB); |
---|
688 | // Si el ideal es cero, no es monomial. |
---|
689 | if ( size(I) == 0) |
---|
690 | { |
---|
691 | return(0); |
---|
692 | } |
---|
693 | // Si ya viene dado por sistema de generadores monomiales, devolvemos 1 |
---|
694 | if (checkIdeal (I) == 1) |
---|
695 | { |
---|
696 | return(1); |
---|
697 | } |
---|
698 | // Hallamos GB |
---|
699 | I = std(I); |
---|
700 | // Una vez que tenemos la GB, no es mas que comprobar si el ideal |
---|
701 | // esta generado por monomios. |
---|
702 | resp = checkIdeal(I); |
---|
703 | // Volvemos a dejar el comando "std" devolviendo una GB estandar. |
---|
704 | option(noredSB); |
---|
705 | setring R; |
---|
706 | kill R1; |
---|
707 | return(resp); |
---|
708 | } |
---|
709 | example |
---|
710 | { "EXAMPLE:"; echo = 2; |
---|
711 | ring R = 0,(w,x,y,z,t),lp; |
---|
712 | ideal I = w^3*x*y, w^2*x^2*y^2*z^2 - y^3*z+x^4*z^4*t^4, w*x*y*z*t - w*x^6*y^5*z^4, x^2*z^4*t^3 , w^6*y^4*z^2 + x^2*y^2*z^2; |
---|
713 | isMonomial(I); |
---|
714 | ideal J = w^3*x*y + x^3*y^9*t^3, w^2*x^2*y^2*z^2 - y^3*z, w*x*y*z*t - w*x^6*y^5*z^4, x^2*z^4*t^3 + y^4*z^4*t^4, w^6*y^4*z^2 + x^2*y^2*z^2; |
---|
715 | isMonomial(J); |
---|
716 | } |
---|
717 | ///////////////////////////////////////////////////////////////////////////// |
---|
718 | // |
---|
719 | proc minbaseMon (ideal I) |
---|
720 | "USAGE: minbaseMon (I); I ideal. |
---|
721 | RETURN: an ideal, the minimal monomial generators of I. |
---|
722 | (-1 if the generators of I are not monomials) |
---|
723 | ASSUME: I is an ideal generated by a list of monomials of the basering. |
---|
724 | EXAMPLE: example minbaseMon; shows an example. |
---|
725 | " |
---|
726 | { |
---|
727 | // VARIABLES |
---|
728 | int i; |
---|
729 | ideal J; |
---|
730 | // Si no esta generado por monomios este metodo no vale |
---|
731 | int control = checkIdeal(I); |
---|
732 | if (control == 0) |
---|
733 | { |
---|
734 | return (-1); |
---|
735 | } |
---|
736 | // Quitamos los ceros del sistema de generadores. |
---|
737 | I = simplify(I,2); |
---|
738 | int sizI = size(I); |
---|
739 | for (i = 1 ; i <= sizI ; i++) |
---|
740 | { |
---|
741 | if (sizI > 1) |
---|
742 | { |
---|
743 | if (i == 1) |
---|
744 | { |
---|
745 | J = I[2..sizI]; |
---|
746 | } |
---|
747 | else |
---|
748 | { |
---|
749 | if (i > 1 && i < sizI) |
---|
750 | { |
---|
751 | J = I[1..i-1], I[i+1..sizI]; |
---|
752 | } |
---|
753 | else |
---|
754 | { |
---|
755 | if (i == sizI) |
---|
756 | { |
---|
757 | J = I[1..sizI-1]; |
---|
758 | } |
---|
759 | } |
---|
760 | } |
---|
761 | // Si quitamos el generador del lugar "i", luego el que |
---|
762 | // ocupa ahora el lugar "i" es el "i+1", de ahi que restemos |
---|
763 | // 1 al i para volver al for de manera que recorramos los |
---|
764 | // generadores como debemos. |
---|
765 | if (membershipMon(I[i],J) == 1) |
---|
766 | { |
---|
767 | I = J; |
---|
768 | i--; |
---|
769 | sizI = size(I); |
---|
770 | } |
---|
771 | } |
---|
772 | } |
---|
773 | return (I); |
---|
774 | } |
---|
775 | example |
---|
776 | {"EXAMPLE:"; echo = 2; |
---|
777 | ring R = 0,(w,x,y,z,t),lp; |
---|
778 | ideal I = w^3*x*y, w^2*x^2*y^2*z^2, y^3*z,x^4*z^4*t^4, w*x*y*z*t,w*x^6*y^5*z^4, x^2*z^4*t^3 , w^6*y^4*z^2,x^2*y^2*z^2; |
---|
779 | minbaseMon(I); |
---|
780 | } |
---|
781 | ///////////////////////////////////////////////////////////////////////////// |
---|
782 | // |
---|
783 | proc gcdMon (poly f,poly g) |
---|
784 | "USAGE: gcdMon (f,g); f,g polynomials. |
---|
785 | RETURN: a monomial, the greatest common divisor of f and g. |
---|
786 | ASSUME: f and g are monomials of the basering. |
---|
787 | EXAMPLE: example gcdMon; shows an example. |
---|
788 | " |
---|
789 | { |
---|
790 | if (size(f) <> 1 or size(g) <> 1) |
---|
791 | { |
---|
792 | ERROR ("the input must be 2 monomials."); |
---|
793 | } |
---|
794 | return(gcd(f,g)); |
---|
795 | |
---|
796 | // // Variables |
---|
797 | // int k; |
---|
798 | // intvec exp; |
---|
799 | // int nvar = nvars(basering); |
---|
800 | // // intput: monomials |
---|
801 | // |
---|
802 | // intvec expf = leadexp(f); |
---|
803 | // intvec expg = leadexp(g); |
---|
804 | // // Nos quedamos con el menor exponente de cada variable. |
---|
805 | // for (k = 1 ; k <= nvar ; k++) |
---|
806 | // { |
---|
807 | // if (expf[k] <= expg[k]) |
---|
808 | // { |
---|
809 | // exp[k] = expf[k]; |
---|
810 | // } |
---|
811 | // else |
---|
812 | // { |
---|
813 | // exp[k] = expg[k]; |
---|
814 | // } |
---|
815 | // } |
---|
816 | // // Devolvemos el monomio correspondiente al exponente que hemos |
---|
817 | // // calculado. |
---|
818 | // return(monomial(exp)); |
---|
819 | } |
---|
820 | example |
---|
821 | {"EXAMPLE:"; echo = 2; |
---|
822 | ring R = 0,(x,y,z,t),dp; |
---|
823 | poly f = x^3*z^5*t^2; |
---|
824 | poly g = y^6*z^3*t^3; |
---|
825 | gcdMon(f,g); |
---|
826 | } |
---|
827 | ///////////////////////////////////////////////////////////////////////////// |
---|
828 | // |
---|
829 | proc lcmMon (poly f,poly g) |
---|
830 | "USAGE: lcmMon (f,g); f,g polynomials. |
---|
831 | RETURN: a monomial,the least common multiple of f and g. |
---|
832 | ASSUME: f,g are monomials of the basering. |
---|
833 | EXAMPLE: example lcmMon; shows an example. |
---|
834 | " |
---|
835 | { |
---|
836 | // Hay que verificar que son monomios |
---|
837 | if (size(f) <> 1 or size(g) <> 1) |
---|
838 | { |
---|
839 | ERROR ("the input must be 2 monomials."); |
---|
840 | } |
---|
841 | // Variables. |
---|
842 | int k; |
---|
843 | intvec exp; |
---|
844 | int nvar = nvars(basering); |
---|
845 | |
---|
846 | // No tenemos mas que tomar el mayor exponente. |
---|
847 | intvec expf = leadexp (f); |
---|
848 | intvec expg = leadexp (g); |
---|
849 | |
---|
850 | for (k = 1 ; k <= nvar ; k ++) |
---|
851 | { |
---|
852 | if (expf[k] <= expg[k]) |
---|
853 | { |
---|
854 | exp[k] = expg[k]; |
---|
855 | } |
---|
856 | else |
---|
857 | { |
---|
858 | exp[k] = expf[k]; |
---|
859 | } |
---|
860 | } |
---|
861 | // Transformamos el vector de exponentes al monomio correspondiente. |
---|
862 | return(monomial (exp)); |
---|
863 | } |
---|
864 | example |
---|
865 | {"EXAMPLE:"; echo = 2; |
---|
866 | ring R = 0,(x,y,z,t),dp; |
---|
867 | poly f = x^3*z^5*t^2; |
---|
868 | poly g = y^6*z^3*t^3; |
---|
869 | lcmMon(f,g); |
---|
870 | } |
---|
871 | ////////////////////////////////////////////////////////////////////// |
---|
872 | // |
---|
873 | proc membershipMon(poly f,ideal I) |
---|
874 | "USAGE: membershipMon(f,I); f polynomial, I ideal. |
---|
875 | RETURN: 1, if f lies in I; 0 otherwise. |
---|
876 | (-1 if I and f are nonzero and I is not a monomial ideal) |
---|
877 | ASSUME: I is a monomial ideal of the basering. |
---|
878 | EXAMPLE: example membershipMon; shows some examples |
---|
879 | " |
---|
880 | { |
---|
881 | def R = basering; |
---|
882 | // Variables |
---|
883 | int i,j,resp,k,control; |
---|
884 | intvec restf; |
---|
885 | // Si el ideal es cero no es monomial, pero la pertenencia no se da si |
---|
886 | // el polinomio es no nulo |
---|
887 | if ( size(I) == 0 && size(f) > 0) |
---|
888 | { |
---|
889 | return (0); |
---|
890 | } |
---|
891 | // El cero esta en todos los ideales. |
---|
892 | if (f == 0) |
---|
893 | { |
---|
894 | return (1); |
---|
895 | } |
---|
896 | // COMPROBACIONES |
---|
897 | control = checkIdeal(I); |
---|
898 | if (control == 0) |
---|
899 | { |
---|
900 | list isMon = isMonomialGB (I); |
---|
901 | if (isMon[1] == 0) |
---|
902 | { |
---|
903 | ERROR ("the ideal is not monomial."); |
---|
904 | } |
---|
905 | else |
---|
906 | { |
---|
907 | // Sabemos que I ya viene dado por el sistema minimal de |
---|
908 | // generadores, aunque aqui no sea necesario. |
---|
909 | I = isMon[2]; |
---|
910 | } |
---|
911 | } |
---|
912 | // Quitamos ceros. |
---|
913 | I = simplify(I,2); |
---|
914 | int n = size(I); |
---|
915 | int m = size(f); |
---|
916 | int nvar = nvars(R); |
---|
917 | for (i=1 ; i<=m ; i++) |
---|
918 | { |
---|
919 | resp = 0; |
---|
920 | for (j=1 ; j<=n ;j++) |
---|
921 | { |
---|
922 | // Vamos termino a termino viendo si son divididos por algun |
---|
923 | // generador. Trabajamos con los exponentes, pues es mas |
---|
924 | // simple. |
---|
925 | restf = leadexp(f) - leadexp(I[j]); |
---|
926 | for (k=1 ; k<=nvar; k++) |
---|
927 | { |
---|
928 | // Si hay una componente negativa es que este generador |
---|
929 | // no divide. Queremos entonces ir al siguiente |
---|
930 | // generador. |
---|
931 | if (restf[k] < 0) |
---|
932 | { |
---|
933 | break; |
---|
934 | } |
---|
935 | } |
---|
936 | // Si no ha habido componente nula, hemos encontrado un |
---|
937 | // divisor para el actual termino de f. En esta situacion |
---|
938 | // queremos pasar a otro termino de f, no seguir con los |
---|
939 | // otros generadores. |
---|
940 | if (k == nvar+1) |
---|
941 | { |
---|
942 | resp = 1; |
---|
943 | break; |
---|
944 | } |
---|
945 | } |
---|
946 | // Si hemos encontrado para el anterior termino, voy al |
---|
947 | // siguiente; en caso contrario salimos, pues desde que un |
---|
948 | // termino no sea dividido, f no esta en I. |
---|
949 | if (resp == 1) |
---|
950 | { |
---|
951 | f = f - lead(f); |
---|
952 | } |
---|
953 | else |
---|
954 | { |
---|
955 | break; |
---|
956 | } |
---|
957 | } |
---|
958 | // Si hemos recorrido todo el bucle, f esta en I. |
---|
959 | if (i == m+1) |
---|
960 | { |
---|
961 | return (1); |
---|
962 | } |
---|
963 | return (0); |
---|
964 | } |
---|
965 | example |
---|
966 | {"EXAMPLE:"; echo = 2; |
---|
967 | ring R = 0,(w,x,y,z,t),lp; |
---|
968 | ideal I = w*x, x^2, y*z*t, y^5*t; |
---|
969 | poly f = 3*x^2*y + 6*t^5*z*y^6 - 4*x^2 + 8*w*x^5*y^6 - 10*y^10*t^10; |
---|
970 | membershipMon(f,I); |
---|
971 | poly g = 3*w^2*t^3 - 4*y^3*z*t^3 - 2*x^2*y^5*t + 4*x*y^3; |
---|
972 | membershipMon(g,I); |
---|
973 | } |
---|
974 | ////////////////////////////////////////////////////////////////////// |
---|
975 | // |
---|
976 | proc intersectMon (ideal I,ideal J) |
---|
977 | "USAGE: intersectMon (I,J); I,J ideals. |
---|
978 | RETURN: an ideal, the intersection of I and J. |
---|
979 | (it returns -1 if I or J are not monomial ideals) |
---|
980 | ASSUME: I,J are monomial ideals of the basering. |
---|
981 | NOTE: the minimal monomial generating set is returned. |
---|
982 | EXAMPLE: example intersectMon; shows some examples |
---|
983 | " |
---|
984 | { |
---|
985 | // Variables |
---|
986 | ideal K; |
---|
987 | int i,j,control; |
---|
988 | list isMon; |
---|
989 | // El ideal trivial no es monomial. |
---|
990 | if ( size(I) == 0 || size(J) == 0) |
---|
991 | { |
---|
992 | ERROR("one of the ideals is zero, hence not monomial."); |
---|
993 | } |
---|
994 | // COMPROBACIONES |
---|
995 | control = checkIdeal(I); |
---|
996 | if (control == 0) |
---|
997 | { |
---|
998 | isMon = isMonomialGB(I); |
---|
999 | if (isMon[1] == 0) |
---|
1000 | { |
---|
1001 | ERROR ("the first ideal is not monomial."); |
---|
1002 | } |
---|
1003 | else |
---|
1004 | { |
---|
1005 | // Sabemos que I ya viene dado por el sistema minimal de |
---|
1006 | // generadores, aunque aqui no sea necesario. |
---|
1007 | I = isMon[2]; |
---|
1008 | } |
---|
1009 | } |
---|
1010 | else |
---|
1011 | { |
---|
1012 | // Los generadores son monomiales, hallamos el sistema minimal |
---|
1013 | I = minbase(I); |
---|
1014 | } |
---|
1015 | control = checkIdeal(J); |
---|
1016 | if (control == 0) |
---|
1017 | { |
---|
1018 | isMon = isMonomialGB (J); |
---|
1019 | if (isMon[1] == 0) |
---|
1020 | { |
---|
1021 | ERROR ("the second ideal is not monomial."); |
---|
1022 | } |
---|
1023 | else |
---|
1024 | { |
---|
1025 | // Sabemos que J ya viene dado por el sistema minimal de |
---|
1026 | // generadores, aunque aqui no sea necesario. |
---|
1027 | J = isMon[2]; |
---|
1028 | } |
---|
1029 | } |
---|
1030 | else |
---|
1031 | { |
---|
1032 | // Los generadores son monomiales,hallamos la base minimal |
---|
1033 | J = minbase(J); |
---|
1034 | } |
---|
1035 | // Hemos asegurado que los ideales sean monomiales. |
---|
1036 | // Quitamos ceros de la base para no alargar calculos. |
---|
1037 | int n = size(I); |
---|
1038 | int m = size(J); |
---|
1039 | // Hallamos el m.c.m.de cada par de generadores de uno y otro ideal |
---|
1040 | // y los a?adimos al ideal interseccion. |
---|
1041 | for (i=1 ; i<=n ; i++) |
---|
1042 | { |
---|
1043 | for (j=1 ; j<=m ; j++) |
---|
1044 | { |
---|
1045 | K = K , lcmMon (I[i],J[j]); |
---|
1046 | } |
---|
1047 | } |
---|
1048 | // Devolvemos el ideal ya dado por la base minimal porque sabemos |
---|
1049 | // que este procedimiento genera muchos generadores redundantes. |
---|
1050 | return(minbase(K)); |
---|
1051 | } |
---|
1052 | example |
---|
1053 | {"EXAMPLE:"; echo = 2; |
---|
1054 | ring R = 0,(w,x,y,z,t),lp; |
---|
1055 | ideal I = w^3*x*y,w*x*y*z*t,x^2*y^2*z^2,x^2*z^4*t^3,y^3*z; |
---|
1056 | ideal J = w*x, x^2, y*z*t, y^5*t; |
---|
1057 | intersectMon (I,J); |
---|
1058 | } |
---|
1059 | ////////////////////////////////////////////////////////////////////// |
---|
1060 | // |
---|
1061 | proc quotientMon (ideal I,ideal J) |
---|
1062 | "USAGE: quotientMon (I,J); I,J ideals. |
---|
1063 | RETURN: an ideal, the quotient I:J. |
---|
1064 | (returns -1 if I or J is not monomial) |
---|
1065 | ASSUME: I,J are monomial ideals of the basering. |
---|
1066 | NOTE: the minimal monomial generating set is returned. |
---|
1067 | EXAMPLE: example quotientMon; shows an example. |
---|
1068 | " |
---|
1069 | { |
---|
1070 | // Variables |
---|
1071 | int i,control,n; |
---|
1072 | poly f; |
---|
1073 | list isMon; |
---|
1074 | //COMPROBACIONES |
---|
1075 | if (size(I) == 0 || size(J) == 0) |
---|
1076 | { |
---|
1077 | ERROR("one of the ideals is zero, hence not monomial."); |
---|
1078 | } |
---|
1079 | control = checkIdeal(I); |
---|
1080 | if (control == 0) |
---|
1081 | { |
---|
1082 | isMon = isMonomialGB (I); |
---|
1083 | if (isMon[1] == 0) |
---|
1084 | { |
---|
1085 | ERROR ("the first ideal is not monomial."); |
---|
1086 | } |
---|
1087 | else |
---|
1088 | { |
---|
1089 | // Sabemos que I ya viene dado por el sistema minimal de |
---|
1090 | // generadores, aunque aqui no sea necesario. |
---|
1091 | I = isMon[2]; |
---|
1092 | } |
---|
1093 | } |
---|
1094 | else |
---|
1095 | { |
---|
1096 | // Los generadores son monomiales,hallamos sistema minimal |
---|
1097 | I = minbase(I); |
---|
1098 | } |
---|
1099 | control = checkIdeal(J); |
---|
1100 | if (control == 0) |
---|
1101 | { |
---|
1102 | isMon = isMonomialGB (J); |
---|
1103 | if (isMon[1] == 0) |
---|
1104 | { |
---|
1105 | ERROR ("the second ideal is not monomial."); |
---|
1106 | return (-1); |
---|
1107 | } |
---|
1108 | else |
---|
1109 | { |
---|
1110 | // Sabemos que J ya viene dado por el sistema minimal de |
---|
1111 | // generadores, aunque aqui no sea necesario. |
---|
1112 | J = isMon[2]; |
---|
1113 | } |
---|
1114 | } |
---|
1115 | else |
---|
1116 | { |
---|
1117 | // Los generadores son monomiales, hallamos el sistema minimal |
---|
1118 | J = minbase(J); |
---|
1119 | } |
---|
1120 | // Tenemos los ideales dados por su sistema minimal (aunque no es necesario, ahorra |
---|
1121 | // calculos. En K vamos a tener la interseccion de los ideales. |
---|
1122 | ideal K = 1; |
---|
1123 | // ------ Empezamos a hacer el cociente. |
---|
1124 | // Los ideales estan dados por su sistema minimal, con lo que no aparecen ceros. |
---|
1125 | // Luego podemos usar size(J). |
---|
1126 | n = size(J); |
---|
1127 | for (i = 1 ; i <= n ; i++) |
---|
1128 | { |
---|
1129 | K = intersect (K ,quotientIdealMon(I,J[i])); |
---|
1130 | } |
---|
1131 | // Aqui tambien surgen muchos generadores que no forman parte de la |
---|
1132 | // base minimal del ideal obtenido. |
---|
1133 | return(minbase(K)); |
---|
1134 | } |
---|
1135 | example |
---|
1136 | {"EXAMPLE:"; echo = 2; |
---|
1137 | ring R = 0,(w,x,y,z,t),lp; |
---|
1138 | ideal I = w^3*x*y,w*x*y*z*t,x^2*y^2*z^2,x^2*z^4*t^3,y^3*z; |
---|
1139 | ideal J = w*x, x^2, y*z*t, y^5*t; |
---|
1140 | quotientMon (I,J); |
---|
1141 | } |
---|
1142 | ////////////////////////////////////////////////////////////////////// |
---|
1143 | // |
---|
1144 | proc radicalMon(ideal I) |
---|
1145 | "USAGE: radicalMon(I); I ideal |
---|
1146 | RETURN: an ideal, the radical ideal of the ideal I. |
---|
1147 | (returns -1 if I is not a monomial ideal) |
---|
1148 | ASSUME: I is a monomial ideal of the basering. |
---|
1149 | NOTE: the minimal monomial generating set is returned. |
---|
1150 | EXAMPLE: example radicalMon; shows an example. |
---|
1151 | " |
---|
1152 | { |
---|
1153 | // Cambiamos de anillo |
---|
1154 | def R = basering; |
---|
1155 | int nvar = nvars(R); |
---|
1156 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
1157 | execute(s); |
---|
1158 | // Variables |
---|
1159 | int i,m,j,control; |
---|
1160 | poly f; |
---|
1161 | intvec v; |
---|
1162 | ideal rad_I; |
---|
1163 | ideal I = fetch(R,I); |
---|
1164 | // COMPROBACIONES |
---|
1165 | control = checkIdeal(I); |
---|
1166 | // Si el sistema de generadores no esta formado por monomios, hay |
---|
1167 | // que comprobar si el ideal es monomial. |
---|
1168 | if (control == 0) |
---|
1169 | { |
---|
1170 | list isMon = isMonomialGB (I); |
---|
1171 | if (isMon[1] == 0) |
---|
1172 | { |
---|
1173 | ERROR ("the ideal is not monomial."); |
---|
1174 | } |
---|
1175 | else |
---|
1176 | { |
---|
1177 | I = isMon[2]; |
---|
1178 | // Ya lo tenemos con los generadores monomiales minimales |
---|
1179 | } |
---|
1180 | } |
---|
1181 | else |
---|
1182 | { |
---|
1183 | // Generadores monomiales, hallamos sistema minimal |
---|
1184 | I = minbase(I); |
---|
1185 | } |
---|
1186 | // Ya tenemos el ideal generado por la BASE MINIMAL MONOMIAL |
---|
1187 | m = size(I); |
---|
1188 | // Solo hay que poner exponente 1 a todas las variables que tengan |
---|
1189 | // exponente >1. |
---|
1190 | for (i = 1 ; i <= m ; i++) |
---|
1191 | { |
---|
1192 | v = leadexp(I[i]); |
---|
1193 | f = 1; |
---|
1194 | for (j = 1 ; j <= nvar ; j++) |
---|
1195 | { |
---|
1196 | if (v[j] <> 0) |
---|
1197 | { |
---|
1198 | f = f*x(j); |
---|
1199 | } |
---|
1200 | } |
---|
1201 | rad_I = rad_I,f; |
---|
1202 | } |
---|
1203 | setring R; |
---|
1204 | // Hay que devolver el ideal dado por la base minimal, pues se |
---|
1205 | // producen muchos generadores redundantes. |
---|
1206 | ideal rad_I = fetch(R1,rad_I); |
---|
1207 | kill R1; |
---|
1208 | return( minbase (rad_I)); |
---|
1209 | } |
---|
1210 | example |
---|
1211 | {"EXAMPLE:"; echo = 2; |
---|
1212 | ring R = 0,(w,x,y,z,t),lp; |
---|
1213 | ideal I = w^3*x*y,w*x*y*z*t,x^2*y^2*z^2,x^2*z^4*t^3,y^3*z; |
---|
1214 | radicalMon(I); |
---|
1215 | } |
---|
1216 | ////////////////////////////////////////////////////////////////////// |
---|
1217 | // |
---|
1218 | proc isprimeMon (ideal I) |
---|
1219 | "USAGE: isprimeMon (I); I ideal |
---|
1220 | RETURN: 1, if I is prime; 0, otherwise. |
---|
1221 | (returns -1 if I is not a monomial ideal) |
---|
1222 | ASSUME: I is a monomial ideal of the basering. |
---|
1223 | EXAMPLE: example isprimeMon; shows some example. |
---|
1224 | " |
---|
1225 | { |
---|
1226 | // Variables |
---|
1227 | int control,i,j,suma; |
---|
1228 | intvec expin; |
---|
1229 | // COMPROBACIONES |
---|
1230 | control = checkIdeal(I); |
---|
1231 | // Si el sistema de generadores no esta formado por monomios, hay |
---|
1232 | // que comprobar si el ideal es monomial. |
---|
1233 | if (control == 0) |
---|
1234 | { |
---|
1235 | list isMon = isMonomialGB (I); |
---|
1236 | if (isMon[1] == 0) |
---|
1237 | { |
---|
1238 | ERROR ("the ideal is not monomial."); |
---|
1239 | } |
---|
1240 | else |
---|
1241 | { |
---|
1242 | I = isMon[2]; |
---|
1243 | // Ya lo tenemos con los generadores minimales |
---|
1244 | } |
---|
1245 | } |
---|
1246 | else |
---|
1247 | { |
---|
1248 | // Generadores monomiales, hallamos el sistema minimal |
---|
1249 | I = minbase(I); |
---|
1250 | } |
---|
1251 | // Ya tenemos el ideal generado por la BASE MINIMAL |
---|
1252 | if (maxdeg1(I) == 1) |
---|
1253 | { |
---|
1254 | return (1); |
---|
1255 | } |
---|
1256 | return (0); |
---|
1257 | } |
---|
1258 | example |
---|
1259 | {"EXAMPLE:"; echo = 2; |
---|
1260 | ring R = 0,(w,x,y,z,t),lp; |
---|
1261 | ideal I = w,y,t; |
---|
1262 | isprimeMon (I); |
---|
1263 | ideal J = w,y,t,x*z; |
---|
1264 | isprimeMon (J); |
---|
1265 | } |
---|
1266 | ////////////////////////////////////////////////////////////////////// |
---|
1267 | // |
---|
1268 | proc isprimaryMon (ideal I) |
---|
1269 | "USAGE: isprimaryMon (I); I ideal |
---|
1270 | RETURN: 1, if I is primary; 0, otherwise. |
---|
1271 | (returns -1 if I is not a monomial ideal) |
---|
1272 | ASSUME: I is a monomial ideal of the basering. |
---|
1273 | EXAMPLE: example isprimaryMon; shows some examples |
---|
1274 | " |
---|
1275 | { |
---|
1276 | def R = basering; |
---|
1277 | // Variables |
---|
1278 | int nvar,control,m,l,sub_in,i,j,k; |
---|
1279 | intvec v,w,exp_gen; |
---|
1280 | // COMPROBACIONES |
---|
1281 | control = checkIdeal(I); |
---|
1282 | // Si el sistema de generadores no esta formado por monomios, hay |
---|
1283 | // que comprobar si el ideal es monomial. |
---|
1284 | if (control == 0) |
---|
1285 | { |
---|
1286 | list isMon = isMonomialGB (I); |
---|
1287 | if (isMon[1] == 0) |
---|
1288 | { |
---|
1289 | ERROR ("the ideal is not monomial."); |
---|
1290 | } |
---|
1291 | else |
---|
1292 | { |
---|
1293 | I = isMon[2]; |
---|
1294 | // Ya lo tenemos con los generadores minimales |
---|
1295 | } |
---|
1296 | } |
---|
1297 | else |
---|
1298 | { |
---|
1299 | // Generadores monomiales, hallamos el sistema minimal |
---|
1300 | I = minbase(I); |
---|
1301 | } |
---|
1302 | // Ya tenemos el ideal generado por la BASE MINIMAL |
---|
1303 | // Usamos la funcion "soporte" que hemos creado, para saber que |
---|
1304 | // variables aparecen en la base de generadores como producto de si |
---|
1305 | // mismas y tambien cuales son los generadores del ideal donde |
---|
1306 | // tenemos que comprobar si aparecen tales variables. |
---|
1307 | nvar = nvars(R); |
---|
1308 | m = size(I); |
---|
1309 | // Inicializo la ultima componente del vector para que contenga a |
---|
1310 | // todas las variables (el subindice de la variable es el lugar |
---|
1311 | // que ocupa como componente de v). |
---|
1312 | v[nvar] = 0; |
---|
1313 | k = 1; |
---|
1314 | // v = 1 en variables solas y 0 en el resto. |
---|
1315 | // w = lugar de los generadores de I que son producto de mas de una variable. |
---|
1316 | for (i = 1 ; i <= m ; i++) |
---|
1317 | { |
---|
1318 | sub_in = soporte(I[i]); |
---|
1319 | // Si soporte <> 0 la variable aparece sola, en caso contrario |
---|
1320 | // el generador es producto de mas de una variable |
---|
1321 | if (sub_in <> 0) |
---|
1322 | { |
---|
1323 | v[sub_in] = 1; |
---|
1324 | } |
---|
1325 | else |
---|
1326 | { |
---|
1327 | w[k] = i; |
---|
1328 | k++; |
---|
1329 | } |
---|
1330 | } |
---|
1331 | // Ahora solo hay que ver que no aparecen variables distintas de |
---|
1332 | // las que tenemos marcadas con 1 en v. |
---|
1333 | l = size(w); |
---|
1334 | // Si w es cero, quiere decir que todos los generadores del ideal |
---|
1335 | // son producto de una sola variable, luego es primario. |
---|
1336 | if (l == 1 && w[1] == 0) |
---|
1337 | { |
---|
1338 | return(1); |
---|
1339 | } |
---|
1340 | // Estudiamos el exponente de los generadores de I oportunos (los |
---|
1341 | // que nos indica w). |
---|
1342 | for (i = 1 ; i <= l ; i++) |
---|
1343 | { |
---|
1344 | exp_gen = leadexp(I[w[i]]); |
---|
1345 | for (j = 1 ; j <= nvar ; j++) |
---|
1346 | { |
---|
1347 | if (v[j] == 0) |
---|
1348 | { |
---|
1349 | if (exp_gen[j] <> 0) |
---|
1350 | { |
---|
1351 | return (0); |
---|
1352 | } |
---|
1353 | } |
---|
1354 | } |
---|
1355 | } |
---|
1356 | // Si hemos recorrido todo el ideal sin que salte el "for" |
---|
1357 | // quiere decir que no se ha contradicho la caracterizacion, |
---|
1358 | // luego el ideal es primario. |
---|
1359 | return(1); |
---|
1360 | } |
---|
1361 | example |
---|
1362 | {"EXAMPLE:"; echo = 2; |
---|
1363 | ring R = 0,(w,x,y,z,t),lp; |
---|
1364 | ideal I = w^4,x^3,z^2,t^5,x*t,w*x^2*z; |
---|
1365 | isprimaryMon (I); |
---|
1366 | ideal J = w^4,x^3,z^2,t^5,x*t,w*x^2*z,y^3*t^3; |
---|
1367 | isprimaryMon (J); |
---|
1368 | } |
---|
1369 | ////////////////////////////////////////////////////////////////////// |
---|
1370 | // |
---|
1371 | proc isirreducibleMon (ideal I) |
---|
1372 | "USAGE: isirreducibleMon(I); I ideal |
---|
1373 | RETURN: 1, if I is irreducible; 0, otherwise. |
---|
1374 | (return -1 if I is not a monomial ideal) |
---|
1375 | ASSUME: I is a monomial ideal of the basering. |
---|
1376 | EXAMPLE: example isirreducibleMon; shows some examples |
---|
1377 | " |
---|
1378 | { |
---|
1379 | // Variables |
---|
1380 | intvec v; |
---|
1381 | int n,i,j,sum,control; |
---|
1382 | control = checkIdeal(I); |
---|
1383 | // Si el sistema de generadores no esta formado por monomios, hay |
---|
1384 | // que comprobar si el ideal es monomial. |
---|
1385 | if (control == 0) |
---|
1386 | { |
---|
1387 | list isMon = isMonomialGB (I); |
---|
1388 | if (isMon[1] == 0) |
---|
1389 | { |
---|
1390 | ERROR ("the ideal is not monomial."); |
---|
1391 | } |
---|
1392 | else |
---|
1393 | { |
---|
1394 | I = isMon[2]; |
---|
1395 | // Ya lo tenemos con los generadores minimales |
---|
1396 | } |
---|
1397 | } |
---|
1398 | else |
---|
1399 | { |
---|
1400 | // Generadores monomiales, hallamos sistema minimal |
---|
1401 | I = minbase(I); |
---|
1402 | } |
---|
1403 | // Ya tenemos el ideal generado por la BASE MINIMAL |
---|
1404 | n = size(I); |
---|
1405 | // La funcion soporte devuelve 0 si el monomio es producto de mas |
---|
1406 | // de una variable. Chequeamos generador a generador si el ideal |
---|
1407 | // esta generado por potencias de variables. |
---|
1408 | for (i = 1 ; i <= n ; i ++) |
---|
1409 | { |
---|
1410 | if (soporte(I[i]) == 0) |
---|
1411 | { |
---|
1412 | return(0); |
---|
1413 | } |
---|
1414 | } |
---|
1415 | return (1); |
---|
1416 | } |
---|
1417 | example |
---|
1418 | {"EXAMPLE:"; echo = 2; |
---|
1419 | ring R = 0,(w,x,y,z,t),lp; |
---|
1420 | ideal I = w^4,x^3,z^2,t^5; |
---|
1421 | isirreducibleMon (I); |
---|
1422 | ideal J = w^4*x,x^3,z^2,t^5; |
---|
1423 | isirreducibleMon (J); |
---|
1424 | } |
---|
1425 | ////////////////////////////////////////////////////////////////////// |
---|
1426 | // |
---|
1427 | proc isartinianMon (ideal I) |
---|
1428 | "USAGE: isartinianMon(I); I ideal. |
---|
1429 | RETURN: 1, if ideal is artinian; 0, otherwise. |
---|
1430 | (return -1 if ideal I is not a monmomial ideal). |
---|
1431 | ASSUME: I is a monomial ideal of the basering. |
---|
1432 | EXAMPLE: example isartinianMon; shows some examples |
---|
1433 | " |
---|
1434 | { |
---|
1435 | def R = basering; |
---|
1436 | int nvar = nvars(R); |
---|
1437 | // Declaracion de variables |
---|
1438 | int i,j,k,cont,sizI; |
---|
1439 | intvec v; |
---|
1440 | // COMPROBACIONES |
---|
1441 | int control = checkIdeal(I); |
---|
1442 | // Si el sistema de generadores no esta formado por monomios, hay |
---|
1443 | // que comprobar si el ideal es monomial. |
---|
1444 | if (control == 0) |
---|
1445 | { |
---|
1446 | list isMon = isMonomialGB (I); |
---|
1447 | if (isMon[1] == 0) |
---|
1448 | { |
---|
1449 | ERROR ("the ideal is not monomial."); |
---|
1450 | } |
---|
1451 | else |
---|
1452 | { |
---|
1453 | I = isMon[2]; |
---|
1454 | // Ya lo tenemos con los generadores minimales |
---|
1455 | } |
---|
1456 | } |
---|
1457 | else |
---|
1458 | { |
---|
1459 | // Generadores monomiales, hallamos sistema minimal |
---|
1460 | I = minbase(I); |
---|
1461 | } |
---|
1462 | // Ya tenemos el ideal generado por la BASE MINIMAL |
---|
1463 | sizI = size(I); |
---|
1464 | // Comprobamos que entre los generadores minimales aparece una |
---|
1465 | // potencia de cada. Cuando encontramos un generador que es potencia |
---|
1466 | // de una sola variable aumento contador |
---|
1467 | cont = 0; |
---|
1468 | for (i = 1 ; i <= sizI ; i++) |
---|
1469 | { |
---|
1470 | if (soporte(I[i]) <> 0) |
---|
1471 | { |
---|
1472 | cont ++; |
---|
1473 | // Solo volvemos a evaluar en caso de que hayamos aumentado |
---|
1474 | if (cont == nvar) |
---|
1475 | { |
---|
1476 | // Ya hemos encontrado que todas las variables aparrecen en |
---|
1477 | // el sistema minimal como potencia pura. No queremos seguir |
---|
1478 | // buscando |
---|
1479 | return (1); |
---|
1480 | } |
---|
1481 | } |
---|
1482 | } |
---|
1483 | // Si ha salido, es que faltan variables |
---|
1484 | return(0); |
---|
1485 | } |
---|
1486 | example |
---|
1487 | {"EXAMPLE:"; echo = 2; |
---|
1488 | ring R = 0,(w,x,y,z,t),lp; |
---|
1489 | ideal I = w^4,x^3,y^4,z^2,t^6,w^2*x^2*y,w*z*t^4,x^2*y^3,z^2*t^5; |
---|
1490 | isartinianMon (I); |
---|
1491 | ideal J = w^4,x^3,y^4,z^2,w^2*x^2*y,w*z*t^4,x^2*y^3,z^2*t^5; |
---|
1492 | isartinianMon (J); |
---|
1493 | } |
---|
1494 | ////////////////////////////////////////////////////////////////////// |
---|
1495 | // |
---|
1496 | proc isgenericMon (ideal I) |
---|
1497 | "USAGE: isgenericMon(I); I ideal. |
---|
1498 | RETURN: 1, if ideal is generic; 0, otherwise. |
---|
1499 | (return -1 if ideal I is not a monomial ideal) |
---|
1500 | ASSUME: I is a monomial ideal of the basering. |
---|
1501 | EXAMPLE: example isgenericMon; shows some examples. |
---|
1502 | " |
---|
1503 | { |
---|
1504 | def R = basering; |
---|
1505 | int nvar = nvars(R); |
---|
1506 | // Declaracion de variables |
---|
1507 | int sizI,i,j,k; |
---|
1508 | list exp; |
---|
1509 | // COMPROBACIONES |
---|
1510 | int control = checkIdeal(I); |
---|
1511 | // Si el sistema de generadores no esta formado por monomios, hay |
---|
1512 | // que comprobar si el ideal es monomial. |
---|
1513 | if (control == 0) |
---|
1514 | { |
---|
1515 | list isMon = isMonomialGB (I); |
---|
1516 | if (isMon[1] == 0) |
---|
1517 | { |
---|
1518 | ERROR ("the ideal is not monomial."); |
---|
1519 | } |
---|
1520 | else |
---|
1521 | { |
---|
1522 | I = isMon[2]; |
---|
1523 | // Ya lo tenemos con los generadores minimales |
---|
1524 | } |
---|
1525 | } |
---|
1526 | else |
---|
1527 | { |
---|
1528 | // Generadores monomiales, hallamos sistema minimal |
---|
1529 | I = minbase(I); |
---|
1530 | } |
---|
1531 | // Ya tenemos el ideal generado por la BASE MINIMAL |
---|
1532 | sizI = size(I); |
---|
1533 | // Creamos una lista que tenga los exponentes de todos los |
---|
1534 | // generadores. |
---|
1535 | for (i = 1 ; i <= sizI ; i++) |
---|
1536 | { |
---|
1537 | exp[i] = leadexp(I[i]); |
---|
1538 | } |
---|
1539 | // Ahora hay que ver si alguno se repite, y si uno de ellos |
---|
1540 | // lo hace, ya no es gen?rico. |
---|
1541 | for (i = 1 ; i <= nvar ; i++) |
---|
1542 | { |
---|
1543 | for (j = 1 ; j <= sizI-1 ; j++) |
---|
1544 | { |
---|
1545 | for (k = j+1 ; k <= sizI ; k++) |
---|
1546 | { |
---|
1547 | // Notar que no se pueden repetir si la variable realmente |
---|
1548 | // aparece en el generador, es decir, exponente >1. |
---|
1549 | if (exp[j][i] == exp[k][i] & exp[j][i] <> 0) |
---|
1550 | { |
---|
1551 | return (0); |
---|
1552 | } |
---|
1553 | } |
---|
1554 | } |
---|
1555 | } |
---|
1556 | return (1); |
---|
1557 | } |
---|
1558 | example |
---|
1559 | {"EXAMPLE:"; echo = 2; |
---|
1560 | ring R = 0,(w,x,y,z,t),lp; |
---|
1561 | ideal I = w^4,x^3,y^4,z^2,w^2*x^2*y,w*z*t^4,x*y^3,z*t^5; |
---|
1562 | isgenericMon (I); |
---|
1563 | ideal J = w^4,x^3,y^4,z^3,w^2*x^2*y,w*z*t^4,x*y^3,z^2*t^5; |
---|
1564 | isgenericMon (J); |
---|
1565 | } |
---|
1566 | ////////////////////////////////////////////////////////////////////// |
---|
1567 | // |
---|
1568 | proc dimMon (ideal I) |
---|
1569 | "USAGE: dimMon (I); I ideal |
---|
1570 | RETURN: an integer, the dimension of the affine variety defined by |
---|
1571 | the ideal I. |
---|
1572 | (returns -1 if I is not a monomial ideal) |
---|
1573 | ASSUME: I is a monomial ideal of the basering. |
---|
1574 | EXAMPLE: example dimMon; shows some examples. |
---|
1575 | " |
---|
1576 | { |
---|
1577 | def R = basering; |
---|
1578 | int nvar = nvars(R); |
---|
1579 | // VARIABLES |
---|
1580 | int control,sizSum,sumandos,i,j,k,cont; |
---|
1581 | intvec index,indexAux,vaux,w; |
---|
1582 | list sum, sumAux; |
---|
1583 | // La base del ideal tiene que ser la monomial |
---|
1584 | // El ideal trivial no es monomial. |
---|
1585 | if ( size(I) == 0 ) |
---|
1586 | { |
---|
1587 | ERROR("the ideal is zero, hence not monomial."); |
---|
1588 | } |
---|
1589 | // COMPROBACIONES |
---|
1590 | control = checkIdeal(I); |
---|
1591 | if (control == 0) |
---|
1592 | { |
---|
1593 | list isMon = isMonomialGB (I); |
---|
1594 | if (isMon[1] == 0) |
---|
1595 | { |
---|
1596 | ERROR ("the ideal is not monomial."); |
---|
1597 | } |
---|
1598 | else |
---|
1599 | { |
---|
1600 | // Sabemos que I ya viene dado por el sistema minimal de |
---|
1601 | // generadores, aunque aqui no sea necesario. |
---|
1602 | I = isMon[2]; |
---|
1603 | } |
---|
1604 | } |
---|
1605 | // Si el ideal es artiniano, es 0-dimensional |
---|
1606 | if (isartinianMon(I) == 1) |
---|
1607 | { |
---|
1608 | return (0); |
---|
1609 | } |
---|
1610 | int sizI = size(I); |
---|
1611 | // v(i) = vector con sizI entradas y donde cada entrada "j" se corresponde |
---|
1612 | // con el exponente del generador "i" en la variable "j" |
---|
1613 | for (i = 1 ; i <= nvar ; i++) |
---|
1614 | { |
---|
1615 | intvec v(i); |
---|
1616 | for (j = 1 ; j <= sizI ;j++ ) |
---|
1617 | { |
---|
1618 | v(i)[j] = leadexp(I[j])[i]; |
---|
1619 | } |
---|
1620 | } |
---|
1621 | // Vamos a guardar en el vector "index" la ultima variable que se ha |
---|
1622 | // sumado y en cada "sum(i)" el vector suma que se corresponde con la |
---|
1623 | // entrada "i" del vector index. |
---|
1624 | // Inicializo los valores de index y de cada sum |
---|
1625 | w[sizI] = 0; |
---|
1626 | sum[1] = w; |
---|
1627 | index[1] = 0; |
---|
1628 | sizSum = 1; |
---|
1629 | while ( 1 ) |
---|
1630 | { |
---|
1631 | cont = 1; |
---|
1632 | sumandos ++; |
---|
1633 | for (i = 1 ; i <= sizSum ; i ++) |
---|
1634 | { |
---|
1635 | for (j = index[i] + 1 ; j <= nvar ; j ++) |
---|
1636 | { |
---|
1637 | w = sum[i]; |
---|
1638 | vaux = w + v(j); |
---|
1639 | // Comprobamos |
---|
1640 | for (k = 1 ; k <= sizI ; k ++) |
---|
1641 | { |
---|
1642 | if (vaux[k] == 0) |
---|
1643 | { |
---|
1644 | break; |
---|
1645 | } |
---|
1646 | } |
---|
1647 | if (k == sizI +1) |
---|
1648 | { |
---|
1649 | return (nvar - sumandos); |
---|
1650 | } |
---|
1651 | if (j <> nvar) |
---|
1652 | { |
---|
1653 | sumAux[cont] = vaux; |
---|
1654 | indexAux[cont] = j; |
---|
1655 | cont ++; |
---|
1656 | } |
---|
1657 | } |
---|
1658 | |
---|
1659 | } |
---|
1660 | index = indexAux; |
---|
1661 | sum = sumAux; |
---|
1662 | sizSum = size(sumAux); |
---|
1663 | } |
---|
1664 | } |
---|
1665 | example |
---|
1666 | {"EXAMPLE:"; echo = 2; |
---|
1667 | ring R = 0,(w,x,y,z,t),lp; |
---|
1668 | ideal I = w^3*x*y,w*x*y*z*t,x^2*y^2*z^2,x^2*z^4*t^3,y^3*z; |
---|
1669 | dimMon (I); |
---|
1670 | ideal J = w^4,x^3,y^4,z^2,t^6,w^2*x^2*y,w*z*t^4,x^2*y^3,z*t^5; |
---|
1671 | dimMon (J); |
---|
1672 | } |
---|
1673 | ///////////////////////////////////////////////////////////////////////////// |
---|
1674 | //-------------------------------------------------------------------------// |
---|
1675 | //----------------------- DESCOMPOSICIONES -----------------------------_// |
---|
1676 | //-------------------------------------------------------------------------// |
---|
1677 | ///////////////////////////////////////////////////////////////////////////// |
---|
1678 | // |
---|
1679 | // METODO 1: Metodo directo para descomp. irreducible (ver Vasconcelos) |
---|
1680 | // |
---|
1681 | ////////////////////////////////////////////////////////////////////// |
---|
1682 | // Este procedimiento calcula la descomposicion en irreducibles de // |
---|
1683 | // un ideal monomial dado por su base minimal de generadores // |
---|
1684 | // haciendo uso de la caracterizacion de ideal monomial irreducible // |
---|
1685 | // (Vasconcelos) // |
---|
1686 | ////////////////////////////////////////////////////////////////////// |
---|
1687 | // |
---|
1688 | static proc irredDec1 (ideal I) |
---|
1689 | { |
---|
1690 | // Cambiamos de anillo |
---|
1691 | def R = basering; |
---|
1692 | int nvar = nvars(R); |
---|
1693 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
1694 | execute(s); |
---|
1695 | // Variables |
---|
1696 | int i,j,n,resp; |
---|
1697 | list l1,l2; |
---|
1698 | intvec exp,v; |
---|
1699 | ideal J,K; |
---|
1700 | ideal I = fetch(R,I); |
---|
1701 | // ----- DESCOMPOSICION IRREDUCIBLE |
---|
1702 | // Inicializamos la lista que va a estar formada por los ideales |
---|
1703 | // que tenemos que comprobar son irreducibles. |
---|
1704 | I = simplify(I,1); |
---|
1705 | l1 = I; |
---|
1706 | while (size(l1) > 0) |
---|
1707 | { |
---|
1708 | for (i = 1 ; i <= size(l1) ; i++) |
---|
1709 | { |
---|
1710 | J = l1[i]; |
---|
1711 | n = size(J); |
---|
1712 | l1 = delete(l1,i); |
---|
1713 | // Llamamos a la funcion que va a detectar si el ideal es o |
---|
1714 | // no irreducible, y en caso de no serlo sabemos sobre que |
---|
1715 | // generador y con que variables hay que aplicar el |
---|
1716 | // el resultado teorico. |
---|
1717 | v = irredAux (J); |
---|
1718 | // No irreducible |
---|
1719 | if (size(v) > 1) |
---|
1720 | { |
---|
1721 | // En este caso, v[1] nos indica el generador del ideal |
---|
1722 | // que debemos eliminar. |
---|
1723 | exp = leadexp(J[v[1]]); |
---|
1724 | if (v[1] == 1) |
---|
1725 | { |
---|
1726 | J = J[2..n]; |
---|
1727 | } |
---|
1728 | if (v[1] > 1 && v[1] < n) |
---|
1729 | { |
---|
1730 | J = J[1..v[1]-1],J[v[1]+1..n]; |
---|
1731 | } |
---|
1732 | if (v[1] == n) |
---|
1733 | { |
---|
1734 | J = J[1..n-1]; |
---|
1735 | } |
---|
1736 | // Ahora vamos a introducir los nuevos generadores en |
---|
1737 | // cada uno de los nuevos ideales que generamos. Los |
---|
1738 | // ponemos en la lista en la que comprobamos. |
---|
1739 | for (j = 1 ; j <= size(v)-1 ; j++) |
---|
1740 | { |
---|
1741 | K = J,x(v[j+1])^exp[v[j+1]]; |
---|
1742 | l1 = insert(l1,minbase(K)); |
---|
1743 | } |
---|
1744 | } |
---|
1745 | // Si v[1]=0, el ideal es irreducible y lo introducimos en |
---|
1746 | // la lista l2, que es la que finalmente devolvera las |
---|
1747 | // componentes de la descomposicion. |
---|
1748 | else |
---|
1749 | { |
---|
1750 | l2 = insert(l2,J); |
---|
1751 | } |
---|
1752 | } |
---|
1753 | } |
---|
1754 | // ---- IRREDUNDANTE |
---|
1755 | l2 = irredundant (l2); |
---|
1756 | // La salida es la lista de los ideales irreducibles. |
---|
1757 | setring R; |
---|
1758 | list l2 = fetch(R1,l2); |
---|
1759 | kill R1; |
---|
1760 | return (l2); |
---|
1761 | } |
---|
1762 | ////////////////////////////////////////////////////////////////////// |
---|
1763 | // La siguiente funcion va a obtener una descomposicion primaria // |
---|
1764 | // minimal a partir de la irreducible anterior. // |
---|
1765 | ////////////////////////////////////////////////////////////////////// |
---|
1766 | // |
---|
1767 | static proc primDec1 (ideal I) { |
---|
1768 | // Variables |
---|
1769 | list l1,l2; |
---|
1770 | // ----- DESCOMPOSICION IRREDUCIBLE |
---|
1771 | l1 = irredDec1 (I); |
---|
1772 | // ----- DESCOMPOSICION PRIMARIA |
---|
1773 | l2 = irredPrimary (l1); |
---|
1774 | return (l2); |
---|
1775 | } |
---|
1776 | // |
---|
1777 | // METODO 2: Metodo directo para descomp. primaria (ver Vasconcelos) |
---|
1778 | // |
---|
1779 | ////////////////////////////////////////////////////////////////////// |
---|
1780 | // La siguiente funcion va a calcular una descomposicion primaria // |
---|
1781 | // minimal de un ideal monomial, pero esta vez usando la // |
---|
1782 | // caracterizacion de ideal monomial primario y un resultado que // |
---|
1783 | // hace uso de esta (Vasconcelos). // |
---|
1784 | ////////////////////////////////////////////////////////////////////// |
---|
1785 | // |
---|
1786 | static proc primDec2 (ideal I) { |
---|
1787 | // Cambiamos de anillo |
---|
1788 | def R = basering; |
---|
1789 | int nvar = nvars(R); |
---|
1790 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
1791 | execute(s); |
---|
1792 | // Variables en el nuevo anillo |
---|
1793 | int i,n,max; |
---|
1794 | list l1,l2; |
---|
1795 | intvec v; |
---|
1796 | ideal J,K; |
---|
1797 | ideal I = fetch(R,I); |
---|
1798 | // Vamos a tener dos listas: l1 que va a guardar todos los ideales |
---|
1799 | // que vayamos generando con el resultado citado antes, que seran |
---|
1800 | // los que vamos a comprobar si son primarios; y l2, donde guardamos |
---|
1801 | // aquellos de l1 que verifiquemos son primarios. |
---|
1802 | I = simplify(I,1); |
---|
1803 | l1 = I; |
---|
1804 | while (size(l1) > 0) |
---|
1805 | { |
---|
1806 | for (i = 1 ; i <= size(l1) ; i++) |
---|
1807 | { |
---|
1808 | J = l1[i]; |
---|
1809 | n = size(J); |
---|
1810 | l1 = delete (l1,i); |
---|
1811 | // Usamos la funcion que hemos creado para saber si el ideal |
---|
1812 | // es primario. Si no lo es devuelve la variable que crea |
---|
1813 | // conflicto y los generadores del ideal que luego hay que |
---|
1814 | // usar (los que tienen productos de mas de una vble). |
---|
1815 | // Se le llama con el sistema minimal de generadores |
---|
1816 | v = primAux (J); |
---|
1817 | // En caso de no ser primario, hay que buscar el maximo |
---|
1818 | // exponente de la variable que aparece en los generadores |
---|
1819 | // del ideal multiplicada siempre por otras variables, |
---|
1820 | // nunca por si misma. |
---|
1821 | if (v[1] == 0) |
---|
1822 | { |
---|
1823 | max = maxExp(J,v); |
---|
1824 | K = J,x(v[2])^max; |
---|
1825 | l1 = insert (l1,minbase(K)); |
---|
1826 | K = quotientIdealMon(J,x(v[2])^max); |
---|
1827 | // quotientidealMon devuelve sistema minimal de generadores |
---|
1828 | l1 = insert (l1,minbase(K)); |
---|
1829 | } |
---|
1830 | // En caso de ser primario, lo introducimos en la lista |
---|
1831 | // conveniente. |
---|
1832 | else |
---|
1833 | { |
---|
1834 | l2 = insert (l2,J); |
---|
1835 | } |
---|
1836 | } |
---|
1837 | } |
---|
1838 | // ------ IRREDUNDANTE |
---|
1839 | l2 = irredundant (l2); |
---|
1840 | setring R; |
---|
1841 | list l2 = fetch (R1,l2); |
---|
1842 | kill R1; |
---|
1843 | return (l2); |
---|
1844 | } |
---|
1845 | // |
---|
1846 | // METODO 3: via dual de Alexander y doble dual (Miller) |
---|
1847 | // |
---|
1848 | ////////////////////////////////////////////////////////////////////// |
---|
1849 | // Esta funcion calcula la descomposicion irreducible usando el // |
---|
1850 | // dual de Alexander teniendo en cuenta que el dual del dual es el // |
---|
1851 | // ideal de partida (Miller) // |
---|
1852 | ////////////////////////////////////////////////////////////////////// |
---|
1853 | // |
---|
1854 | static proc irredDec3 (ideal I) { |
---|
1855 | def R = basering; |
---|
1856 | int i,n,j; |
---|
1857 | poly lcm; |
---|
1858 | intvec v,exp_I,exp; |
---|
1859 | ideal J; |
---|
1860 | list l; |
---|
1861 | // Hallamos el m.c.m. de los generadores minimales del ideal. |
---|
1862 | n = size (I); |
---|
1863 | lcm = I[1]; |
---|
1864 | for ( i = 2 ; i <= n ; i++ ) |
---|
1865 | { |
---|
1866 | lcm = lcmMon (lcm,I[i]); |
---|
1867 | } |
---|
1868 | v = leadexp (lcm); |
---|
1869 | // Calculamos el dual de Alexander. |
---|
1870 | // Hacemos una funcion para este paso porque luego lo volveremos a |
---|
1871 | // utilizar. |
---|
1872 | l = alexDif (v,I); |
---|
1873 | // Tenemos los ideales irreducibles cuya interseccion nos da el dual |
---|
1874 | // de Alexander. Notar que tenemos tantos ideales como generadores |
---|
1875 | // minimales tiene I. |
---|
1876 | // Hallamos la base minimal. |
---|
1877 | J = minbase(intersect(l[1..size(l)])); |
---|
1878 | // Ya solo queda el ultimo paso: hallar de nuevo el dual de |
---|
1879 | // Alexander. Sabemos que este proceso ya devuelve la descomposicion |
---|
1880 | // irreducible irredundante. |
---|
1881 | l = alexDif (v,J); |
---|
1882 | return (l); |
---|
1883 | } |
---|
1884 | ////////////////////////////////////////////////////////////////////// |
---|
1885 | // En este caso hallamos una descomposicion primaria minimal usando // |
---|
1886 | // la irreducible irredundante del procedimiento anterior. // |
---|
1887 | ////////////////////////////////////////////////////////////////////// |
---|
1888 | // |
---|
1889 | static proc primDec3 (ideal I) { |
---|
1890 | // Variables |
---|
1891 | list l1,l2; |
---|
1892 | // ----- DESCOMPOSICION IREDUCIBLE |
---|
1893 | l1 = irredDec3 (I); |
---|
1894 | // ----- DESCOMPOSICION PRIMARIA |
---|
1895 | l2 = irredPrimary (l1); |
---|
1896 | return (l2); |
---|
1897 | } |
---|
1898 | // |
---|
1899 | // METODO 4: via dual de Alexander y cociente (Miller) |
---|
1900 | // |
---|
1901 | ////////////////////////////////////////////////////////////////////// |
---|
1902 | // Vamos a hallar las componentes irreducibles de un ideal monomial // |
---|
1903 | // dado por sus generadores minimales haciendo uso del dual de // |
---|
1904 | // Alexander (con el cociente) (Miller) // |
---|
1905 | ////////////////////////////////////////////////////////////////////// |
---|
1906 | // |
---|
1907 | static proc irredDec4 (ideal I) { |
---|
1908 | // Cambiamos de anillo. |
---|
1909 | def R = basering; |
---|
1910 | int nvar = nvars(R); |
---|
1911 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
1912 | execute(s); |
---|
1913 | // Variables |
---|
1914 | int n,i,j,m,resp; |
---|
1915 | poly lcm; |
---|
1916 | intvec v; |
---|
1917 | ideal J,K; |
---|
1918 | list L; |
---|
1919 | ideal I = fetch (R,I); |
---|
1920 | // Calculamos el l.c.m. de los generadores minimales del ideal. |
---|
1921 | n = size (I); |
---|
1922 | lcm = I[1]; |
---|
1923 | for ( i = 2 ; i <= n ; i++ ) |
---|
1924 | { |
---|
1925 | lcm = lcmMon (lcm,I[i]); |
---|
1926 | } |
---|
1927 | v = leadexp (lcm); |
---|
1928 | // Hallamos el ideal J = (x(1)^(l(1)+1),...,x(n)^(l(n)+1)). Como |
---|
1929 | // luego, en el procedimiento quotientMon, vamos a hallar la base |
---|
1930 | // minimal de cada ideal, no nos preocupa que tengamos un cero en |
---|
1931 | // el ideal J. |
---|
1932 | for ( i = 1 ; i <= nvar ; i++ ) |
---|
1933 | { |
---|
1934 | J[i] = (x(i))^(v[i]+1); |
---|
1935 | } |
---|
1936 | // Ahora hacemos el cociente oportuno. |
---|
1937 | K = minbase(quotient (J,I)); |
---|
1938 | // Buscamos aquellos generadores de K que no son divisibles por los |
---|
1939 | // generadores de J. Los generadores que son divisibles los hacemos |
---|
1940 | // cero y luego los eliminamos. |
---|
1941 | m = size (K); |
---|
1942 | for ( i = 1 ; i <= m ; i++ ) |
---|
1943 | { |
---|
1944 | resp = membershipMon(K[i],J); |
---|
1945 | if ( resp == 1) |
---|
1946 | { |
---|
1947 | K[i] = 0; |
---|
1948 | } |
---|
1949 | } |
---|
1950 | K = simplify (K,2); |
---|
1951 | // Ahora obtenemos las componentes de la descomposicion irreducible, |
---|
1952 | // que estan en correspondencia con los generadores minimales de K. |
---|
1953 | L = alexDif (v,K); |
---|
1954 | // Volvemos al anillo de partida y devolvemos la lista de las |
---|
1955 | // componentes irreducibles irredundantes. |
---|
1956 | setring R; |
---|
1957 | list L = fetch(R1,L); |
---|
1958 | kill R1; |
---|
1959 | return (L); |
---|
1960 | } |
---|
1961 | ////////////////////////////////////////////////////////////////////// |
---|
1962 | // Ahora hallamos una descomposicion primaria irredundante usando // |
---|
1963 | // la ultima funcion para hallar las componentes irreducibles de un // |
---|
1964 | // ideal monomial dado por sus generadores minimales. // |
---|
1965 | ////////////////////////////////////////////////////////////////////// |
---|
1966 | // |
---|
1967 | static proc primDec4 (ideal I) { |
---|
1968 | // Variables |
---|
1969 | list l1,l2; |
---|
1970 | // ----- DESCOMPOSICION IREDUCIBLE |
---|
1971 | l1 = irredDec4 (I); |
---|
1972 | // ----- DESCOMPOSICION PRIMARIA |
---|
1973 | l2 = irredPrimary (l1); |
---|
1974 | return (l2); |
---|
1975 | } |
---|
1976 | // |
---|
1977 | // METODO 5: un misterio!! |
---|
1978 | // |
---|
1979 | ////////////////////////////////////////////////////////////////////// |
---|
1980 | // Este procedimiento halla los elementos maximales de la base // |
---|
1981 | // estandar del ideal, que se correspoenden con las componentes // |
---|
1982 | // irreducibles del ideal 1-1. // |
---|
1983 | ////////////////////////////////////////////////////////////////////// |
---|
1984 | // |
---|
1985 | static proc irredDec5 (ideal I) |
---|
1986 | { |
---|
1987 | // New ring |
---|
1988 | def R = basering; |
---|
1989 | int nvar = nvars(R); |
---|
1990 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
1991 | execute(s); |
---|
1992 | ideal I = fetch (R,I); |
---|
1993 | //Variables |
---|
1994 | int i,j; |
---|
1995 | ideal K; |
---|
1996 | // Artinianization |
---|
1997 | list artiniano = artinian (I); |
---|
1998 | if (artiniano[1] == 0) |
---|
1999 | { |
---|
2000 | I = artiniano[2]; |
---|
2001 | intvec elimina = artiniano[3]; |
---|
2002 | } |
---|
2003 | // Quotient |
---|
2004 | ideal M = (x(1..nvar)); |
---|
2005 | ideal J = quotient (I,M); |
---|
2006 | // Deleting generators lying in I |
---|
2007 | for (i = 1 ; i <= size(J) ; i ++) |
---|
2008 | { |
---|
2009 | if (membershipMon(J[i],I) == 1) |
---|
2010 | { |
---|
2011 | if (i == 1) |
---|
2012 | { |
---|
2013 | J = J[2..size(J)]; |
---|
2014 | i --; |
---|
2015 | } |
---|
2016 | else |
---|
2017 | { |
---|
2018 | if (i == size(J)) |
---|
2019 | { |
---|
2020 | J = J[1..size(J)-1]; |
---|
2021 | i --; |
---|
2022 | } |
---|
2023 | else |
---|
2024 | { |
---|
2025 | J = J[1..i-1],J[i+1..size(J)]; |
---|
2026 | i --; |
---|
2027 | } |
---|
2028 | } |
---|
2029 | } |
---|
2030 | } |
---|
2031 | // Exponents of the ideals are going to form the decomposition |
---|
2032 | int sizJ = size(J); |
---|
2033 | for (i = 1 ; i <= sizJ ; i ++ ) |
---|
2034 | { |
---|
2035 | intvec exp(i) = leadexp(J[i]) + 1; |
---|
2036 | } |
---|
2037 | // Deleting artinianization process |
---|
2038 | if (artiniano[1] == 0) |
---|
2039 | { |
---|
2040 | // En elimina estan guardadas las variables que hay que eliminar |
---|
2041 | for (i = 1 ; i <= nvar ; i ++) |
---|
2042 | { |
---|
2043 | if (elimina[i] <> 0) |
---|
2044 | { |
---|
2045 | for (j = 1 ; j <= sizJ ; j ++) |
---|
2046 | { |
---|
2047 | if (exp(j)[i] == elimina[i]) |
---|
2048 | { |
---|
2049 | exp(j)[i] = 0; |
---|
2050 | } |
---|
2051 | } |
---|
2052 | } |
---|
2053 | } |
---|
2054 | } |
---|
2055 | // En exp(i) tengo los exponentes de cada variable de las que aparecen |
---|
2056 | // en cada ideal. |
---|
2057 | list facets; |
---|
2058 | for (i = 1 ; i <= sizJ ; i ++) |
---|
2059 | { |
---|
2060 | J = 0; |
---|
2061 | for (j = 1 ; j <= nvar ; j ++) |
---|
2062 | { |
---|
2063 | if (exp(i)[j] <> 0) |
---|
2064 | { |
---|
2065 | J = J,x(j)^exp(i)[j]; |
---|
2066 | } |
---|
2067 | } |
---|
2068 | J = simplify(J,2); |
---|
2069 | facets[i] = J; |
---|
2070 | } |
---|
2071 | setring R; |
---|
2072 | list facets = fetch (R1,facets); |
---|
2073 | kill R1; |
---|
2074 | return (facets); |
---|
2075 | } |
---|
2076 | ////////////////////////////////////////////////////////////////////// |
---|
2077 | // Ahora hallamos una descomposicion primaria irredundante usando // |
---|
2078 | // la ultima funcion para hallar las componentes irreducibles de un // |
---|
2079 | // ideal monomial dado por sus generadores minimales. // |
---|
2080 | ////////////////////////////////////////////////////////////////////// |
---|
2081 | // |
---|
2082 | static proc primDec5 (ideal I) { |
---|
2083 | // Variables |
---|
2084 | list l1,l2; |
---|
2085 | // ----- IRREDUCIBLE DECOMPOSITION |
---|
2086 | l1 = irredDec5 (I); |
---|
2087 | // ----- PRIMARY DECOMPOSITION |
---|
2088 | l2 = irredPrimary (l1); |
---|
2089 | return (l2); |
---|
2090 | } |
---|
2091 | // |
---|
2092 | // METODO 6: via complejo de Scarf (Milovsky) |
---|
2093 | // |
---|
2094 | ////////////////////////////////////////////////////////////////////// |
---|
2095 | // Metodo que usa el complejo de Scarf asociado a un ideal monomial // |
---|
2096 | // de k[x(1)..x(n)] (Milowski) // |
---|
2097 | ////////////////////////////////////////////////////////////////////// |
---|
2098 | ////////////////////////////////////////////////////////////////////// |
---|
2099 | // Calcula el maximo exponente de la variable x(i) entre los // |
---|
2100 | // generadores del ideal. // |
---|
2101 | ////////////////////////////////////////////////////////////////////// |
---|
2102 | // |
---|
2103 | static proc maximoExp(ideal I,int i) |
---|
2104 | { |
---|
2105 | // VARIABLES |
---|
2106 | int max,j,k,sizI; |
---|
2107 | intvec exp; |
---|
2108 | sizI = size(I); |
---|
2109 | max = 0; |
---|
2110 | for (j = 1 ; j <= sizI ; j ++) |
---|
2111 | { |
---|
2112 | exp = leadexp(I[j]); |
---|
2113 | if ( exp[i] > max) |
---|
2114 | { |
---|
2115 | max = exp[i]; |
---|
2116 | } |
---|
2117 | } |
---|
2118 | return(max); |
---|
2119 | } |
---|
2120 | ////////////////////////////////////////////////////////////////////// |
---|
2121 | // Esta funcion estudia si un ideal monomial dado por su sistema // |
---|
2122 | // minimal de generadores es o no artiniano. En caso de no serlo, // |
---|
2123 | // halla el artiniano mas proximo y ademas devuelve los generadores // |
---|
2124 | // que han sido introducidos. // |
---|
2125 | ////////////////////////////////////////////////////////////////////// |
---|
2126 | // |
---|
2127 | static proc artinian (ideal I) |
---|
2128 | { |
---|
2129 | // Cambiamos de anillo |
---|
2130 | def R = basering; |
---|
2131 | int nvar = nvars(R); |
---|
2132 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
2133 | execute(s); |
---|
2134 | // Declaracion de variables |
---|
2135 | int i,j,k,cont1,cont2,sizI,marcavar,max; |
---|
2136 | intvec v,variablesin,cambio; |
---|
2137 | list nuevo; |
---|
2138 | ideal J; |
---|
2139 | ideal I = fetch(R,I); |
---|
2140 | sizI = size(I); |
---|
2141 | // Comprobamos que entre los generadores minimales aparece una |
---|
2142 | // potencia de cada |
---|
2143 | cont2 = 0; |
---|
2144 | for (i = 1 ; i <= sizI ; i++) |
---|
2145 | { |
---|
2146 | v = leadexp(I[i]); |
---|
2147 | marcavar = 0; |
---|
2148 | cont1 = 0; |
---|
2149 | for (j = 1 ; j <= nvar ; j++) |
---|
2150 | { |
---|
2151 | if (v[j] <> 0) |
---|
2152 | { |
---|
2153 | cont1 ++; |
---|
2154 | marcavar = j; |
---|
2155 | } |
---|
2156 | } |
---|
2157 | // Si cont1=1 hemos encontrado un generador de los que nos |
---|
2158 | // interesa."variablesin" guarda el indice de las que estan. |
---|
2159 | if (cont1 == 1) |
---|
2160 | { |
---|
2161 | cont2 ++; |
---|
2162 | variablesin[cont2] = marcavar; |
---|
2163 | } |
---|
2164 | } |
---|
2165 | // Notar que como el sistema de generadores es minimal no se |
---|
2166 | // va a repetir la potencia de la misma variable. Por tanto basta |
---|
2167 | // comprobar si cont2 es o no nvar. |
---|
2168 | if (cont2 == nvar) |
---|
2169 | { |
---|
2170 | setring R; |
---|
2171 | list output; |
---|
2172 | output[1] = 1; |
---|
2173 | return(output); |
---|
2174 | } |
---|
2175 | else |
---|
2176 | { |
---|
2177 | J = I; |
---|
2178 | // Buscamos las que no estan |
---|
2179 | if (cont2 == 0) |
---|
2180 | { |
---|
2181 | for (i = 1 ; i <= nvar ; i ++) |
---|
2182 | { |
---|
2183 | max = maximoExp(I,i); |
---|
2184 | cambio[i] = max + 1; |
---|
2185 | J = J,x(i)^(max + 1); |
---|
2186 | } |
---|
2187 | } |
---|
2188 | else |
---|
2189 | { |
---|
2190 | for (i = 1 ; i <= nvar ; i++) |
---|
2191 | { |
---|
2192 | for (j = 1 ; j <= cont2 ; j ++) |
---|
2193 | { |
---|
2194 | if (i == variablesin[j]) |
---|
2195 | { |
---|
2196 | cambio[i] = 0; |
---|
2197 | break; |
---|
2198 | } |
---|
2199 | } |
---|
2200 | if (j == cont2 + 1) |
---|
2201 | { |
---|
2202 | max = maximoExp(I,i); |
---|
2203 | cambio[i] = max + 1; |
---|
2204 | J = J,x(i)^(max + 1); |
---|
2205 | } |
---|
2206 | } |
---|
2207 | } |
---|
2208 | list output; |
---|
2209 | output[1] = 0; |
---|
2210 | output[2] = J; |
---|
2211 | output[3] = cambio; |
---|
2212 | setring R; |
---|
2213 | list output = fetch (R1,output); |
---|
2214 | kill R1; |
---|
2215 | return(output); |
---|
2216 | } |
---|
2217 | } |
---|
2218 | ////////////////////////////////////////////////////////////////////// |
---|
2219 | // En este caso vamos primero a chequear si el ideal es o no // |
---|
2220 | // generico y en caso de no serlo vamos a devolver los cambios, // |
---|
2221 | // pues estos son una aplicacion biyectiva. // |
---|
2222 | ////////////////////////////////////////////////////////////////////// |
---|
2223 | // |
---|
2224 | static proc generic (ideal I) |
---|
2225 | { |
---|
2226 | // New ring |
---|
2227 | def R = basering; |
---|
2228 | int nvar = nvars(R); |
---|
2229 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
2230 | execute(s); |
---|
2231 | ideal I = fetch(R,I); |
---|
2232 | // VARIABLES |
---|
2233 | int i,j,k; |
---|
2234 | // Cargamos la matriz con los exponentes |
---|
2235 | int sizI = size(I); |
---|
2236 | intmat EXP[sizI][nvar]; |
---|
2237 | for (i = 1 ; i <= sizI ; i ++) |
---|
2238 | { |
---|
2239 | // Ordenamos el vector de exponentes oportuno |
---|
2240 | EXP[i,1..nvar] = leadexp(I[i]); |
---|
2241 | } |
---|
2242 | |
---|
2243 | // Ahora tenemos que ordenarla segun la variable que este en conficto. |
---|
2244 | intvec vari,change; |
---|
2245 | intmat NEWEXP = EXP; |
---|
2246 | list aux; |
---|
2247 | int count = 0; |
---|
2248 | for (i = 1 ; i <= nvar ; i ++) |
---|
2249 | { |
---|
2250 | // Buscamos conflicto en la variable x(i), para ello tengo que ordenar |
---|
2251 | // la columna i de EXP |
---|
2252 | vari = EXP[1..sizI,i]; |
---|
2253 | aux = sort(vari); |
---|
2254 | vari = aux[1]; |
---|
2255 | change = aux[2]; |
---|
2256 | for (j = 1 ; j <= sizI - 1 ; j ++) |
---|
2257 | { |
---|
2258 | if (vari[j] > 0) |
---|
2259 | { |
---|
2260 | while (NEWEXP[change[j + count] , i] >= vari[j + 1 + count]) |
---|
2261 | { |
---|
2262 | NEWEXP[change[j + 1 + count] , i] = NEWEXP[change[j + count] , i] + 1; |
---|
2263 | count ++; |
---|
2264 | if (j + 1 + count > sizI) |
---|
2265 | { |
---|
2266 | break; |
---|
2267 | } |
---|
2268 | } |
---|
2269 | } |
---|
2270 | j = j + count; |
---|
2271 | count = 0; |
---|
2272 | } |
---|
2273 | } |
---|
2274 | setring R; |
---|
2275 | I = fetch(R1,I); |
---|
2276 | // Devolvemos tambien la matriz, pues aqui tengo la biyeccion entre los exponentes |
---|
2277 | if (EXP == NEWEXP) |
---|
2278 | { |
---|
2279 | return (1,I); |
---|
2280 | } |
---|
2281 | else |
---|
2282 | { |
---|
2283 | // Hallamos el ideal con los nuevos exponentes |
---|
2284 | intvec expI; |
---|
2285 | for (i = 1 ; i <= sizI ; i ++) |
---|
2286 | { |
---|
2287 | expI = NEWEXP[i,1..nvar]; |
---|
2288 | I[i] = monomial(expI); |
---|
2289 | } |
---|
2290 | return(0,I,EXP,NEWEXP); |
---|
2291 | } |
---|
2292 | } |
---|
2293 | ////////////////////////////////////////////////////////////////////// |
---|
2294 | // Esta funci?n obtiene una descomposicion irreducible del ideal // |
---|
2295 | // monomial a partir de la descomposicion irreducible del idal // |
---|
2296 | // generico que le asociamos. // |
---|
2297 | ////////////////////////////////////////////////////////////////////// |
---|
2298 | // |
---|
2299 | static proc nonGeneric (EXP,NEWEXP,Faces,sizI) |
---|
2300 | { |
---|
2301 | def R = basering; |
---|
2302 | int nvar = nvars(R); |
---|
2303 | int sizFaces = size(Faces); |
---|
2304 | // Variables |
---|
2305 | int i,j,k; |
---|
2306 | // Vamos variable a variable |
---|
2307 | intvec exp, newexp; |
---|
2308 | list newFaces; |
---|
2309 | newFaces = Faces; |
---|
2310 | for (i = 1 ; i <= nvar ; i ++) |
---|
2311 | { |
---|
2312 | // comparamos las matrices de exponentes por columnas |
---|
2313 | exp = EXP[1..sizI,i]; |
---|
2314 | newexp = NEWEXP[1..sizI,i]; |
---|
2315 | if (exp <> newexp) |
---|
2316 | { |
---|
2317 | for (j = 1 ; j <= sizI ; j ++) |
---|
2318 | { |
---|
2319 | if (exp[j] <> newexp[j]) |
---|
2320 | { |
---|
2321 | for (k = 1 ; k <= sizFaces ; k ++) |
---|
2322 | { |
---|
2323 | if (Faces[k][i] == newexp[j]) |
---|
2324 | { |
---|
2325 | newFaces[k][i] = exp[j]; |
---|
2326 | } |
---|
2327 | } |
---|
2328 | } |
---|
2329 | } |
---|
2330 | } |
---|
2331 | } |
---|
2332 | return (newFaces); |
---|
2333 | } |
---|
2334 | ////////////////////////////////////////////////////////////////////// |
---|
2335 | // Este procedimiento va a dar una faceta inicial para el complejo // |
---|
2336 | // de Scarf asociado a I, donde I es un ideal monomial artiniano // |
---|
2337 | // y generico (evidentemente I dado por la bse minimal) // |
---|
2338 | ////////////////////////////////////////////////////////////////////// |
---|
2339 | // |
---|
2340 | static proc initialFacet (ideal I) |
---|
2341 | { |
---|
2342 | // Cambiamos de anillo |
---|
2343 | // Queremos usar x(1)..x(n) como variables. |
---|
2344 | def R = basering; |
---|
2345 | int nvar = nvars(R); |
---|
2346 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
2347 | execute(s); |
---|
2348 | // Declaracion de variables. |
---|
2349 | int i,sizJ,j,max,aux,sizK,l, elim; |
---|
2350 | intvec v; |
---|
2351 | list face; |
---|
2352 | // Traemos al nuevo anillo el ideal de entrada. |
---|
2353 | ideal I = fetch(R,I); |
---|
2354 | // Hacemos una copia de I pues ahora modificaremos el sistema |
---|
2355 | // de generadores. |
---|
2356 | ideal J = I; |
---|
2357 | sizJ = size(J); |
---|
2358 | // Para cada variable buscamos el maximo exponente, teniendo en |
---|
2359 | // cuenta que un mismo generador no puede dar dos exponentes. |
---|
2360 | // Vamos a guardar los exponentes en "expIni" |
---|
2361 | intvec expIni; |
---|
2362 | for (i = 1 ; i <= nvar ; i++) |
---|
2363 | { |
---|
2364 | max = 0; |
---|
2365 | for (j = 1 ; j <= sizJ ; j++) |
---|
2366 | { |
---|
2367 | aux = leadexp(J[j])[i]; |
---|
2368 | if (aux > max) |
---|
2369 | { |
---|
2370 | max = aux; |
---|
2371 | elim = j; |
---|
2372 | } |
---|
2373 | } |
---|
2374 | // Guardamos el exponente |
---|
2375 | expIni[i] = max; |
---|
2376 | // Ahora tenemos el maximo de la variable x(i), por lo que |
---|
2377 | // eliminamos el generador en el que la encontramos. |
---|
2378 | // Si queda un generador no hay nada que hacer |
---|
2379 | if (sizJ <> 1) |
---|
2380 | { |
---|
2381 | if (elim <> 1 & elim <> sizJ) |
---|
2382 | { |
---|
2383 | J = J[1..elim-1],J[elim+1..sizJ]; |
---|
2384 | } |
---|
2385 | else |
---|
2386 | { |
---|
2387 | if (elim == 1) |
---|
2388 | { |
---|
2389 | J = J[2..sizJ]; |
---|
2390 | } |
---|
2391 | else |
---|
2392 | { |
---|
2393 | J = J[1..sizJ-1]; |
---|
2394 | } |
---|
2395 | } |
---|
2396 | sizJ = size(J); |
---|
2397 | // Eliminamos la variable x(i) en todos los generadores. |
---|
2398 | for (j = 1 ; j <= sizJ ; j++) |
---|
2399 | { |
---|
2400 | v = leadexp(J[j]); |
---|
2401 | if (v [i] <> 0) |
---|
2402 | { |
---|
2403 | v[i] = 0; |
---|
2404 | J[j] = monomial(v); |
---|
2405 | } |
---|
2406 | } |
---|
2407 | // Hallamos el sistema minimal de generadores que |
---|
2408 | // corresponde al ideal que nos ha quedado. |
---|
2409 | J = minbase(J); |
---|
2410 | sizJ = size(J); |
---|
2411 | } |
---|
2412 | } |
---|
2413 | // En expIni tenemos los exponentes de los monomios que dan la cara |
---|
2414 | // inicial, ahora hay que buscar en el ideal original a que |
---|
2415 | // generador se corresponde (el ideal es generico) |
---|
2416 | int sizI = size(I); |
---|
2417 | for (i = 1 ; i <= nvar ; i ++) |
---|
2418 | { |
---|
2419 | for (j = 1 ; j <= sizI ; j ++) |
---|
2420 | { |
---|
2421 | if (expIni[i] == leadexp(I[j])[i]) |
---|
2422 | { |
---|
2423 | face = insert(face, I[j]); |
---|
2424 | // Si lo encontramos buscamos el siguiente |
---|
2425 | break; |
---|
2426 | } |
---|
2427 | } |
---|
2428 | } |
---|
2429 | setring R; |
---|
2430 | list face = fetch (R1,face); |
---|
2431 | kill R1; |
---|
2432 | return (face); |
---|
2433 | } |
---|
2434 | ////////////////////////////////////////////////////////////////////// |
---|
2435 | // La funcion que sigue devuelve las facetas adyacentes a una dada // |
---|
2436 | // en el complejo de Scarf asociado a I. // |
---|
2437 | ////////////////////////////////////////////////////////////////////// |
---|
2438 | // |
---|
2439 | static proc adyacency (list l1, ideal I) |
---|
2440 | { |
---|
2441 | // Cambiamos de anillo |
---|
2442 | // Queremos usar x(1)..x(n) como variables. |
---|
2443 | def R = basering; |
---|
2444 | int nvar = nvars(R); |
---|
2445 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
2446 | execute(s); |
---|
2447 | // Declaracion de variables. |
---|
2448 | int i,j,cambio,sizI,k,min,m,generador,max; |
---|
2449 | list l2,newl1,w,expI; |
---|
2450 | poly LCM,newLCM; |
---|
2451 | intvec v,newv,expgen; |
---|
2452 | // Traemos al nuevo anillo las dos entradas. |
---|
2453 | list l1 = fetch(R,l1); |
---|
2454 | ideal I = fetch(R,I); |
---|
2455 | sizI = size(I); |
---|
2456 | // Hallamos el lcm de los elementos, e. d., la faceta del |
---|
2457 | // complejo para luego comparar con los nuevos |
---|
2458 | LCM = 1; |
---|
2459 | for (i = 1 ; i <= nvar ; i++) |
---|
2460 | { |
---|
2461 | LCM = lcmMon(LCM,l1[i]); |
---|
2462 | } |
---|
2463 | v = leadexp(LCM); |
---|
2464 | // Calculo los exponentes de los monomios de I |
---|
2465 | for (i = 1 ; i <= sizI ; i++) |
---|
2466 | { |
---|
2467 | expI[i] = leadexp(I[i]); |
---|
2468 | } |
---|
2469 | // Hay que quitar cada elemento de la lista y comprobar si hay o no |
---|
2470 | // cara adyacente al simplice que queda, y en caso de haberla, la |
---|
2471 | // calculamos. |
---|
2472 | for (i = 1 ; i <= nvar ; i++) |
---|
2473 | { |
---|
2474 | newl1 = delete(l1,i); |
---|
2475 | // Hallamos el lcm de los elementos que hay en la nueva lista. |
---|
2476 | newLCM = 1; |
---|
2477 | for (j = 1 ; j <= nvar - 1 ; j++) |
---|
2478 | { |
---|
2479 | newLCM = lcmMon(newLCM,newl1[j]); |
---|
2480 | } |
---|
2481 | // Ahora hay que detectar si alguna variable ha desaparecido |
---|
2482 | // en este LCM. |
---|
2483 | newv = leadexp(newLCM); |
---|
2484 | for (j = 1 ; j <= nvar ; j++) |
---|
2485 | { |
---|
2486 | if (newv[j] == 0) |
---|
2487 | { |
---|
2488 | l2[i] = 0; |
---|
2489 | break; |
---|
2490 | } |
---|
2491 | } |
---|
2492 | if (j == nvar+1) |
---|
2493 | { |
---|
2494 | // Si no ha habido ceros, queremos hallar la cara adyacente, |
---|
2495 | // es decir, buscar un generador que introducido en l1 de una |
---|
2496 | // faceta del complejo. |
---|
2497 | // Comparamos los lcm entre s?, para comprobar en que variable |
---|
2498 | // contribu?a el monomio que hemos eliminado. |
---|
2499 | for (j = 1 ; j <= nvar ; j++) |
---|
2500 | { |
---|
2501 | if (v[j] <> newv[j]) |
---|
2502 | { |
---|
2503 | cambio = j; |
---|
2504 | // Una vez encontrado no hay mas |
---|
2505 | break; |
---|
2506 | } |
---|
2507 | } |
---|
2508 | // Hallamos los exponentes de los monomios que quedan |
---|
2509 | // para ver cual da el exponente en "newv" |
---|
2510 | for (j = 1 ; j <= nvar - 1 ; j++) |
---|
2511 | { |
---|
2512 | w[j] = leadexp(newl1[j]); |
---|
2513 | } |
---|
2514 | for (j = 1 ; j <= nvar ; j++) |
---|
2515 | { |
---|
2516 | for (k = 1 ; k <= nvar - 1 ; k++) |
---|
2517 | { |
---|
2518 | if (newv[cambio] == w[k][cambio]) |
---|
2519 | { |
---|
2520 | cambio = k; |
---|
2521 | break; |
---|
2522 | } |
---|
2523 | } |
---|
2524 | // Si no termino el for con k es que hemos encontrado ya |
---|
2525 | // los que son iguales. |
---|
2526 | if (k <> nvar) |
---|
2527 | { |
---|
2528 | break; |
---|
2529 | } |
---|
2530 | } |
---|
2531 | |
---|
2532 | // Donde contribuye antes, e.d., en "v" |
---|
2533 | for (j = 1 ; j <= nvar ; j++) |
---|
2534 | { |
---|
2535 | if (w[cambio][j] == v[j]) |
---|
2536 | { |
---|
2537 | cambio = j; |
---|
2538 | break; |
---|
2539 | } |
---|
2540 | } |
---|
2541 | // Ahora ya buscamos entre los generadores el nuevo monomio. |
---|
2542 | // Ponemos de tope para encontrar el minimo el maximo de |
---|
2543 | // las variables en el ideal |
---|
2544 | max = 0; |
---|
2545 | for (m = 1 ; m <= sizI ; m ++) |
---|
2546 | { |
---|
2547 | if (expI[m][cambio] > max) |
---|
2548 | { |
---|
2549 | max = expI[m][cambio]; |
---|
2550 | } |
---|
2551 | } |
---|
2552 | min = max; |
---|
2553 | for (j = 1 ; j <= sizI ; j++) |
---|
2554 | { |
---|
2555 | for (k = 1 ; k <= nvar ; k ++) |
---|
2556 | { |
---|
2557 | if (I[j] == l1[k]) |
---|
2558 | { |
---|
2559 | break; |
---|
2560 | } |
---|
2561 | } |
---|
2562 | // El generador no esta en la lista, es de los que hay que |
---|
2563 | // comprobar |
---|
2564 | if (k == nvar +1) |
---|
2565 | { |
---|
2566 | for (m = 1 ; m <= nvar ; m++) |
---|
2567 | { |
---|
2568 | if (m <> cambio) |
---|
2569 | { |
---|
2570 | if (expI[j][m] > newv[m]) |
---|
2571 | { |
---|
2572 | break; |
---|
2573 | } |
---|
2574 | } |
---|
2575 | else |
---|
2576 | { |
---|
2577 | if (expI[j][m] <= newv[m]) |
---|
2578 | { |
---|
2579 | break; |
---|
2580 | } |
---|
2581 | } |
---|
2582 | } |
---|
2583 | // Si termina el bucle cumple las condiciones |
---|
2584 | // oportunas, solo hay que comparar con el |
---|
2585 | // otro que tengamos. |
---|
2586 | if (m == nvar + 1) |
---|
2587 | { |
---|
2588 | if (expI[j][cambio] <= min) |
---|
2589 | { |
---|
2590 | min = expI[j][cambio]; |
---|
2591 | generador = j; |
---|
2592 | } |
---|
2593 | } |
---|
2594 | } |
---|
2595 | } |
---|
2596 | // En la lista ponemos en el lugar "i" el generador que |
---|
2597 | // hay que introducir cuando eliminamos el generador |
---|
2598 | // "i" de la lista de entrada. |
---|
2599 | l2[i] = I[generador]; |
---|
2600 | } |
---|
2601 | } |
---|
2602 | setring R; |
---|
2603 | list l2 = fetch(R1,l2); |
---|
2604 | kill R1; |
---|
2605 | return(l2); |
---|
2606 | } |
---|
2607 | ////////////////////////////////////////////////////////////////////// |
---|
2608 | // Metodo que calcula la descomposicion irreducible de un ideal // |
---|
2609 | // monomial usando el complejo de Scarf (Milowski) // |
---|
2610 | ////////////////////////////////////////////////////////////////////// |
---|
2611 | // |
---|
2612 | static proc ScarfMethod (ideal I) |
---|
2613 | { |
---|
2614 | // Cambiamos de anillo |
---|
2615 | // Queremos usar x(1)..x(n) como variables. |
---|
2616 | def R = basering; |
---|
2617 | int nvar = nvars(R); |
---|
2618 | // Sabemos que dp siempre es mejor para trabajar, auqque luego para |
---|
2619 | // comparar I y genI vamos a cambiarlo al lexicografico. |
---|
2620 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
2621 | execute(s); |
---|
2622 | // Variables |
---|
2623 | int i,j,k,sizl1,sizl,cont1,cont2; |
---|
2624 | int sizI; |
---|
2625 | list auxl,expl1,l1,l,l2,newLCM,expI,expgenI,Faces; |
---|
2626 | poly LCM,mon; |
---|
2627 | intvec v,w,betas; |
---|
2628 | ideal J,genI,artgenI; |
---|
2629 | ideal I = fetch(R,I); |
---|
2630 | // Comprobamos si el ideal es generico y artiniano, y, en caso de |
---|
2631 | // no serlo, obtenemos una modificacion de este ideal que si |
---|
2632 | // verifique estas propiedades |
---|
2633 | list genericlist = generic(I); |
---|
2634 | if (genericlist[1] == 0) |
---|
2635 | { |
---|
2636 | genI = genericlist[2]; |
---|
2637 | } |
---|
2638 | else |
---|
2639 | { |
---|
2640 | genI = I; |
---|
2641 | } |
---|
2642 | list artinianization = artinian (genI); |
---|
2643 | if (artinianization[1] == 0) |
---|
2644 | { |
---|
2645 | artgenI = artinianization[2]; |
---|
2646 | } |
---|
2647 | else |
---|
2648 | { |
---|
2649 | artgenI = genI; |
---|
2650 | } |
---|
2651 | // Una vez tenemos el ideal artiniano y generico, podemos hallar |
---|
2652 | // el complejo de Scarf asociado al ideal modificado |
---|
2653 | |
---|
2654 | // Hay que obtener una cara inicial del ideal. |
---|
2655 | list initial = initialFacet(artgenI); |
---|
2656 | // Ahora de cada cara que tengamos en una lista obtenemos sus |
---|
2657 | // caras adyacentes. Hay que tener en cuenta que si una cara la |
---|
2658 | // obtengo como adyacente de otra, cuando calculemos sus adyacentes |
---|
2659 | // sale la anterior, luego hay que evitar repetir. |
---|
2660 | // Guardamos la primera faceta, su LCM |
---|
2661 | LCM = 1; |
---|
2662 | for (i = 1 ; i <= nvar ; i++) |
---|
2663 | { |
---|
2664 | mon = initial[i]; |
---|
2665 | LCM = lcmMon(LCM,mon); |
---|
2666 | } |
---|
2667 | v = leadexp(LCM); |
---|
2668 | // Guardamos la primera faceta |
---|
2669 | Faces[1] = v; |
---|
2670 | int sizfaces = 1; |
---|
2671 | // Lista de monomios que dan las facetas para hallar sus caras |
---|
2672 | // adyacentes |
---|
2673 | l[1] = initial; |
---|
2674 | sizl = 1; |
---|
2675 | // Ahora hayamos las posibles caras maximales adyacentes |
---|
2676 | while (sizl <> 0) |
---|
2677 | { |
---|
2678 | // Hallamos la lista de monomios que hay que introducir |
---|
2679 | // cuando eliminamos cada monomio. |
---|
2680 | auxl = adyacency(l[1],artgenI); |
---|
2681 | cont1 = 1; |
---|
2682 | cont2 = 0; |
---|
2683 | l1 = 0; |
---|
2684 | for (j = 1 ; j <= nvar ; j++) |
---|
2685 | { |
---|
2686 | if (auxl[j] <> 0) |
---|
2687 | { |
---|
2688 | l2 = delete(l[1],j); |
---|
2689 | l1[cont1] = insert(l2,auxl[j],cont1 + cont2 - 1); |
---|
2690 | cont1 ++; |
---|
2691 | } |
---|
2692 | else |
---|
2693 | { |
---|
2694 | cont2 ++; |
---|
2695 | } |
---|
2696 | } |
---|
2697 | // Hallamos los nuevos LCM |
---|
2698 | sizl1 = size(l1); |
---|
2699 | for (i = 1 ; i <= sizl1 ; i++) |
---|
2700 | { |
---|
2701 | newLCM[i] = 1; |
---|
2702 | for (j = 1 ; j <= nvar ; j++) |
---|
2703 | { |
---|
2704 | newLCM[i] = lcmMon(newLCM[i],l1[i][j]); |
---|
2705 | } |
---|
2706 | expl1[i] = leadexp(newLCM[i]); |
---|
2707 | } |
---|
2708 | // Hallamos los LCM de las nuevas caras y eliminamos las que |
---|
2709 | // ya esten en la lista Faces |
---|
2710 | cont1 = 0; |
---|
2711 | cont2 = 0; |
---|
2712 | for (i = 1 ; i <= sizl1 ; i++) |
---|
2713 | { |
---|
2714 | for (j = 1 ; j <= sizfaces ; j++) |
---|
2715 | { |
---|
2716 | v = expl1[i]; |
---|
2717 | w = Faces[j]; |
---|
2718 | if (v == w) |
---|
2719 | { |
---|
2720 | // Si ya esta el LCM en la lista, no queremos |
---|
2721 | // seguir buscando |
---|
2722 | break; |
---|
2723 | } |
---|
2724 | } |
---|
2725 | // Si no ha salido del bucle en "j" es que este LCM |
---|
2726 | // no esta en la lista de las caras, la introducimos |
---|
2727 | if (j == sizfaces + 1) |
---|
2728 | { |
---|
2729 | Faces = insert(Faces,expl1[i],sizfaces + cont1); |
---|
2730 | l = insert(l,l1[i]); |
---|
2731 | cont1 ++; |
---|
2732 | } |
---|
2733 | } |
---|
2734 | l = delete(l,cont1 + 1); |
---|
2735 | sizl = size(l); |
---|
2736 | sizfaces = size(Faces); |
---|
2737 | } |
---|
2738 | // En "Faces" ya tengo los exponentes que luego seran los exponentes |
---|
2739 | // de los ideales que forman la descomposicion. |
---|
2740 | // Deshacemos la artinianizacion |
---|
2741 | intvec elimin = artinianization[3]; |
---|
2742 | if (artinianization[1] == 0) |
---|
2743 | { |
---|
2744 | // En elimina tenemos las variables que hemos introducido |
---|
2745 | // y cual es la potencia |
---|
2746 | // Solo miro las que tengan cambio |
---|
2747 | for (i = 1 ; i <= nvar ; i ++) |
---|
2748 | { |
---|
2749 | if (elimin[i] <> 0) |
---|
2750 | { |
---|
2751 | for (j = 1 ; j <= sizfaces ; j ++) |
---|
2752 | { |
---|
2753 | if (Faces[j][i] == elimin[i]) |
---|
2754 | { |
---|
2755 | Faces[j][i] = 0; |
---|
2756 | } |
---|
2757 | } |
---|
2758 | } |
---|
2759 | } |
---|
2760 | } |
---|
2761 | // Generico |
---|
2762 | sizI = size(I); |
---|
2763 | if (genericlist[1] == 0) |
---|
2764 | { |
---|
2765 | Faces = nonGeneric(genericlist[3],genericlist[4],Faces,sizI); |
---|
2766 | } |
---|
2767 | // Ya tenemos en Faces los exponentes de las componentes |
---|
2768 | // ahora solo hay que obtener los ideales. |
---|
2769 | for (i = 1 ; i <= sizfaces ; i ++) |
---|
2770 | { |
---|
2771 | J = 0; |
---|
2772 | for (j = 1 ; j <= nvar ; j ++) |
---|
2773 | { |
---|
2774 | if (Faces[i][j] <> 0) |
---|
2775 | { |
---|
2776 | J = J,x(j)^(Faces[i][j]); |
---|
2777 | } |
---|
2778 | } |
---|
2779 | J = simplify(J,2); |
---|
2780 | Faces[i] = J; |
---|
2781 | } |
---|
2782 | // Esta es la parte LENTA computacionalmente si el ideal de partida |
---|
2783 | // no es generico |
---|
2784 | if (genericlist[1] == 0) |
---|
2785 | { |
---|
2786 | Faces = irredundant(Faces); |
---|
2787 | } |
---|
2788 | setring R; |
---|
2789 | list components = fetch(R1,Faces); |
---|
2790 | kill R1; |
---|
2791 | return(components); |
---|
2792 | } |
---|
2793 | ////////////////////////////////////////////////////////////////////// |
---|
2794 | // Devuelve una descomposicion primaria minimal de un ideal // |
---|
2795 | // monomial via el complejo de Scarf. // |
---|
2796 | ////////////////////////////////////////////////////////////////////// |
---|
2797 | // |
---|
2798 | static proc scarfMethodPrim (ideal I) |
---|
2799 | { |
---|
2800 | // VARIABLES |
---|
2801 | list l1,l2; |
---|
2802 | // Hallamos la despomposicion irreducible del ideal dado usando |
---|
2803 | // el complejo de Scarf |
---|
2804 | l1 = ScarfMethod (I); |
---|
2805 | // ----- DESCOMPOSICION PRIMARIA |
---|
2806 | l2 = irredPrimary (l1); |
---|
2807 | return (l2); |
---|
2808 | } |
---|
2809 | // |
---|
2810 | // METODO 7: algoritmo de etiquetas (Roune) |
---|
2811 | // |
---|
2812 | ////////////////////////////////////////////////////////////////////// |
---|
2813 | // Las siguientes funciones calculan la descomposicion en // |
---|
2814 | // irreducibles de un ideal monomial. En este caso utilizamos el // |
---|
2815 | // algoritmo de etiquetas de B. Roune. // |
---|
2816 | ////////////////////////////////////////////////////////////////////// |
---|
2817 | // |
---|
2818 | static proc phi (list F) |
---|
2819 | { |
---|
2820 | // Cambiamos de anillo |
---|
2821 | def R = basering; |
---|
2822 | int nvar = nvars(R); |
---|
2823 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
2824 | execute(s); |
---|
2825 | // Variables |
---|
2826 | int sizF,i,j; |
---|
2827 | poly f; |
---|
2828 | list listphi; |
---|
2829 | intvec exp,newexp; |
---|
2830 | list F = fetch(R,F); |
---|
2831 | // F es una lista de pares, que indica una x(i) etiqueta de una |
---|
2832 | // cara del ideal. Suponemos que F tiene ordenados sus elementos |
---|
2833 | // segun las x(i) |
---|
2834 | sizF = size(F); |
---|
2835 | for (i = 1 ; i <= sizF ; i ++) |
---|
2836 | { |
---|
2837 | f = F[i]; |
---|
2838 | exp = leadexp(f); |
---|
2839 | for (j = 1 ; j <= nvar ; j ++) |
---|
2840 | { |
---|
2841 | if (j <> i) |
---|
2842 | { |
---|
2843 | exp[j] = exp[j] + 1; |
---|
2844 | } |
---|
2845 | } |
---|
2846 | listphi[i] = monomial(exp); |
---|
2847 | } |
---|
2848 | // Ya tenemos la lista de los monomios a los que |
---|
2849 | // luego haremos el "lcm" |
---|
2850 | setring R; |
---|
2851 | list listphi = fetch (R1,listphi); |
---|
2852 | kill R1; |
---|
2853 | return (listphi); |
---|
2854 | } |
---|
2855 | ////////////////////////////////////////////////////////////////////// |
---|
2856 | // |
---|
2857 | static proc pi(poly f) |
---|
2858 | { |
---|
2859 | // Cambiamos de anillo |
---|
2860 | def R = basering; |
---|
2861 | int nvar = nvars(R); |
---|
2862 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
2863 | execute(s); |
---|
2864 | int i,sizI; |
---|
2865 | intvec exp; |
---|
2866 | poly f = fetch (R,f); |
---|
2867 | exp = leadexp(f); |
---|
2868 | for (i = 1 ; i <= nvar ; i ++) |
---|
2869 | { |
---|
2870 | if (exp[i] <> 0) |
---|
2871 | { |
---|
2872 | exp[i] = exp[i] - 1; |
---|
2873 | } |
---|
2874 | } |
---|
2875 | f = monomial(exp); |
---|
2876 | setring R; |
---|
2877 | f = fetch (R1,f); |
---|
2878 | kill R1; |
---|
2879 | return (f); |
---|
2880 | } |
---|
2881 | ////////////////////////////////////////////////////////////////////// |
---|
2882 | // |
---|
2883 | static proc conditionComplex (intvec posActual,ideal I,ideal S) |
---|
2884 | { |
---|
2885 | def R = basering; |
---|
2886 | int nvar = nvars(R); |
---|
2887 | // VARIABLES |
---|
2888 | int i,nuevo; |
---|
2889 | list F; |
---|
2890 | // Vemos cual ha sido la ultima incorporacion al ideal, que es el |
---|
2891 | // ultimo dentro de posActual que es distinto de 0. |
---|
2892 | for (i = 1 ; i <= nvar ; i ++) |
---|
2893 | { |
---|
2894 | if (posActual[i] == 0) |
---|
2895 | { |
---|
2896 | break ; |
---|
2897 | } |
---|
2898 | } |
---|
2899 | nuevo = i - 1; |
---|
2900 | // No se pueden repetir generadores, se mira que el ultimo que se ha |
---|
2901 | // ha introducido no sea de los que ya tenemos |
---|
2902 | for (i = 1 ; i <= nuevo - 1 ; i ++) |
---|
2903 | { |
---|
2904 | if (posActual[i] == posActual[nuevo]) |
---|
2905 | { |
---|
2906 | return (0); |
---|
2907 | } |
---|
2908 | } |
---|
2909 | // Vemos si la variable oportuna divide al generador |
---|
2910 | if (leadexp(I[i]) == 0) |
---|
2911 | { |
---|
2912 | return (0); |
---|
2913 | } |
---|
2914 | // Caso de que el LCM sea multiplo de los que ya tenemos |
---|
2915 | poly LCM = 1; |
---|
2916 | for (i = 1 ; i <= nuevo ; i ++) |
---|
2917 | { |
---|
2918 | F = insert (F,I[posActual[i]],size(F)); |
---|
2919 | } |
---|
2920 | list phiF = phi(F); |
---|
2921 | for (i = 1 ; i <= nuevo ; i ++) |
---|
2922 | { |
---|
2923 | LCM = lcmMon(phiF[i],LCM); |
---|
2924 | } |
---|
2925 | // Comprobamos si ya tenemos algun divisor del actual |
---|
2926 | if (membershipMon(LCM,S) == 1) |
---|
2927 | { |
---|
2928 | return (0); |
---|
2929 | } |
---|
2930 | // Ahora vemos si la lista esta en el complejo simplicial |
---|
2931 | if (membershipMon(LCM,I) == 1) |
---|
2932 | { |
---|
2933 | if (membershipMon(pi(LCM),I) == 0) |
---|
2934 | { |
---|
2935 | return (1,LCM); |
---|
2936 | } |
---|
2937 | } |
---|
2938 | return (0); |
---|
2939 | } |
---|
2940 | ////////////////////////////////////////////////////////////////////// |
---|
2941 | // |
---|
2942 | static proc findFaces (ideal I) |
---|
2943 | { |
---|
2944 | def R = basering; |
---|
2945 | int nvar = nvars(R); |
---|
2946 | // Variables |
---|
2947 | int i; |
---|
2948 | ideal S; |
---|
2949 | list condiciones; |
---|
2950 | // Inicializamos valores |
---|
2951 | list F; |
---|
2952 | intvec posActual; |
---|
2953 | posActual[nvar] = 0; |
---|
2954 | |
---|
2955 | int variable = 1; |
---|
2956 | int sizI = size(I); |
---|
2957 | while (1) |
---|
2958 | { |
---|
2959 | while (posActual[variable] == sizI) |
---|
2960 | { |
---|
2961 | posActual[variable] = 0; |
---|
2962 | variable --; |
---|
2963 | if (variable == 0) |
---|
2964 | { |
---|
2965 | break; |
---|
2966 | } |
---|
2967 | } |
---|
2968 | // Comprobamos si hemos recorrido todas las posibilidades. Si |
---|
2969 | // es as?, terminamos el while |
---|
2970 | if (variable == 0) |
---|
2971 | { |
---|
2972 | break; |
---|
2973 | } |
---|
2974 | posActual[variable] = posActual[variable] + 1; |
---|
2975 | // Comprobamos las condiciones para saber si los generadores que |
---|
2976 | // tenemos est?n o no en el complejo. |
---|
2977 | condiciones = conditionComplex (posActual,I,S); |
---|
2978 | |
---|
2979 | if (condiciones[1] == 1 ) |
---|
2980 | { |
---|
2981 | if (posActual[nvar] <> 0) |
---|
2982 | { |
---|
2983 | S = S,condiciones[2]; |
---|
2984 | F = insert (F,condiciones[2]); |
---|
2985 | } |
---|
2986 | if (variable < nvar) |
---|
2987 | { |
---|
2988 | variable ++; |
---|
2989 | } |
---|
2990 | } |
---|
2991 | } |
---|
2992 | return (F); |
---|
2993 | } |
---|
2994 | ////////////////////////////////////////////////////////////////////// |
---|
2995 | // La siguiente funcion calcula la descomposicion en irreducibles de// |
---|
2996 | // un ideal monomial artininano usando el algoritmo de etiquetas del// |
---|
2997 | // metodo de Bjarke Roune. // |
---|
2998 | ////////////////////////////////////////////////////////////////////// |
---|
2999 | // |
---|
3000 | static proc labelAlgorithm(ideal I) |
---|
3001 | { |
---|
3002 | def R = basering; |
---|
3003 | int nvar = nvars(R); |
---|
3004 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
3005 | execute(s); |
---|
3006 | ideal I = fetch(R,I); |
---|
3007 | |
---|
3008 | // Variables |
---|
3009 | int i,j,sizComponents; |
---|
3010 | list components; |
---|
3011 | // El ideal tiene que ser artininano, si no lo es hacemos el cambio |
---|
3012 | // oportuno para que lo sea (luego se deshace). |
---|
3013 | ideal artI; |
---|
3014 | list artiniano = artinian (I); |
---|
3015 | if (artiniano[1] == 0) |
---|
3016 | { |
---|
3017 | artI = artiniano[2]; |
---|
3018 | intvec elimina = artiniano[3]; |
---|
3019 | } |
---|
3020 | else |
---|
3021 | { |
---|
3022 | artI = I; |
---|
3023 | } |
---|
3024 | // Llamamos a findFaces para que encuentre las caras maximales del |
---|
3025 | // complejo asociado al ideal |
---|
3026 | components = findFaces(artI); |
---|
3027 | sizComponents = size(components); |
---|
3028 | list expComponents; |
---|
3029 | poly f; |
---|
3030 | for (i = 1 ; i <= sizComponents ; i ++) |
---|
3031 | { |
---|
3032 | f = components[i]; |
---|
3033 | expComponents[i] = leadexp(f); |
---|
3034 | } |
---|
3035 | // Deshacemos la artinianizacion |
---|
3036 | if (artiniano[1] == 0) |
---|
3037 | { |
---|
3038 | // En elimina tenemos las variables que hemos introducido |
---|
3039 | // y cual es la potencia |
---|
3040 | // Solo miro las que tengan cambio |
---|
3041 | for (i = 1 ; i <= nvar ; i ++) |
---|
3042 | { |
---|
3043 | if (elimina[i] <> 0) |
---|
3044 | { |
---|
3045 | for (j = 1 ; j <= sizComponents ; j ++) |
---|
3046 | { |
---|
3047 | if (expComponents[j][i] == elimina[i]) |
---|
3048 | { |
---|
3049 | expComponents[j][i] = 0; |
---|
3050 | } |
---|
3051 | } |
---|
3052 | } |
---|
3053 | } |
---|
3054 | } |
---|
3055 | // En exp(i) tengo los exponentes de cada variable de las que aparecen |
---|
3056 | // en cada ideal. |
---|
3057 | ideal J; |
---|
3058 | list facets; |
---|
3059 | for (i = 1 ; i <= sizComponents ; i ++) |
---|
3060 | { |
---|
3061 | J = 0; |
---|
3062 | for (j = 1 ; j <= nvar ; j ++) |
---|
3063 | { |
---|
3064 | if (expComponents[i][j] <> 0) |
---|
3065 | { |
---|
3066 | J = J,x(j)^expComponents[i][j]; |
---|
3067 | } |
---|
3068 | } |
---|
3069 | J = simplify(J,2); |
---|
3070 | facets[i] = J; |
---|
3071 | } |
---|
3072 | setring R; |
---|
3073 | list facets = fetch (R1,facets); |
---|
3074 | kill R1; |
---|
3075 | return (facets); |
---|
3076 | } |
---|
3077 | ////////////////////////////////////////////////////////////////////// |
---|
3078 | // Devuelve una descomposicion primaria minimal de un ideal monomial// |
---|
3079 | // dado. // |
---|
3080 | ////////////////////////////////////////////////////////////////////// |
---|
3081 | // |
---|
3082 | static proc labelAlgPrim (ideal I) |
---|
3083 | { |
---|
3084 | // VARIABLES |
---|
3085 | list l1,l2; |
---|
3086 | // Hallamos la despomposicion irreducible del ideal dado usando |
---|
3087 | // el complejo de Scarf |
---|
3088 | l1 = labelAlgorithm (I); |
---|
3089 | // ----- DESCOMPOSICION PRIMARIA |
---|
3090 | l2 = irredPrimary (l1); |
---|
3091 | return (l2); |
---|
3092 | } |
---|
3093 | // |
---|
3094 | // METODO 8: Gao-Zhu |
---|
3095 | // |
---|
3096 | ////////////////////////////////////////////////////////////////////// |
---|
3097 | // |
---|
3098 | static proc divide (intvec v, intvec w, int k) |
---|
3099 | { |
---|
3100 | def R = basering; |
---|
3101 | int nvar = nvars(R); |
---|
3102 | // Variables |
---|
3103 | int i; |
---|
3104 | for (i = 1 ; i <= nvar ; i ++) |
---|
3105 | { |
---|
3106 | if (i == k) |
---|
3107 | { |
---|
3108 | if (v[i] <> w[i]) |
---|
3109 | { |
---|
3110 | return (0); |
---|
3111 | } |
---|
3112 | } |
---|
3113 | else |
---|
3114 | { |
---|
3115 | if (v[i] >= w[i]) |
---|
3116 | { |
---|
3117 | return (0); |
---|
3118 | } |
---|
3119 | } |
---|
3120 | } |
---|
3121 | return (1); |
---|
3122 | } |
---|
3123 | ////////////////////////////////////////////////////////////////////// |
---|
3124 | // // |
---|
3125 | ////////////////////////////////////////////////////////////////////// |
---|
3126 | // |
---|
3127 | static proc incrementalAlg (ideal I) |
---|
3128 | { |
---|
3129 | def R = basering; |
---|
3130 | int nvar = nvars(R); |
---|
3131 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
3132 | execute(s); |
---|
3133 | ideal I = fetch(R,I); |
---|
3134 | // COMPROBACIONES |
---|
3135 | // Variables |
---|
3136 | int i,sop,j,k,l,m,cont,cont2; |
---|
3137 | intvec beta,dbeta,betaaux,elimina; |
---|
3138 | // El ideal tiene que ser artininano, si no lo es hacemos el cambio |
---|
3139 | // oportuno para que lo sea (luego se deshace). |
---|
3140 | list artiniano = artinian (I); |
---|
3141 | ideal artI; |
---|
3142 | if (artiniano[1] == 0) |
---|
3143 | { |
---|
3144 | artI = artiniano[2]; |
---|
3145 | elimina = artiniano[3]; |
---|
3146 | } |
---|
3147 | else |
---|
3148 | { |
---|
3149 | artI = I; |
---|
3150 | elimina[nvar] = 0; |
---|
3151 | } |
---|
3152 | // Buscamos la primera componente irreducible o, lo que es lo |
---|
3153 | // mismo, aquellos generadores que son potencia de una variable. |
---|
3154 | // Si el tama?o de elimina es nvar es que hemos a?adido todos los |
---|
3155 | // generadores que son potencia luego estar?n todos al final del |
---|
3156 | // ideal. |
---|
3157 | list MinI,componentes; |
---|
3158 | int sizartI = size(artI); |
---|
3159 | int sizelimina = size(elimina); |
---|
3160 | for (i = 1 ; i <= nvar ; i ++) |
---|
3161 | { |
---|
3162 | if (elimina[i] == 0) |
---|
3163 | { |
---|
3164 | // Buscamos en el ideal los generadores que nos interesan |
---|
3165 | for (j = 1 ; j <= sizartI ; j ++) |
---|
3166 | { |
---|
3167 | sop = soporte(artI[j]); |
---|
3168 | if (sop <> 0) |
---|
3169 | { |
---|
3170 | beta[sop] = leadexp(artI[j])[sop]; |
---|
3171 | MinI = insert(MinI,leadexp(artI[j])); |
---|
3172 | if (j <> 1 and j <> sizartI) |
---|
3173 | { |
---|
3174 | artI = artI[1..j - 1],artI[j + 1..sizartI]; |
---|
3175 | } |
---|
3176 | else |
---|
3177 | { |
---|
3178 | if (j == 1) |
---|
3179 | { |
---|
3180 | artI = artI[2..sizartI]; |
---|
3181 | } |
---|
3182 | else |
---|
3183 | { |
---|
3184 | artI = artI[1..sizartI - 1]; |
---|
3185 | } |
---|
3186 | } |
---|
3187 | sizartI = size(artI); |
---|
3188 | break; |
---|
3189 | } |
---|
3190 | } |
---|
3191 | } |
---|
3192 | else |
---|
3193 | { |
---|
3194 | // Buscamos la que esta al final |
---|
3195 | sop = soporte(artI[sizartI]); |
---|
3196 | beta[sop] = leadexp(artI[sizartI])[sop]; |
---|
3197 | MinI = insert(MinI,leadexp(artI[sizartI])); |
---|
3198 | if (sizartI <> 1) |
---|
3199 | { |
---|
3200 | artI = artI[1..sizartI - 1]; |
---|
3201 | } |
---|
3202 | else |
---|
3203 | { |
---|
3204 | artI = artI[1]; |
---|
3205 | } |
---|
3206 | sizartI = size(artI); |
---|
3207 | } |
---|
3208 | } |
---|
3209 | // En beta tenemos la primera componente |
---|
3210 | componentes = insert(componentes,beta); |
---|
3211 | int sizcomponents = size(componentes); |
---|
3212 | int sizMin = size(MinI); |
---|
3213 | // Es mas facil trabajar con los exponentes para nuestro objetivo |
---|
3214 | // Se elige un nuevo generador, que en nuestro caso es un nuevo |
---|
3215 | // exponente. |
---|
3216 | int min,max; |
---|
3217 | intvec expartI; |
---|
3218 | for(i = 1 ; i <= sizartI ; i ++) |
---|
3219 | { |
---|
3220 | expartI = leadexp(artI[1]); |
---|
3221 | if (size(artI) <> 1) |
---|
3222 | { |
---|
3223 | artI = artI[2..size(artI)]; |
---|
3224 | } |
---|
3225 | // Hay que distinguir T_1 y T_2. Para ello se comparar vectores |
---|
3226 | // de la lista actual de generadores con el que se acaba de |
---|
3227 | // introducir. |
---|
3228 | cont2 = 0; |
---|
3229 | for (j = 1 ; j <= sizcomponents ; j ++) |
---|
3230 | { |
---|
3231 | beta = componentes[1 + cont2]; |
---|
3232 | // Si el nuevo generador divide a la componente beta, hay |
---|
3233 | // que buscar las nuevas componentes |
---|
3234 | for (k = 1 ; k <= nvar ; k ++) |
---|
3235 | { |
---|
3236 | if (expartI[k] >= beta[k]) |
---|
3237 | { |
---|
3238 | break; |
---|
3239 | } |
---|
3240 | } |
---|
3241 | // Si el bucle anterior termino, divide y hay que hacer |
---|
3242 | // los cambios. |
---|
3243 | if (k == nvar + 1) |
---|
3244 | { |
---|
3245 | componentes = delete (componentes,1 + cont2); |
---|
3246 | // Buscamos las nuevas componentes calculando las |
---|
3247 | // distancias. Para cada variable busco d(beta,k,l) |
---|
3248 | for (k = 1 ; k <= nvar ; k ++) |
---|
3249 | { |
---|
3250 | betaaux = beta; |
---|
3251 | max = -1; |
---|
3252 | cont = 0; |
---|
3253 | dbeta = 0; |
---|
3254 | for (l = 1 ; l <= nvar ; l ++) |
---|
3255 | { |
---|
3256 | if (l <> k) |
---|
3257 | { |
---|
3258 | min = 32767; |
---|
3259 | cont ++; |
---|
3260 | for (m = 1 ; m <= sizMin ; m ++) |
---|
3261 | { |
---|
3262 | // Estos son de los buenos |
---|
3263 | if (divide(MinI[m],beta,l) == 1) |
---|
3264 | { |
---|
3265 | if (MinI[m][k] < min) |
---|
3266 | { |
---|
3267 | min = MinI[m][k]; |
---|
3268 | } |
---|
3269 | } |
---|
3270 | } |
---|
3271 | dbeta[cont] = min; |
---|
3272 | } |
---|
3273 | } |
---|
3274 | // Aqui ya tenemos d(beta,k,l) para cada k |
---|
3275 | // Hallamos el maximo cuando terminemos |
---|
3276 | for (l = 1 ; l <= cont ; l ++) |
---|
3277 | { |
---|
3278 | if (dbeta[l] > max) |
---|
3279 | { |
---|
3280 | max = dbeta[l]; |
---|
3281 | } |
---|
3282 | } |
---|
3283 | // Condicion para introducir nueva componente |
---|
3284 | if (max < expartI[k]) |
---|
3285 | { |
---|
3286 | betaaux[k] = expartI[k]; |
---|
3287 | componentes = insert(componentes,betaaux,size(componentes)); |
---|
3288 | } |
---|
3289 | } |
---|
3290 | } |
---|
3291 | else |
---|
3292 | { |
---|
3293 | cont2 ++; |
---|
3294 | } |
---|
3295 | } |
---|
3296 | MinI = insert(MinI,expartI); |
---|
3297 | sizMin = size(MinI); |
---|
3298 | sizcomponents = size(componentes); |
---|
3299 | } |
---|
3300 | // Deahacer los cambios de artiniano si se han hecho |
---|
3301 | if (artiniano[1] == 0) |
---|
3302 | { |
---|
3303 | // En elimina tenemos las variables que hemos introducido |
---|
3304 | // y cual es la potencia |
---|
3305 | // Solo miro las que tengan cambio |
---|
3306 | for (i = 1 ; i <= nvar ; i ++) |
---|
3307 | { |
---|
3308 | if (elimina[i] <> 0) |
---|
3309 | { |
---|
3310 | for (j = 1 ; j <= sizcomponents ; j ++) |
---|
3311 | { |
---|
3312 | if (componentes[j][i] == elimina[i]) |
---|
3313 | { |
---|
3314 | componentes[j][i] = 0; |
---|
3315 | } |
---|
3316 | } |
---|
3317 | } |
---|
3318 | } |
---|
3319 | } |
---|
3320 | // En exp(i) tengo los exponentes de cada variable de las que aparecen |
---|
3321 | // en cada ideal. |
---|
3322 | ideal J; |
---|
3323 | list facets; |
---|
3324 | for (i = 1 ; i <= sizcomponents ; i ++) |
---|
3325 | { |
---|
3326 | J = 0; |
---|
3327 | for (j = 1 ; j <= nvar ; j ++) |
---|
3328 | { |
---|
3329 | if (componentes[i][j] <> 0) |
---|
3330 | { |
---|
3331 | J = J,x(j)^componentes[i][j]; |
---|
3332 | } |
---|
3333 | } |
---|
3334 | J = simplify(J,2); |
---|
3335 | facets[i] = J; |
---|
3336 | } |
---|
3337 | setring R; |
---|
3338 | list facets = fetch (R1,facets); |
---|
3339 | kill R1; |
---|
3340 | return (facets); |
---|
3341 | } |
---|
3342 | ////////////////////////////////////////////////////////////////////// |
---|
3343 | // |
---|
3344 | static proc incrementalAlgPrim (ideal I) |
---|
3345 | { |
---|
3346 | // VARIABLES |
---|
3347 | list l1,l2; |
---|
3348 | // Hallamos la despomposicion irreducible del ideal dado usando |
---|
3349 | // el algoritmo de Gao-Zhu |
---|
3350 | l1 = incrementalAlg (I); |
---|
3351 | // ----- DESCOMPOSICION PRIMARIA |
---|
3352 | l2 = irredPrimary (l1); |
---|
3353 | return (l2); |
---|
3354 | } |
---|
3355 | // |
---|
3356 | // METODO 9: slice algorithm (Roune) |
---|
3357 | // |
---|
3358 | ////////////////////////////////////////////////////////////////////// |
---|
3359 | // SLICE ALGORITHM (B.Roune) // |
---|
3360 | ////////////////////////////////////////////////////////////////////// |
---|
3361 | // |
---|
3362 | static proc divideMon (poly f , poly g) |
---|
3363 | { |
---|
3364 | def R = basering; |
---|
3365 | int nvar = nvars(R); |
---|
3366 | intvec expf = leadexp(f); |
---|
3367 | intvec expg = leadexp(g); |
---|
3368 | for (int i = 1 ; i <= nvar ; i ++) |
---|
3369 | { |
---|
3370 | if (expf[i] > expg[i]) |
---|
3371 | { |
---|
3372 | return (0); |
---|
3373 | } |
---|
3374 | } |
---|
3375 | return (1); |
---|
3376 | } |
---|
3377 | ////////////////////////////////////////////////////////////////////// |
---|
3378 | // |
---|
3379 | static proc pivot (ideal I , poly lcmMin, ideal S) |
---|
3380 | { |
---|
3381 | // I is monomial ideal |
---|
3382 | def R = basering; |
---|
3383 | I = fetch (R,I); |
---|
3384 | S = fetch(R,S); |
---|
3385 | int sizI = size(I); |
---|
3386 | int nvar = nvars(R); |
---|
3387 | intvec explcmMin = leadexp(lcmMin); |
---|
3388 | // Variables |
---|
3389 | int i,j; |
---|
3390 | // The median estrategy |
---|
3391 | poly p; |
---|
3392 | int cont, exp, median, sizxi, max; |
---|
3393 | intvec xiexp; |
---|
3394 | for (i = 1 ; i <= nvar ; i ++) |
---|
3395 | { |
---|
3396 | if (explcmMin[i] >= 2 ) |
---|
3397 | { |
---|
3398 | // Median exponent of x(i) from intersection(minI,x(i)) |
---|
3399 | cont = 0; |
---|
3400 | for (j = 1 ; j <= sizI ; j ++) |
---|
3401 | { |
---|
3402 | exp = leadexp(I[j])[i]; |
---|
3403 | if (exp > 0) |
---|
3404 | { |
---|
3405 | cont ++; |
---|
3406 | xiexp[cont] = exp; |
---|
3407 | } |
---|
3408 | } |
---|
3409 | xiexp = sort(xiexp)[1]; |
---|
3410 | sizxi = size(xiexp); |
---|
3411 | if (size(xiexp) == 1) |
---|
3412 | { |
---|
3413 | median = xiexp[1] - 1; |
---|
3414 | } |
---|
3415 | else |
---|
3416 | { |
---|
3417 | if (size(xiexp) == 2) |
---|
3418 | { |
---|
3419 | median = xiexp[2] - 1; |
---|
3420 | } |
---|
3421 | else |
---|
3422 | { |
---|
3423 | median = xiexp[(size(xiexp) + 1) / 2]; |
---|
3424 | } |
---|
3425 | } |
---|
3426 | p = x(i)^median; |
---|
3427 | // valid pivot?? |
---|
3428 | if ( membershipMon(p,S) == 0) |
---|
3429 | { |
---|
3430 | return(p); |
---|
3431 | } |
---|
3432 | else |
---|
3433 | { |
---|
3434 | max = maximoExp(S,i); |
---|
3435 | if ( xiexp[sizxi] == max ) |
---|
3436 | { |
---|
3437 | return(x(i)^(max-1)); |
---|
3438 | } |
---|
3439 | } |
---|
3440 | xiexp = 0; |
---|
3441 | } |
---|
3442 | } |
---|
3443 | } |
---|
3444 | ////////////////////////////////////////////////////////////////////// |
---|
3445 | // |
---|
3446 | static proc simplification (I) |
---|
3447 | { |
---|
3448 | // VARIABLES |
---|
3449 | int i, j, k, cont, numdeleted; |
---|
3450 | intvec isMaximal; |
---|
3451 | def R = basering; |
---|
3452 | I = fetch(R,I); |
---|
3453 | int sizI = size(I); |
---|
3454 | int nvar = nvars(R); |
---|
3455 | poly lcmMinI = 1; |
---|
3456 | for (i = 1 ; i <= sizI ; i ++) |
---|
3457 | { |
---|
3458 | lcmMinI = lcmMon(I[i],lcmMinI); |
---|
3459 | } |
---|
3460 | intvec explcmMinI = leadexp(lcmMinI); |
---|
3461 | // Buscamos los elementos que son x(i) maximales. En caso de que |
---|
3462 | // un generador del ideal sea maximal para 2 variables distintas, |
---|
3463 | // ese generador se elimina. |
---|
3464 | isMaximal[sizI] = 0; |
---|
3465 | intvec genexp; |
---|
3466 | for (i = 1 ; i <= sizI ; i ++) |
---|
3467 | { |
---|
3468 | genexp = leadexp(I[i]); |
---|
3469 | cont = 0; |
---|
3470 | for ( j = 1 ; j <= nvar ; j ++) |
---|
3471 | { |
---|
3472 | if (genexp[j] <> 0 && genexp[j] == explcmMinI[j]) |
---|
3473 | { |
---|
3474 | |
---|
3475 | if (cont == 0) |
---|
3476 | { |
---|
3477 | cont ++; |
---|
3478 | isMaximal[i] = j; |
---|
3479 | } |
---|
3480 | else |
---|
3481 | { |
---|
3482 | // Porque cuando encontramos que era maximal para |
---|
3483 | // la primera variable, lo guardamos |
---|
3484 | isMaximal[i] = 0; |
---|
3485 | // Eliminamos del ideal |
---|
3486 | if (i <> 1 && i <> sizI) |
---|
3487 | { |
---|
3488 | I = I[1..i - 1],I[i + 1..sizI]; |
---|
3489 | } |
---|
3490 | else |
---|
3491 | { |
---|
3492 | if (i == 1) |
---|
3493 | { |
---|
3494 | I = I[2..sizI]; |
---|
3495 | } |
---|
3496 | else |
---|
3497 | { |
---|
3498 | I = I[1..sizI - 1]; |
---|
3499 | } |
---|
3500 | } |
---|
3501 | i --; |
---|
3502 | sizI = size(I); |
---|
3503 | // Generador i eliminado, miramos el siguiente |
---|
3504 | break; |
---|
3505 | } |
---|
3506 | } |
---|
3507 | } |
---|
3508 | } |
---|
3509 | // En isMaximal[i] tenemos 0 si I[i] no es maximal, |
---|
3510 | // y j si I[i] es maximal en x(j). |
---|
3511 | // Matriz de exponentes de los generadores del ideal |
---|
3512 | intmat expI[sizI][nvar]; |
---|
3513 | for (i = 1 ; i <= sizI ; i++) |
---|
3514 | { |
---|
3515 | expI[i,1..nvar] = leadexp(I[i]); |
---|
3516 | } |
---|
3517 | // Buscamos ahora cota inferior |
---|
3518 | poly lcmMi = 1; |
---|
3519 | poly l,gcdMi; |
---|
3520 | intvec Mi, mincol,expgcd; |
---|
3521 | for (i = 1 ; i <= nvar ; i ++) |
---|
3522 | { |
---|
3523 | Mi = 0; |
---|
3524 | cont = 0; |
---|
3525 | for (j = 1 ; j <= sizI ; j ++) |
---|
3526 | { |
---|
3527 | // De isMaximal solo se usan las entradas que se corresponden con elementos del ideal |
---|
3528 | if (expI[j,i] <> 0) |
---|
3529 | { |
---|
3530 | if (isMaximal[j] == 0 or isMaximal[j] == i) |
---|
3531 | { |
---|
3532 | // Elementos del sistema minimal que estan |
---|
3533 | // en Mi |
---|
3534 | cont ++; |
---|
3535 | Mi[cont] = j; |
---|
3536 | } |
---|
3537 | } |
---|
3538 | } |
---|
3539 | // Si solo hay un elemento en Mi, no hay nada que hacer |
---|
3540 | if (cont > 1) |
---|
3541 | { |
---|
3542 | gcdMi = I[Mi[1]]; |
---|
3543 | // Tenemos los generadores a los que hay que hallar el gcd |
---|
3544 | for (j = 2; j <= cont ; j ++) |
---|
3545 | { |
---|
3546 | gcdMi = gcdMon(gcdMi,I[Mi[j]]); |
---|
3547 | } |
---|
3548 | } |
---|
3549 | else |
---|
3550 | { |
---|
3551 | if (Mi <> 0) |
---|
3552 | { |
---|
3553 | gcdMi = I[Mi[1]]; |
---|
3554 | } |
---|
3555 | else |
---|
3556 | { |
---|
3557 | // Falta alguna variable |
---|
3558 | return (0,I); |
---|
3559 | } |
---|
3560 | } |
---|
3561 | l = gcdMi/x(i); |
---|
3562 | lcmMi = lcmMon(lcmMi,l); |
---|
3563 | } |
---|
3564 | // Ahora devolvemos la cota inferior, que luego hay que multiplicar |
---|
3565 | // por el monomio que define el corte. |
---|
3566 | // Devolvemos tambien el ideal (por si se ha modificado). |
---|
3567 | return (lcmMi,I); |
---|
3568 | } |
---|
3569 | ////////////////////////////////////////////////////////////////////// |
---|
3570 | // |
---|
3571 | static proc con (ideal I , ideal S , poly q) |
---|
3572 | { |
---|
3573 | def R = basering; |
---|
3574 | int nvar = nvars(R); |
---|
3575 | I = fetch(R,I); |
---|
3576 | S = fetch(R,S); |
---|
3577 | q = fetch(R,q); |
---|
3578 | // Variables |
---|
3579 | int i; |
---|
3580 | poly piI; |
---|
3581 | int sizI = size(I); |
---|
3582 | // Simplification process |
---|
3583 | poly p; |
---|
3584 | list sol; |
---|
3585 | while (1) |
---|
3586 | { |
---|
3587 | // (I,S,q) normal slice? |
---|
3588 | // Como cada vez que introducimos una cota inferior sabemos |
---|
3589 | // que la slice actual es la inner slice (la otra es vacio), |
---|
3590 | // hay que volver a verificar si es normal |
---|
3591 | if ( S <> 0 ) |
---|
3592 | { |
---|
3593 | // m/rad(m) esta en S, para m generador minimal de I?? |
---|
3594 | for (i = 1 ; i <= sizI ; i ++) |
---|
3595 | { |
---|
3596 | piI = pi(I[i]); |
---|
3597 | if (membershipMon(piI,S) == 1) |
---|
3598 | { |
---|
3599 | if (i == 1) |
---|
3600 | { |
---|
3601 | I = I[2..sizI]; |
---|
3602 | } |
---|
3603 | else |
---|
3604 | { |
---|
3605 | if (i == sizI) |
---|
3606 | { |
---|
3607 | I = I[1..sizI - 1]; |
---|
3608 | } |
---|
3609 | else |
---|
3610 | { |
---|
3611 | I = I[1..i - 1],I[i + 1..sizI]; |
---|
3612 | } |
---|
3613 | } |
---|
3614 | sizI = size(I); |
---|
3615 | i --; |
---|
3616 | } |
---|
3617 | } |
---|
3618 | } |
---|
3619 | // Buscamos cota inferior, y si es distinta de 1, simplificamos |
---|
3620 | sol = simplification(I); |
---|
3621 | p = sol[1]; |
---|
3622 | if (p == 1) |
---|
3623 | { |
---|
3624 | break; |
---|
3625 | } |
---|
3626 | else |
---|
3627 | { |
---|
3628 | if (p == 0) |
---|
3629 | { |
---|
3630 | break; |
---|
3631 | } |
---|
3632 | else |
---|
3633 | { |
---|
3634 | if (membershipMon(p,I) == 1 ) |
---|
3635 | { |
---|
3636 | break; |
---|
3637 | } |
---|
3638 | } |
---|
3639 | } |
---|
3640 | // Changing slice by simplification |
---|
3641 | I = sol[2]; |
---|
3642 | I = minbase(quotient(I,p)); |
---|
3643 | q = p*q; |
---|
3644 | S = minbase(quotient(S,p)); |
---|
3645 | sizI = size(I); |
---|
3646 | } |
---|
3647 | sizI = size(I); |
---|
3648 | // (I,S,q) base case? |
---|
3649 | poly lcmMinI; |
---|
3650 | lcmMinI = 1; |
---|
3651 | for (i = 1 ; i <= sizI ; i ++) |
---|
3652 | { |
---|
3653 | lcmMinI = lcmMon(lcmMinI,I[i]); |
---|
3654 | } |
---|
3655 | // a:b generates an intvec of length b with constant entries a |
---|
3656 | intvec one = 1:nvar; |
---|
3657 | if (divideMon(monomial(one),lcmMinI) == 0) |
---|
3658 | { |
---|
3659 | return (0); |
---|
3660 | } |
---|
3661 | if (equal(radicalMon(I),I) == 1) |
---|
3662 | { |
---|
3663 | if (equal(I, maxideal(1)) == 0) |
---|
3664 | { |
---|
3665 | return (0); |
---|
3666 | } |
---|
3667 | else |
---|
3668 | { |
---|
3669 | for (i = 1 ; i <= nvar ; i ++) |
---|
3670 | { |
---|
3671 | q = q * x(i); |
---|
3672 | } |
---|
3673 | return (q); |
---|
3674 | } |
---|
3675 | } |
---|
3676 | // Selecting pivot |
---|
3677 | p = pivot(I,lcmMinI,S); |
---|
3678 | // New slices |
---|
3679 | ideal S1 = minbase(quotient(S,p)); |
---|
3680 | ideal I1 = minbase(quotient(I,p)); |
---|
3681 | ideal S2 = S,p; |
---|
3682 | S2 = minbase(S2); |
---|
3683 | return (con(I1,S1,p*q),con(I,S2,q)); |
---|
3684 | } |
---|
3685 | ////////////////////////////////////////////////////////////////////// |
---|
3686 | // |
---|
3687 | static proc irredDecMonSlice (ideal I) |
---|
3688 | { |
---|
3689 | // New ring |
---|
3690 | def R = basering; |
---|
3691 | int nvar = nvars(R); |
---|
3692 | string s = "ring R1 =",charstr(R),",x(1..nvar),dp;"; |
---|
3693 | execute(s); |
---|
3694 | ideal I = fetch(R,I); |
---|
3695 | int sizI = size(I); |
---|
3696 | int i,j; |
---|
3697 | // Artinian ideal |
---|
3698 | ideal artI; |
---|
3699 | list artinianization = artinian(I); |
---|
3700 | if (artinianization[1] == 0) |
---|
3701 | { |
---|
3702 | artI = artinianization[2]; |
---|
3703 | } |
---|
3704 | else |
---|
3705 | { |
---|
3706 | artI = I; |
---|
3707 | } |
---|
3708 | // Easy case: 2 variables |
---|
3709 | if (nvar == 2) |
---|
3710 | { |
---|
3711 | artI = sort(artI)[1]; |
---|
3712 | int sizartI = size(artI); |
---|
3713 | for (i = 1 ; i <= sizartI - 1 ; i ++) |
---|
3714 | { |
---|
3715 | components[i] = x(1)^(leadexp[artI[i]][1])*x(2)^(leadexp[artI[i + 1]][2]); |
---|
3716 | } |
---|
3717 | setring R; |
---|
3718 | list components = fetch(R1,components); |
---|
3719 | kill R1; |
---|
3720 | return (components); |
---|
3721 | } |
---|
3722 | ideal irredDec = con (artI,0,1); |
---|
3723 | // Delelting zeros |
---|
3724 | irredDec = simplify(irredDec,2); |
---|
3725 | // Delting, in case, generators |
---|
3726 | intvec elimina; |
---|
3727 | if (artinianization[1] == 0) |
---|
3728 | { |
---|
3729 | elimina = artinianization[3]; |
---|
3730 | } |
---|
3731 | else |
---|
3732 | { |
---|
3733 | elimina = 0; |
---|
3734 | } |
---|
3735 | // Each generator (monomial) corresponds to an ideal |
---|
3736 | list components; |
---|
3737 | poly comp; |
---|
3738 | intvec exp; |
---|
3739 | int sizIrred = size(irredDec); |
---|
3740 | ideal auxIdeal; |
---|
3741 | for (i = 1 ; i <= sizIrred ; i ++) |
---|
3742 | { |
---|
3743 | comp = irredDec[i]; |
---|
3744 | exp = leadexp(comp); |
---|
3745 | for (j = 1 ; j <= nvar ; j ++) |
---|
3746 | { |
---|
3747 | if (exp[j] <> 0) |
---|
3748 | { |
---|
3749 | if (elimina <> 0) |
---|
3750 | { |
---|
3751 | if (exp[j] == elimina[j]) |
---|
3752 | { |
---|
3753 | auxIdeal[j] = 0; |
---|
3754 | } |
---|
3755 | else |
---|
3756 | { |
---|
3757 | auxIdeal[j] = x(j)^exp[j]; |
---|
3758 | } |
---|
3759 | } |
---|
3760 | else |
---|
3761 | { |
---|
3762 | auxIdeal[j] = x(j)^exp[j]; |
---|
3763 | } |
---|
3764 | } |
---|
3765 | } |
---|
3766 | components[i] = simplify(auxIdeal,2); |
---|
3767 | auxIdeal = 0; |
---|
3768 | } |
---|
3769 | setring R; |
---|
3770 | list components = fetch(R1,components); |
---|
3771 | kill R1; |
---|
3772 | return (components); |
---|
3773 | } |
---|
3774 | ////////////////////////////////////////////////////////////////////// |
---|
3775 | // |
---|
3776 | static proc primDecMonSlice (ideal I) |
---|
3777 | { |
---|
3778 | // VARIABLES |
---|
3779 | list l1,l2; |
---|
3780 | // ---- Irreducible decomposition |
---|
3781 | // Slice Method |
---|
3782 | l1 = irredDecMonSlice (I); |
---|
3783 | // ----- Primary decomposition |
---|
3784 | l2 = irredPrimary (l1); |
---|
3785 | return (l2); |
---|
3786 | } |
---|
3787 | ////////////////////////////////////////////////////////////////////// |
---|
3788 | // // |
---|
3789 | // DECOMPOSITIONS // |
---|
3790 | // // |
---|
3791 | ////////////////////////////////////////////////////////////////////// |
---|
3792 | ////////////////////////////////////////////////////////////////////// |
---|
3793 | // |
---|
3794 | proc irreddecMon |
---|
3795 | "USAGE: irreddecMon (I[,alg]); I ideal, alg string. |
---|
3796 | RETURN: list, the irreducible components of the monomial ideal I. |
---|
3797 | (returns -1 if I is not a monomial ideal). |
---|
3798 | ASSUME: I is a monomial ideal of the basering k[x(1)..x(n)]. |
---|
3799 | NOTE: This procesure returns the irreducible decomposition of I. |
---|
3800 | One may call the procedure with different algorithms using |
---|
3801 | the optional argument 'alg': |
---|
3802 | - the direct method following Vasconcelos' book (alg=vas) |
---|
3803 | - via the Alexander dual and using doble dual (alg=add), |
---|
3804 | - via the Alexander dual and quotients following E. Miller |
---|
3805 | (alg=ad), |
---|
3806 | - the formula of irreducible components (alg=for), |
---|
3807 | - via the Scarf complex following Milowski (alg=mil), |
---|
3808 | - using the label algorihtm of Roune (alg=lr), |
---|
3809 | - using the algorithm of Gao-Zhu (alg=gz). |
---|
3810 | - using the slice algorithm of Roune (alg=sr). |
---|
3811 | EXAMPLE: example irreddecMon; shows some examples. |
---|
3812 | " |
---|
3813 | { |
---|
3814 | // COMPROBACIONES |
---|
3815 | ideal I = #[1]; |
---|
3816 | int control = checkIdeal(I); |
---|
3817 | // Si el sistema de generadores no esta formado por monomios, hay |
---|
3818 | // que comprobar si el ideal es monomial. |
---|
3819 | if (control == 0) |
---|
3820 | { |
---|
3821 | list isMon = isMonomialGB (I); |
---|
3822 | if (isMon[1] == 0) |
---|
3823 | { |
---|
3824 | ERROR ("the ideal is not monomial."); |
---|
3825 | } |
---|
3826 | else |
---|
3827 | { |
---|
3828 | I = isMon[2]; |
---|
3829 | // Ya lo tenemos con los generadores minimales |
---|
3830 | } |
---|
3831 | } |
---|
3832 | else |
---|
3833 | { |
---|
3834 | // Generadores monomiales, hallamos sistema minimal |
---|
3835 | I = minbase(I); |
---|
3836 | |
---|
3837 | } |
---|
3838 | // Si el ideal es irreducible, devolvemos el mismo |
---|
3839 | if (isirreducibleMon(I) == 1) |
---|
3840 | { |
---|
3841 | return (I); |
---|
3842 | } |
---|
3843 | // Si no me han dado opcion, elijo una yo. |
---|
3844 | if (size(#) == 1) |
---|
3845 | { |
---|
3846 | return (irredDec3(I)); |
---|
3847 | } |
---|
3848 | // Leo la opcion y llamo al procedimiento oportuno |
---|
3849 | else |
---|
3850 | { |
---|
3851 | if (#[2] == "vas") |
---|
3852 | { |
---|
3853 | return (irredDec1(I)); |
---|
3854 | } |
---|
3855 | if (#[2] == "add") |
---|
3856 | { |
---|
3857 | return (irredDec3(I)); |
---|
3858 | } |
---|
3859 | if (#[2] == "ad") |
---|
3860 | { |
---|
3861 | return (irredDec4(I)); |
---|
3862 | } |
---|
3863 | if (#[2] == "for") |
---|
3864 | { |
---|
3865 | return (irredDec5(I)); |
---|
3866 | } |
---|
3867 | if (#[2] == "mil") |
---|
3868 | { |
---|
3869 | return (ScarfMethod(I)); |
---|
3870 | } |
---|
3871 | if (#[2] == "lr") |
---|
3872 | { |
---|
3873 | return (labelAlgorithm(I)); |
---|
3874 | } |
---|
3875 | if (#[2] == "gz") |
---|
3876 | { |
---|
3877 | return (incrementalAlg(I)); |
---|
3878 | } |
---|
3879 | if (#[2] == "sr") |
---|
3880 | { |
---|
3881 | return (irredDecMonSlice(I)); |
---|
3882 | } |
---|
3883 | } |
---|
3884 | } |
---|
3885 | example |
---|
3886 | {"EXAMPLE:"; echo = 2; |
---|
3887 | ring R = 0,(w,x,y,z),Dp; |
---|
3888 | ideal I = w^3*x*y,w*x*y*z,x^2*y^2*z^2,x^2*z^4,y^3*z; |
---|
3889 | // Vasconcelos |
---|
3890 | irreddecMon (I,"vas"); |
---|
3891 | // Alexander Dual |
---|
3892 | irreddecMon (I,"ad"); |
---|
3893 | // Scarf Complex |
---|
3894 | irreddecMon (I,"mil"); |
---|
3895 | // slice algorithm |
---|
3896 | irreddecMon(I,"sr"); |
---|
3897 | } |
---|
3898 | ////////////////////////////////////////////////////////////////////// |
---|
3899 | // |
---|
3900 | proc primdecMon |
---|
3901 | "USAGE: primdecMon (I[,alg]); I ideal, alg string |
---|
3902 | RETURN: list, the components in a minimal primary decomposition of I. |
---|
3903 | (returns -1 if I is not a monomial ideal). |
---|
3904 | ASSUME: I is a monomial ideal of the basering k[x(1)..x(n)]. |
---|
3905 | NOTE: This procesure returns a minimal primary decomposition of I. |
---|
3906 | One may call the procedure with different algorithms using |
---|
3907 | the optional argument 'alg': |
---|
3908 | - the direct method for a primary decomposition following |
---|
3909 | Vasconcelos' book (alg=vp), |
---|
3910 | - from the irreducible decomposition obtained via the direct |
---|
3911 | method following Vasconcelos' book (alg=vi), |
---|
3912 | - from the irreducible decomposition obtained via the |
---|
3913 | Alexander dual and using doble dual (alg=add), |
---|
3914 | - from the irreducible decomposition obtained via the |
---|
3915 | Alexander dual and quotients following E. Miller (alg=ad), |
---|
3916 | - from the irreducible decomposition obtained |
---|
3917 | via ........ (alg=for), |
---|
3918 | - from the irreducible decomposition obtained via the Scarf |
---|
3919 | complex following Milowski (alg=mil), |
---|
3920 | - from the irreducible decomposition obtained using the label |
---|
3921 | algorihtm of Roune (alg=lr), |
---|
3922 | - from the irreducible decomposition obtained using the |
---|
3923 | algorithm of Gao-Zhu (alg=gz), |
---|
3924 | - from the irreducible decomposition obtained using the slice |
---|
3925 | algorithm of Roune (alg=sr). |
---|
3926 | EXAMPLE: example primdecMon; shows some examples. |
---|
3927 | " |
---|
3928 | { |
---|
3929 | // COMPROBACIONES |
---|
3930 | ideal I = #[1]; |
---|
3931 | int control = checkIdeal(I); |
---|
3932 | // Si el sistema de generadores no esta formado por monomios, hay |
---|
3933 | // que comprobar si el ideal es monomial. |
---|
3934 | if (control == 0) |
---|
3935 | { |
---|
3936 | list isMon = isMonomialGB (I); |
---|
3937 | if (isMon[1] == 0) |
---|
3938 | { |
---|
3939 | ERROR ("the ideal is not monomial."); |
---|
3940 | } |
---|
3941 | else |
---|
3942 | { |
---|
3943 | I = isMon[2]; |
---|
3944 | // Ya lo tenemos con los generadores minimales |
---|
3945 | } |
---|
3946 | } |
---|
3947 | else |
---|
3948 | { |
---|
3949 | // Generadores monomiales, hallamos sistema minimal |
---|
3950 | I = minbase(I); |
---|
3951 | } |
---|
3952 | // Estudiamos si el ideal es o no primario |
---|
3953 | if (isprimaryMon(I) == 1) |
---|
3954 | { |
---|
3955 | return (I); |
---|
3956 | } |
---|
3957 | // Si no me han dado opcion, elijo una yo. |
---|
3958 | if (size(#) == 1) |
---|
3959 | { |
---|
3960 | return(primDec3(I)); |
---|
3961 | } |
---|
3962 | // Leo la opcion y llamo al procedimiento oportuno |
---|
3963 | else |
---|
3964 | { |
---|
3965 | if (#[2] == "vi") |
---|
3966 | { |
---|
3967 | return (primDec1(I)); |
---|
3968 | } |
---|
3969 | if (#[2] == "vp") |
---|
3970 | { |
---|
3971 | return (primDec2(I)); |
---|
3972 | } |
---|
3973 | if (#[2] == "add") |
---|
3974 | { |
---|
3975 | return (primDec3(I)); |
---|
3976 | } |
---|
3977 | if (#[2] == "ad") |
---|
3978 | { |
---|
3979 | return (primDec4(I)); |
---|
3980 | } |
---|
3981 | if (#[2] == "for") |
---|
3982 | { |
---|
3983 | return (primDec5(I)); |
---|
3984 | } |
---|
3985 | if (#[2] == "mil") |
---|
3986 | { |
---|
3987 | return (scarfMethodPrim(I)); |
---|
3988 | } |
---|
3989 | if (#[2] == "lr") |
---|
3990 | { |
---|
3991 | return (labelAlgPrim(I)); |
---|
3992 | } |
---|
3993 | if (#[2] == "gz") |
---|
3994 | { |
---|
3995 | return (incrementalAlgPrim(I)); |
---|
3996 | } |
---|
3997 | if (#[2] == "sr") |
---|
3998 | { |
---|
3999 | return (primDecMonSlice(I)); |
---|
4000 | } |
---|
4001 | } |
---|
4002 | } |
---|
4003 | example |
---|
4004 | {"EXAMPLE:"; echo = 2; |
---|
4005 | ring R = 0,(w,x,y,z),Dp; |
---|
4006 | ideal I = w^3*x*y,w*x*y*z,x^2*y^2*z^2,x^2*z^4,y^3*z; |
---|
4007 | // Vasconcelos para primaria |
---|
4008 | primdecMon(I,"vp"); |
---|
4009 | // Alexander dual |
---|
4010 | primdecMon(I,"add"); |
---|
4011 | // label algorithm |
---|
4012 | primdecMon(I,"lr"); |
---|
4013 | //slice algorithm |
---|
4014 | primdecMon(I,"sr"); |
---|
4015 | } |
---|