Changeset 28c487 in git
- Timestamp:
- Apr 7, 2011, 5:00:38 PM (12 years ago)
- Branches:
- (u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')
- Children:
- f9e6d7592f3b35aaff38fe73f121615de78b162c
- Parents:
- c0b2e03243dcc8b84e3afb3a38cac55b6bb590c8
- File:
-
- 1 edited
-
Singular/LIB/monomialideal.lib (modified) (95 diffs)
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/monomialideal.lib
rc0b2e03 r28c487 1 // last modified: 10.06.2010 1 2 ////////////////////////////////////////////////////////////////////////////// 2 3 version = "$Id$"; 3 4 category = "Commutative algebra"; 4 5 info = " 5 LIBRARY: monomialideal.lib Primary and irreducible decompositions of 6 monomialideals7 AUTHORS: I.Bermejo, ibermejo@ull.es8 @* E.Garcia-Llorente, evgarcia@ull.es9 @* Ph.Gimenez, pgimenez@agt.uva.es6 LIBRARY: monomialideal.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 10 11 11 12 OVERVIEW: 12 A library for computing a primary and the irreducible decomposition of 13 a monomial ideal using several methods.@* 14 In addition, taking advantage of the fact that the ideals under 15 consideration are monomial, the library offers some basic operations 16 on ideals which are Groebner free in the monomial case (radical, 17 intersection, ideal quotient...). Note, however, that the general 18 Singular kernel commands for these operations are usually faster. 19 In a future edition of Singular, the specialized algorithms will also 20 be implemented in the Singular kernel. 21 22 Literature: Miller, Ezra and Sturmfels, Bernd: Combinatorial Commutative 23 Algebra, Springer 2004 13 A library for computing a primary and the irreducible decompositions of a 14 monomial ideal using several methods. 15 In this library we also take advantage of the fact that the ideal is 16 monomial to make some computations that are Grobner free in this case 17 (radical, intersection, quotient...). 24 18 25 19 PROCEDURES: 26 isMonomial(id); checks whether an ideal id is monomial 27 minbaseMon(id); computes the minimal monomial generating set of a 28 monomial ideal id 29 gcdMon(f,g); computes the gcd of two monomials f, g 30 lcmMon(f,g); computes the lcm of two monomials f, g 31 membershipMon(f,id); checks whether a polynomial f belongs to a monomial 32 ideal id 33 intersectMon(id1,id2); intersection of monomial ideals id1 and id2 34 quotientMon(id1,id2); quotient ideal id1:id2 35 radicalMon(id); computes the radical of a monomial ideal id 36 isprimeMon(id); checks whether a monomial ideal id is prime 37 isprimaryMon(id); checks whether a monomial ideal id is primary 38 isirreducibleMon(id); checks whether a monomial ideal id is irreducible 39 isartinianMon(id); checks whether a monomial ideal id is artininan 40 isgenericMon(id); checks whether a monomial ideal id is generic, i.e., 41 no two minimal generators of it agree in the exponent 42 of any variable that actually appears in both of them 43 dimMon(id); dimension of a monomial ideal id 44 irreddecMon(id,..); computes the irreducible decomposition of a monomial 45 ideal id 46 primdecMon(id,..); computes a minimal primary decomposition of a monomial 47 ideal id 20 isMonomial(id); checks whether an ideal id is monomial 21 minbaseMon(id); computes the minimal monomial generating set of a 22 monomial ideal id 23 gcdMon(f,g); computes the gcd of two monomials f, g 24 lcmMon(f,g); computes the lcm of two monomials f, g 25 membershipMon(f,id); checks whether a polynomial f belongs to a monomial 26 ideal id 27 intersectMon(id1,id2);intersection of monomial ideals id1 and id2 28 quotientMon(id1,id2); quotient ideal id1:id2 29 radicalMon(id); computes the radical of a monomial ideal id 30 isprimeMon(id); checks whether a monomial ideal id is prime 31 isprimaryMon(id); checks whether a monomial ideal id is primary 32 isirreducibleMon(id); checks whether a monomial ideal id is irreducible 33 isartinianMon(id); checks whether a monomial ideal id is artininan 34 isgenericMon(id); checks whether a monomial ideal id is generic 35 dimMon(id); dimension of a monomial ideal id 36 irreddecMon(id,..); computes the irreducible decomposition of a monomial 37 ideal id 38 primdecMon(id,..); computes a minimal primary decomposition of a monomial 39 ideal id 48 40 "; 49 50 41 LIB "poly.lib"; // Para "maxdeg1" en "isprimeMon" 51 52 42 //--------------------------------------------------------------------------- 53 43 //----------------------- INTERNOS ------------------------------------- 54 44 //--------------------------------------------------------------------------- 55 56 45 ///////////////////////////////////////////////////////////////////////////// 46 // 57 47 static proc checkIdeal (ideal I) 58 48 " 59 49 USAGE: checkIdeal (I); I ideal. 60 RETURN: 1, if the given generators of I aremonomials; 0, otherwise.50 RETURN: 1, if ideal is generated by monomials; 0, otherwise. 61 51 " 62 52 // Aqui NO estoy quitando el caso de que el ideal sea el trivial. … … 73 63 return (1); 74 64 } 75 76 65 ///////////////////////////////////////////////////////////////////////////// 77 static proc quotientIdealMon (ideal I, poly f) 66 // 67 static proc quotientIdealMon (ideal I,poly f) 78 68 " 79 69 USAGE: quotientIdealMon(I,f); I ideal, f polynomial. 80 70 RETURN: an ideal, the quotient ideal I:(f). 81 ASSUME: I is an ideal g ivenby a list of monomials and f is a monomial71 ASSUME: I is an ideal generated by a list of monomials and f is a monomial 82 72 of the basering. 83 73 " … … 106 96 return ( minbase(J) ); 107 97 } 108 109 98 ///////////////////////////////////////////////////////////////////////////// 99 // 110 100 static proc soporte (poly f) 111 101 " … … 140 130 return(sop); 141 131 } 142 143 132 ///////////////////////////////////////////////////////////////////////////// 133 // 144 134 static proc irredAux (ideal I) 145 135 " 146 136 USAGE: irredAux (I); I ideal. 147 RETURN: 1, if I is irreducible; otherwise, an intvec whose fi rst entry is137 RETURN: 1, if I is irreducible; otherwise, an intvec whose fist entry is 148 138 the position of a generator which is the product of more than one 149 variable, the next entries are the ind ices of those variables.139 variable, the next entries are the indexes of those variables. 150 140 ASSUME: I is a monomial ideal of the basering K[x(1)..x(n)] and it is 151 141 generated by its minimal monomial generators. 152 142 NOTE: This procedure is a modification of isirreducibleMon to give 153 more information when theideal is not irreducible.143 more information when ideal is not irreducible. 154 144 " 155 145 { … … 182 172 return(1); 183 173 } 184 185 // ///////////////////////////////////////////////////////////////////////////186 static proc contents (ideal I, 174 ////////////////////////////////////////////////////////////////////// 175 // 176 static proc contents (ideal I,ideal J) 187 177 " 188 178 USAGE: contents (I,J); I,J ideals. 189 179 RETURN: 1, if I is contained in J; 0, otherwise. 190 ASSUME: I, 180 ASSUME: I,J are monomial ideals of the basering. 191 181 " 192 182 { … … 207 197 return(1); 208 198 } 209 210 199 ///////////////////////////////////////////////////////////////////////////// 211 static proc equal (ideal I, ideal J) 200 // 201 static proc equal (ideal I,ideal J) 212 202 " 213 203 USAGE: equal (I,J); I,J ideals. 214 204 RETURN: 1, if I and J are the same ideal; 0, otherwise. 215 ASSUME: I, 205 ASSUME: I,J are monomial ideals of the basering and are defined by their 216 206 minimal monomial generators. 217 207 " … … 222 212 // Si no tienen el mismo numero de generadores, no pueden ser iguales; ya 223 213 // que vienen dados por el sistema minimal de generadores. 224 if ( ncols(I) <> ncols(J))214 if (size(I) <> size(J)) 225 215 { 226 216 return(0); … … 243 233 //return(1); 244 234 } 245 246 235 ///////////////////////////////////////////////////////////////////////////// 236 // 247 237 static proc radicalAux (ideal I) 248 238 " … … 279 269 return (rad); 280 270 } 281 282 271 ///////////////////////////////////////////////////////////////////////////// 272 // 283 273 static proc primAux (ideal I) 284 274 " … … 287 277 0, the second is the index of one variable such that a power of it 288 278 does not appear as a generator of I, the rest of the elements are 289 the position in the ideal of those elements of I which are product290 of more than one variable.279 the situation in the ideal of that elements of I which 280 are product of more than one variable. 291 281 ASSUME: I is a monomial ideal of the basering K[x(1)..x(n)]. 292 NOTE: This procedure detects if the ideal is primary . When the282 NOTE: This procedure detects if the ideal is primary, when the 293 283 ideal is not primary, it gives some additional information. 294 284 " … … 346 336 return (1); 347 337 } 348 349 338 ///////////////////////////////////////////////////////////////////////////// 350 static proc maxExp (ideal I, intvec v) 339 // 340 static proc maxExp (ideal I,intvec v) 351 341 " 352 342 USAGE: maxExp (I,v); I ideal, v integer vector. … … 356 346 variable considered is v[2]. 357 347 If the ideal I is primary, it returns 0. 358 NOTE: The elements of the vector s uggest what variable and which348 NOTE: The elements of the vector shows what variable and what 359 349 generators we must consider to look for the greatest power 360 350 of this variable. … … 381 371 return (max); 382 372 } 383 384 373 ///////////////////////////////////////////////////////////////////////////// 374 // 385 375 static proc irredundant (list l) 386 376 " … … 388 378 RETURN: a list such that the intersection of the elements in that list has 389 379 no redundant component. 390 ASSUME: Theelements of l are monomial ideals of the basering.380 ASSUME: elements of l are monomial ideals of the basering. 391 381 " 392 382 { … … 419 409 return (l); 420 410 } 421 422 411 ///////////////////////////////////////////////////////////////////////////// 423 static proc alexDif (intvec v, ideal I) 412 // 413 static proc alexDif (intvec v,ideal I) 424 414 " 425 415 USAGE: alexDif (v,I); v, intvec; I, ideal. … … 428 418 ASSUME: I is a monomial ideal of the basering K[x(1),...,x(n)] given by 429 419 its minimal monomial generators and v is an integer vector with 430 n entries s.t. 420 n entries s.t.monomial(v) is a multiple of all minimal monomial 431 421 generators of I. 432 422 " … … 461 451 return (l); 462 452 } 463 464 453 ///////////////////////////////////////////////////////////////////////////// 454 // 465 455 static proc irredPrimary (list l1) 466 456 " … … 513 503 return (l3); 514 504 } 515 516 505 ///////////////////////////////////////////////////////////////////////////// 506 // 517 507 static proc isMinimal (ideal I) 518 508 " 519 509 USAGE: isMinimal (I); I ideal. 520 RETURN: 1, if the g iven generators of I are the minimal ones;510 RETURN: 1, if the generators of I are the minimal ones; 521 511 0 & minimal generators of I, otherwise. 522 ASSUME: I is an ideal of the basering g iven by monomial generators.512 ASSUME: I is an ideal of the basering generated by monomials. 523 513 " 524 514 { … … 559 549 I = J; 560 550 i--; 561 sizI = ncols(I);551 sizI = size(I); 562 552 } 563 553 } … … 572 562 } 573 563 } 574 575 564 ///////////////////////////////////////////////////////////////////////////// 565 // 576 566 static proc isMonomialGB (ideal I) 577 567 " … … 579 569 RETURN: a list, 1 & the minimal generators of I, if I is a monomial ideal; 580 570 0, otherwise. 581 ASSUME: I is an ideal of the basering wh ose given generators are not571 ASSUME: I is an ideal of the basering which is not generated by 582 572 monomials. 583 NOTE: This procedure is NOT Groebner free and should be used only if the584 given generators are not monomials. (Use the proc checkIdeal first.)573 NOTE: this procedure is NOT Grobner free and should be used only if the 574 ideal has non-monomial generators (use first checkIdeal) 585 575 " 586 576 { … … 610 600 } 611 601 } 612 613 602 ///////////////////////////////////////////////////////////////////////////// 614 603 // … … 616 605 // WARNING: this is not a test, when the answer is 1 and the decompositions 617 606 // may not coincide but it is fast and easy and when the answer is 618 // 0 the decomposition sdo not coincide.619 // 620 proc areEqual(list l1, 607 // 0 the decomposition do not coincide. 608 // 609 proc areEqual(list l1,list l2) 621 610 { 622 611 int i,j,sizIdeal; … … 647 636 return (equal(l1Ideal,l2Ideal)); 648 637 } 649 650 638 ///////////////////////////////////////////////////////////////////////////// 651 639 //-------------------------------------------------------------------------// … … 653 641 //-------------------------------------------------------------------------// 654 642 ///////////////////////////////////////////////////////////////////////////// 655 656 ///////////////////////////////////////////////////////////////////////////// 643 // 657 644 proc isMonomial (ideal I) 658 "USAGE: isMonomial (I); I ideal659 RETURN: 1, if I is amonomial ideal; 0, otherwise.645 "USAGE: isMonomial (I); I ideal. 646 RETURN: 1, if I is monomial ideal; 0, otherwise. 660 647 ASSUME: I is an ideal of the basering. 661 648 EXAMPLE: example isMonomial; shows some examples. … … 694 681 isMonomial(J); 695 682 } 696 697 683 ///////////////////////////////////////////////////////////////////////////// 684 // 698 685 proc minbaseMon (ideal I) 699 "USAGE: minbaseMon (I); I ideal.686 "USAGE: minbaseMon (I); I ideal. 700 687 RETURN: an ideal, the minimal monomial generators of I. 701 -1 if the given generators of I are not monomials688 (-1 if the generators of I are not monomials) 702 689 ASSUME: I is an ideal generated by a list of monomials of the basering. 703 690 EXAMPLE: example minbaseMon; shows an example. … … 711 698 if (control == 0) 712 699 { 713 ERROR ("the ideal is not monomial");700 return (-1); 714 701 } 715 702 // Quitamos los ceros del sistema de generadores. … … 758 745 minbaseMon(I); 759 746 } 760 761 747 ///////////////////////////////////////////////////////////////////////////// 762 proc gcdMon (poly f, poly g) 763 "USAGE: gcdMon (f,g); f,g polynomials. 748 // 749 proc gcdMon (poly f,poly g) 750 "USAGE: gcdMon (f,g); f,g polynomials. 764 751 RETURN: a monomial, the greatest common divisor of f and g. 765 752 ASSUME: f and g are monomials of the basering. … … 804 791 gcdMon(f,g); 805 792 } 806 807 793 ///////////////////////////////////////////////////////////////////////////// 808 proc lcmMon (poly f, poly g) 809 "USAGE: lcmMon (f,g); f, g polynomials. 794 // 795 proc lcmMon (poly f,poly g) 796 "USAGE: lcmMon (f,g); f,g polynomials. 810 797 RETURN: a monomial,the least common multiple of f and g. 811 798 ASSUME: f,g are monomials of the basering. … … 849 836 lcmMon(f,g); 850 837 } 851 852 // ///////////////////////////////////////////////////////////////////////////853 proc membershipMon(poly f, 854 "USAGE: membershipMon(f,I); f polynomial, I ideal.838 ////////////////////////////////////////////////////////////////////// 839 // 840 proc membershipMon(poly f,ideal I) 841 "USAGE: membershipMon(f,I); f polynomial, I ideal. 855 842 RETURN: 1, if f lies in I; 0 otherwise. 856 -1 if I and f are nonzero and I is not a monomial ideal843 (-1 if I and f are nonzero and I is not a monomial ideal) 857 844 ASSUME: I is a monomial ideal of the basering. 858 845 EXAMPLE: example membershipMon; shows some examples … … 951 938 membershipMon(g,I); 952 939 } 953 954 // ///////////////////////////////////////////////////////////////////////////955 proc intersectMon (ideal I, 956 "USAGE: intersectMon (I, J); I,J ideals.940 ////////////////////////////////////////////////////////////////////// 941 // 942 proc intersectMon (ideal I,ideal J) 943 "USAGE: intersectMon (I,J); I,J ideals. 957 944 RETURN: an ideal, the intersection of I and J. 958 945 (it returns -1 if I or J are not monomial ideals) 959 946 ASSUME: I,J are monomial ideals of the basering. 960 947 NOTE: the minimal monomial generating set is returned. 961 USING THE SINGULAR COMMAND 'intersect' IS USUALLY FASTER962 948 EXAMPLE: example intersectMon; shows some examples 963 949 " … … 1037 1023 intersectMon (I,J); 1038 1024 } 1039 1040 // ///////////////////////////////////////////////////////////////////////////1041 proc quotientMon (ideal I, 1042 "USAGE: quotientMon (I, J); I,J ideals.1025 ////////////////////////////////////////////////////////////////////// 1026 // 1027 proc quotientMon (ideal I,ideal J) 1028 "USAGE: quotientMon (I,J); I,J ideals. 1043 1029 RETURN: an ideal, the quotient I:J. 1044 1030 (returns -1 if I or J is not monomial) 1045 ASSUME: I, 1031 ASSUME: I,J are monomial ideals of the basering. 1046 1032 NOTE: the minimal monomial generating set is returned. 1047 1033 EXAMPLE: example quotientMon; shows an example. … … 1084 1070 { 1085 1071 ERROR ("the second ideal is not monomial."); 1072 return (-1); 1086 1073 } 1087 1074 else … … 1119 1106 quotientMon (I,J); 1120 1107 } 1121 1122 // ///////////////////////////////////////////////////////////////////////////1108 ////////////////////////////////////////////////////////////////////// 1109 // 1123 1110 proc radicalMon(ideal I) 1124 "USAGE: radicalMon(I); I ideal1111 "USAGE: radicalMon(I); I ideal 1125 1112 RETURN: an ideal, the radical ideal of the ideal I. 1126 1113 (returns -1 if I is not a monomial ideal) 1127 1114 ASSUME: I is a monomial ideal of the basering. 1128 NOTE: The minimal monomial generating set is returned.1115 NOTE: the minimal monomial generating set is returned. 1129 1116 EXAMPLE: example radicalMon; shows an example. 1130 1117 " … … 1186 1173 radicalMon(I); 1187 1174 } 1188 1189 // ///////////////////////////////////////////////////////////////////////////1175 ////////////////////////////////////////////////////////////////////// 1176 // 1190 1177 proc isprimeMon (ideal I) 1191 "USAGE: isprimeMon (I); I ideal1178 "USAGE: isprimeMon (I); I ideal 1192 1179 RETURN: 1, if I is prime; 0, otherwise. 1193 1180 (returns -1 if I is not a monomial ideal) … … 1236 1223 isprimeMon (J); 1237 1224 } 1238 1239 // ///////////////////////////////////////////////////////////////////////////1225 ////////////////////////////////////////////////////////////////////// 1226 // 1240 1227 proc isprimaryMon (ideal I) 1241 "USAGE: isprimaryMon (I); I ideal1228 "USAGE: isprimaryMon (I); I ideal 1242 1229 RETURN: 1, if I is primary; 0, otherwise. 1243 1230 (returns -1 if I is not a monomial ideal) … … 1338 1325 isprimaryMon (J); 1339 1326 } 1340 1341 // ///////////////////////////////////////////////////////////////////////////1327 ////////////////////////////////////////////////////////////////////// 1328 // 1342 1329 proc isirreducibleMon (ideal I) 1343 "USAGE: isirreducibleMon(I); I ideal1330 "USAGE: isirreducibleMon(I); I ideal 1344 1331 RETURN: 1, if I is irreducible; 0, otherwise. 1345 returns -1 if I is not a monomial ideal1332 (return -1 if I is not a monomial ideal) 1346 1333 ASSUME: I is a monomial ideal of the basering. 1347 1334 EXAMPLE: example isirreducibleMon; shows some examples … … 1394 1381 isirreducibleMon (J); 1395 1382 } 1396 1397 // ///////////////////////////////////////////////////////////////////////////1383 ////////////////////////////////////////////////////////////////////// 1384 // 1398 1385 proc isartinianMon (ideal I) 1399 "USAGE: isartinianMon(I); I ideal.1386 "USAGE: isartinianMon(I); I ideal. 1400 1387 RETURN: 1, if ideal is artinian; 0, otherwise. 1401 returns -1 if ideal I is not a monmomial ideal1388 (return -1 if ideal I is not a monmomial ideal). 1402 1389 ASSUME: I is a monomial ideal of the basering. 1403 1390 EXAMPLE: example isartinianMon; shows some examples … … 1462 1449 isartinianMon (J); 1463 1450 } 1464 1465 // ///////////////////////////////////////////////////////////////////////////1451 ////////////////////////////////////////////////////////////////////// 1452 // 1466 1453 proc isgenericMon (ideal I) 1467 "USAGE: isgenericMon(I); I ideal.1454 "USAGE: isgenericMon(I); I ideal. 1468 1455 RETURN: 1, if ideal is generic; 0, otherwise. 1469 returns -1 if ideal I is not a monomial ideal1456 (return -1 if ideal I is not a monomial ideal) 1470 1457 ASSUME: I is a monomial ideal of the basering. 1471 1458 EXAMPLE: example isgenericMon; shows some examples. … … 1533 1520 isgenericMon (J); 1534 1521 } 1535 1536 // ///////////////////////////////////////////////////////////////////////////1522 ////////////////////////////////////////////////////////////////////// 1523 // 1537 1524 proc dimMon (ideal I) 1538 "USAGE: dimMon (I); I ideal1525 "USAGE: dimMon (I); I ideal 1539 1526 RETURN: an integer, the dimension of the affine variety defined by 1540 1527 the ideal I. 1541 returns -1 if I is not a monomial ideal1528 (returns -1 if I is not a monomial ideal) 1542 1529 ASSUME: I is a monomial ideal of the basering. 1543 1530 EXAMPLE: example dimMon; shows some examples. … … 1640 1627 dimMon (J); 1641 1628 } 1642 1643 1629 ///////////////////////////////////////////////////////////////////////////// 1644 1630 //-------------------------------------------------------------------------// … … 1646 1632 //-------------------------------------------------------------------------// 1647 1633 ///////////////////////////////////////////////////////////////////////////// 1648 1649 ////////////////////////////////////////////////////////////////////// 1634 // 1650 1635 // METODO 1: Metodo directo para descomp. irreducible (ver Vasconcelos) 1651 1636 // … … 1656 1641 // (Vasconcelos) // 1657 1642 ////////////////////////////////////////////////////////////////////// 1643 // 1658 1644 static proc irredDec1 (ideal I) 1659 1645 { … … 1721 1707 return (l2); 1722 1708 } 1723 1724 1709 ////////////////////////////////////////////////////////////////////// 1725 1710 // La siguiente funcion va a obtener una descomposicion primaria // 1726 1711 // minimal a partir de la irreducible anterior. // 1727 1712 ////////////////////////////////////////////////////////////////////// 1713 // 1728 1714 static proc primDec1 (ideal I) 1729 1715 { … … 1736 1722 return (l2); 1737 1723 } 1738 1739 ////////////////////////////////////////////////////////////////////// 1724 // 1740 1725 // METODO 2: Metodo directo para descomp. primaria (ver Vasconcelos) 1741 1726 // … … 1746 1731 // hace uso de esta (Vasconcelos). // 1747 1732 ////////////////////////////////////////////////////////////////////// 1733 // 1748 1734 static proc primDec2 (ideal I) 1749 1735 { … … 1797 1783 return (l2); 1798 1784 } 1799 // ////////////////////////////////////////////////////////////////////1785 // 1800 1786 // METODO 3: via dual de Alexander y doble dual (Miller) 1801 1787 // … … 1805 1791 // ideal de partida (Miller) // 1806 1792 ////////////////////////////////////////////////////////////////////// 1793 // 1807 1794 static proc irredDec3 (ideal I) 1808 1795 { … … 1835 1822 return (l); 1836 1823 } 1837 1838 1824 ////////////////////////////////////////////////////////////////////// 1839 1825 // En este caso hallamos una descomposicion primaria minimal usando // 1840 1826 // la irreducible irredundante del procedimiento anterior. // 1841 1827 ////////////////////////////////////////////////////////////////////// 1828 // 1842 1829 static proc primDec3 (ideal I) 1843 1830 { … … 1850 1837 return (l2); 1851 1838 } 1852 1853 ////////////////////////////////////////////////////////////////////// 1839 // 1854 1840 // METODO 4: via dual de Alexander y cociente (Miller) 1855 1841 // … … 1859 1845 // Alexander (con el cociente) (Miller) // 1860 1846 ////////////////////////////////////////////////////////////////////// 1847 // 1861 1848 static proc irredDec4 (ideal I) 1862 1849 { … … 1907 1894 return (L); 1908 1895 } 1909 1910 1896 ////////////////////////////////////////////////////////////////////// 1911 1897 // Ahora hallamos una descomposicion primaria irredundante usando // … … 1913 1899 // ideal monomial dado por sus generadores minimales. // 1914 1900 ////////////////////////////////////////////////////////////////////// 1901 // 1915 1902 static proc primDec4 (ideal I) 1916 1903 { … … 1923 1910 return (l2); 1924 1911 } 1925 1926 ////////////////////////////////////////////////////////////////////// 1912 // 1927 1913 // METODO 5: un misterio!! 1928 1914 // … … 1932 1918 // irreducibles del ideal 1-1. // 1933 1919 ////////////////////////////////////////////////////////////////////// 1920 // 1934 1921 static proc irredDec5 (ideal I) 1935 1922 { … … 2015 2002 return (facets); 2016 2003 } 2017 2018 2004 ////////////////////////////////////////////////////////////////////// 2019 2005 // Ahora hallamos una descomposicion primaria irredundante usando // … … 2021 2007 // ideal monomial dado por sus generadores minimales. // 2022 2008 ////////////////////////////////////////////////////////////////////// 2009 // 2023 2010 static proc primDec5 (ideal I) 2024 2011 { … … 2031 2018 return (l2); 2032 2019 } 2033 2034 ////////////////////////////////////////////////////////////////////// 2020 // 2035 2021 // METODO 6: via complejo de Scarf (Milovsky) 2036 2022 // … … 2043 2029 // generadores del ideal. // 2044 2030 ////////////////////////////////////////////////////////////////////// 2031 // 2045 2032 static proc maximoExp(ideal I,int i) 2046 2033 { … … 2060 2047 return(max); 2061 2048 } 2062 2063 2049 ////////////////////////////////////////////////////////////////////// 2064 2050 // Esta funcion estudia si un ideal monomial dado por su sistema // … … 2067 2053 // que han sido introducidos. // 2068 2054 ////////////////////////////////////////////////////////////////////// 2055 // 2069 2056 static proc artinian (ideal I) 2070 2057 { … … 2150 2137 } 2151 2138 } 2152 2153 2139 ////////////////////////////////////////////////////////////////////// 2154 2140 // En este caso vamos primero a chequear si el ideal es o no // … … 2156 2142 // pues estos son una aplicacion biyectiva. // 2157 2143 ////////////////////////////////////////////////////////////////////// 2144 // 2158 2145 static proc generic (ideal I) 2159 2146 { … … 2219 2206 } 2220 2207 } 2221 2222 2208 ////////////////////////////////////////////////////////////////////// 2223 2209 // Esta funci?n obtiene una descomposicion irreducible del ideal // … … 2225 2211 // generico que le asociamos. // 2226 2212 ////////////////////////////////////////////////////////////////////// 2213 // 2227 2214 static proc nonGeneric (EXP,NEWEXP,Faces,sizI) 2228 2215 { … … 2259 2246 return (newFaces); 2260 2247 } 2261 2262 2248 ////////////////////////////////////////////////////////////////////// 2263 2249 // Este procedimiento va a dar una faceta inicial para el complejo // … … 2265 2251 // y generico (evidentemente I dado por la bse minimal) // 2266 2252 ////////////////////////////////////////////////////////////////////// 2253 // 2267 2254 static proc initialFacet (ideal I) 2268 2255 { … … 2351 2338 return (face); 2352 2339 } 2353 2354 2340 ////////////////////////////////////////////////////////////////////// 2355 2341 // La funcion que sigue devuelve las facetas adyacentes a una dada // 2356 2342 // en el complejo de Scarf asociado a I. // 2357 2343 ////////////////////////////////////////////////////////////////////// 2344 // 2358 2345 static proc adyacency (list l1, ideal I) 2359 2346 { … … 2515 2502 return(l2); 2516 2503 } 2517 2518 2504 ////////////////////////////////////////////////////////////////////// 2519 2505 // Metodo que calcula la descomposicion irreducible de un ideal // 2520 2506 // monomial usando el complejo de Scarf (Milowski) // 2521 2507 ////////////////////////////////////////////////////////////////////// 2508 // 2522 2509 static proc ScarfMethod (ideal I) 2523 2510 { … … 2666 2653 } 2667 2654 // Generico 2668 sizI = ncols(I);2655 sizI = size(I); 2669 2656 if (genericlist[1] == 0) 2670 2657 { … … 2694 2681 return(Faces); 2695 2682 } 2696 2697 2683 ////////////////////////////////////////////////////////////////////// 2698 2684 // Devuelve una descomposicion primaria minimal de un ideal // 2699 2685 // monomial via el complejo de Scarf. // 2700 2686 ////////////////////////////////////////////////////////////////////// 2687 // 2701 2688 static proc scarfMethodPrim (ideal I) 2702 2689 { … … 2710 2697 return (l2); 2711 2698 } 2712 2713 ////////////////////////////////////////////////////////////////////// 2699 // 2714 2700 // METODO 7: algoritmo de etiquetas (Roune) 2715 2701 // … … 2719 2705 // algoritmo de etiquetas de B. Roune. // 2720 2706 ////////////////////////////////////////////////////////////////////// 2707 // 2721 2708 static proc phi (list F) 2722 2709 { … … 2749 2736 return (listphi); 2750 2737 } 2751 2752 // ///////////////////////////////////////////////////////////////////////////2738 ////////////////////////////////////////////////////////////////////// 2739 // 2753 2740 static proc pi(poly f) 2754 2741 { … … 2768 2755 return (f); 2769 2756 } 2770 2771 // ///////////////////////////////////////////////////////////////////////////2757 ////////////////////////////////////////////////////////////////////// 2758 // 2772 2759 static proc conditionComplex (intvec posActual,ideal I,ideal S) 2773 2760 { … … 2826 2813 return (0); 2827 2814 } 2828 2829 // ///////////////////////////////////////////////////////////////////////////2815 ////////////////////////////////////////////////////////////////////// 2816 // 2830 2817 static proc findFaces (ideal I) 2831 2818 { … … 2879 2866 return (F); 2880 2867 } 2881 2882 2868 ////////////////////////////////////////////////////////////////////// 2883 2869 // La siguiente funcion calcula la descomposicion en irreducibles de// … … 2885 2871 // metodo de Bjarke Roune. // 2886 2872 ////////////////////////////////////////////////////////////////////// 2873 // 2887 2874 static proc labelAlgorithm(ideal I) 2888 2875 { … … 2955 2942 return (facets); 2956 2943 } 2957 2958 2944 ////////////////////////////////////////////////////////////////////// 2959 2945 // Devuelve una descomposicion primaria minimal de un ideal monomial// 2960 2946 // dado. // 2961 2947 ////////////////////////////////////////////////////////////////////// 2962 static proc labelAlgPrim (ideal I) 2948 // 2949 static proc labelAlgPrim (ideal I) 2963 2950 { 2964 2951 // VARIABLES … … 2971 2958 return (l2); 2972 2959 } 2973 2974 ////////////////////////////////////////////////////////////////////// 2960 // 2975 2961 // METODO 8: Gao-Zhu 2976 2962 // 2977 2963 ////////////////////////////////////////////////////////////////////// 2964 // 2978 2965 static proc divide (intvec v, intvec w, int k) 2979 2966 { … … 3000 2987 return (1); 3001 2988 } 3002 3003 ///////////////////////////////////////////////////////////////////////////// 2989 ////////////////////////////////////////////////////////////////////// 2990 // // 2991 ////////////////////////////////////////////////////////////////////// 2992 // 3004 2993 static proc incrementalAlg (ideal I) 3005 2994 { … … 3092 3081 { 3093 3082 expartI = leadexp(artI[1]); 3094 if ( ncols(artI) <> 1)3095 { 3096 artI = artI[2.. ncols(artI)];3083 if (size(artI) <> 1) 3084 { 3085 artI = artI[2..size(artI)]; 3097 3086 } 3098 3087 // Hay que distinguir T_1 y T_2. Para ello se comparar vectores … … 3210 3199 return (facets); 3211 3200 } 3212 3213 // ///////////////////////////////////////////////////////////////////////////3201 ////////////////////////////////////////////////////////////////////// 3202 // 3214 3203 static proc incrementalAlgPrim (ideal I) 3215 3204 { … … 3223 3212 return (l2); 3224 3213 } 3225 3226 ////////////////////////////////////////////////////////////////////// 3214 // 3227 3215 // METODO 9: slice algorithm (Roune) 3228 3216 // … … 3230 3218 // SLICE ALGORITHM (B.Roune) // 3231 3219 ////////////////////////////////////////////////////////////////////// 3220 // 3232 3221 static proc divideMon (poly f , poly g) 3233 3222 { … … 3245 3234 //return (1); 3246 3235 } 3247 3248 // ///////////////////////////////////////////////////////////////////////////3236 ////////////////////////////////////////////////////////////////////// 3237 // 3249 3238 static proc pivot (ideal I , poly lcmMin, ideal S) 3250 3239 { … … 3309 3298 } 3310 3299 } 3311 3312 // ///////////////////////////////////////////////////////////////////////////3300 ////////////////////////////////////////////////////////////////////// 3301 // 3313 3302 static proc simplification (I) 3314 3303 { … … 3431 3420 return (lcmMi,I); 3432 3421 } 3433 3434 // ///////////////////////////////////////////////////////////////////////////3422 ////////////////////////////////////////////////////////////////////// 3423 // 3435 3424 static proc con (ideal I , ideal S , poly q) 3436 3425 { … … 3543 3532 return (con(I1,S1,p*q),con(I,S2,q)); 3544 3533 } 3545 3546 // ///////////////////////////////////////////////////////////////////////////3534 ////////////////////////////////////////////////////////////////////// 3535 // 3547 3536 static proc irredDecMonSlice (ideal I) 3548 3537 { … … 3565 3554 { 3566 3555 artI = sort(artI)[1]; 3567 int sizartI = ncols(artI);3556 int sizartI = size(artI); 3568 3557 for (i = 1 ; i <= sizartI - 1 ; i ++) 3569 3558 { … … 3589 3578 poly comp; 3590 3579 intvec exp; 3591 int sizIrred = ncols(irredDec);3580 int sizIrred = size(irredDec); 3592 3581 ideal auxIdeal; 3593 3582 for (i = 1 ; i <= sizIrred ; i ++) … … 3621 3610 return (components); 3622 3611 } 3623 3624 // ///////////////////////////////////////////////////////////////////////////3612 ////////////////////////////////////////////////////////////////////// 3613 // 3625 3614 static proc primDecMonSlice (ideal I) 3626 3615 { … … 3634 3623 return (l2); 3635 3624 } 3636 3637 3625 ////////////////////////////////////////////////////////////////////// 3638 3626 // // … … 3641 3629 ////////////////////////////////////////////////////////////////////// 3642 3630 ////////////////////////////////////////////////////////////////////// 3643 3644 ///////////////////////////////////////////////////////////////////////////// 3631 // 3645 3632 proc irreddecMon 3646 "USAGE: irreddecMon (I[,alg]); I ideal, alg string.3633 "USAGE: irreddecMon (I[,alg]); I ideal, alg string. 3647 3634 RETURN: list, the irreducible components of the monomial ideal I. 3648 3635 (returns -1 if I is not a monomial ideal). 3649 3636 ASSUME: I is a monomial ideal of the basering k[x(1)..x(n)]. 3650 NOTE: This procedure returns the irreducible decomposition of I, 3651 i.e., the unique irredundant decomposition of I into irreducible 3652 monomial ideals. 3637 NOTE: This procesure returns the irreducible decomposition of I. 3653 3638 One may call the procedure with different algorithms using 3654 3639 the optional argument 'alg': … … 3748 3733 irreddecMon(I,"sr"); 3749 3734 } 3750 3751 // ///////////////////////////////////////////////////////////////////////////3735 ////////////////////////////////////////////////////////////////////// 3736 // 3752 3737 proc primdecMon 3753 "USAGE: primdecMon (I[,alg]); I ideal, alg string3738 "USAGE: primdecMon (I[,alg]); I ideal, alg string 3754 3739 RETURN: list, the components in a minimal primary decomposition of I. 3755 3740 (returns -1 if I is not a monomial ideal). 3756 3741 ASSUME: I is a monomial ideal of the basering k[x(1)..x(n)]. 3757 NOTE: This proce dure returns a minimal primary decomposition of I.3742 NOTE: This procesure returns a minimal primary decomposition of I. 3758 3743 One may call the procedure with different algorithms using 3759 3744 the optional argument 'alg':
Note: See TracChangeset
for help on using the changeset viewer.
