[f3a8c2e] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
[341696] | 4 | /* $Id$ */ |
---|
[f3a8c2e] | 5 | /* |
---|
[585bbcb] | 6 | * ABSTRACT: ringgb interface |
---|
[f3a8c2e] | 7 | */ |
---|
[cea6f3] | 8 | //#define HAVE_TAIL_RING |
---|
[585bbcb] | 9 | #define NO_BUCKETS |
---|
| 10 | |
---|
[599326] | 11 | #include <kernel/mod2.h> |
---|
| 12 | #include <kernel/kutil.h> |
---|
| 13 | #include <kernel/structs.h> |
---|
[b1dfaf] | 14 | #include <omalloc/omalloc.h> |
---|
[210e07] | 15 | #include <polys/polys.h> |
---|
| 16 | #include <polys/monomials/p_polys.h> |
---|
[599326] | 17 | #include <kernel/ideals.h> |
---|
| 18 | #include <kernel/febase.h> |
---|
| 19 | #include <kernel/kstd1.h> |
---|
| 20 | #include <kernel/khstd.h> |
---|
[210e07] | 21 | #include <polys/kbuckets.h> |
---|
[76cfef] | 22 | #include <polys/weight.h> |
---|
[210e07] | 23 | #include <misc/intvec.h> |
---|
[eedd22] | 24 | #include <libpolys/polys/polys.h> |
---|
[585bbcb] | 25 | #ifdef HAVE_PLURAL |
---|
[210e07] | 26 | #include <polys/nc/nc.h> |
---|
[585bbcb] | 27 | #endif |
---|
| 28 | |
---|
[599326] | 29 | #include <kernel/ringgb.h> |
---|
[585bbcb] | 30 | |
---|
[c90b43] | 31 | #ifdef HAVE_RINGS |
---|
[fd49e9] | 32 | poly reduce_poly_fct(poly p, ring r) |
---|
| 33 | { |
---|
[a6889e] | 34 | return kFindZeroPoly(p, r, r); |
---|
[585bbcb] | 35 | } |
---|
| 36 | |
---|
| 37 | /* |
---|
| 38 | * Returns maximal k, such that |
---|
| 39 | * 2^k | n |
---|
| 40 | */ |
---|
[c90b43] | 41 | int indexOf2(number n) |
---|
| 42 | { |
---|
[585bbcb] | 43 | long test = (long) n; |
---|
| 44 | int i = 0; |
---|
[c90b43] | 45 | while (test%2 == 0) |
---|
| 46 | { |
---|
[585bbcb] | 47 | i++; |
---|
| 48 | test = test / 2; |
---|
| 49 | } |
---|
| 50 | return i; |
---|
| 51 | } |
---|
| 52 | |
---|
| 53 | /*************************************************************** |
---|
| 54 | * |
---|
| 55 | * Lcm business |
---|
| 56 | * |
---|
| 57 | ***************************************************************/ |
---|
| 58 | // get m1 = LCM(LM(p1), LM(p2))/LM(p1) |
---|
| 59 | // m2 = LCM(LM(p1), LM(p2))/LM(p2) |
---|
| 60 | BOOLEAN ring2toM_GetLeadTerms(const poly p1, const poly p2, const ring p_r, |
---|
| 61 | poly &m1, poly &m2, const ring m_r) |
---|
| 62 | { |
---|
| 63 | int i; |
---|
[0b5e3d] | 64 | int x; |
---|
[585bbcb] | 65 | m1 = p_Init(m_r); |
---|
| 66 | m2 = p_Init(m_r); |
---|
| 67 | |
---|
| 68 | for (i = p_r->N; i; i--) |
---|
| 69 | { |
---|
| 70 | x = p_GetExpDiff(p1, p2, i, p_r); |
---|
| 71 | if (x > 0) |
---|
| 72 | { |
---|
| 73 | p_SetExp(m2,i,x, m_r); |
---|
| 74 | p_SetExp(m1,i,0, m_r); |
---|
| 75 | } |
---|
| 76 | else |
---|
| 77 | { |
---|
| 78 | p_SetExp(m1,i,-x, m_r); |
---|
| 79 | p_SetExp(m2,i,0, m_r); |
---|
| 80 | } |
---|
| 81 | } |
---|
| 82 | p_Setm(m1, m_r); |
---|
| 83 | p_Setm(m2, m_r); |
---|
| 84 | long cp1 = (long) pGetCoeff(p1); |
---|
| 85 | long cp2 = (long) pGetCoeff(p2); |
---|
[c90b43] | 86 | if (cp1 != 0 && cp2 != 0) |
---|
| 87 | { |
---|
| 88 | while (cp1%2 == 0 && cp2%2 == 0) |
---|
| 89 | { |
---|
[585bbcb] | 90 | cp1 = cp1 / 2; |
---|
| 91 | cp2 = cp2 / 2; |
---|
| 92 | } |
---|
| 93 | } |
---|
| 94 | p_SetCoeff(m1, (number) cp2, m_r); |
---|
| 95 | p_SetCoeff(m2, (number) cp1, m_r); |
---|
| 96 | return TRUE; |
---|
| 97 | } |
---|
| 98 | |
---|
[bd9c4a] | 99 | void printPolyMsg(const char * start, poly f, const char * end) |
---|
| 100 | { |
---|
[585bbcb] | 101 | PrintS(start); |
---|
| 102 | wrp(f); |
---|
| 103 | PrintS(end); |
---|
| 104 | } |
---|
| 105 | |
---|
[c90b43] | 106 | poly spolyRing2toM(poly f, poly g, ring r) |
---|
| 107 | { |
---|
[585bbcb] | 108 | poly m1 = NULL; |
---|
| 109 | poly m2 = NULL; |
---|
| 110 | ring2toM_GetLeadTerms(f, g, r, m1, m2, r); |
---|
[a48e19] | 111 | // printPolyMsg("spoly: m1=", m1, " | "); |
---|
| 112 | // printPolyMsg("m2=", m2, ""); |
---|
| 113 | // PrintLn(); |
---|
[8e48589] | 114 | poly sp = pSub(p_Mult_mm(f, m1, r), pp_Mult_mm(g, m2, r)); |
---|
| 115 | pDelete(&m1); |
---|
| 116 | pDelete(&m2); |
---|
| 117 | return(sp); |
---|
[585bbcb] | 118 | } |
---|
| 119 | |
---|
[c90b43] | 120 | poly ringRedNF (poly f, ideal G, ring r) |
---|
| 121 | { |
---|
[585bbcb] | 122 | // If f = 0, then normal form is also 0 |
---|
| 123 | if (f == NULL) { return NULL; } |
---|
| 124 | poly h = NULL; |
---|
| 125 | poly g = pCopy(f); |
---|
| 126 | int c = 0; |
---|
[ca4d0e6] | 127 | while (g != NULL) |
---|
| 128 | { |
---|
[585bbcb] | 129 | Print("%d-step RedNF - g=", c); |
---|
| 130 | wrp(g); |
---|
| 131 | PrintS(" | h="); |
---|
| 132 | wrp(h); |
---|
| 133 | PrintLn(); |
---|
| 134 | g = ringNF(g, G, r); |
---|
| 135 | if (g != NULL) { |
---|
| 136 | h = pAdd(h, pHead(g)); |
---|
| 137 | pLmDelete(&g); |
---|
| 138 | } |
---|
| 139 | c++; |
---|
| 140 | } |
---|
| 141 | return h; |
---|
[f3a8c2e] | 142 | } |
---|
[69bc59] | 143 | |
---|
[206e158] | 144 | #endif |
---|
| 145 | |
---|
| 146 | #ifdef HAVE_RINGS |
---|
| 147 | |
---|
| 148 | /* |
---|
| 149 | * Find an index i from G, such that |
---|
| 150 | * LT(rside) = x * LT(G[i]) has a solution |
---|
| 151 | * or -1 if rside is not in the |
---|
| 152 | * ideal of the leading coefficients |
---|
| 153 | * of the suitable g from G. |
---|
| 154 | */ |
---|
[c90b43] | 155 | int findRingSolver(poly rside, ideal G, ring r) |
---|
| 156 | { |
---|
[206e158] | 157 | if (rside == NULL) return -1; |
---|
| 158 | int i; |
---|
| 159 | // int iO2rside = indexOf2(pGetCoeff(rside)); |
---|
[c90b43] | 160 | for (i = 0; i < IDELEMS(G); i++) |
---|
| 161 | { |
---|
[206e158] | 162 | if // (indexOf2(pGetCoeff(G->m[i])) <= iO2rside && / should not be necessary any more |
---|
[c90b43] | 163 | (p_LmDivisibleBy(G->m[i], rside, r)) |
---|
| 164 | { |
---|
[206e158] | 165 | return i; |
---|
| 166 | } |
---|
| 167 | } |
---|
| 168 | return -1; |
---|
| 169 | } |
---|
| 170 | |
---|
[c90b43] | 171 | poly plain_spoly(poly f, poly g) |
---|
| 172 | { |
---|
[2dc9911] | 173 | number cf = nCopy(pGetCoeff(f)), cg = nCopy(pGetCoeff(g)); |
---|
[1b74f3] | 174 | (void)ksCheckCoeff(&cf, &cg); // gcd and zero divisors |
---|
[206e158] | 175 | poly fm, gm; |
---|
| 176 | k_GetLeadTerms(f, g, currRing, fm, gm, currRing); |
---|
| 177 | pSetCoeff0(fm, cg); |
---|
| 178 | pSetCoeff0(gm, cf); // and now, m1 * LT(p1) == m2 * LT(p2) |
---|
[2dc9911] | 179 | poly sp = pSub(ppMult_mm(f, fm), ppMult_mm(g, gm)); |
---|
[206e158] | 180 | pDelete(&fm); |
---|
| 181 | pDelete(&gm); |
---|
| 182 | return(sp); |
---|
| 183 | } |
---|
| 184 | |
---|
[aef8bb] | 185 | /*2 |
---|
| 186 | * Generates spoly(0, h) if applicable. Assumes ring in Z/2^n. |
---|
| 187 | */ |
---|
| 188 | poly plain_zero_spoly(poly h) |
---|
| 189 | { |
---|
| 190 | poly p = NULL; |
---|
| 191 | number gcd = nGcd((number) 0, pGetCoeff(h), currRing); |
---|
| 192 | if ((NATNUMBER) gcd > 1) |
---|
| 193 | { |
---|
| 194 | p = p_Copy(h->next, currRing); |
---|
| 195 | p = p_Mult_nn(p, nIntDiv(0, gcd), currRing); |
---|
| 196 | } |
---|
| 197 | return p; |
---|
| 198 | } |
---|
| 199 | |
---|
[c90b43] | 200 | poly ringNF(poly f, ideal G, ring r) |
---|
| 201 | { |
---|
[206e158] | 202 | // If f = 0, then normal form is also 0 |
---|
| 203 | if (f == NULL) { return NULL; } |
---|
[aef8bb] | 204 | poly tmp = NULL; |
---|
[206e158] | 205 | poly h = pCopy(f); |
---|
| 206 | int i = findRingSolver(h, G, r); |
---|
| 207 | int c = 1; |
---|
| 208 | while (h != NULL && i >= 0) { |
---|
[2dc9911] | 209 | // Print("%d-step NF - h:", c); |
---|
| 210 | // wrp(h); |
---|
| 211 | // PrintS(" "); |
---|
| 212 | // PrintS("G->m[i]:"); |
---|
| 213 | // wrp(G->m[i]); |
---|
| 214 | // PrintLn(); |
---|
[aef8bb] | 215 | tmp = h; |
---|
[206e158] | 216 | h = plain_spoly(h, G->m[i]); |
---|
[aef8bb] | 217 | pDelete(&tmp); |
---|
[2dc9911] | 218 | // PrintS("=> h="); |
---|
| 219 | // wrp(h); |
---|
| 220 | // PrintLn(); |
---|
[206e158] | 221 | i = findRingSolver(h, G, r); |
---|
| 222 | c++; |
---|
| 223 | } |
---|
| 224 | return h; |
---|
| 225 | } |
---|
| 226 | |
---|
[a2466f] | 227 | int testGB(ideal I, ideal GI) { |
---|
[aef8bb] | 228 | poly f, g, h, nf; |
---|
[69bc59] | 229 | int i = 0; |
---|
| 230 | int j = 0; |
---|
[ca4d0e6] | 231 | PrintS("I included?"); |
---|
[a2466f] | 232 | for (i = 0; i < IDELEMS(I); i++) { |
---|
| 233 | if (ringNF(I->m[i], GI, currRing) != NULL) { |
---|
[ca4d0e6] | 234 | PrintS("Not reduced to zero from I: "); |
---|
[a2466f] | 235 | wrp(I->m[i]); |
---|
[ca4d0e6] | 236 | PrintS(" --> "); |
---|
[a2466f] | 237 | wrp(ringNF(I->m[i], GI, currRing)); |
---|
| 238 | PrintLn(); |
---|
| 239 | return(0); |
---|
| 240 | } |
---|
[ca4d0e6] | 241 | PrintS("-"); |
---|
[a2466f] | 242 | } |
---|
[ca4d0e6] | 243 | PrintS(" Yes!\nspoly --> 0?"); |
---|
| 244 | for (i = 0; i < IDELEMS(GI); i++) |
---|
| 245 | { |
---|
| 246 | for (j = i + 1; j < IDELEMS(GI); j++) |
---|
| 247 | { |
---|
[69bc59] | 248 | f = pCopy(GI->m[i]); |
---|
| 249 | g = pCopy(GI->m[j]); |
---|
| 250 | h = plain_spoly(f, g); |
---|
[aef8bb] | 251 | nf = ringNF(h, GI, currRing); |
---|
[ca4d0e6] | 252 | if (nf != NULL) |
---|
| 253 | { |
---|
| 254 | PrintS("spoly("); |
---|
[69bc59] | 255 | wrp(GI->m[i]); |
---|
[ca4d0e6] | 256 | PrintS(", "); |
---|
[69bc59] | 257 | wrp(GI->m[j]); |
---|
[ca4d0e6] | 258 | PrintS(") = "); |
---|
[69bc59] | 259 | wrp(h); |
---|
[ca4d0e6] | 260 | PrintS(" --> "); |
---|
[aef8bb] | 261 | wrp(nf); |
---|
[69bc59] | 262 | PrintLn(); |
---|
| 263 | return(0); |
---|
| 264 | } |
---|
[aef8bb] | 265 | pDelete(&f); |
---|
| 266 | pDelete(&g); |
---|
[69bc59] | 267 | pDelete(&h); |
---|
[aef8bb] | 268 | pDelete(&nf); |
---|
[ca4d0e6] | 269 | PrintS("-"); |
---|
[69bc59] | 270 | } |
---|
| 271 | } |
---|
[1e579c6] | 272 | if (!(rField_is_Domain())) |
---|
[aef8bb] | 273 | { |
---|
[ca4d0e6] | 274 | PrintS(" Yes!\nzero-spoly --> 0?"); |
---|
[c90b43] | 275 | for (i = 0; i < IDELEMS(GI); i++) |
---|
[1e579c6] | 276 | { |
---|
| 277 | f = plain_zero_spoly(GI->m[i]); |
---|
| 278 | nf = ringNF(f, GI, currRing); |
---|
| 279 | if (nf != NULL) { |
---|
[ca4d0e6] | 280 | PrintS("spoly("); |
---|
[1e579c6] | 281 | wrp(GI->m[i]); |
---|
[ca4d0e6] | 282 | PrintS(", "); |
---|
[1e579c6] | 283 | wrp(0); |
---|
[ca4d0e6] | 284 | PrintS(") = "); |
---|
[1e579c6] | 285 | wrp(h); |
---|
[ca4d0e6] | 286 | PrintS(" --> "); |
---|
[1e579c6] | 287 | wrp(nf); |
---|
| 288 | PrintLn(); |
---|
| 289 | return(0); |
---|
| 290 | } |
---|
| 291 | pDelete(&f); |
---|
| 292 | pDelete(&nf); |
---|
[ca4d0e6] | 293 | PrintS("-"); |
---|
[aef8bb] | 294 | } |
---|
| 295 | } |
---|
[ca4d0e6] | 296 | PrintS(" Yes!"); |
---|
[aef8bb] | 297 | PrintLn(); |
---|
[69bc59] | 298 | return(1); |
---|
| 299 | } |
---|
| 300 | |
---|
[fd49e9] | 301 | #endif |
---|