Changeset a2466f in git for kernel/kutil.cc
 Timestamp:
 Jun 12, 2006, 2:07:12 AM (17 years ago)
 Branches:
 (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
 Children:
 c4c516319dd7380d23251f74e2a664cdb5664571
 Parents:
 30f22c1ce9b7faf89c70d82bed9c82dd6d7b4979
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

kernel/kutil.cc
r30f22c ra2466f 2 2 * Computer Algebra System SINGULAR * 3 3 ****************************************/ 4 /* $Id: kutil.cc,v 1.2 4 20060607 18:44:23wienand Exp $ */4 /* $Id: kutil.cc,v 1.25 20060612 00:07:11 wienand Exp $ */ 5 5 /* 6 6 * ABSTRACT: kernel: utils for kStd … … 52 52 #define KDEBUG 2 53 53 #endif 54 #define pDivComp_EQUAL 2 55 #define pDivComp_LESS 1 56 #define pDivComp_GREATER 1 57 #define pDivComp_INCOMP 0 58 54 59 55 60 #ifdef ENTER_USE_MYMEMMOVE … … 100 105 static poly redBba (poly h,int maxIndex,kStrategy strat); 101 106 107 /* Checks the relation of LM(p) and LM(q) 108 LM(p) = LM(q) => return pDivComp_EQUAL 109 LM(p)  LM(q) => return pDivComp_LESS 110 LM(q)  LM(p) => return pDivComp_GREATER 111 else return pDivComp_INCOMP */ 102 112 static inline int pDivComp(poly p, poly q) 103 113 { … … 132 142 if (a) return 1; 133 143 if (b) return 1; 144 if (!a & !b) return pDivComp_EQUAL; 134 145 } 135 146 return 0; … … 438 449 } 439 450 451 #ifdef HAVE_RING2TOM 452 //void initLMtest(kStrategy strat) 453 //{ 454 // strat>lmtest = (unsigned int *)omAlloc0((strat>sl*strat>sl/2+2)*sizeof(BOOLEAN)); 455 //} 456 #endif 457 440 458 /*2 441 459 *test whether (p1,p2) or (p2,p1) is in L up position length … … 996 1014 else 997 1015 { 998 if (b % 2 == 1) 1016 if (b % 2 == 1) 999 1017 { 1000 1018 return 0; … … 1026 1044 pSetm(Lp.lcm); 1027 1045 pSetCoeff(Lp.lcm, nLcm(pGetCoeff(p), pGetCoeff(strat>S[i]), currRing)); 1028 if (strat>sugarCrit) 1029 { 1030 WarnS("Sugar Criterion not yet available on in the ring case"); 1031 } 1032 else /*sugarcrit*/ 1033 { 1034 // basic product criterion 1035 if (pHasNotCF(p,strat>S[i]) && (long) pGetCoeff(p) % 2 == 1 && (long) pGetCoeff(strat>S[i]) % 2 == 1) 1036 { 1037 strat>cp++; 1046 assume(!strat>sugarCrit); 1047 // basic product criterion 1048 if (pHasNotCF(p,strat>S[i]) && (long) pGetCoeff(p) % 2 == 1 && (long) pGetCoeff(strat>S[i]) % 2 == 1) 1049 { 1050 strat>cp++; 1051 pLmFree(Lp.lcm); 1052 Lp.lcm=NULL; 1053 return; 1054 } 1055 assume(!strat>fromT); 1056 /* 1057 *the set B collects the pairs of type (S[j],p) 1058 *suppose (r,p) is in B and (s,p) is the new pair and lcm(s,p) != lcm(r,p) 1059 *if the leading term of s devides lcm(r,p) then (r,p) will be canceled 1060 *if the leading term of r devides lcm(s,p) then (s,p) will not enter B 1061 */ 1062 for(j = strat>Bl;j>=0;j) 1063 { 1064 compare=pDivComp(strat>B[j].lcm,Lp.lcm); 1065 compareCoeff = nComp((long) pGetCoeff(strat>B[j].lcm), (long) pGetCoeff(Lp.lcm)); 1066 if (compareCoeff == 0  compare == compareCoeff) 1067 { 1068 if (compare == 1) 1069 { 1070 strat>c3++; 1071 if ((strat>fromQ==NULL)  (isFromQ==0)  (strat>fromQ[i]==0)) 1072 { 1038 1073 pLmFree(Lp.lcm); 1039 Lp.lcm=NULL;1040 1074 return; 1041 } 1042 if (strat>fromT) // && (strat>ecartS[i]>ecart)) 1043 { 1044 WarnS("Sugar Criterion not yet available on in the ring case"); 1045 } 1046 /* 1047 *the set B collects the pairs of type (S[j],p) 1048 *suppose (r,p) is in B and (s,p) is the new pair and lcm(s,p)#lcm(r,p) 1049 *if the leading term of s devides lcm(r,p) then (r,p) will be canceled 1050 *if the leading term of r devides lcm(s,p) then (s,p) will not enter B 1051 */ 1052 for(j = strat>Bl;j>=0;j) 1053 { 1054 compare=pDivComp(strat>B[j].lcm,Lp.lcm); 1055 compareCoeff = nComp((long) pGetCoeff(strat>B[j].lcm), (long) pGetCoeff(Lp.lcm)); 1056 if (compareCoeff == 0  compare == compareCoeff) 1057 { 1058 if (compare==1) 1059 { 1060 strat>c3++; 1061 if ((strat>fromQ==NULL)  (isFromQ==0)  (strat>fromQ[i]==0)) 1062 { 1063 pLmFree(Lp.lcm); 1064 return; 1065 } 1066 break; 1067 } 1068 else 1069 if (compare ==1) 1070 { 1071 deleteInL(strat>B,&strat>Bl,j,strat); 1072 strat>c3++; 1073 } 1074 } 1075 } 1076 } 1075 } 1076 break; 1077 } 1078 else 1079 if (compare == 1) 1080 { 1081 deleteInL(strat>B,&strat>Bl,j,strat); 1082 strat>c3++; 1083 } 1084 } 1085 if (compare == pDivComp_EQUAL) 1086 { 1087 // Add hint for same LM and direction of LC (later) (TODO Oliver) 1088 if (compareCoeff == 1) 1089 { 1090 strat>c3++; 1091 if ((strat>fromQ==NULL)  (isFromQ==0)  (strat>fromQ[i]==0)) 1092 { 1093 pLmFree(Lp.lcm); 1094 return; 1095 } 1096 break; 1097 } 1098 else 1099 if (compareCoeff == 1) 1100 { 1101 deleteInL(strat>B,&strat>Bl,j,strat); 1102 strat>c3++; 1103 } 1104 } 1105 } 1077 1106 /* 1078 1107 *the pair (S[i],p) enters B if the spoly != 0 … … 1083 1112 if ((strat>fromQ!=NULL) && (isFromQ!=0) && (strat>fromQ[i]!=0)) 1084 1113 { 1085 WarnS("Oliver weiss nicht, was dieses genau macht."); 1114 // Is from a previous computed GB, therefore we know that spoly will 1115 // reduce to zero. Oliver. 1086 1116 Lp.p=NULL; 1087 1117 } … … 1755 1785 { 1756 1786 int i,j,l; 1757 1758 1787 /* 1759 1788 *pairtest[i] is TRUE if spoly(S[i],p) == 0. … … 1783 1812 strat>pairtest=NULL; 1784 1813 } 1785 if (strat>Gebauer  strat>fromT) 1786 { 1787 WarnS("Gebauer or fromT not tested yet in chainCritRing."); 1788 if (strat>sugarCrit) 1789 { 1790 WarnS("Sugar Criterion not yet available for coefficient rings."); 1791 } 1792 else /*sugarCrit*/ 1793 { 1794 /* 1795 *suppose L[j] == (s,r) and p/lcm(s,r) 1796 *and lcm(s,r)#lcm(s,p) and lcm(s,r)#lcm(r,p) 1797 *and in case the sugar is o.k. then L[j] can be canceled 1798 */ 1799 for (j=strat>Ll; j>=0; j) 1800 { 1801 if (pCompareChain(p,strat>L[j].p1,strat>L[j].p2,strat>L[j].lcm)) 1802 { 1803 if ((pNext(strat>L[j].p) == strat>tail)(pOrdSgn==1)) 1804 { 1805 deleteInL(strat>L,&strat>Ll,j,strat); 1806 strat>c3++; 1807 } 1808 } 1809 } 1810 /* 1811 *this is GEBAUERMOELLER: 1812 *in B all elements with the same lcm except the "best" 1813 *(i.e. the last one in B with this property) will be canceled 1814 */ 1815 j = strat>Bl; 1816 loop /*cannot be changed into a for !!! */ 1817 { 1818 if (j <= 0) break; 1819 for(i=j1; i>=0; i) 1820 { 1821 if (pLmEqual(strat>B[j].lcm,strat>B[i].lcm)) 1822 { 1823 strat>c3++; 1824 deleteInL(strat>B,&strat>Bl,i,strat); 1825 j; 1826 } 1827 } 1828 j; 1829 } 1830 } 1831 /* 1832 *the elements of B enter L/their order with respect to B is kept 1833 *j = posInL(L,j,B[i]) would permutate the order 1834 *if once B is ordered different from L 1835 *then one should use j = posInL(L,Ll,B[i]) 1836 */ 1837 j = strat>Ll+1; 1838 for (i=strat>Bl; i>=0; i) 1839 { 1840 j = strat>posInL(strat>L,j1,&(strat>B[i]),strat); 1841 enterL(&strat>L,&strat>Ll,&strat>Lmax,strat>B[i],j); 1842 } 1843 strat>Bl = 1; 1844 } 1845 else /* Gebauer or fromT */ 1846 { 1847 for (j=strat>Ll; j>=0; j) 1814 assume(!(strat>Gebauer  strat>fromT)); 1815 for (j=strat>Ll; j>=0; j) 1816 { 1817 if (nGreater(pGetCoeff(strat>L[j].lcm), pGetCoeff(p))) 1848 1818 { 1849 1819 if (pCompareChain(p,strat>L[j].p1,strat>L[j].p2,strat>L[j].lcm)) 1850 1820 { 1851 if ((pNext(strat>L[j].p) == strat>tail) (pOrdSgn==1))1821 if ((pNext(strat>L[j].p) == strat>tail)  (pOrdSgn==1)) 1852 1822 { 1853 1823 deleteInL(strat>L,&strat>Ll,j,strat); 1854 1824 strat>c3++; 1855 } 1856 } 1857 } 1858 /* 1859 *this is our MODIFICATION of GEBAUERMOELLER: 1860 *First the elements of B enter L, 1861 *then we fix a lcm and the "best" element in L 1862 *(i.e the last in L with this lcm and of type (s,p)) 1863 *and cancel all the other elements of type (r,p) with this lcm 1864 *except the case the element (s,r) has also the same lcm 1865 *and is on the worst position with respect to (s,p) and (r,p) 1866 */ 1867 /* 1868 *B enters to L/their order with respect to B is permutated for elements 1869 *B[i].p with the same leading term 1870 */ 1871 j = strat>Ll; 1872 for (i=strat>Bl; i>=0; i) 1873 { 1874 j = strat>posInL(strat>L,j,&(strat>B[i]),strat); 1875 enterL(&strat>L,&strat>Ll,&strat>Lmax,strat>B[i],j); 1876 } 1877 strat>Bl = 1; 1878 j = strat>Ll; 1879 loop /*cannot be changed into a for !!! */ 1880 { 1881 if (j <= 0) 1882 { 1883 /*now L[0] cannot be canceled any more and the tail can be removed*/ 1884 if (strat>L[0].p2 == strat>tail) strat>L[0].p2 = p; 1885 break; 1886 } 1887 if (strat>L[j].p2 == p) 1888 { 1889 i = j1; 1890 loop 1891 { 1892 if (i < 0) break; 1893 if ((strat>L[i].p2 == p) && pLmEqual(strat>L[j].lcm,strat>L[i].lcm)) 1825 Print("UL"); 1826 } 1827 } 1828 } 1829 } 1830 /* 1831 *this is our MODIFICATION of GEBAUERMOELLER: 1832 *First the elements of B enter L, 1833 *then we fix a lcm and the "best" element in L 1834 *(i.e the last in L with this lcm and of type (s,p)) 1835 *and cancel all the other elements of type (r,p) with this lcm 1836 *except the case the element (s,r) has also the same lcm 1837 *and is on the worst position with respect to (s,p) and (r,p) 1838 */ 1839 /* 1840 *B enters to L/their order with respect to B is permutated for elements 1841 *B[i].p with the same leading term 1842 */ 1843 j = strat>Ll; 1844 for (i=strat>Bl; i>=0; i) 1845 { 1846 j = strat>posInL(strat>L,j,&(strat>B[i]),strat); 1847 enterL(&strat>L,&strat>Ll,&strat>Lmax,strat>B[i],j); 1848 } 1849 strat>Bl = 1; 1850 j = strat>Ll; 1851 loop /*cannot be changed into a for !!! */ 1852 { 1853 if (j <= 0) 1854 { 1855 /*now L[0] cannot be canceled any more and the tail can be removed*/ 1856 if (strat>L[0].p2 == strat>tail) strat>L[0].p2 = p; 1857 break; 1858 } 1859 if (strat>L[j].p2 == p) // Was the element added from B? 1860 { 1861 i = j1; 1862 loop 1863 { 1864 if (i < 0) break; 1865 // Element is from B and has the same lcm as L[j] 1866 if ((strat>L[i].p2 == p) && pLmEqual(strat>L[j].lcm,strat>L[i].lcm) 1867 #ifdef HAVE_RING2TOM 1868 && nGreater(pGetCoeff(strat>L[j].lcm), pGetCoeff(strat>L[i].lcm)) 1869 #endif 1870 ) 1871 { 1872 /*L[i] could be canceled but we search for a better one to cancel*/ 1873 strat>c3++; 1874 Print("EP"); 1875 if (isInPairsetL(i1,strat>L[j].p1,strat>L[i].p1,&l,strat) 1876 && (pNext(strat>L[l].p) == strat>tail) 1877 && (!pLmEqual(strat>L[i].p,strat>L[l].p)) 1878 #ifdef HAVE_RING2TOM 1879 // && 1 == 0 1880 #endif 1881 && pDivisibleBy(p,strat>L[l].lcm)) 1894 1882 { 1895 /*L[i] could be canceled but we search for a better one to cancel*/ 1896 strat>c3++; 1897 if (isInPairsetL(i1,strat>L[j].p1,strat>L[i].p1,&l,strat) 1898 && (pNext(strat>L[l].p) == strat>tail) 1899 && (!pLmEqual(strat>L[i].p,strat>L[l].p)) 1900 && pDivisibleBy(p,strat>L[l].lcm)) 1901 { 1902 /* 1903 *"NOT equal(...)" because in case of "equal" the element L[l] 1904 *is "older" and has to be from theoretical point of view behind 1905 *L[i], but we do not want to reorder L 1906 */ 1907 strat>L[i].p2 = strat>tail; 1908 /* 1909 *L[l] will be canceled, we cannot cancel L[i] later on, 1910 *so we mark it with "tail" 1911 */ 1912 deleteInL(strat>L,&strat>Ll,l,strat); 1913 i; 1914 } 1915 else 1916 { 1917 deleteInL(strat>L,&strat>Ll,i,strat); 1918 } 1919 j; 1883 /* 1884 *"NOT equal(...)" because in case of "equal" the element L[l] 1885 *is "older" and has to be from theoretical point of view behind 1886 *L[i], but we do not want to reorder L 1887 */ 1888 strat>L[i].p2 = strat>tail; 1889 /* 1890 *L[l] will be canceled, we cannot cancel L[i] later on, 1891 *so we mark it with "tail" 1892 */ 1893 deleteInL(strat>L,&strat>Ll,l,strat); 1894 i; 1920 1895 } 1921 i; 1922 } 1923 } 1924 else if (strat>L[j].p2 == strat>tail) 1925 { 1926 /*now L[j] cannot be canceled any more and the tail can be removed*/ 1927 strat>L[j].p2 = p; 1928 } 1929 j; 1930 } 1896 else 1897 { 1898 deleteInL(strat>L,&strat>Ll,i,strat); 1899 } 1900 j; 1901 } 1902 i; 1903 } 1904 } 1905 else if (strat>L[j].p2 == strat>tail) 1906 { 1907 /*now L[j] cannot be canceled any more and the tail can be removed*/ 1908 strat>L[j].p2 = p; 1909 } 1910 j; 1931 1911 } 1932 1912 } … … 1986 1966 } 1987 1967 1988 if (new_pair) chainCrit (h,ecart,strat);1968 if (new_pair) chainCritRing(h,ecart,strat); 1989 1969 1990 1970 } … … 4540 4520 } 4541 4521 #endif 4522 #ifdef HAVE_RING2TOM 4523 // Coefficient ring? 4524 if (currRing>cring == 1) 4525 { 4526 strat>sugarCrit = FALSE; 4527 strat>Gebauer = FALSE ; 4528 strat>honey = FALSE; 4529 } 4530 #endif 4542 4531 if (TEST_OPT_DEBUG) 4543 4532 {
Note: See TracChangeset
for help on using the changeset viewer.