[2381568] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
| 4 | /*************************************************************** |
---|
| 5 | * File: ratgring.cc |
---|
| 6 | * Purpose: Ore-noncommutative kernel procedures |
---|
| 7 | * Author: levandov (Viktor Levandovsky) |
---|
| 8 | * Created: 8/00 - 11/00 |
---|
[326434] | 9 | * Version: $Id: ratgring.cc,v 1.11 2008-08-07 21:15:56 levandov Exp $ |
---|
[2381568] | 10 | *******************************************************************/ |
---|
| 11 | #include "mod2.h" |
---|
[ac4b53] | 12 | #include "ratgring.h" |
---|
[1bcfc5] | 13 | #ifdef HAVE_RATGRING |
---|
[2381568] | 14 | #include "gring.h" |
---|
| 15 | #include "febase.h" |
---|
| 16 | #include "ring.h" |
---|
| 17 | #include "polys.h" |
---|
| 18 | #include "numbers.h" |
---|
| 19 | #include "ideals.h" |
---|
| 20 | #include "matpol.h" |
---|
| 21 | #include "kbuckets.h" |
---|
| 22 | #include "kstd1.h" |
---|
| 23 | #include "sbuckets.h" |
---|
| 24 | #include "prCopy.h" |
---|
| 25 | #include "p_Mult_q.h" |
---|
| 26 | #include "clapsing.h" |
---|
| 27 | |
---|
| 28 | void pLcmRat(poly a, poly b, poly m, int rat_shift) |
---|
| 29 | { |
---|
[326434] | 30 | /* rat_shift is the last exp one should count with */ |
---|
[2381568] | 31 | int i; |
---|
[326434] | 32 | for (i=pVariables; i>=rat_shift; i--) |
---|
[2381568] | 33 | { |
---|
| 34 | pSetExp(m,i, si_max( pGetExp(a,i), pGetExp(b,i))); |
---|
| 35 | } |
---|
| 36 | pSetComp(m, si_max(pGetComp(a), pGetComp(b))); |
---|
| 37 | /* Don't do a pSetm here, otherwise hres/lres chockes */ |
---|
| 38 | } |
---|
| 39 | |
---|
[cbc372] | 40 | // void pLcmRat(poly a, poly b, poly m, poly pshift) |
---|
| 41 | // { |
---|
| 42 | // /* shift is the exp of rational elements */ |
---|
| 43 | // int i; |
---|
| 44 | // for (i=pVariables; i; i--) |
---|
| 45 | // { |
---|
| 46 | // if (!pGetExp(pshift,i)) |
---|
| 47 | // { |
---|
| 48 | // pSetExp(m,i, si_max( pGetExp(a,i), pGetExp(b,i))); |
---|
| 49 | // } |
---|
| 50 | // else |
---|
| 51 | // { |
---|
| 52 | // /* do we really need it? */ |
---|
| 53 | // pSetExp(m,i,0); |
---|
| 54 | // } |
---|
| 55 | // } |
---|
| 56 | // pSetComp(m, si_max(pGetComp(a), pGetComp(b))); |
---|
| 57 | // /* Don't do a pSetm here, otherwise hres/lres chockes */ |
---|
| 58 | // } |
---|
[2381568] | 59 | |
---|
| 60 | /* returns a subpoly of p, s.t. its monomials have the same D-part */ |
---|
| 61 | |
---|
| 62 | poly p_HeadRat(poly p, int ishift, ring r) |
---|
| 63 | { |
---|
[cbc372] | 64 | poly q = pNext(p); |
---|
[112e09] | 65 | if (q == NULL) return p; |
---|
[2381568] | 66 | poly res = p_Head(p,r); |
---|
[9fb610] | 67 | while ( (q!=NULL) && (p_Comp_k_n(p, q, ishift+1, r))) |
---|
[2381568] | 68 | { |
---|
[cbc372] | 69 | res = p_Add_q(res,p_Head(q,r),r); |
---|
[9fb610] | 70 | q = pNext(q); |
---|
[2381568] | 71 | } |
---|
| 72 | return res; |
---|
| 73 | } |
---|
| 74 | |
---|
[9fb610] | 75 | /* TO TEST!!! */ |
---|
[2381568] | 76 | /* returns x-coeff of p, i.e. a poly in x, s.t. corresponding xd-monomials |
---|
| 77 | have the same D-part */ |
---|
| 78 | |
---|
| 79 | poly p_GetCoeffRat(poly p, int ishift, ring r) |
---|
| 80 | { |
---|
[cbc372] | 81 | poly q = pNext(p); |
---|
[9fb610] | 82 | poly res; // = p_Head(p,r); |
---|
| 83 | res = p_GetExp_k_n(p, ishift+1, r->N, r); |
---|
| 84 | p_SetCoeff(res,n_Copy(p_GetCoeff(p,r),r),r); |
---|
[2381568] | 85 | poly s; |
---|
[9fb610] | 86 | while ((q!= NULL) && (p_Comp_k_n(p, q, ishift+1, r))) |
---|
[2381568] | 87 | { |
---|
[9fb610] | 88 | s = p_GetExp_k_n(q, ishift+1, r->N, r); |
---|
| 89 | p_SetCoeff(s,n_Copy(p_GetCoeff(q,r),r),r); |
---|
[cbc372] | 90 | res = p_Add_q(res,s,r); |
---|
[9fb610] | 91 | q = pNext(q); |
---|
[2381568] | 92 | } |
---|
| 93 | return res; |
---|
| 94 | } |
---|
| 95 | |
---|
[9fb610] | 96 | void p_LmDeleteAndNextRat(poly *p, int ishift, ring r) |
---|
[2381568] | 97 | { |
---|
[cbc372] | 98 | /* modifies p*/ |
---|
[9fb610] | 99 | Print("start: "); Print(" "); p_wrp(*p,r); |
---|
| 100 | p_LmCheckPolyRing2(*p, r); |
---|
| 101 | poly q = p_Head(*p,r); |
---|
| 102 | // in the next line ishift is correct |
---|
| 103 | while ( ( (*p)!=NULL ) && ( p_Comp_k_n(*p, q, ishift, r) )) |
---|
| 104 | { |
---|
| 105 | p_LmDelete(p,r); |
---|
| 106 | Print("while: ");p_wrp(*p,r);Print(" "); |
---|
| 107 | } |
---|
| 108 | p_wrp(*p,r);Print(" "); |
---|
| 109 | PrintS("end\n"); |
---|
| 110 | p_LmDelete(&q,r); |
---|
| 111 | } |
---|
| 112 | |
---|
| 113 | /* to test!!! */ |
---|
| 114 | /* ExpVector(pr) = ExpVector(p1) - ExpVector(p2) */ |
---|
| 115 | void p_ExpVectorDiffRat(poly pr, poly p1, poly p2, int ishift, ring r) |
---|
| 116 | { |
---|
| 117 | p_LmCheckPolyRing1(p1, r); |
---|
| 118 | p_LmCheckPolyRing1(p2, r); |
---|
| 119 | p_LmCheckPolyRing1(pr, r); |
---|
| 120 | int i; |
---|
| 121 | poly t=pr; |
---|
| 122 | Exponent_t e1,e2; |
---|
[326434] | 123 | for (i=ishift+1; i<=r->N; i++) |
---|
[2381568] | 124 | { |
---|
[9fb610] | 125 | e1 = p_GetExp(p1, i, r); |
---|
| 126 | e2 = p_GetExp(p2, i, r); |
---|
| 127 | // pAssume1(p_GetExp(p1, i, r) >= p_GetExp(p2, i, r)); |
---|
| 128 | if (e1 < e2) |
---|
| 129 | { |
---|
| 130 | #ifdef PDEBUG |
---|
| 131 | Print("negative ExpVectorDiff\n"); |
---|
| 132 | #endif |
---|
| 133 | p_Delete(&t,r); |
---|
| 134 | break; |
---|
| 135 | } |
---|
| 136 | else |
---|
| 137 | { |
---|
| 138 | p_SetExp(t,i, e1-e2,r); |
---|
| 139 | } |
---|
[2381568] | 140 | } |
---|
[9fb610] | 141 | p_Setm(t,r); |
---|
[2381568] | 142 | } |
---|
| 143 | |
---|
[cbc372] | 144 | /* returns ideal (u,v) s.t. up + vq = 0 */ |
---|
| 145 | |
---|
[326434] | 146 | ideal ncGCD2(poly p, poly q, const ring r) |
---|
[cbc372] | 147 | { |
---|
| 148 | intvec *w = NULL; |
---|
| 149 | ideal h = idInit(2,1); |
---|
| 150 | h->m[0] = p_Copy(p,r); |
---|
| 151 | h->m[1] = p_Copy(q,r); |
---|
| 152 | #ifdef PDEBUG |
---|
[112e09] | 153 | Print("running syzygy comp. for nc_GCD:\n"); |
---|
[cbc372] | 154 | #endif |
---|
| 155 | ideal sh = idSyzygies(h, testHomog, &w); |
---|
| 156 | #ifdef PDEBUG |
---|
[112e09] | 157 | Print("done syzygy comp. for nc_GCD\n"); |
---|
[cbc372] | 158 | #endif |
---|
| 159 | /* in comm case, there is only 1 syzygy */ |
---|
| 160 | /* singclap_gcd(); */ |
---|
| 161 | poly K, K1, K2; |
---|
| 162 | K = sh->m[0]; /* take just the first element - to be enhanced later */ |
---|
| 163 | K1 = pTakeOutComp(&K, 1); // 1st component is taken out from K |
---|
[9fb610] | 164 | // pShift(&K,-2); // 2nd component to 0th comp. |
---|
| 165 | K2 = pTakeOutComp(&K, 1); |
---|
| 166 | // K2 = K; |
---|
| 167 | |
---|
| 168 | Print("syz1: "); p_wrp(K1,r); |
---|
| 169 | Print("syz2: "); p_wrp(K2,r); |
---|
[cbc372] | 170 | |
---|
| 171 | /* checking signs before multiplying */ |
---|
| 172 | number ck1 = p_GetCoeff(K1,r); |
---|
| 173 | number ck2 = p_GetCoeff(K2,r); |
---|
| 174 | BOOLEAN bck1, bck2; |
---|
| 175 | bck1 = n_GreaterZero(ck1,r); |
---|
| 176 | bck2 = n_GreaterZero(ck2,r); |
---|
| 177 | /* K1 <0, K2 <0 (-K1,-K2) */ |
---|
[9fb610] | 178 | // if ( !(bck1 && bck2) ) /* - , - */ |
---|
| 179 | // { |
---|
| 180 | // K1 = p_Neg(K1,r); |
---|
| 181 | // K2 = p_Neg(K2,r); |
---|
| 182 | // } |
---|
| 183 | id_Delete(&h,r); |
---|
[cbc372] | 184 | h = idInit(2,1); |
---|
[112e09] | 185 | h->m[0] = p_Copy(K1,r); |
---|
| 186 | h->m[1] = p_Copy(K2,r); |
---|
[9fb610] | 187 | id_Delete(&sh,r); |
---|
[cbc372] | 188 | return(h); |
---|
| 189 | } |
---|
| 190 | |
---|
[326434] | 191 | /* returns ideal (u,v) s.t. up + vq = 0 */ |
---|
[cbc372] | 192 | |
---|
[326434] | 193 | ideal ncGCD(poly p, poly q, const ring r) |
---|
| 194 | { |
---|
| 195 | // assume: p,q are in the comm. ring |
---|
| 196 | // to be used in the coeff business |
---|
| 197 | #ifdef PDEBUG |
---|
| 198 | Print("G_start:"); |
---|
| 199 | #endif |
---|
| 200 | poly g = singclap_gcd(p_Copy(p,r),p_Copy(q,r)); |
---|
| 201 | #ifdef PDEBUG |
---|
| 202 | p_wrp(g,r); |
---|
| 203 | Print("G_end;"); |
---|
| 204 | #endif |
---|
| 205 | poly u = singclap_pdivide(q,g); //q/g |
---|
| 206 | poly v = singclap_pdivide(p,g); //p/g |
---|
| 207 | ideal h = idInit(2,1); |
---|
| 208 | h->m[0] = u; // p_Copy(u,r); |
---|
| 209 | h->m[1] = v; // p_Copy(v,r); |
---|
| 210 | return(h); |
---|
| 211 | } |
---|
[cbc372] | 212 | |
---|
[2381568] | 213 | /* PINLINE1 void p_ExpVectorDiff |
---|
| 214 | remains as is -> BUT we can do memory shift on smaller number of exp's */ |
---|
| 215 | |
---|
| 216 | |
---|
| 217 | /*4 - follow the numbering of gring.cc |
---|
| 218 | * creates the S-polynomial of p1 and p2 |
---|
| 219 | * do not destroy p1 and p2 |
---|
| 220 | */ |
---|
[cbc372] | 221 | // poly nc_rat_CreateSpoly(poly p1, poly p2, poly spNoether, int ishift, const ring r) |
---|
| 222 | // { |
---|
| 223 | // if ((p_GetComp(p1,r)!=p_GetComp(p2,r)) |
---|
| 224 | // && (p_GetComp(p1,r)!=0) |
---|
| 225 | // && (p_GetComp(p2,r)!=0)) |
---|
| 226 | // { |
---|
| 227 | // #ifdef PDEBUG |
---|
| 228 | // Print("nc_CreateSpoly : different components!"); |
---|
| 229 | // #endif |
---|
| 230 | // return(NULL); |
---|
| 231 | // } |
---|
| 232 | // /* prod. crit does not apply yet */ |
---|
| 233 | // // if ((r->nc->type==nc_lie) && pHasNotCF(p1,p2)) /* prod crit */ |
---|
| 234 | // // { |
---|
| 235 | // // return(nc_p_Bracket_qq(pCopy(p2),p1)); |
---|
| 236 | // // } |
---|
| 237 | // poly pL=pOne(); |
---|
| 238 | // poly m1=pOne(); |
---|
| 239 | // poly m2=pOne(); |
---|
| 240 | // /* define shift */ |
---|
| 241 | // int is = ishift; /* TODO */ |
---|
| 242 | // pLcmRat(p1,p2,pL,is); |
---|
| 243 | // p_Setm(pL,r); |
---|
| 244 | // poly pr1 = p_GetExp_k_n(p1,1,ishift-1,r); /* rat D-exp of p1 */ |
---|
| 245 | // poly pr2 = p_GetExp_k_n(p2,1,ishift-1,r); /* rat D-exp of p2 */ |
---|
| 246 | // #ifdef PDEBUG |
---|
| 247 | // p_Test(pL,r); |
---|
| 248 | // #endif |
---|
| 249 | // p_ExpVectorDiff(m1,pL,p1,r); /* purely in D part by construction */ |
---|
| 250 | // //p_SetComp(m1,0,r); |
---|
| 251 | // //p_Setm(m1,r); |
---|
| 252 | // #ifdef PDEBUG |
---|
| 253 | // p_Test(m1,r); |
---|
| 254 | // #endif |
---|
| 255 | // p_ExpVectorDiff(m2,pL,p2,r); /* purely in D part by construction */ |
---|
| 256 | // //p_SetComp(m2,0,r); |
---|
| 257 | // //p_Setm(m2,r); |
---|
| 258 | // #ifdef PDEBUG |
---|
| 259 | // p_Test(m2,r); |
---|
| 260 | // #endif |
---|
| 261 | // p_Delete(&pL,r); |
---|
| 262 | // /* zero exponents ! */ |
---|
| 263 | |
---|
| 264 | // /* EXTRACT LEADCOEF */ |
---|
| 265 | |
---|
| 266 | // poly H1 = p_HeadRat(p1,is,r); |
---|
| 267 | // poly M1 = r->nc->p_Procs.mm_Mult_p(m1,p_Copy(H1,r),r); |
---|
| 268 | |
---|
| 269 | // /* POLY: number C1 = n_Copy(p_GetCoeff(M1,r),r); */ |
---|
| 270 | // /* RAT: */ |
---|
| 271 | |
---|
| 272 | // poly C1 = p_GetCoeffRat(M1,ishift,r); |
---|
| 273 | |
---|
| 274 | // poly H2 = p_HeadRat(p2,is,r); |
---|
| 275 | // poly M2 = r->nc->p_Procs.mm_Mult_p(m2,p_Copy(H2,r),r); |
---|
| 276 | |
---|
| 277 | // /* POLY: number C2 = n_Copy(p_GetCoeff(M2,r),r); */ |
---|
| 278 | // /* RAT: */ |
---|
| 279 | |
---|
| 280 | // poly C2 = p_GetCoeffRat(M2,ishift,r); |
---|
| 281 | |
---|
| 282 | // /* we do not assume that X's commute */ |
---|
| 283 | // /* we just run NC syzygies */ |
---|
| 284 | |
---|
| 285 | // /* NEW IDEA: change the ring to K<X>, map things there |
---|
| 286 | // and return the result back; seems to be a good optimization */ |
---|
| 287 | // /* to be done later */ |
---|
| 288 | // /* problem: map to subalgebra. contexts, induced (non-unique) orderings etc. */ |
---|
| 289 | |
---|
| 290 | // intvec *w = NULL; |
---|
| 291 | // ideal h = idInit(2,1); |
---|
| 292 | // h->m[0] = p_Copy(C1,r); |
---|
| 293 | // h->m[1] = p_Copy(C2,r); |
---|
| 294 | // #ifdef PDEBUG |
---|
| 295 | // Print("running syzygy comp. for coeffs"); |
---|
| 296 | // #endif |
---|
| 297 | // ideal sh = idSyzygies(h, testHomog, &w); |
---|
| 298 | // /* in comm case, there is only 1 syzygy */ |
---|
| 299 | // /* singclap_gcd(); */ |
---|
| 300 | // poly K,K1,K2; |
---|
| 301 | // K = sh->m[0]; |
---|
| 302 | // K1 = pTakeOutComp(&K, 1); // 1st component is taken out from K |
---|
| 303 | // pShift(&K,-2); // 2nd component to 0th comp. |
---|
| 304 | // K2 = K; |
---|
| 305 | |
---|
| 306 | // /* checking signs before multiplying */ |
---|
| 307 | // number ck1 = p_GetCoeff(K1,r); |
---|
| 308 | // number ck2 = p_GetCoeff(K2,r); |
---|
| 309 | // BOOLEAN bck1, bck2; |
---|
| 310 | // bck1 = n_GreaterZero(ck1,r); |
---|
| 311 | // bck2 = n_GreaterZero(ck2,r); |
---|
| 312 | // /* K1 >0, K2 >0 (K1,-K2) */ |
---|
| 313 | // /* K1 >0, K2 <0 (K1,-K2) */ |
---|
| 314 | // /* K1 <0, K2 >0 (-K1,K2) */ |
---|
| 315 | // /* K1 <0, K2 <0 (-K1,K2) */ |
---|
| 316 | // if ( (bck1) && (bck2) ) /* +, + */ |
---|
| 317 | // { |
---|
| 318 | // K2 = p_Neg(K2,r); |
---|
| 319 | // } |
---|
| 320 | // if ( (bck1) && (!bck2) ) /* + , - */ |
---|
| 321 | // { |
---|
| 322 | // K2 = p_Neg(K2,r); |
---|
| 323 | // } |
---|
| 324 | // if ( (!bck1) && (bck2) ) /* - , + */ |
---|
| 325 | // { |
---|
| 326 | // K1 = p_Neg(K1,r); |
---|
| 327 | // } |
---|
| 328 | // if ( !(bck1 && bck2) ) /* - , - */ |
---|
| 329 | // { |
---|
| 330 | // K1 = p_Neg(K1,r); |
---|
| 331 | // } |
---|
| 332 | |
---|
| 333 | // poly P1,P2; |
---|
| 334 | |
---|
| 335 | // // p_LmDeleteRat(M1,ishift,r); // get tail(D^(gamma-alpha) * lm(p1)) = h_f |
---|
| 336 | // P1 = p_Copy(p1,r); |
---|
| 337 | // p_LmDeleteAndNextRat(P1,ishift,r); // get tail(p1) = t_f |
---|
| 338 | // P1 = r->nc->p_Procs.mm_Mult_p(m1,P1,r); |
---|
| 339 | // P1 = p_Add_q(P1,M1,r); |
---|
| 340 | |
---|
| 341 | // // p_LmDeleteRat(M2,ishift,r); |
---|
| 342 | // P2 = p_Copy(p2,r); |
---|
| 343 | // p_LmDeleteAndNextRat(P2,ishift,r);// get tail(p2)=t_g |
---|
| 344 | // P2 = r->nc->p_Procs.mm_Mult_p(m2,P2,r); |
---|
| 345 | // P2 = p_Add_q(P2,M2,r); |
---|
| 346 | |
---|
| 347 | // /* coeff business */ |
---|
| 348 | |
---|
| 349 | // P1 = p_Mult_q(P1,K1,r); |
---|
| 350 | // P2 = p_Mult_q(P2,K2,r); |
---|
| 351 | // P1 = p_Add_q(P1,P2,r); |
---|
| 352 | |
---|
| 353 | // /* cleaning up */ |
---|
| 354 | |
---|
| 355 | // #ifdef PDEBUG |
---|
| 356 | // p_Test(p1,r); |
---|
| 357 | // #endif |
---|
| 358 | // /* questionable: */ |
---|
| 359 | // if (P1!=NULL) pCleardenom(P1); |
---|
| 360 | // if (P1!=NULL) pContent(P1); |
---|
| 361 | // return(P1); |
---|
| 362 | // } |
---|
| 363 | |
---|
| 364 | /*2 |
---|
| 365 | * reduction of p2 with p1 |
---|
| 366 | * do not destroy p1, but p2 |
---|
| 367 | * p1 divides p2 -> for use in NF algorithm |
---|
| 368 | * works in an integer fashion |
---|
| 369 | */ |
---|
| 370 | |
---|
| 371 | poly nc_rat_ReduceSpolyNew(const poly p1, poly p2, int ishift, const ring r) |
---|
[2381568] | 372 | { |
---|
[cbc372] | 373 | const long lCompP1 = p_GetComp(p1,r); |
---|
| 374 | const long lCompP2 = p_GetComp(p2,r); |
---|
| 375 | |
---|
| 376 | if ((lCompP1!=lCompP2) && (lCompP1!=0) && (lCompP2!=0)) |
---|
[2381568] | 377 | { |
---|
| 378 | #ifdef PDEBUG |
---|
[cbc372] | 379 | Werror("nc_rat_ReduceSpolyNew: different non-zero components!"); |
---|
[2381568] | 380 | #endif |
---|
| 381 | return(NULL); |
---|
| 382 | } |
---|
[cbc372] | 383 | |
---|
[2381568] | 384 | int is = ishift; /* TODO */ |
---|
[cbc372] | 385 | |
---|
[9fb610] | 386 | poly m = pOne(); |
---|
[326434] | 387 | p_ExpVectorDiffRat(m, p1, p2, ishift, r); // includes X and D parts |
---|
[cbc372] | 388 | //p_Setm(m,r); |
---|
[9fb610] | 389 | // m = p_GetExp_k_n(m,1,ishift,r); /* rat D-exp of m */ |
---|
[2381568] | 390 | #ifdef PDEBUG |
---|
[cbc372] | 391 | p_Test(m,r); |
---|
[2381568] | 392 | #endif |
---|
| 393 | |
---|
[cbc372] | 394 | /* pSetComp(m,r)=0? */ |
---|
[9fb610] | 395 | poly HH = NULL; |
---|
| 396 | poly H = NULL; |
---|
[112e09] | 397 | HH = p_Copy(p_HeadRat(p1,is,r),r); // lm_D(g) |
---|
[52e2f6] | 398 | // H = r->nc->p_Procs.mm_Mult_p(m, p_Copy(HH, r), r); // d^aplha lm_D(g) |
---|
[326434] | 399 | H = nc_mm_Mult_pp(m, HH, r); // d^aplha lm_D(g) == h_g in the paper |
---|
[2381568] | 400 | |
---|
[326434] | 401 | poly K = p_Copy( p_GetCoeffRat(H, is, r), r); // k in the paper |
---|
[583146c] | 402 | Print("k: "); p_wrp(K,r); PrintS("\n"); |
---|
[326434] | 403 | poly P = p_Copy( p_GetCoeffRat(p2, is, r), r); // lc_D(p_2) == lc_D(f) |
---|
[583146c] | 404 | Print("p: "); p_wrp(P,r); PrintS("\n"); |
---|
[2381568] | 405 | |
---|
[9fb610] | 406 | // HH = p_Neg(HH, r); |
---|
| 407 | // poly out = NULL; |
---|
| 408 | // out = p_Add_q(p_Copy(p1,r), HH, r); // out == t_g |
---|
| 409 | |
---|
[583146c] | 410 | Print("f: "); p_wrp(p2,r); PrintS("\n"); |
---|
| 411 | Print("g: "); p_wrp(p1,r); PrintS("\n"); |
---|
[2381568] | 412 | |
---|
[cbc372] | 413 | // alt: |
---|
[9fb610] | 414 | poly out = p1; //p_Copy(p1,r); |
---|
| 415 | p_LmDeleteAndNextRat(&out, is+1, r); // out == t_g |
---|
| 416 | |
---|
| 417 | Print("t_g: "); p_wrp(out,r); |
---|
[2381568] | 418 | |
---|
[cbc372] | 419 | ideal ncsyz = ncGCD(P,K,r); |
---|
[112e09] | 420 | poly KK = p_Copy(ncsyz->m[0],r); // k' |
---|
| 421 | poly PP = p_Copy(ncsyz->m[1],r); // p' |
---|
[cbc372] | 422 | |
---|
[9fb610] | 423 | // HH = p_Copy(p_HeadRat(p2,is,r),r); |
---|
| 424 | // HH = p_Neg(HH, r); |
---|
| 425 | // p2 = p_Add_q(p2, HH, r); // t_f |
---|
[2381568] | 426 | |
---|
[cbc372] | 427 | // alt: |
---|
[9fb610] | 428 | p_LmDeleteAndNextRat(&p2, is+1, r); // t_f |
---|
[2381568] | 429 | |
---|
[9fb610] | 430 | Print("t_f: "); p_wrp(p2,r); |
---|
[2381568] | 431 | |
---|
[9fb610] | 432 | // HH = p_Copy(p_HeadRat(H,is,r),r); |
---|
| 433 | // HH = p_Neg(HH, r); |
---|
| 434 | // H = p_Add_q(H, HH, r); // r_g |
---|
[2381568] | 435 | |
---|
[cbc372] | 436 | // alt: |
---|
[9fb610] | 437 | p_LmDeleteAndNextRat(&H, is+1, r); // r_g |
---|
[2381568] | 438 | |
---|
[9fb610] | 439 | Print("r_g: "); p_wrp(H,r); |
---|
[2381568] | 440 | |
---|
[9fb610] | 441 | p2 = p_Mult_q(KK, p2, r); // p2 = k' t_f |
---|
[cbc372] | 442 | p_Test(p2,r); |
---|
[112e09] | 443 | // p_Delete(&KK,r); |
---|
[2381568] | 444 | |
---|
[9fb610] | 445 | Print("k' t_f: "); p_wrp(p2,r); |
---|
| 446 | |
---|
[52e2f6] | 447 | // out = r->nc->p_Procs.mm_Mult_p(m, out, r); // d^aplha t_g |
---|
| 448 | out = nc_mm_Mult_p(m, out, r); // d^aplha t_g |
---|
| 449 | |
---|
[cbc372] | 450 | p_Delete(&m,r); |
---|
[2381568] | 451 | |
---|
[9fb610] | 452 | Print("d^a t_g: "); p_wrp(out,r); |
---|
[326434] | 453 | Print(" end reduction\n"); |
---|
| 454 | out = p_Add_q(H, out, r); // r_g + d^a t_g |
---|
[cbc372] | 455 | p_Test(out,r); |
---|
[326434] | 456 | out = p_Mult_q(PP, out, r); // c' (r_g + d^a t_g) |
---|
[2381568] | 457 | |
---|
[326434] | 458 | out = p_Add_q(p2,out,r); // delete out, p2; // the sum |
---|
[cbc372] | 459 | p_Test(out,r); |
---|
| 460 | if ( out!=NULL ) pContent(out); |
---|
| 461 | return(out); |
---|
| 462 | } |
---|
[2381568] | 463 | |
---|
[532688] | 464 | // return: FALSE, if there exists i in ishift..r->N, |
---|
| 465 | // such that a->exp[i] > b->exp[i] |
---|
| 466 | // TRUE, otherwise |
---|
| 467 | |
---|
| 468 | BOOLEAN p_DivisibleByRat(poly a, poly b, int ishift, const ring r) |
---|
| 469 | { |
---|
| 470 | int i; |
---|
| 471 | for(i=r->N;i>ishift;i--) |
---|
| 472 | { |
---|
| 473 | if (p_GetExp(a,i,r) > p_GetExp(b,i,r)) return FALSE; |
---|
| 474 | } |
---|
| 475 | return ((p_GetComp(a,r)==p_GetComp(b,r)) || (p_GetComp(a,r)==0)); |
---|
| 476 | } |
---|
| 477 | /*2 |
---|
| 478 | *reduces h with elements from reducer choosing the best possible |
---|
| 479 | * element in t with respect to the given red_length |
---|
| 480 | * arrays reducer and red_length are [0..(rl-1)] |
---|
| 481 | */ |
---|
[9fb610] | 482 | int redRat (poly* h, poly *reducer, int *red_length, int rl, int ishift, ring r) |
---|
[532688] | 483 | { |
---|
[fb6d7b] | 484 | if ((*h)==NULL) return 0; |
---|
[532688] | 485 | |
---|
| 486 | int j,i,l; |
---|
| 487 | |
---|
| 488 | loop |
---|
| 489 | { |
---|
| 490 | j=rl;l=MAX_INT_VAL; |
---|
| 491 | for(i=rl-1;i>=0;i--) |
---|
| 492 | { |
---|
[fb6d7b] | 493 | if ((l>red_length[i]) && (p_DivisibleByRat(reducer[i],*h,ishift,r))) |
---|
[532688] | 494 | { |
---|
| 495 | j=i; l=red_length[i]; |
---|
| 496 | } |
---|
| 497 | } |
---|
| 498 | if (j >=rl) |
---|
| 499 | { |
---|
| 500 | return 1; // not reducible |
---|
| 501 | } |
---|
| 502 | |
---|
| 503 | if (TEST_OPT_DEBUG) |
---|
| 504 | { |
---|
| 505 | PrintS("reduce "); |
---|
[fb6d7b] | 506 | p_wrp(*h,r); |
---|
[532688] | 507 | PrintS(" with "); |
---|
| 508 | p_wrp(reducer[j],r); |
---|
| 509 | } |
---|
[9fb610] | 510 | poly hh=nc_rat_ReduceSpolyNew(reducer[j], *h, ishift, r); |
---|
| 511 | // p_Delete(h,r); |
---|
| 512 | *h=hh; |
---|
[532688] | 513 | if (TEST_OPT_DEBUG) |
---|
| 514 | { |
---|
| 515 | PrintS(" to "); |
---|
[fb6d7b] | 516 | p_wrp(*h,r); |
---|
[532688] | 517 | PrintLn(); |
---|
| 518 | } |
---|
[fb6d7b] | 519 | if ((*h)==NULL) |
---|
[532688] | 520 | { |
---|
| 521 | return 0; |
---|
| 522 | } |
---|
| 523 | } |
---|
| 524 | } |
---|
[2381568] | 525 | #endif |
---|