sca.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /***************************************************************
5  * File: sca.cc
6  * Purpose: supercommutative kernel procedures
7  * Author: motsak (Oleksandr Motsak)
8  * Created: 2006/12/18
9  *******************************************************************/
10 
11 // set it here if needed.
12 #define OUTPUT 0
13 #define MYTEST 0
14 
15 #if MYTEST
16 #define OM_CHECK 4
17 #define OM_TRACK 5
18 #endif
19 
20 // #define PDEBUG 2
21 
22 
23 
24 #include <misc/auxiliary.h>
25 
26 #ifdef HAVE_PLURAL
27 
28 // for
29 #define PLURAL_INTERNAL_DECLARATIONS
30 
31 #include <polys/nc/sca.h>
32 #include <polys/nc/nc.h>
33 #include <polys/nc/gb_hack.h>
34 // #include <polys/gring.h>
35 
36 
37 #include <coeffs/numbers.h>
38 #include <polys/coeffrings.h>
39 
40 
41 // #include <polys/febase.h>
42 #include <misc/options.h>
43 
45 
46 // #include <polys/kutil.h>
47 #include <polys/simpleideals.h>
48 #include <misc/intvec.h>
49 
50 #include <polys/monomials/ring.h>
51 #include <polys/kbuckets.h>
52 // #include <polys/kstd1.h>
53 #include <polys/sbuckets.h>
54 
55 #include <polys/prCopy.h>
56 
59 
60 // #include <polys/kutil.h>
61 // #include <polys/kstd1.h>
62 
63 #include <polys/weight.h>
64 
65 
66 // poly functions defined in p_Procs :
67 
68 // return pPoly * pMonom; preserve pPoly and pMonom.
69 poly sca_pp_Mult_mm(const poly pPoly, const poly pMonom, const ring rRing, poly &);
70 
71 // return pMonom * pPoly; preserve pPoly and pMonom.
72 static poly sca_mm_Mult_pp(const poly pMonom, const poly pPoly, const ring rRing);
73 
74 // return pPoly * pMonom; preserve pMonom, destroy or reuse pPoly.
75 poly sca_p_Mult_mm(poly pPoly, const poly pMonom, const ring rRing);
76 
77 // return pMonom * pPoly; preserve pMonom, destroy or reuse pPoly.
78 static poly sca_mm_Mult_p(const poly pMonom, poly pPoly, const ring rRing);
79 
80 
81 // compute the spolynomial of p1 and p2
82 poly sca_SPoly(const poly p1, const poly p2, const ring r);
83 poly sca_ReduceSpoly(const poly p1, poly p2, const ring r);
84 
85 
86 ////////////////////////////////////////////////////////////////////////////////////////////////////
87 // Super Commutative Algebra extension by Oleksandr
88 ////////////////////////////////////////////////////////////////////////////////////////////////////
89 
90 // returns the sign of: lm(pMonomM) * lm(pMonomMM),
91 // preserves input, may return +/-1, 0
92 static inline int sca_Sign_mm_Mult_mm( const poly pMonomM, const poly pMonomMM, const ring rRing )
93 {
94 #ifdef PDEBUG
95  p_Test(pMonomM, rRing);
96  p_Test(pMonomMM, rRing);
97 #endif
98 
99  const short iFirstAltVar = scaFirstAltVar(rRing);
100  const short iLastAltVar = scaLastAltVar(rRing);
101 
102  register unsigned int tpower = 0;
103  register unsigned int cpower = 0;
104 
105  for( register short j = iLastAltVar; j >= iFirstAltVar; j-- )
106  {
107  const unsigned int iExpM = p_GetExp(pMonomM, j, rRing);
108  const unsigned int iExpMM = p_GetExp(pMonomMM, j, rRing);
109 
110 #ifdef PDEBUG
111  assume( iExpM <= 1);
112  assume( iExpMM <= 1);
113 #endif
114 
115  if( iExpMM != 0 ) // TODO: think about eliminating there if-s...
116  {
117  if( iExpM != 0 )
118  {
119  return 0; // lm(pMonomM) * lm(pMonomMM) == 0
120  }
121  tpower ^= cpower; // compute degree of (-1).
122  }
123  cpower ^= iExpM;
124  }
125 
126 #ifdef PDEBUG
127  assume(tpower <= 1);
128 #endif
129 
130  // 1 => -1 // degree is odd => negate coeff.
131  // 0 => 1
132 
133  return(1 - (tpower << 1) );
134 }
135 
136 
137 
138 
139 // returns and changes pMonomM: lt(pMonomM) = lt(pMonomM) * lt(pMonomMM),
140 // preserves pMonomMM. may return NULL!
141 // if result != NULL => next(result) = next(pMonomM), lt(result) = lt(pMonomM) * lt(pMonomMM)
142 // if result == NULL => pMonomM MUST BE deleted manually!
143 static inline poly sca_m_Mult_mm( poly pMonomM, const poly pMonomMM, const ring rRing )
144 {
145 #ifdef PDEBUG
146  p_Test(pMonomM, rRing);
147  p_Test(pMonomMM, rRing);
148 #endif
149 
150  const unsigned int iFirstAltVar = scaFirstAltVar(rRing);
151  const unsigned int iLastAltVar = scaLastAltVar(rRing);
152 
153  register unsigned int tpower = 0;
154  register unsigned int cpower = 0;
155 
156  for( register unsigned int j = iLastAltVar; j >= iFirstAltVar; j-- )
157  {
158  const unsigned int iExpM = p_GetExp(pMonomM, j, rRing);
159  const unsigned int iExpMM = p_GetExp(pMonomMM, j, rRing);
160 
161 #ifdef PDEBUG
162  assume( iExpM <= 1);
163  assume( iExpMM <= 1);
164 #endif
165 
166  if( iExpMM != 0 )
167  {
168  if( iExpM != 0 ) // result is zero!
169  {
170  return NULL; // we do nothing with pMonomM in this case!
171  }
172 
173  tpower ^= cpower; // compute degree of (-1).
174  }
175 
176  cpower ^= iExpM;
177  }
178 
179 #ifdef PDEBUG
180  assume(tpower <= 1);
181 #endif
182 
183  p_ExpVectorAdd(pMonomM, pMonomMM, rRing); // "exponents" are additive!!!
184 
185  number nCoeffM = p_GetCoeff(pMonomM, rRing); // no new copy! should be deleted!
186 
187  if( (tpower) != 0 ) // degree is odd => negate coeff.
188  nCoeffM = n_InpNeg(nCoeffM, rRing); // negate nCoeff (will destroy the original number)
189 
190  const number nCoeffMM = p_GetCoeff(pMonomMM, rRing); // no new copy!
191 
192  number nCoeff = n_Mult(nCoeffM, nCoeffMM, rRing); // new number!
193 
194  p_SetCoeff(pMonomM, nCoeff, rRing); // delete lc(pMonomM) and set lc(pMonomM) = nCoeff
195 
196 #ifdef PDEBUG
197  p_LmTest(pMonomM, rRing);
198 #endif
199 
200  return(pMonomM);
201 }
202 
203 // returns and changes pMonomM: lt(pMonomM) = lt(pMonomMM) * lt(pMonomM),
204 // preserves pMonomMM. may return NULL!
205 // if result != NULL => next(result) = next(pMonomM), lt(result) = lt(pMonomMM) * lt(pMonomM)
206 // if result == NULL => pMonomM MUST BE deleted manually!
207 static inline poly sca_mm_Mult_m( const poly pMonomMM, poly pMonomM, const ring rRing )
208 {
209 #ifdef PDEBUG
210  p_Test(pMonomM, rRing);
211  p_Test(pMonomMM, rRing);
212 #endif
213 
214  const unsigned int iFirstAltVar = scaFirstAltVar(rRing);
215  const unsigned int iLastAltVar = scaLastAltVar(rRing);
216 
217  register unsigned int tpower = 0;
218  register unsigned int cpower = 0;
219 
220  for( register unsigned int j = iLastAltVar; j >= iFirstAltVar; j-- )
221  {
222  const unsigned int iExpMM = p_GetExp(pMonomMM, j, rRing);
223  const unsigned int iExpM = p_GetExp(pMonomM, j, rRing);
224 
225 #ifdef PDEBUG
226  assume( iExpM <= 1);
227  assume( iExpMM <= 1);
228 #endif
229 
230  if( iExpM != 0 )
231  {
232  if( iExpMM != 0 ) // result is zero!
233  {
234  return NULL; // we do nothing with pMonomM in this case!
235  }
236 
237  tpower ^= cpower; // compute degree of (-1).
238  }
239 
240  cpower ^= iExpMM;
241  }
242 
243 #ifdef PDEBUG
244  assume(tpower <= 1);
245 #endif
246 
247  p_ExpVectorAdd(pMonomM, pMonomMM, rRing); // "exponents" are additive!!!
248 
249  number nCoeffM = p_GetCoeff(pMonomM, rRing); // no new copy! should be deleted!
250 
251  if( (tpower) != 0 ) // degree is odd => negate coeff.
252  nCoeffM = n_InpNeg(nCoeffM, rRing); // negate nCoeff (will destroy the original number), creates new number!
253 
254  const number nCoeffMM = p_GetCoeff(pMonomMM, rRing); // no new copy!
255 
256  number nCoeff = n_Mult(nCoeffM, nCoeffMM, rRing); // new number!
257 
258  p_SetCoeff(pMonomM, nCoeff, rRing); // delete lc(pMonomM) and set lc(pMonomM) = nCoeff
259 
260 #ifdef PDEBUG
261  p_LmTest(pMonomM, rRing);
262 #endif
263 
264  return(pMonomM);
265 }
266 
267 
268 
269 // returns: result = lt(pMonom1) * lt(pMonom2),
270 // preserves pMonom1, pMonom2. may return NULL!
271 // if result != NULL => next(result) = NULL, lt(result) = lt(pMonom1) * lt(pMonom2)
272 static inline poly sca_mm_Mult_mm( poly pMonom1, const poly pMonom2, const ring rRing )
273 {
274 #ifdef PDEBUG
275  p_Test(pMonom1, rRing);
276  p_Test(pMonom2, rRing);
277 #endif
278 
279  const unsigned int iFirstAltVar = scaFirstAltVar(rRing);
280  const unsigned int iLastAltVar = scaLastAltVar(rRing);
281 
282  register unsigned int tpower = 0;
283  register unsigned int cpower = 0;
284 
285  for( register unsigned int j = iLastAltVar; j >= iFirstAltVar; j-- )
286  {
287  const unsigned int iExp1 = p_GetExp(pMonom1, j, rRing);
288  const unsigned int iExp2 = p_GetExp(pMonom2, j, rRing);
289 
290 #ifdef PDEBUG
291  assume( iExp1 <= 1);
292  assume( iExp2 <= 1);
293 #endif
294 
295  if( iExp2 != 0 )
296  {
297  if( iExp1 != 0 ) // result is zero!
298  {
299  return NULL;
300  }
301  tpower ^= cpower; // compute degree of (-1).
302  }
303  cpower ^= iExp1;
304  }
305 
306 #ifdef PDEBUG
307  assume(cpower <= 1);
308 #endif
309 
310  poly pResult;
311  p_AllocBin(pResult,rRing->PolyBin,rRing);
312 
313  p_ExpVectorSum(pResult, pMonom1, pMonom2, rRing); // "exponents" are additive!!!
314 
315  pNext(pResult) = NULL;
316 
317  const number nCoeff1 = p_GetCoeff(pMonom1, rRing); // no new copy!
318  const number nCoeff2 = p_GetCoeff(pMonom2, rRing); // no new copy!
319 
320  number nCoeff = n_Mult(nCoeff1, nCoeff2, rRing); // new number!
321 
322  if( (tpower) != 0 ) // degree is odd => negate coeff.
323  nCoeff = n_InpNeg(nCoeff, rRing); // negate nCoeff (will destroy the original number)
324 
325  p_SetCoeff0(pResult, nCoeff, rRing); // set lc(pResult) = nCoeff, no destruction!
326 
327 #ifdef PDEBUG
328  p_LmTest(pResult, rRing);
329 #endif
330 
331  return(pResult);
332 }
333 
334 // returns: result = x_i * lt(pMonom),
335 // preserves pMonom. may return NULL!
336 // if result != NULL => next(result) = NULL, lt(result) = x_i * lt(pMonom)
337 static inline poly sca_xi_Mult_mm(short i, const poly pMonom, const ring rRing)
338 {
339 #ifdef PDEBUG
340  p_Test(pMonom, rRing);
341 #endif
342 
343  assume( i <= scaLastAltVar(rRing));
344  assume( scaFirstAltVar(rRing) <= i );
345 
346  if( p_GetExp(pMonom, i, rRing) != 0 ) // => result is zero!
347  return NULL;
348 
349  const short iFirstAltVar = scaFirstAltVar(rRing);
350 
351  register unsigned int cpower = 0;
352 
353  for( register short j = iFirstAltVar; j < i ; j++ )
354  cpower ^= p_GetExp(pMonom, j, rRing);
355 
356 #ifdef PDEBUG
357  assume(cpower <= 1);
358 #endif
359 
360  poly pResult = p_LmInit(pMonom, rRing);
361 
362  p_SetExp(pResult, i, 1, rRing); // pResult*=X_i &&
363  p_Setm(pResult, rRing); // addjust degree after previous step!
364 
365  number nCoeff = n_Copy(p_GetCoeff(pMonom, rRing), rRing); // new number!
366 
367  if( cpower != 0 ) // degree is odd => negate coeff.
368  nCoeff = n_InpNeg(nCoeff, rRing); // negate nCoeff (will destroy the original number)
369 
370  p_SetCoeff0(pResult, nCoeff, rRing); // set lc(pResult) = nCoeff, no destruction!
371 
372 #ifdef PDEBUG
373  p_LmTest(pResult, rRing);
374 #endif
375 
376  return(pResult);
377 }
378 
379 //-----------------------------------------------------------------------------------//
380 
381 // return poly = pPoly * pMonom; preserve pMonom, destroy or reuse pPoly.
382 poly sca_p_Mult_mm(poly pPoly, const poly pMonom, const ring rRing)
383 {
384  assume( rIsSCA(rRing) );
385 
386 #ifdef PDEBUG
387 // Print("sca_p_Mult_mm\n"); // !
388 
389  p_Test(pPoly, rRing);
390  p_Test(pMonom, rRing);
391 #endif
392 
393  if( pPoly == NULL )
394  return NULL;
395 
396  assume(pMonom !=NULL);
397  //if( pMonom == NULL )
398  //{
399  // // pPoly != NULL =>
400  // p_Delete( &pPoly, rRing );
401  // return NULL;
402  //}
403 
404  const int iComponentMonomM = p_GetComp(pMonom, rRing);
405 
406  poly p = pPoly; poly* ppPrev = &pPoly;
407 
408  loop
409  {
410 #ifdef PDEBUG
411  p_Test(p, rRing);
412 #endif
413  const int iComponent = p_GetComp(p, rRing);
414 
415  if( iComponent!=0 )
416  {
417  if( iComponentMonomM!=0 ) // TODO: make global if on iComponentMonomM =?= 0
418  {
419  // REPORT_ERROR
420  Werror("sca_p_Mult_mm: exponent mismatch %d and %d\n", iComponent, iComponentMonomM);
421  // what should we do further?!?
422 
423  p_Delete( &pPoly, rRing); // delete the result AND rest
424  return NULL;
425  }
426 #ifdef PDEBUG
427  if(iComponentMonomM==0 )
428  {
429  dReportError("sca_p_Mult_mm: Multiplication in the left module from the right");
430  }
431 #endif
432  }
433 
434  // terms will be in the same order because of quasi-ordering!
435  poly v = sca_m_Mult_mm(p, pMonom, rRing);
436 
437  if( v != NULL )
438  {
439  ppPrev = &pNext(p); // fixed!
440 
441  // *p is changed if v != NULL ( p == v )
442  pIter(p);
443 
444  if( p == NULL )
445  break;
446  }
447  else
448  { // Upps! Zero!!! we must kill this term!
449 
450  //
451  p = p_LmDeleteAndNext(p, rRing);
452 
453  *ppPrev = p;
454 
455  if( p == NULL )
456  break;
457  }
458  }
459 
460 #ifdef PDEBUG
461  p_Test(pPoly,rRing);
462 #endif
463 
464  return(pPoly);
465 }
466 
467 // return new poly = pPoly * pMonom; preserve pPoly and pMonom.
468 poly sca_pp_Mult_mm(const poly pPoly, const poly pMonom, const ring rRing)
469 {
470  assume( rIsSCA(rRing) );
471 
472 #ifdef PDEBUG
473 // Print("sca_pp_Mult_mm\n"); // !
474 
475  p_Test(pPoly, rRing);
476  p_Test(pMonom, rRing);
477 #endif
478 
479  if (/*(*/ pPoly == NULL /*)*/) /*|| ( pMonom == NULL )*/
480  return NULL;
481 
482  const int iComponentMonomM = p_GetComp(pMonom, rRing);
483 
484  poly pResult = NULL;
485  poly* ppPrev = &pResult;
486 
487  for( poly p = pPoly; p!= NULL; pIter(p) )
488  {
489 #ifdef PDEBUG
490  p_Test(p, rRing);
491 #endif
492  const int iComponent = p_GetComp(p, rRing);
493 
494  if( iComponent!=0 )
495  {
496  if( iComponentMonomM!=0 ) // TODO: make global if on iComponentMonomM =?= 0
497  {
498  // REPORT_ERROR
499  Werror("sca_pp_Mult_mm: exponent mismatch %d and %d\n", iComponent, iComponentMonomM);
500  // what should we do further?!?
501 
502  p_Delete( &pResult, rRing); // delete the result
503  return NULL;
504  }
505 
506 #ifdef PDEBUG
507  if(iComponentMonomM==0 )
508  {
509  dReportError("sca_pp_Mult_mm: Multiplication in the left module from the right");
510  }
511 #endif
512  }
513 
514  // terms will be in the same order because of quasi-ordering!
515  poly v = sca_mm_Mult_mm(p, pMonom, rRing);
516 
517  if( v != NULL )
518  {
519  *ppPrev = v;
520  ppPrev = &pNext(v);
521  }
522  }
523 
524 #ifdef PDEBUG
525  p_Test(pResult,rRing);
526 #endif
527 
528  return(pResult);
529 }
530 
531 //-----------------------------------------------------------------------------------//
532 
533 // return x_i * pPoly; preserve pPoly.
534 static inline poly sca_xi_Mult_pp(short i, const poly pPoly, const ring rRing)
535 {
536  assume( rIsSCA(rRing) );
537 
538 #ifdef PDEBUG
539  p_Test(pPoly, rRing);
540 #endif
541 
542  assume(i <= scaLastAltVar(rRing));
543  assume(scaFirstAltVar(rRing) <= i);
544 
545  if( pPoly == NULL )
546  return NULL;
547 
548  poly pResult = NULL;
549  poly* ppPrev = &pResult;
550 
551  for( poly p = pPoly; p!= NULL; pIter(p) )
552  {
553 
554  // terms will be in the same order because of quasi-ordering!
555  poly v = sca_xi_Mult_mm(i, p, rRing);
556 
557 #ifdef PDEBUG
558  p_Test(v, rRing);
559 #endif
560 
561  if( v != NULL )
562  {
563  *ppPrev = v;
564  ppPrev = &pNext(*ppPrev);
565  }
566  }
567 
568 
569 #ifdef PDEBUG
570  p_Test(pResult, rRing);
571 #endif
572 
573  return(pResult);
574 }
575 
576 
577 // return new poly = pMonom * pPoly; preserve pPoly and pMonom.
578 static poly sca_mm_Mult_pp(const poly pMonom, const poly pPoly, const ring rRing)
579 {
580  assume( rIsSCA(rRing) );
581 
582 #ifdef PDEBUG
583 // Print("sca_mm_Mult_pp\n"); // !
584 
585  p_Test(pPoly, rRing);
586  p_Test(pMonom, rRing);
587 #endif
588 
589  if ((pPoly==NULL) || (pMonom==NULL)) return NULL;
590 
591  assume( (pPoly != NULL) && (pMonom !=NULL));
592 
593  const int iComponentMonomM = p_GetComp(pMonom, rRing);
594 
595  poly pResult = NULL;
596  poly* ppPrev = &pResult;
597 
598  for( poly p = pPoly; p!= NULL; pIter(p) )
599  {
600 #ifdef PDEBUG
601  p_Test(p, rRing);
602 #endif
603  const int iComponent = p_GetComp(p, rRing);
604 
605  if( iComponentMonomM!=0 )
606  {
607  if( iComponent!=0 ) // TODO: make global if on iComponentMonomM =?= 0
608  {
609  // REPORT_ERROR
610  Werror("sca_mm_Mult_pp: exponent mismatch %d and %d\n", iComponent, iComponentMonomM);
611  // what should we do further?!?
612 
613  p_Delete( &pResult, rRing); // delete the result
614  return NULL;
615  }
616 #ifdef PDEBUG
617  if(iComponent==0 )
618  {
619  dReportError("sca_mm_Mult_pp: Multiplication in the left module from the right!");
620 // PrintS("mm = "); p_Write(pMonom, rRing);
621 // PrintS("pp = "); p_Write(pPoly, rRing);
622 // assume(iComponent!=0);
623  }
624 #endif
625  }
626 
627  // terms will be in the same order because of quasi-ordering!
628  poly v = sca_mm_Mult_mm(pMonom, p, rRing);
629 
630  if( v != NULL )
631  {
632  *ppPrev = v;
633  ppPrev = &pNext(*ppPrev); // nice line ;-)
634  }
635  }
636 
637 #ifdef PDEBUG
638  p_Test(pResult,rRing);
639 #endif
640 
641  return(pResult);
642 }
643 
644 
645 // return poly = pMonom * pPoly; preserve pMonom, destroy or reuse pPoly.
646 static poly sca_mm_Mult_p(const poly pMonom, poly pPoly, const ring rRing) // !!!!! the MOST used procedure !!!!!
647 {
648  assume( rIsSCA(rRing) );
649 
650 #ifdef PDEBUG
651  p_Test(pPoly, rRing);
652  p_Test(pMonom, rRing);
653 #endif
654 
655  if( pPoly == NULL )
656  return NULL;
657 
658  assume(pMonom!=NULL);
659  //if( pMonom == NULL )
660  //{
661  // // pPoly != NULL =>
662  // p_Delete( &pPoly, rRing );
663  // return NULL;
664  //}
665 
666  const int iComponentMonomM = p_GetComp(pMonom, rRing);
667 
668  poly p = pPoly; poly* ppPrev = &pPoly;
669 
670  loop
671  {
672 #ifdef PDEBUG
673  if( !p_Test(p, rRing) )
674  {
675  PrintS("p is wrong!");
676  p_Write(p,rRing);
677  }
678 #endif
679 
680  const int iComponent = p_GetComp(p, rRing);
681 
682  if( iComponentMonomM!=0 )
683  {
684  if( iComponent!=0 )
685  {
686  // REPORT_ERROR
687  Werror("sca_mm_Mult_p: exponent mismatch %d and %d\n", iComponent, iComponentMonomM);
688  // what should we do further?!?
689 
690  p_Delete( &pPoly, rRing); // delete the result
691  return NULL;
692  }
693 #ifdef PDEBUG
694  if(iComponent==0)
695  {
696  dReportError("sca_mm_Mult_p: Multiplication in the left module from the right!");
697 // PrintS("mm = "); p_Write(pMonom, rRing);
698 // PrintS("p = "); p_Write(pPoly, rRing);
699 // assume(iComponent!=0);
700  }
701 #endif
702  }
703 
704  // terms will be in the same order because of quasi-ordering!
705  poly v = sca_mm_Mult_m(pMonom, p, rRing);
706 
707  if( v != NULL )
708  {
709  ppPrev = &pNext(p);
710 
711  // *p is changed if v != NULL ( p == v )
712  pIter(p);
713 
714  if( p == NULL )
715  break;
716  }
717  else
718  { // Upps! Zero!!! we must kill this term!
719  p = p_LmDeleteAndNext(p, rRing);
720 
721  *ppPrev = p;
722 
723  if( p == NULL )
724  break;
725  }
726  }
727 
728 #ifdef PDEBUG
729  if( !p_Test(pPoly, rRing) )
730  {
731  PrintS("pPoly is wrong!");
732  p_Write(pPoly, rRing);
733  }
734 #endif
735 
736  return(pPoly);
737 }
738 
739 //-----------------------------------------------------------------------------------//
740 
741 #ifdef PDEBUG
742 #endif
743 
744 
745 
746 
747 //-----------------------------------------------------------------------------------//
748 
749 // GB computation routines:
750 
751 /*4
752 * creates the S-polynomial of p1 and p2
753 * does not destroy p1 and p2
754 */
755 poly sca_SPoly( const poly p1, const poly p2, const ring r )
756 {
757  assume( rIsSCA(r) );
758 
759  const long lCompP1 = p_GetComp(p1,r);
760  const long lCompP2 = p_GetComp(p2,r);
761 
762  if ((lCompP1!=lCompP2) && (lCompP1!=0) && (lCompP2!=0))
763  {
764 #ifdef PDEBUG
765  dReportError("sca_SPoly: different non-zero components!\n");
766 #endif
767  return(NULL);
768  }
769 
770  poly pL = p_Lcm(p1, p2, si_max(lCompP1, lCompP2), r); // pL = lcm( lm(p1), lm(p2) )
771 
772  poly m1 = p_One( r);
773  p_ExpVectorDiff(m1, pL, p1, r); // m1 = pL / lm(p1)
774 
775  //p_SetComp(m1,0,r);
776  //p_Setm(m1,r);
777 #ifdef PDEBUG
778  p_Test(m1,r);
779 #endif
780 
781 
782  poly m2 = p_One( r);
783  p_ExpVectorDiff (m2, pL, p2, r); // m2 = pL / lm(p2)
784 
785  //p_SetComp(m2,0,r);
786  //p_Setm(m2,r);
787 #ifdef PDEBUG
788  p_Test(m2,r);
789 #endif
790 
791  p_Delete(&pL,r);
792 
793  number C1 = n_Copy(p_GetCoeff(p1,r),r); // C1 = lc(p1)
794  number C2 = n_Copy(p_GetCoeff(p2,r),r); // C2 = lc(p2)
795 
796  number C = n_Gcd(C1,C2,r); // C = gcd(C1, C2)
797 
798  if (!n_IsOne(C, r)) // if C != 1
799  {
800  C1=n_Div(C1, C, r); // C1 = C1 / C
801  C2=n_Div(C2, C, r); // C2 = C2 / C
802  }
803 
804  n_Delete(&C,r); // destroy the number C
805 
806  const int iSignSum = sca_Sign_mm_Mult_mm (m1, p1, r) + sca_Sign_mm_Mult_mm (m2, p2, r);
807  // zero if different signs
808 
809  assume( (iSignSum*iSignSum == 0) || (iSignSum*iSignSum == 4) );
810 
811  if( iSignSum != 0 ) // the same sign!
812  C2=n_InpNeg (C2, r);
813 
814  p_SetCoeff(m1, C2, r); // lc(m1) = C2!!!
815  p_SetCoeff(m2, C1, r); // lc(m2) = C1!!!
816 
817  poly tmp1 = nc_mm_Mult_pp (m1, pNext(p1), r); // tmp1 = m1 * tail(p1),
818  p_Delete(&m1,r); // => n_Delete(&C1,r);
819 
820  poly tmp2 = nc_mm_Mult_pp (m2, pNext(p2), r); // tmp1 = m2 * tail(p2),
821  p_Delete(&m2,r); // => n_Delete(&C1,r);
822 
823  poly spoly = p_Add_q (tmp1, tmp2, r); // spoly = spoly(lt(p1), lt(p2)) + m1 * tail(p1), delete tmp1,2
824 
825  if (spoly!=NULL) p_Cleardenom (spoly, r);
826 // if (spoly!=NULL) p_Content (spoly); // r?
827 
828 #ifdef PDEBUG
829  p_Test (spoly, r);
830 #endif
831 
832  return(spoly);
833 }
834 
835 
836 
837 
838 /*2
839 * reduction of p2 with p1
840 * do not destroy p1, but p2
841 * p1 divides p2 -> for use in NF algorithm
842 */
843 poly sca_ReduceSpoly(const poly p1, poly p2, const ring r)
844 {
845  assume( rIsSCA(r) );
846 
847  assume( p1 != NULL );
848 
849  const long lCompP1 = p_GetComp (p1, r);
850  const long lCompP2 = p_GetComp (p2, r);
851 
852  if ((lCompP1!=lCompP2) && (lCompP1!=0) && (lCompP2!=0))
853  {
854 #ifdef PDEBUG
855  dReportError("sca_ReduceSpoly: different non-zero components!");
856 #endif
857  return(NULL);
858  }
859 
860  poly m = p_ISet (1, r);
861  p_ExpVectorDiff (m, p2, p1, r); // m = lm(p2) / lm(p1)
862  //p_Setm(m,r);
863 #ifdef PDEBUG
864  p_Test (m,r);
865 #endif
866 
867  number C1 = n_Copy( p_GetCoeff(p1, r), r);
868  number C2 = n_Copy( p_GetCoeff(p2, r), r);
869 
870  /* GCD stuff */
871  number C = n_Gcd(C1, C2, r);
872 
873  if (!n_IsOne(C, r))
874  {
875  C1 = n_Div(C1, C, r);
876  C2 = n_Div(C2, C, r);
877  }
878  n_Delete(&C,r);
879 
880  const int iSign = sca_Sign_mm_Mult_mm( m, p1, r );
881 
882  if(iSign == 1)
883  C2 = n_InpNeg(C2,r);
884 
885  p_SetCoeff(m, C2, r);
886 
887 #ifdef PDEBUG
888  p_Test(m,r);
889 #endif
890 
891  p2 = p_LmDeleteAndNext( p2, r );
892 
893  p2 = p_Mult_nn(p2, C1, r); // p2 !!!
894  n_Delete(&C1,r);
895 
896  poly T = nc_mm_Mult_pp(m, pNext(p1), r);
897  p_Delete(&m, r);
898 
899  p2 = p_Add_q(p2, T, r);
900 
901  if ( p2!=NULL ) p_Content(p2,r);
902 
903 #ifdef PDEBUG
904  p_Test(p2,r);
905 #endif
906 
907  return(p2);
908 }
909 
910 // should be used only inside nc_SetupQuotient!
911 // Check whether this our case:
912 // 1. rG is a commutative polynomial ring \otimes anticommutative algebra
913 // 2. factor ideal rGR->qideal contains squares of all alternating variables.
914 //
915 // if yes, make rGR a super-commutative algebra!
916 // NOTE: Factors of SuperCommutative Algebras are supported this way!
917 //
918 // rG == NULL means that there is no separate base G-algebra in this case take rGR == rG
919 
920 // special case: bCopy == true (default value: false)
921 // meaning: rGR copies structure from rG
922 // (maybe with some minor changes, which don't change the type!)
923 bool sca_SetupQuotient(ring rGR, ring rG, bool bCopy)
924 {
925 
926  //////////////////////////////////////////////////////////////////////////
927  // checks...
928  //////////////////////////////////////////////////////////////////////////
929  if( rG == NULL )
930  rG = rGR;
931 
932  assume(rGR != NULL);
933  assume(rG != NULL);
934  assume(rIsPluralRing(rG));
935 
936 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
937  PrintS("sca_SetupQuotient(rGR, rG, bCopy)");
938 
939  {
940  PrintS("\nrG: \n"); rWrite(rG);
941  PrintS("\nrGR: \n"); rWrite(rGR);
942  PrintLn();
943  }
944 #endif
945 
946 
947  if(bCopy)
948  {
949  if(rIsSCA(rG) && (rG != rGR))
950  return sca_Force(rGR, scaFirstAltVar(rG), scaLastAltVar(rG));
951  else
952  return false;
953  }
954 
955  assume(!bCopy);
956 
957  const int N = rG->N;
958 
959  if(N < 2)
960  return false;
961 
962 
963 // if( (ncRingType(rG) != nc_skew) || (ncRingType(rG) != nc_comm) )
964 // return false;
965 
966 #if OUTPUT
967  PrintS("sca_SetupQuotient: qring?\n");
968 #endif
969 
970  if(rGR->qideal == NULL) // there should be a factor!
971  return false;
972 
973 #if OUTPUT
974  PrintS("sca_SetupQuotient: qideal!!!\n");
975 #endif
976 
977 // if((rG->qideal != NULL) && (rG != rGR) ) // we cannot change from factor to factor at the time, sorry!
978 // return false;
979 
980 
981  int iAltVarEnd = -1;
982  int iAltVarStart = N+1;
983 
984  const nc_struct* NC = rG->GetNC();
985  const ring rBase = rG; //NC->basering;
986  const matrix C = NC->C; // live in rBase!
987  const matrix D = NC->D; // live in rBase!
988 
989 #if OUTPUT
990  PrintS("sca_SetupQuotient: AltVars?!\n");
991 #endif
992 
993  for(int i = 1; i < N; i++)
994  {
995  for(int j = i + 1; j <= N; j++)
996  {
997  if( MATELEM(D,i,j) != NULL) // !!!???
998  {
999 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1000  Print("Nonzero D[%d, %d]\n", i, j);
1001 #endif
1002  return false;
1003  }
1004 
1005 
1006  assume(MATELEM(C,i,j) != NULL); // after CallPlural!
1007  number c = p_GetCoeff(MATELEM(C,i,j), rBase);
1008 
1009  if( n_IsMOne(c, rBase) ) // !!!???
1010  {
1011  if( i < iAltVarStart)
1012  iAltVarStart = i;
1013 
1014  if( j > iAltVarEnd)
1015  iAltVarEnd = j;
1016  } else
1017  {
1018  if( !n_IsOne(c, rBase) )
1019  {
1020 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1021  Print("Wrong Coeff at: [%d, %d]\n", i, j);
1022 #endif
1023  return false;
1024  }
1025  }
1026  }
1027  }
1028 
1029 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1030  Print("AltVars?1: [%d, %d]\n", iAltVarStart, iAltVarEnd);
1031 #endif
1032 
1033 
1034  if( (iAltVarEnd == -1) || (iAltVarStart == (N+1)) )
1035  return false; // either no alternating varables, or a single one => we are in commutative case!
1036 
1037 
1038  for(int i = 1; i < N; i++)
1039  {
1040  for(int j = i + 1; j <= N; j++)
1041  {
1042  assume(MATELEM(C,i,j) != NULL); // after CallPlural!
1043  number c = p_GetCoeff(MATELEM(C,i,j), rBase);
1044 
1045  if( (iAltVarStart <= i) && (j <= iAltVarEnd) ) // S <= i < j <= E
1046  { // anticommutative part
1047  if( !n_IsMOne(c, rBase) )
1048  {
1049 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1050  Print("Wrong Coeff at: [%d, %d]\n", i, j);
1051 #endif
1052  return false;
1053  }
1054  } else
1055  { // should commute
1056  if( !n_IsOne(c, rBase) )
1057  {
1058 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1059  Print("Wrong Coeff at: [%d, %d]\n", i, j);
1060 #endif
1061  return false;
1062  }
1063  }
1064  }
1065  }
1066 
1067 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1068  Print("AltVars!?: [%d, %d]\n", iAltVarStart, iAltVarEnd);
1069 #endif
1070 
1071  assume( 1 <= iAltVarStart );
1072  assume( iAltVarStart < iAltVarEnd );
1073  assume( iAltVarEnd <= N );
1074 
1075 
1076 // ring rSaveRing = assureCurrentRing(rG);
1077 
1078 
1079  assume(rGR->qideal != NULL);
1080  assume(rGR->N == rG->N);
1081 // assume(rG->qideal == NULL); // ?
1082 
1083  const ideal idQuotient = rGR->qideal;
1084 
1085 
1086 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1087  PrintS("Analyzing quotient ideal:\n");
1088  idPrint(idQuotient); // in rG!!!
1089 #endif
1090 
1091 
1092  // check for
1093  // y_{iAltVarStart}^2, y_{iAltVarStart+1}^2, \ldots, y_{iAltVarEnd}^2 (iAltVarEnd > iAltVarStart)
1094  // to be within quotient ideal.
1095 
1096  bool bSCA = true;
1097 
1098  int b = N+1;
1099  int e = -1;
1100 
1101  if(rIsSCA(rG))
1102  {
1103  b = si_min(b, scaFirstAltVar(rG));
1104  e = si_max(e, scaLastAltVar(rG));
1105 
1106 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1107  Print("AltVars!?: [%d, %d]\n", b, e);
1108 #endif
1109  }
1110 
1111  for ( int i = iAltVarStart; (i <= iAltVarEnd) && bSCA; i++ )
1112  if( (i < b) || (i > e) ) // otherwise it's ok since rG is an SCA!
1113  {
1114  poly square = p_One( rG);
1115  p_SetExp(square, i, 2, rG); // square = var(i)^2.
1116  p_Setm(square, rG);
1117 
1118  // square = NF( var(i)^2 | Q )
1119  // NOTE: there is no better way to check this in general!
1120  square = nc_NF(idQuotient, NULL, square, 0, 1, rG); // must ran in currRing == rG!
1121 
1122  if( square != NULL ) // var(i)^2 is not in Q?
1123  {
1124  p_Delete(&square, rG);
1125  bSCA = false;
1126  break;
1127  }
1128  }
1129 
1130 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1131  Print("ScaVars!: [%d, %d]\n", iAltVarStart, iAltVarEnd);
1132 #endif
1133 
1134 
1135  //////////////////////////////////////////////////////////////////////////
1136  // ok... here we go. let's setup it!!!
1137  //////////////////////////////////////////////////////////////////////////
1138  ideal tempQ = id_KillSquares(idQuotient, iAltVarStart, iAltVarEnd, rG); // in rG!!!
1139 
1140 
1141 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1142  PrintS("Quotient: \n");
1143  iiWriteMatrix((matrix)idQuotient,"__",1, rG, 0);
1144  PrintS("tempSCAQuotient: \n");
1145  iiWriteMatrix((matrix)tempQ,"__",1, rG, 0);
1146 #endif
1147 
1148  idSkipZeroes( tempQ );
1149 
1150  ncRingType( rGR, nc_exterior );
1151 
1152  scaFirstAltVar( rGR, iAltVarStart );
1153  scaLastAltVar( rGR, iAltVarEnd );
1154 
1155  if( idIs0(tempQ) )
1156  rGR->GetNC()->SCAQuotient() = NULL;
1157  else
1158  rGR->GetNC()->SCAQuotient() = idrMoveR(tempQ, rG, rGR); // deletes tempQ!
1159 
1160  nc_p_ProcsSet(rGR, rGR->p_Procs); // !!!!!!!!!!!!!!!!!
1161 
1162 
1163 #if ((defined(PDEBUG) && OUTPUT) || MYTEST)
1164  PrintS("SCAQuotient: \n");
1165  if(tempQ != NULL)
1166  iiWriteMatrix((matrix)tempQ,"__",1, rGR, 0);
1167  else
1168  PrintS("(NULL)\n");
1169 #endif
1170 
1171  return true;
1172 }
1173 
1174 
1175 bool sca_Force(ring rGR, int b, int e)
1176 {
1177  assume(rGR != NULL);
1178  assume(rIsPluralRing(rGR));
1179  assume(!rIsSCA(rGR));
1180 
1181  const int N = rGR->N;
1182 
1183 // ring rSaveRing = currRing;
1184 // if(rSaveRing != rGR)
1185 // rChangeCurrRing(rGR);
1186 
1187  const ideal idQuotient = rGR->qideal;
1188 
1189  ideal tempQ = idQuotient;
1190 
1191  if( b <= N && e >= 1 )
1192  tempQ = id_KillSquares(idQuotient, b, e, rGR);
1193 
1194  idSkipZeroes( tempQ );
1195 
1196  ncRingType( rGR, nc_exterior );
1197 
1198  if( idIs0(tempQ) )
1199  rGR->GetNC()->SCAQuotient() = NULL;
1200  else
1201  rGR->GetNC()->SCAQuotient() = tempQ;
1202 
1203 
1204  scaFirstAltVar( rGR, b );
1205  scaLastAltVar( rGR, e );
1206 
1207 
1208  nc_p_ProcsSet(rGR, rGR->p_Procs);
1209 
1210 // if(rSaveRing != rGR)
1211 // rChangeCurrRing(rSaveRing);
1212 
1213  return true;
1214 }
1215 
1216 // return x_i * pPoly; preserve pPoly.
1217 poly sca_pp_Mult_xi_pp(short i, const poly pPoly, const ring rRing)
1218 {
1219  assume(1 <= i);
1220  assume(i <= rVar(rRing));
1221 
1222  if(rIsSCA(rRing))
1223  return sca_xi_Mult_pp(i, pPoly, rRing);
1224 
1225 
1226 
1227  poly xi = p_One( rRing);
1228  p_SetExp(xi, i, 1, rRing);
1229  p_Setm(xi, rRing);
1230 
1231  poly pResult = pp_Mult_qq(xi, pPoly, rRing);
1232 
1233  p_Delete( &xi, rRing);
1234 
1235  return pResult;
1236 
1237 }
1238 
1239 void sca_p_ProcsSet(ring rGR, p_Procs_s* p_Procs)
1240 {
1241 
1242  // "commutative" procedures:
1243  rGR->p_Procs->p_Mult_mm = sca_p_Mult_mm;
1244  rGR->p_Procs->pp_Mult_mm = sca_pp_Mult_mm;
1245 
1246  p_Procs->p_Mult_mm = sca_p_Mult_mm;
1247  p_Procs->pp_Mult_mm = sca_pp_Mult_mm;
1248 
1249  // non-commutaitve
1250  rGR->GetNC()->p_Procs.mm_Mult_p = sca_mm_Mult_p;
1251  rGR->GetNC()->p_Procs.mm_Mult_pp = sca_mm_Mult_pp;
1252 
1253 // rGR->GetNC()->p_Procs.SPoly = sca_SPoly;
1254 // rGR->GetNC()->p_Procs.ReduceSPoly = sca_ReduceSpoly;
1255 
1256 #if 0
1257 
1258  // Multiplication procedures:
1259 
1260  p_Procs->p_Mult_mm = sca_p_Mult_mm;
1261  _p_procs->p_Mult_mm = sca_p_Mult_mm;
1262 
1263  p_Procs->pp_Mult_mm = sca_pp_Mult_mm;
1264  _p_procs->pp_Mult_mm = sca_pp_Mult_mm;
1265 
1266  r->GetNC()->mmMultP() = sca_mm_Mult_p;
1267  r->GetNC()->mmMultPP() = sca_mm_Mult_pp;
1268 
1269 /*
1270  // ??????????????????????????????????????? coefficients swell...
1271  r->GetNC()->SPoly() = sca_SPoly;
1272  r->GetNC()->ReduceSPoly() = sca_ReduceSpoly;
1273 */
1274 // r->GetNC()->BucketPolyRed() = gnc_kBucketPolyRed;
1275 // r->GetNC()->BucketPolyRed_Z()= gnc_kBucketPolyRed_Z;
1276 #endif
1277 
1278  // local ordering => Mora, otherwise - Buchberger!
1279  if (rHasLocalOrMixedOrdering(rGR))
1280  rGR->GetNC()->p_Procs.GB = cast_A_to_vptr(sca_mora);
1281  else
1282  rGR->GetNC()->p_Procs.GB = cast_A_to_vptr(sca_bba); // sca_gr_bba?
1283 }
1284 
1285 
1286 // bi-Degree (x, y) of monomial "m"
1287 // x-es and y-s are weighted by wx and wy resp.
1288 // [optional] components have weights by wCx and wCy.
1289 static inline void m_GetBiDegree(const poly m,
1290  const intvec *wx, const intvec *wy,
1291  const intvec *wCx, const intvec *wCy,
1292  int& dx, int& dy, const ring r)
1293 {
1294  const unsigned int N = r->N;
1295 
1296  p_Test(m, r);
1297 
1298  assume( wx != NULL );
1299  assume( wy != NULL );
1300 
1301  assume( wx->cols() == 1 );
1302  assume( wy->cols() == 1 );
1303 
1304  assume( (unsigned int)wx->rows() >= N );
1305  assume( (unsigned int)wy->rows() >= N );
1306 
1307  int x = 0;
1308  int y = 0;
1309 
1310  for(int i = N; i > 0; i--)
1311  {
1312  const int d = p_GetExp(m, i, r);
1313  x += d * (*wx)[i-1];
1314  y += d * (*wy)[i-1];
1315  }
1316 
1317  if( (wCx != NULL) && (wCy != NULL) )
1318  {
1319  const int c = p_GetComp(m, r);
1320 
1321  if( wCx->range(c) )
1322  x += (*wCx)[c];
1323 
1324  if( wCy->range(c) )
1325  x += (*wCy)[c];
1326  }
1327 
1328  dx = x;
1329  dy = y;
1330 }
1331 
1332 // returns true if polynom p is bi-homogenous with respect to the given weights
1333 // simultaneously sets bi-Degree
1335  const intvec *wx, const intvec *wy,
1336  const intvec *wCx, const intvec *wCy,
1337  int &dx, int &dy,
1338  const ring r)
1339 {
1340  if( p == NULL )
1341  {
1342  dx = 0;
1343  dy = 0;
1344  return true;
1345  }
1346 
1347  poly q = p;
1348 
1349 
1350  int ddx, ddy;
1351 
1352  m_GetBiDegree( q, wx, wy, wCx, wCy, ddx, ddy, r); // get bi degree of lm(p)
1353 
1354  pIter(q);
1355 
1356  for(; q != NULL; pIter(q) )
1357  {
1358  int x, y;
1359 
1360  m_GetBiDegree( q, wx, wy, wCx, wCy, x, y, r); // get bi degree of q
1361 
1362  if ( (x != ddx) || (y != ddy) ) return false;
1363  }
1364 
1365  dx = ddx;
1366  dy = ddy;
1367 
1368  return true;
1369 }
1370 
1371 
1372 // returns true if id is bi-homogenous without respect to the given weights
1373 bool id_IsBiHomogeneous(const ideal id,
1374  const intvec *wx, const intvec *wy,
1375  const intvec *wCx, const intvec *wCy,
1376  const ring r)
1377 {
1378  if (id == NULL) return true; // zero ideal
1379 
1380  const int iSize = IDELEMS(id);
1381 
1382  if (iSize == 0) return true;
1383 
1384  bool b = true;
1385  int x, y;
1386 
1387  for(int i = iSize - 1; (i >= 0 ) && b; i--)
1388  b = p_IsBiHomogeneous(id->m[i], wx, wy, wCx, wCy, x, y, r);
1389 
1390  return b;
1391 }
1392 
1393 
1394 // returns an intvector with [nvars(r)] integers [1/0]
1395 // 1 - for commutative variables
1396 // 0 - for anticommutative variables
1398 {
1399  const unsigned int N = r->N;
1400 
1401  const int CommutativeVariable = 0; // bug correction!
1402  const int AntiCommutativeVariable = 0;
1403 
1404  intvec* w = new intvec(N, 1, CommutativeVariable);
1405 
1406  if(AntiCommutativeVariable != CommutativeVariable)
1407  if( rIsSCA(r) )
1408  {
1409  const unsigned int m_iFirstAltVar = scaFirstAltVar(r);
1410  const unsigned int m_iLastAltVar = scaLastAltVar(r);
1411 
1412  for (unsigned int i = m_iFirstAltVar; i<= m_iLastAltVar; i++)
1413  {
1414  (*w)[i-1] = AntiCommutativeVariable;
1415  }
1416  }
1417 
1418  return w;
1419 }
1420 
1421 
1422 // returns an intvector with [nvars(r)] integers [1/0]
1423 // 0 - for commutative variables
1424 // 1 - for anticommutative variables
1426 {
1427  const unsigned int N = r->N;
1428 
1429  const int CommutativeVariable = 0;
1430  const int AntiCommutativeVariable = 1;
1431 
1432  intvec* w = new intvec(N, 1, CommutativeVariable);
1433 
1434  if(AntiCommutativeVariable != CommutativeVariable)
1435  if( rIsSCA(r) )
1436  {
1437  const unsigned int m_iFirstAltVar = scaFirstAltVar(r);
1438  const unsigned int m_iLastAltVar = scaLastAltVar(r);
1439 
1440  for (unsigned int i = m_iFirstAltVar; i<= m_iLastAltVar; i++)
1441  {
1442  (*w)[i-1] = AntiCommutativeVariable;
1443  }
1444  }
1445  return w;
1446 }
1447 
1448 
1449 
1450 
1451 // reduce term lt(m) modulo <y_i^2> , i = iFirstAltVar .. iLastAltVar:
1452 // either create a copy of m or return NULL
1453 static inline poly m_KillSquares(const poly m,
1454  const short iFirstAltVar, const short iLastAltVar,
1455  const ring r)
1456 {
1457 #ifdef PDEBUG
1458  p_Test(m, r);
1459  assume( (iFirstAltVar >= 1) && (iLastAltVar <= rVar(r)) && (iFirstAltVar <= iLastAltVar) );
1460 
1461 #if 0
1462  Print("m_KillSquares, m = "); // !
1463  p_Write(m, r);
1464 #endif
1465 #endif
1466 
1467  assume( m != NULL );
1468 
1469  for(short k = iFirstAltVar; k <= iLastAltVar; k++)
1470  if( p_GetExp(m, k, r) > 1 )
1471  return NULL;
1472 
1473  return p_Head(m, r);
1474 }
1475 
1476 
1477 // reduce polynomial p modulo <y_i^2> , i = iFirstAltVar .. iLastAltVar
1478 // returns a new poly!
1480  const short iFirstAltVar, const short iLastAltVar,
1481  const ring r)
1482 {
1483 #ifdef PDEBUG
1484  p_Test(p, r);
1485 
1486  assume( (iFirstAltVar >= 1) && (iLastAltVar <= r->N) && (iFirstAltVar <= iLastAltVar) );
1487 
1488 #if 0
1489  Print("p_KillSquares, p = "); // !
1490  p_Write(p, r);
1491 #endif
1492 #endif
1493 
1494 
1495  if( p == NULL )
1496  return NULL;
1497 
1498  poly pResult = NULL;
1499  poly* ppPrev = &pResult;
1500 
1501  for( poly q = p; q!= NULL; pIter(q) )
1502  {
1503 #ifdef PDEBUG
1504  p_Test(q, r);
1505 #endif
1506 
1507  // terms will be in the same order because of quasi-ordering!
1508  poly v = m_KillSquares(q, iFirstAltVar, iLastAltVar, r);
1509 
1510  if( v != NULL )
1511  {
1512  *ppPrev = v;
1513  ppPrev = &pNext(v);
1514  }
1515 
1516  }
1517 
1518 #ifdef PDEBUG
1519  p_Test(pResult, r);
1520 #if 0
1521  Print("p_KillSquares => "); // !
1522  p_Write(pResult, r);
1523 #endif
1524 #endif
1525 
1526  return(pResult);
1527 }
1528 
1529 
1530 
1531 
1532 // reduces ideal id modulo <y_i^2> , i = iFirstAltVar .. iLastAltVar
1533 // returns the reduced ideal or zero ideal.
1534 ideal id_KillSquares(const ideal id,
1535  const short iFirstAltVar, const short iLastAltVar,
1536  const ring r, const bool bSkipZeroes)
1537 {
1538  if (id == NULL) return id; // zero ideal
1539 
1540  assume( (iFirstAltVar >= 1) && (iLastAltVar <= rVar(r)) && (iFirstAltVar <= iLastAltVar) );
1541 
1542  const int iSize = IDELEMS(id);
1543 
1544  if (iSize == 0) return id;
1545 
1546  ideal temp = idInit(iSize, id->rank);
1547 
1548 #if 0
1549  PrintS("<id_KillSquares>\n");
1550  {
1551  PrintS("ideal id: \n");
1552  for (unsigned int i = 0; i < IDELEMS(id); i++)
1553  {
1554  Print("; id[%d] = ", i+1);
1555  p_Write(id->m[i], r);
1556  }
1557  PrintS(";\n");
1558  PrintLn();
1559  }
1560 #endif
1561 
1562 
1563  for (int j = 0; j < iSize; j++)
1564  temp->m[j] = p_KillSquares(id->m[j], iFirstAltVar, iLastAltVar, r);
1565 
1566  if( bSkipZeroes )
1567  idSkipZeroes(temp);
1568 
1569 #if 0
1570  PrintS("<id_KillSquares>\n");
1571  {
1572  PrintS("ideal temp: \n");
1573  for (int i = 0; i < IDELEMS(temp); i++)
1574  {
1575  Print("; temp[%d] = ", i+1);
1576  p_Write(temp->m[i], r);
1577  }
1578  PrintS(";\n");
1579  PrintLn();
1580  }
1581  PrintS("</id_KillSquares>\n");
1582 #endif
1583 
1584 // temp->rank = idRankFreeModule(temp, r);
1585 
1586  return temp;
1587 }
1588 
1589 
1590 
1591 
1592 #endif
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:753
BBA_Proc sca_mora
Definition: old.gring.cc:76
static poly sca_xi_Mult_pp(short i, const poly pPoly, const ring rRing)
Definition: sca.cc:534
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of &#39;a&#39; and &#39;b&#39; in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:685
static poly sca_xi_Mult_mm(short i, const poly pMonom, const ring rRing)
Definition: sca.cc:337
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
#define D(A)
Definition: gentable.cc:119
void PrintLn()
Definition: reporter.cc:327
#define Print
Definition: emacs.cc:83
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:721
static poly sca_mm_Mult_p(const poly pMonom, poly pPoly, const ring rRing)
Definition: sca.cc:646
loop
Definition: myNF.cc:98
static int si_min(const int a, const int b)
Definition: auxiliary.h:167
return P p
Definition: myNF.cc:203
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:469
static poly sca_m_Mult_mm(poly pMonomM, const poly pMonomMM, const ring rRing)
Definition: sca.cc:143
struct p_Procs_s p_Procs_s
Definition: ring.h:29
#define p_GetComp(p, r)
Definition: monomials.h:72
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:540
void p_Lcm(const poly a, const poly b, poly m, const ring r)
Definition: p_polys.cc:1572
#define p_AllocBin(p, bin, r)
Definition: monomials.h:256
poly sca_p_Mult_mm(poly pPoly, const poly pMonom, const ring rRing)
Definition: sca.cc:382
static poly m_KillSquares(const poly m, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition: sca.cc:1453
void nc_p_ProcsSet(ring rGR, p_Procs_s *p_Procs)
Definition: old.gring.cc:3264
int k
Definition: cfEzgcd.cc:93
Definition: nc.h:83
static bool rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:361
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition: sca.cc:1479
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:401
static int sca_Sign_mm_Mult_mm(const poly pMonomM, const poly pMonomMM, const ring rRing)
Definition: sca.cc:92
poly sca_ReduceSpoly(const poly p1, poly p2, const ring r)
Definition: sca.cc:843
void iiWriteMatrix(matrix im, const char *n, int dim, const ring r, int spaces)
set spaces to zero by default
Definition: matpol.cc:739
#define pIter(p)
Definition: monomials.h:44
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:635
bool sca_Force(ring rGR, int b, int e)
Definition: sca.cc:1175
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:819
#define idPrint(id)
Definition: ideals.h:59
bool id_IsBiHomogeneous(const ideal id, const intvec *wx, const intvec *wy, const intvec *wCx, const intvec *wCy, const ring r)
Definition: sca.cc:1373
const ring r
Definition: syzextra.cc:208
Definition: intvec.h:16
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
poly p_One(const ring r)
Definition: p_polys.cc:1318
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:465
bool p_IsBiHomogeneous(const poly p, const intvec *wx, const intvec *wy, const intvec *wCx, const intvec *wCy, int &dx, int &dy, const ring r)
Definition: sca.cc:1334
int j
Definition: myNF.cc:70
BBA_Proc sca_bba
Definition: old.gring.cc:75
#define assume(x)
Definition: mod2.h:405
static poly sca_mm_Mult_mm(poly pMonom1, const poly pMonom2, const ring rRing)
Definition: sca.cc:272
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1075
intvec * ivGetSCAYVarWeights(const ring r)
Definition: sca.cc:1425
poly sca_pp_Mult_xi_pp(short i, const poly pPoly, const ring rRing)
Definition: sca.cc:1217
poly sca_pp_Mult_mm(const poly pPoly, const poly pMonom, const ring rRing, poly &)
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
All the auxiliary stuff.
int m
Definition: cfEzgcd.cc:119
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:558
static int si_max(const int a, const int b)
Definition: auxiliary.h:166
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:902
void sca_p_ProcsSet(ring rGR, p_Procs_s *p_Procs)
Definition: sca.cc:1239
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition: p_polys.h:1339
void rWrite(ring r, BOOLEAN details)
Definition: ring.cc:236
void p_Content(poly ph, const ring r)
Definition: p_polys.cc:2182
#define IDELEMS(i)
Definition: simpleideals.h:24
CFList tmp2
Definition: facFqBivar.cc:70
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static short scaFirstAltVar(ring r)
Definition: sca.h:18
#define p_LmTest(p, r)
Definition: p_polys.h:161
poly sca_SPoly(const poly p1, const poly p2, const ring r)
Definition: sca.cc:755
#define p_Test(p, r)
Definition: p_polys.h:160
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:850
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1402
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:484
static poly sca_mm_Mult_pp(const poly pMonom, const poly pPoly, const ring rRing)
Definition: sca.cc:578
Definition: nc.h:29
int range(int i) const
Definition: intvec.h:53
#define NULL
Definition: omList.c:10
int cols() const
Definition: intvec.h:87
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition: sca.cc:1534
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:452
void * cast_A_to_vptr(A a)
Definition: auxiliary.h:442
matrix D
Definition: nc.h:92
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:615
int rows() const
Definition: intvec.h:88
static poly sca_mm_Mult_m(const poly pMonomMM, poly pMonomM, const ring rRing)
Definition: sca.cc:207
CFList tmp1
Definition: facFqBivar.cc:70
const CanonicalForm & w
Definition: facAbsFact.cc:55
bool sca_SetupQuotient(ring rGR, ring rG, bool bCopy)
Definition: sca.cc:923
static short scaLastAltVar(ring r)
Definition: sca.h:25
static p_Procs_s * _p_procs
Definition: p_Procs_Set.h:114
Variable x
Definition: cfModGcd.cc:4023
static bool rIsSCA(const ring r)
Definition: nc.h:206
#define pNext(p)
Definition: monomials.h:43
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1263
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:436
#define p_GetCoeff(p, r)
Definition: monomials.h:57
static nc_type & ncRingType(nc_struct *p)
Definition: nc.h:175
matrix C
Definition: nc.h:91
int dReportError(const char *fmt,...)
Definition: dError.cc:45
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:68
static poly nc_mm_Mult_pp(const poly m, const poly p, const ring r)
Definition: nc.h:240
NF_Proc nc_NF
Definition: old.gring.cc:72
END_NAMESPACE const void * p2
Definition: syzextra.cc:202
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
static FORCE_INLINE BOOLEAN n_IsMOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the additive inverse of the one element, i.e. -1.
Definition: coeffs.h:473
void p_Write(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:206
static void p_ExpVectorSum(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1353
static jList * T
Definition: janet.cc:37
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:884
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
const poly b
Definition: syzextra.cc:213
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2682
static void m_GetBiDegree(const poly m, const intvec *wx, const intvec *wy, const intvec *wCx, const intvec *wCy, int &dx, int &dy, const ring r)
Definition: sca.cc:1289
intvec * ivGetSCAXVarWeights(const ring r)
Definition: sca.cc:1397
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1302
void Werror(const char *fmt,...)
Definition: reporter.cc:199
#define MATELEM(mat, i, j)
Definition: matpol.h:29