My Project  UNKNOWN_GIT_VERSION
tgb.cc
Go to the documentation of this file.
1 //! \file tgb.cc
2 // multiple rings
3 // shorten_tails und dessen Aufrufe pruefen wlength!!!
4 /****************************************
5 * Computer Algebra System SINGULAR *
6 ****************************************/
7 /*
8 * ABSTRACT: slimgb and F4 implementation
9 */
10 //#include <vector>
11 //using namespace std;
12 
13 ///@TODO: delay nur auf Sugarvergroesserung
14 ///@TODO: grade aus ecartS, setze dazu strat->honey; und nutze p.ecart
15 ///@TODO: no tail reductions in syz comp
16 #include "kernel/mod2.h"
17 
18 #include "kernel/GBEngine/tgb.h"
21 
22 #include "misc/options.h"
23 #include "kernel/digitech.h"
24 #include "polys/nc/nc.h"
25 #include "polys/nc/sca.h"
26 #include "polys/prCopy.h"
27 
28 #include "coeffs/longrat.h" // nlQlogSize
29 
30 #include <stdlib.h>
31 #include <stdio.h>
32 #include <queue>
33 
34 #define BUCKETS_FOR_NORO_RED 1
35 #define SR_HDL(A) ((long)(A))
36 static const int bundle_size = 100;
37 static const int bundle_size_noro = 10000;
38 static const int delay_factor = 3;
39 #define ADD_LATER_SIZE 500
40 #if 1
41 static omBin lm_bin = NULL;
42 static int add_to_reductors(slimgb_alg* c, poly h, int len, int ecart, BOOLEAN simplified=FALSE);
43 static void multi_reduction(red_object* los, int & losl, slimgb_alg* c);
44 static void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c);
45 static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c);
46 static poly gcd_of_terms(poly p, ring r);
47 static int tgb_pair_better_gen(const void* ap,const void* bp);
49 static BOOLEAN state_is(calc_state state, const int & i, const int & j, slimgb_alg* c);
51 static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen);
52 static int* make_connections(int from, int to, poly bound, slimgb_alg* c);
53 static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state);
54 static void shorten_tails(slimgb_alg* c, poly monom);
55 static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n=0);
56 static poly redNFTail (poly h,const int sl,kStrategy strat, int len);
57 static int bucket_guess(kBucket* bucket);
58 
59 static void simplify_poly (poly p, ring r)
60 {
61  assume (r == currRing);
63  {
64  p_Cleardenom (p, r);
65  //includes p_Content(p,r);
66  }
67  else
68  pNorm (p);
69 }
70 
71 //static const BOOLEAN up_to_radical=TRUE;
72 
73 int slim_nsize (number n, ring r)
74 {
75  if(rField_is_Zp (r))
76  {
77  return 1;
78  }
79  if(rField_is_Q (r))
80  {
81  return nlQlogSize (n, r->cf);
82  }
83  else
84  {
85  return n_Size (n, r->cf);
86  }
87 }
88 
89 static BOOLEAN monomial_root (poly m, ring r)
90 {
91  BOOLEAN changed = FALSE;
92  int i;
93  for(i = 1; i <= rVar (r); i++)
94  {
95  int e = p_GetExp (m, i, r);
96  if(e > 1)
97  {
98  p_SetExp (m, i, 1, r);
99  changed = TRUE;
100  }
101  }
102  if(changed)
103  {
104  p_Setm (m, r);
105  }
106  return changed;
107 }
108 
109 static BOOLEAN polynomial_root (poly h, ring r)
110 {
111  poly got = gcd_of_terms (h, r);
112  BOOLEAN changed = FALSE;
113  if((got != NULL) && (TEST_V_UPTORADICAL))
114  {
115  poly copy = p_Copy (got, r);
116  //p_wrp(got,c->r);
117  changed = monomial_root (got, r);
118  if(changed)
119  {
120  poly div_by = pMDivide (copy, got);
121  poly iter = h;
122  while(iter)
123  {
124  pExpVectorSub (iter, div_by);
125  pIter (iter);
126  }
127  p_Delete (&div_by, r);
128  if(TEST_OPT_PROT)
129  PrintS ("U");
130  }
131  p_Delete (&copy, r);
132  }
133  p_Delete (&got, r);
134  return changed;
135 }
136 
137 static inline poly p_Init_Special (const ring r)
138 {
139  return p_Init (r, lm_bin);
140 }
141 
142 static inline poly pOne_Special (const ring r = currRing)
143 {
144  poly rc = p_Init_Special (r);
145  pSetCoeff0 (rc, n_Init (1, r->cf));
146  return rc;
147 }
148 
149 // zum Initialiseren: in t_rep_gb plazieren:
150 
151 #endif
152 #define LEN_VAR3
153 #define degbound(p) assume(pTotaldegree(p)<10)
154 //#define inDebug(p) assume((debug_Ideal==NULL)||(kNF(debug_Ideal,NULL,p,0,0)==0))
155 
156 //die meisten Varianten stossen sich an coef_buckets
157 
158 #ifdef LEN_VAR1
159 // erste Variante: Laenge: Anzahl der Monome
160 static inline int pSLength (poly p, int l)
161 {
162  return l;
163 }
164 
165 static inline int kSBucketLength (kBucket * bucket, poly lm)
166 {
167  return bucket_guess (bucket);
168 }
169 #endif
170 
171 #ifdef LEN_VAR2
172 // 2. Variante: Laenge: Platz fuer die Koeff.
173 int pSLength (poly p, int l)
174 {
175  int s = 0;
176  while(p != NULL)
177  {
178  s += nSize (pGetCoeff (p));
179  pIter (p);
180  }
181  return s;
182 }
183 
184 int kSBucketLength (kBucket * b, poly lm)
185 {
186  int s = 0;
187  int i;
188  for(i = MAX_BUCKET; i >= 0; i--)
189  {
190  s += pSLength (b->buckets[i], 0);
191  }
192  return s;
193 }
194 #endif
195 
196 #ifdef LEN_VAR3
197 static inline wlen_type pSLength (poly p, int l)
198 {
199  wlen_type c;
200  number coef = pGetCoeff (p);
201  if(rField_is_Q (currRing))
202  {
203  c = nlQlogSize (coef, currRing->cf);
204  }
205  else
206  c = nSize (coef);
207  if(!(TEST_V_COEFSTRAT))
208  {
209  return (wlen_type) c *(wlen_type) l /*pLength(p) */ ;
210  }
211  else
212  {
213  wlen_type res = l;
214  res *= c;
215  res *= c;
216  return res;
217  }
218 }
219 
220 //! TODO CoefBuckets bercksichtigen
222 {
223  int s = 0;
224  wlen_type c;
225  number coef;
226  if(lm == NULL)
227  coef = pGetCoeff (kBucketGetLm (b));
228  //c=nSize(pGetCoeff(kBucketGetLm(b)));
229  else
230  coef = pGetCoeff (lm);
231  //c=nSize(pGetCoeff(lm));
232  if(rField_is_Q (currRing))
233  {
234  c = nlQlogSize (coef, currRing->cf);
235  }
236  else
237  c = nSize (coef);
238 
239  int i;
240  for(i = b->buckets_used; i >= 0; i--)
241  {
242  assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL));
243  s += b->buckets_length[i] /*pLength(b->buckets[i]) */ ;
244  }
245 #ifdef HAVE_COEF_BUCKETS
246  assume (b->buckets[0] == kBucketGetLm (b));
247  if(b->coef[0] != NULL)
248  {
249  if(rField_is_Q (currRing))
250  {
251  int modifier = nlQlogSize (pGetCoeff (b->coef[0]), currRing->cf);
252  c += modifier;
253  }
254  else
255  {
256  int modifier = nSize (pGetCoeff (b->coef[0]));
257  c *= modifier;
258  }
259  }
260 #endif
261  if(!(TEST_V_COEFSTRAT))
262  {
263  return s * c;
264  }
265  else
266  {
267  wlen_type res = s;
268  res *= c;
269  res *= c;
270  return res;
271  }
272 }
273 #endif
274 #ifdef LEN_VAR5
275 static inline wlen_type pSLength (poly p, int l)
276 {
277  int c;
278  number coef = pGetCoeff (p);
279  if(rField_is_Q (currRing))
280  {
281  c = nlQlogSize (coef, currRing->cf);
282  }
283  else
284  c = nSize (coef);
285  wlen_type erg = l;
286  erg *= c;
287  erg *= c;
288  //PrintS("lenvar 5");
289  assume (erg >= 0);
290  return erg; /*pLength(p) */ ;
291 }
292 
293 //! TODO CoefBuckets beruecksichtigen
294 wlen_type kSBucketLength (kBucket * b, poly lm = NULL)
295 {
296  wlen_type s = 0;
297  int c;
298  number coef;
299  if(lm == NULL)
300  coef = pGetCoeff (kBucketGetLm (b));
301  //c=nSize(pGetCoeff(kBucketGetLm(b)));
302  else
303  coef = pGetCoeff (lm);
304  //c=nSize(pGetCoeff(lm));
305  if(rField_is_Q (currRing))
306  {
307  c = nlQlogSize (coef, currRing->cf);
308  }
309  else
310  c = nSize (coef);
311 
312  int i;
313  for(i = b->buckets_used; i >= 0; i--)
314  {
315  assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL));
316  s += b->buckets_length[i] /*pLength(b->buckets[i]) */ ;
317  }
318 #ifdef HAVE_COEF_BUCKETS
319  assume (b->buckets[0] == kBucketGetLm (b));
320  if(b->coef[0] != NULL)
321  {
322  if(rField_is_Q (currRing))
323  {
324  int modifier = nlQlogSize (pGetCoeff (b->coef[0]), currRing->cf);
325  c += modifier;
326  }
327  else
328  {
329  int modifier = nSize (pGetCoeff (b->coef[0]));
330  c *= modifier;
331  }
332  }
333 #endif
334  wlen_type erg = s;
335  erg *= c;
336  erg *= c;
337  return erg;
338 }
339 #endif
340 
341 #ifdef LEN_VAR4
342 // 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.)
343 int pSLength (poly p, int l)
344 {
345  int s = 1;
346  int c = nSize (pGetCoeff (p));
347  pIter (p);
348  while(p != NULL)
349  {
350  s += nSize (pGetCoeff (p));
351  pIter (p);
352  }
353  return s * c;
354 }
355 
356 int kSBucketLength (kBucket * b)
357 {
358  int s = 1;
359  int c = nSize (pGetCoeff (kBucketGetLm (b)));
360  int i;
361  for(i = MAX_BUCKET; i > 0; i--)
362  {
363  if(b->buckets[i] == NULL)
364  continue;
365  s += pSLength (b->buckets[i], 0);
366  }
367  return s * c;
368 }
369 #endif
370 //BUG/TODO this stuff will fail on internal Schreyer orderings
372 {
373  ring r = c->r;
374  if(p_GetComp (p, r) != 0)
375  return FALSE;
376  if(c->lastDpBlockStart <= (currRing->N))
377  {
378  int i;
379  for(i = 1; i < c->lastDpBlockStart; i++)
380  {
381  if(p_GetExp (p, i, r) != 0)
382  {
383  break;
384  }
385  }
386  if(i >= c->lastDpBlockStart)
387  {
388  //wrp(p);
389  //PrintS("\n");
390  return TRUE;
391  }
392  else
393  return FALSE;
394  }
395  else
396  return FALSE;
397 }
398 
400 {
401  ring r = c->r;
402  if(p_GetComp (p, r) != 0)
403  return FALSE;
404  if(c->lastDpBlockStart <= (currRing->N))
405  {
406  int i;
407  for(i = 1; i < c->lastDpBlockStart; i++)
408  {
409  if(p_GetExp (p, i, r) != 0)
410  {
411  break;
412  }
413  }
414  if(i >= c->lastDpBlockStart)
415  {
416  //wrp(p);
417  //PrintS("\n");
418  return TRUE;
419  }
420  else
421  return FALSE;
422  }
423  else
424  return FALSE;
425 }
426 
427 static int get_last_dp_block_start (ring r)
428 {
429  //ring r=c->r;
430  int last_block;
431 
433  {
434  last_block = rBlocks (r) - 3;
435  }
436  else
437  {
438  last_block = rBlocks (r) - 2;
439  }
440  assume (last_block >= 0);
441  if(r->order[last_block] == ringorder_dp)
442  return r->block0[last_block];
443  return (currRing->N) + 1;
444 }
445 
446 static wlen_type do_pELength (poly p, slimgb_alg * c, int dlm = -1)
447 {
448  if(p == NULL)
449  return 0;
450  wlen_type s = 0;
451  poly pi = p;
452  if(dlm < 0)
453  {
454  dlm = c->pTotaldegree (p);
455  s = 1;
456  pi = p->next;
457  }
458 
459  while(pi)
460  {
461  int d = c->pTotaldegree (pi);
462  if(d > dlm)
463  s += 1 + d - dlm;
464  else
465  ++s;
466  pi = pi->next;
467  }
468  return s;
469 }
470 
471 wlen_type pELength (poly p, slimgb_alg * c, ring /*r*/)
472 {
473  if(p == NULL)
474  return 0;
475  wlen_type s = 0;
476  poly pi = p;
477  int dlm;
478  dlm = c->pTotaldegree (p);
479  s = 1;
480  pi = p->next;
481 
482  while(pi)
483  {
484  int d = c->pTotaldegree (pi);
485  if(d > dlm)
486  s += 1 + d - dlm;
487  else
488  ++s;
489  pi = pi->next;
490  }
491  return s;
492 }
493 
495 {
496  wlen_type s = 0;
497  if(lm == NULL)
498  {
499  lm = kBucketGetLm (b);
500  }
501  if(lm == NULL)
502  return 0;
503  if(elength_is_normal_length (lm, ca))
504  {
505  return bucket_guess (b);
506  }
507  int d = ca->pTotaldegree (lm);
508 #if 0
509  assume (sugar >= d);
510  s = 1 + (bucket_guess (b) - 1) * (sugar - d + 1);
511  return s;
512 #else
513 
514  //int d=pTotaldegree(lm,ca->r);
515  int i;
516  for(i = b->buckets_used; i >= 0; i--)
517  {
518  if(b->buckets[i] == NULL)
519  continue;
520 
521  if((ca->pTotaldegree (b->buckets[i]) <= d)
522  && (elength_is_normal_length (b->buckets[i], ca)))
523  {
524  s += b->buckets_length[i];
525  }
526  else
527  {
528  s += do_pELength (b->buckets[i], ca, d);
529  }
530  }
531  return s;
532 #endif
533 }
534 
535 static inline int pELength (poly p, slimgb_alg * c, int l)
536 {
537  if(p == NULL)
538  return 0;
539  if((l > 0) && (elength_is_normal_length (p, c)))
540  return l;
541  return do_pELength (p, c);
542 }
543 
544 static inline wlen_type pQuality (poly p, slimgb_alg * c, int l = -1)
545 {
546  if(l < 0)
547  l = pLength (p);
548  if(c->isDifficultField)
549  {
550  if(c->eliminationProblem)
551  {
552  wlen_type cs;
553  number coef = pGetCoeff (p);
554  if(rField_is_Q (currRing))
555  {
556  cs = nlQlogSize (coef, currRing->cf);
557  }
558  else
559  cs = nSize (coef);
560  wlen_type erg = cs;
561  if(TEST_V_COEFSTRAT)
562  erg *= cs;
563  //erg*=cs;//for quadratic
564  erg *= pELength (p, c, l);
565  //FIXME: not quadratic coeff size
566  //return cs*pELength(p,c,l);
567  return erg;
568  }
569  //PrintS("I am here");
570  wlen_type r = pSLength (p, l);
571  assume (r >= 0);
572  return r;
573  }
574  if(c->eliminationProblem)
575  return pELength (p, c, l);
576  return l;
577 }
578 
579 static inline int pTotaldegree_full (poly p)
580 {
581  int r = 0;
582  while(p)
583  {
584  int d = pTotaldegree (p);
585  r = si_max (r, d);
586  pIter (p);
587  }
588  return r;
589 }
590 
592 {
593  //works at the moment only for lenvar 1, because in different
594  //case, you have to look on coefs
595  wlen_type s = 0;
596  if(c->isDifficultField)
597  {
598  //s=kSBucketLength(bucket,this->p);
599  if(c->eliminationProblem)
600  {
601  wlen_type cs;
602  number coef;
603 
604  coef = pGetCoeff (kBucketGetLm (bucket));
605  //c=nSize(pGetCoeff(kBucketGetLm(b)));
606 
607  //c=nSize(pGetCoeff(lm));
608  if(rField_is_Q (currRing))
609  {
610  cs = nlQlogSize (coef, currRing->cf);
611  }
612  else
613  cs = nSize (coef);
614 #ifdef HAVE_COEF_BUCKETS
615  if(bucket->coef[0] != NULL)
616  {
617  if(rField_is_Q (currRing))
618  {
619  int modifier = nlQlogSize (pGetCoeff (bucket->coef[0]), currRing->cf);
620  cs += modifier;
621  }
622  else
623  {
624  int modifier = nSize (pGetCoeff (bucket->coef[0]));
625  cs *= modifier;
626  }
627  }
628 #endif
629  //FIXME:not quadratic
630  wlen_type erg = kEBucketLength (this->bucket, this->p, c);
631  //erg*=cs;//for quadratic
632  erg *= cs;
633  if(TEST_V_COEFSTRAT)
634  erg *= cs;
635  //return cs*kEBucketLength(this->bucket,this->p,c);
636  return erg;
637  }
639  }
640  else
641  {
642  if(c->eliminationProblem)
643  //if (false)
644  s = kEBucketLength (this->bucket, this->p, c);
645  else
646  s = bucket_guess (bucket);
647  }
648  return s;
649 }
650 
651 #if 0 //currently unused
652 static void finalize_reduction_step (reduction_step * r)
653 {
654  delete r;
655 }
656 #endif
657 #if 0 //currently unused
658 static int LObject_better_gen (const void *ap, const void *bp)
659 {
660  LObject *a = *(LObject **) ap;
661  LObject *b = *(LObject **) bp;
662  return (pLmCmp (a->p, b->p));
663 }
664 #endif
665 static int red_object_better_gen (const void *ap, const void *bp)
666 {
667  return (pLmCmp (((red_object *) ap)->p, ((red_object *) bp)->p));
668 }
669 
670 #if 0 //currently unused
671 static int pLmCmp_func_inverted (const void *ap1, const void *ap2)
672 {
673  poly p1, p2;
674  p1 = *((poly *) ap1);
675  p2 = *((poly *) ap2);
676  return -pLmCmp (p1, p2);
677 }
678 #endif
679 
680 int tgb_pair_better_gen2 (const void *ap, const void *bp)
681 {
682  return (-tgb_pair_better_gen (ap, bp));
683 }
684 
686 {
687  poly p = obj.p;
688  if ((strat->syzComp>0) && (pGetComp(p)>strat->syzComp)) return -1;
689  long not_sev = ~obj.sev;
690  for(int i = 0; i <= strat->sl; i++)
691  {
692  if(pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev))
693  return i;
694  }
695  return -1;
696 }
697 
698 int kFindDivisibleByInS_easy (kStrategy strat, poly p, long sev)
699 {
700  if ((strat->syzComp>0) && (pGetComp(p)>strat->syzComp)) return -1;
701  long not_sev = ~sev;
702  for(int i = 0; i <= strat->sl; i++)
703  {
704  if(pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev))
705  return i;
706  }
707  return -1;
708 }
709 
710 static int
712  slimgb_alg * c, int an = 0)
713 {
714  if(pn == 0)
715  return 0;
716 
717  int length = pn - 1;
718  int i;
719  //int an = 0;
720  int en = length;
721 
722  if(pair_better (qe, p[en], c))
723  return length + 1;
724 
725  while(1)
726  {
727  //if (an >= en-1)
728  if(en - 1 <= an)
729  {
730  if(pair_better (p[an], qe, c))
731  return an;
732  return en;
733  }
734  i = (an + en) / 2;
735  if(pair_better (p[i], qe, c))
736  en = i;
737  else
738  an = i;
739  }
740 }
741 
742 static BOOLEAN ascending (int *i, int top)
743 {
744  if(top < 1)
745  return TRUE;
746  if(i[top] < i[top - 1])
747  return FALSE;
748  return ascending (i, top - 1);
749 }
750 
752  sorted_pair_node ** q, int qn, slimgb_alg * c)
753 {
754  int i;
755  int *a = (int *) omalloc (qn * sizeof (int));
756 // int mc;
757 // PrintS("Debug\n");
758 // for(mc=0;mc<qn;mc++)
759 // {
760 // wrp(q[mc]->lcm_of_lm);
761 // PrintS("\n");
762 // }
763 // PrintS("Debug they are in\n");
764 // for(mc=0;mc<pn;mc++)
765 // {
766 // wrp(p[mc]->lcm_of_lm);
767 // PrintS("\n");
768 // }
769  int lastpos = 0;
770  for(i = 0; i < qn; i++)
771  {
772  lastpos = posInPairs (p, pn, q[i], c, si_max (lastpos - 1, 0));
773  // cout<<lastpos<<"\n";
774  a[i] = lastpos;
775  }
776  if((pn + qn) > c->max_pairs)
777  {
778  p =
780  2 * (pn +
781  qn) *
782  sizeof (sorted_pair_node *));
783  c->max_pairs = 2 * (pn + qn);
784  }
785  for(i = qn - 1; i >= 0; i--)
786  {
787  size_t size;
788  if(qn - 1 > i)
789  size = (a[i + 1] - a[i]) * sizeof (sorted_pair_node *);
790  else
791  size = (pn - a[i]) * sizeof (sorted_pair_node *); //as indices begin with 0
792  memmove (p + a[i] + (1 + i), p + a[i], size);
793  p[a[i] + i] = q[i];
794  }
795  omFree (a);
796  return p;
797 }
798 
799 static BOOLEAN
800 trivial_syzygie (int pos1, int pos2, poly bound, slimgb_alg * c)
801 {
802  poly p1 = c->S->m[pos1];
803  poly p2 = c->S->m[pos2];
804 
805  if(pGetComp (p1) > 0 || pGetComp (p2) > 0)
806  return FALSE;
807  int i = 1;
808  poly m = NULL;
809  poly gcd1 = c->gcd_of_terms[pos1];
810  poly gcd2 = c->gcd_of_terms[pos2];
811 
812  if((gcd1 != NULL) && (gcd2 != NULL))
813  {
814  gcd1->next = gcd2; //may ordered incorrect
815  m = gcd_of_terms (gcd1, c->r);
816  gcd1->next = NULL;
817  }
818  if(m == NULL)
819  {
820  loop
821  {
822  if(pGetExp (p1, i) + pGetExp (p2, i) > pGetExp (bound, i))
823  return FALSE;
824  if(i == (currRing->N))
825  {
826  //PrintS("trivial");
827  return TRUE;
828  }
829  i++;
830  }
831  }
832  else
833  {
834  loop
835  {
836  if(pGetExp (p1, i) - pGetExp (m, i) + pGetExp (p2, i) >
837  pGetExp (bound, i))
838  {
839  pDelete (&m);
840  return FALSE;
841  }
842  if(i == (currRing->N))
843  {
844  pDelete (&m);
845  //PrintS("trivial");
846  return TRUE;
847  }
848  i++;
849  }
850  }
851 }
852 
853 //! returns position sets w as weight
854 int find_best (red_object * r, int l, int u, wlen_type & w, slimgb_alg * c)
855 {
856  int best = l;
857  int i;
858  w = r[l].guess_quality (c);
859  for(i = l + 1; i <= u; i++)
860  {
861  wlen_type w2 = r[i].guess_quality (c);
862  if(w2 < w)
863  {
864  w = w2;
865  best = i;
866  }
867  }
868  return best;
869 }
870 
872 {
874 }
875 
877 {
878  assume (i >= 0);
879  assume (j >= 0);
880  if(has_t_rep (i, j, c))
881  return TRUE;
882  //poly lm=pOne();
883  assume (c->tmp_lm != NULL);
884  poly lm = c->tmp_lm;
885 
886  pLcm (c->S->m[i], c->S->m[j], lm);
887  pSetm (lm);
888  assume (lm != NULL);
889  //int deciding_deg= pTotaldegree(lm);
890  int *i_con = make_connections (i, j, lm, c);
891  //p_Delete(&lm,c->r);
892 
893  for(int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++)
894  {
895  if(i_con[n] == j)
896  {
897  now_t_rep (i, j, c);
898  omFree (i_con);
899  return TRUE;
900  }
901  }
902  omFree (i_con);
903 
904  return FALSE;
905 }
906 
908 {
909  int i;
910  for(i = 0; i <= strat->sl; i++)
911  {
912  if(strat->lenS[i] != pLength (strat->S[i]))
913  return FALSE;
914  }
915  return TRUE;
916 }
917 
918 
919 static void cleanS (kStrategy strat, slimgb_alg * c)
920 {
921  int i = 0;
922  LObject P;
923  while(i <= strat->sl)
924  {
925  P.p = strat->S[i];
926  P.sev = strat->sevS[i];
927  //int dummy=strat->sl;
928  //if(kFindDivisibleByInS(strat,&dummy,&P)!=i)
929  if(kFindDivisibleByInS_easy (strat, P.p, P.sev) != i)
930  {
931  deleteInS (i, strat);
932  //remember destroying poly
933  BOOLEAN found = FALSE;
934  int j;
935  for(j = 0; j < c->n; j++)
936  {
937  if(c->S->m[j] == P.p)
938  {
939  found = TRUE;
940  break;
941  }
942  }
943  if(!found)
944  pDelete (&P.p);
945  //remember additional reductors
946  }
947  else
948  i++;
949  }
950 }
951 
952 static int bucket_guess (kBucket * bucket)
953 {
954  int sum = 0;
955  int i;
956  for(i = bucket->buckets_used; i >= 0; i--)
957  {
958  if(bucket->buckets[i])
959  sum += bucket->buckets_length[i];
960  }
961  return sum;
962 }
963 
964 static int
965 add_to_reductors (slimgb_alg * c, poly h, int len, int ecart,
966  BOOLEAN simplified)
967 {
968  //inDebug(h);
969  assume (lenS_correct (c->strat));
970  assume (len == pLength (h));
971  int i;
972 // if (c->isDifficultField)
973 // i=simple_posInS(c->strat,h,pSLength(h,len),c->isDifficultField);
974 // else
975 // i=simple_posInS(c->strat,h,len,c->isDifficultField);
976 
977  LObject P;
978  memset (&P, 0, sizeof (P));
979  P.tailRing = c->r;
980  P.p = h; /*p_Copy(h,c->r); */
981  P.ecart = ecart;
982  P.FDeg = c->r->pFDeg (P.p, c->r);
983  if(!(simplified))
984  {
986  {
987  p_Cleardenom (P.p, c->r); //includes p_Content(P.p,c->r );
988  }
989  else
990  pNorm (P.p);
991  //pNormalize (P.p);
992  }
993  wlen_type pq = pQuality (h, c, len);
994  i = simple_posInS (c->strat, h, len, pq);
995  c->strat->enterS (P, i, c->strat, -1);
996 
997  c->strat->lenS[i] = len;
998  assume (pLength (c->strat->S[i]) == c->strat->lenS[i]);
999  if(c->strat->lenSw != NULL)
1000  c->strat->lenSw[i] = pq;
1001 
1002  return i;
1003 }
1004 
1005 static void length_one_crit (slimgb_alg * c, int pos, int len)
1006 {
1007  if(c->nc)
1008  return;
1009  if(len == 1)
1010  {
1011  int i;
1012  for(i = 0; i < pos; i++)
1013  {
1014  if(c->lengths[i] == 1)
1015  c->states[pos][i] = HASTREP;
1016  }
1017  for(i = pos + 1; i < c->n; i++)
1018  {
1019  if(c->lengths[i] == 1)
1020  c->states[i][pos] = HASTREP;
1021  }
1022  if(!c->nc)
1023  shorten_tails (c, c->S->m[pos]);
1024  }
1025 }
1026 
1027 static void move_forward_in_S (int old_pos, int new_pos, kStrategy strat)
1028 {
1029  assume (old_pos >= new_pos);
1030  poly p = strat->S[old_pos];
1031  int ecart = strat->ecartS[old_pos];
1032  long sev = strat->sevS[old_pos];
1033  int s_2_r = strat->S_2_R[old_pos];
1034  int length = strat->lenS[old_pos];
1035  assume (length == pLength (strat->S[old_pos]));
1036  wlen_type length_w;
1037  if(strat->lenSw != NULL)
1038  length_w = strat->lenSw[old_pos];
1039  int i;
1040  for(i = old_pos; i > new_pos; i--)
1041  {
1042  strat->S[i] = strat->S[i - 1];
1043  strat->ecartS[i] = strat->ecartS[i - 1];
1044  strat->sevS[i] = strat->sevS[i - 1];
1045  strat->S_2_R[i] = strat->S_2_R[i - 1];
1046  }
1047  if(strat->lenS != NULL)
1048  for(i = old_pos; i > new_pos; i--)
1049  strat->lenS[i] = strat->lenS[i - 1];
1050  if(strat->lenSw != NULL)
1051  for(i = old_pos; i > new_pos; i--)
1052  strat->lenSw[i] = strat->lenSw[i - 1];
1053 
1054  strat->S[new_pos] = p;
1055  strat->ecartS[new_pos] = ecart;
1056  strat->sevS[new_pos] = sev;
1057  strat->S_2_R[new_pos] = s_2_r;
1058  strat->lenS[new_pos] = length;
1059  if(strat->lenSw != NULL)
1060  strat->lenSw[new_pos] = length_w;
1061  //assume(lenS_correct(strat));
1062 }
1063 
1064 static void move_backward_in_S (int old_pos, int new_pos, kStrategy strat)
1065 {
1066  assume (old_pos <= new_pos);
1067  poly p = strat->S[old_pos];
1068  int ecart = strat->ecartS[old_pos];
1069  long sev = strat->sevS[old_pos];
1070  int s_2_r = strat->S_2_R[old_pos];
1071  int length = strat->lenS[old_pos];
1072  assume (length == pLength (strat->S[old_pos]));
1073  wlen_type length_w;
1074  if(strat->lenSw != NULL)
1075  length_w = strat->lenSw[old_pos];
1076  int i;
1077  for(i = old_pos; i < new_pos; i++)
1078  {
1079  strat->S[i] = strat->S[i + 1];
1080  strat->ecartS[i] = strat->ecartS[i + 1];
1081  strat->sevS[i] = strat->sevS[i + 1];
1082  strat->S_2_R[i] = strat->S_2_R[i + 1];
1083  }
1084  if(strat->lenS != NULL)
1085  for(i = old_pos; i < new_pos; i++)
1086  strat->lenS[i] = strat->lenS[i + 1];
1087  if(strat->lenSw != NULL)
1088  for(i = old_pos; i < new_pos; i++)
1089  strat->lenSw[i] = strat->lenSw[i + 1];
1090 
1091  strat->S[new_pos] = p;
1092  strat->ecartS[new_pos] = ecart;
1093  strat->sevS[new_pos] = sev;
1094  strat->S_2_R[new_pos] = s_2_r;
1095  strat->lenS[new_pos] = length;
1096  if(strat->lenSw != NULL)
1097  strat->lenSw[new_pos] = length_w;
1098  //assume(lenS_correct(strat));
1099 }
1100 
1101 static int *make_connections (int from, int to, poly bound, slimgb_alg * c)
1102 {
1103  ideal I = c->S;
1104  int *cans = (int *) omAlloc (c->n * sizeof (int));
1105  int *connected = (int *) omAlloc (c->n * sizeof (int));
1106  cans[0] = to;
1107  int cans_length = 1;
1108  connected[0] = from;
1109  int last_cans_pos = -1;
1110  int connected_length = 1;
1111  long neg_bounds_short = ~p_GetShortExpVector (bound, c->r);
1112 
1113  int not_yet_found = cans_length;
1114  int con_checked = 0;
1115  int pos;
1116 
1117  while(TRUE)
1118  {
1119  if((con_checked < connected_length) && (not_yet_found > 0))
1120  {
1121  pos = connected[con_checked];
1122  for(int i = 0; i < cans_length; i++)
1123  {
1124  if(cans[i] < 0)
1125  continue;
1126  //FIXME: triv. syz. does not hold on noncommutative, check it for modules
1127  if((has_t_rep (pos, cans[i], c))
1128  || ((!rIsPluralRing (c->r))
1129  && (trivial_syzygie (pos, cans[i], bound, c))))
1130  {
1131  connected[connected_length] = cans[i];
1132  connected_length++;
1133  cans[i] = -1;
1134  --not_yet_found;
1135 
1136  if(connected[connected_length - 1] == to)
1137  {
1138  if(connected_length < c->n)
1139  {
1140  connected[connected_length] = -1;
1141  }
1142  omFree (cans);
1143  return connected;
1144  }
1145  }
1146  }
1147  con_checked++;
1148  }
1149  else
1150  {
1151  for(last_cans_pos++; last_cans_pos <= c->n; last_cans_pos++)
1152  {
1153  if(last_cans_pos == c->n)
1154  {
1155  if(connected_length < c->n)
1156  {
1157  connected[connected_length] = -1;
1158  }
1159  omFree (cans);
1160  return connected;
1161  }
1162  if((last_cans_pos == from) || (last_cans_pos == to))
1163  continue;
1165  (I->m[last_cans_pos], c->short_Exps[last_cans_pos], bound,
1166  neg_bounds_short, c->r))
1167  {
1168  cans[cans_length] = last_cans_pos;
1169  cans_length++;
1170  break;
1171  }
1172  }
1173  not_yet_found++;
1174  for(int i = 0; i < con_checked; i++)
1175  {
1176  if(has_t_rep (connected[i], last_cans_pos, c))
1177  {
1178  connected[connected_length] = last_cans_pos;
1179  connected_length++;
1180  cans[cans_length - 1] = -1;
1181  --not_yet_found;
1182  if(connected[connected_length - 1] == to)
1183  {
1184  if(connected_length < c->n)
1185  {
1186  connected[connected_length] = -1;
1187  }
1188  omFree (cans);
1189  return connected;
1190  }
1191  break;
1192  }
1193  }
1194  }
1195  }
1196  if(connected_length < c->n)
1197  {
1198  connected[connected_length] = -1;
1199  }
1200  omFree (cans);
1201  return connected;
1202 }
1203 
1204 #ifdef HEAD_BIN
1205 static inline poly p_MoveHead (poly p, omBin b)
1206 {
1207  poly np;
1208  omTypeAllocBin (poly, np, b);
1209  memmove (np, p, omSizeWOfBin(b) * sizeof (long));
1210  omFreeBinAddr (p);
1211  return np;
1212 }
1213 #endif
1214 
1215 static void replace_pair (int &i, int &j, slimgb_alg * c)
1216 {
1217  if(i < 0)
1218  return;
1219  c->soon_free = NULL;
1220  int syz_deg;
1221  poly lm = pOne ();
1222 
1223  pLcm (c->S->m[i], c->S->m[j], lm);
1224  pSetm (lm);
1225 
1226  int *i_con = make_connections (i, j, lm, c);
1227 
1228  for(int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++)
1229  {
1230  if(i_con[n] == j)
1231  {
1232  now_t_rep (i, j, c);
1233  omFree (i_con);
1234  p_Delete (&lm, c->r);
1235  return;
1236  }
1237  }
1238 
1239  int *j_con = make_connections (j, i, lm, c);
1240 
1241 // if(c->n>1)
1242 // {
1243 // if (i_con[1]>=0)
1244 // i=i_con[1];
1245 // else
1246 // {
1247 // if (j_con[1]>=0)
1248 // j=j_con[1];
1249 // }
1250  // }
1251 
1252  int sugar = syz_deg = c->pTotaldegree (lm);
1253 
1254  p_Delete (&lm, c->r);
1255  if(c->T_deg_full) //Sugar
1256  {
1257  int t_i = c->T_deg_full[i] - c->T_deg[i];
1258  int t_j = c->T_deg_full[j] - c->T_deg[j];
1259  sugar += si_max (t_i, t_j);
1260  //Print("\n max: %d\n",max(t_i,t_j));
1261  }
1262 
1263  for(int m = 0; ((m < c->n) && (i_con[m] >= 0)); m++)
1264  {
1265  if(c->T_deg_full != NULL)
1266  {
1267  int s1 = c->T_deg_full[i_con[m]] + syz_deg - c->T_deg[i_con[m]];
1268  if(s1 > sugar)
1269  continue;
1270  }
1271  if(c->weighted_lengths[i_con[m]] < c->weighted_lengths[i])
1272  i = i_con[m];
1273  }
1274  for(int m = 0; ((m < c->n) && (j_con[m] >= 0)); m++)
1275  {
1276  if(c->T_deg_full != NULL)
1277  {
1278  int s1 = c->T_deg_full[j_con[m]] + syz_deg - c->T_deg[j_con[m]];
1279  if(s1 > sugar)
1280  continue;
1281  }
1282  if(c->weighted_lengths[j_con[m]] < c->weighted_lengths[j])
1283  j = j_con[m];
1284  }
1285 
1286  //can also try dependend search
1287  omFree (i_con);
1288  omFree (j_con);
1289  return;
1290 }
1291 
1292 static void add_later (poly p, const char *prot, slimgb_alg * c)
1293 {
1294  int i = 0;
1295  //check, if it is already in the queue
1296 
1297  while(c->add_later->m[i] != NULL)
1298  {
1299  if(p_LmEqual (c->add_later->m[i], p, c->r))
1300  return;
1301  i++;
1302  }
1303  if(TEST_OPT_PROT)
1304  PrintS (prot);
1305  c->add_later->m[i] = p;
1306 }
1307 
1308 static int simple_posInS (kStrategy strat, poly p, int len, wlen_type wlen)
1309 {
1310  if(strat->sl == -1)
1311  return 0;
1312  if(strat->lenSw)
1313  return pos_helper (strat, p, (wlen_type) wlen, (wlen_set) strat->lenSw,
1314  strat->S);
1315  return pos_helper (strat, p, len, strat->lenS, strat->S);
1316 }
1317 
1318 /*2
1319  *if the leading term of p
1320  *divides the leading term of some S[i] it will be canceled
1321  */
1322 static inline void
1323 clearS (poly p, unsigned long p_sev, int l, int *at, int *k, kStrategy strat)
1324 {
1325  assume (p_sev == pGetShortExpVector (p));
1326  if(!pLmShortDivisibleBy (p, p_sev, strat->S[*at], ~strat->sevS[*at]))
1327  return;
1328  if(l >= strat->lenS[*at])
1329  return;
1330  if(TEST_OPT_PROT)
1331  PrintS ("!");
1332  mflush ();
1333  //pDelete(&strat->S[*at]);
1334  deleteInS ((*at), strat);
1335  (*at)--;
1336  (*k)--;
1337 // assume(lenS_correct(strat));
1338 }
1339 
1340 static int iq_crit (const void *ap, const void *bp)
1341 {
1342  sorted_pair_node *a = *((sorted_pair_node **) ap);
1343  sorted_pair_node *b = *((sorted_pair_node **) bp);
1344  assume (a->i > a->j);
1345  assume (b->i > b->j);
1346 
1347  if(a->deg < b->deg)
1348  return -1;
1349  if(a->deg > b->deg)
1350  return 1;
1351  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
1352  if(comp != 0)
1353  return comp;
1354  if(a->expected_length < b->expected_length)
1355  return -1;
1356  if(a->expected_length > b->expected_length)
1357  return 1;
1358  if(a->j > b->j)
1359  return 1;
1360  if(a->j < b->j)
1361  return -1;
1362  return 0;
1363 }
1364 
1365 static wlen_type coeff_mult_size_estimate (int s1, int s2, ring r)
1366 {
1367  if(rField_is_Q (r))
1368  return s1 + s2;
1369  else
1370  return s1 * s2;
1371 }
1372 
1374 {
1375  if((c->isDifficultField) && (c->eliminationProblem))
1376  {
1377  int c1 = slim_nsize (p_GetCoeff (c->S->m[i], c->r), c->r);
1378  int c2 = slim_nsize (p_GetCoeff (c->S->m[j], c->r), c->r);
1379  wlen_type el1 = c->weighted_lengths[i] / c1;
1380  assume (el1 != 0);
1381  assume (c->weighted_lengths[i] % c1 == 0);
1382  wlen_type el2 = c->weighted_lengths[j] / c2;
1383  assume (el2 != 0);
1384  //assume (c->weighted_lengths[j] % c2 == 0); // fails in Tst/Plural/dmod_lib.tst
1385  //should be * for function fields
1386  //return (c1+c2) * (el1+el2-2);
1387  wlen_type res = coeff_mult_size_estimate (c1, c2, c->r);
1388  res *= el1 + el2 - 2;
1389  return res;
1390 
1391  }
1392  if(c->isDifficultField)
1393  {
1394  //int cs=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r)+
1395  // slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r);
1396  if(!(TEST_V_COEFSTRAT))
1397  {
1398  wlen_type cs =
1400  (p_GetCoeff (c->S->m[i], c->r), c->r),
1401  slim_nsize (p_GetCoeff (c->S->m[j], c->r),
1402  c->r), c->r);
1403  return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs;
1404  }
1405  else
1406  {
1407 
1408  wlen_type cs =
1410  (p_GetCoeff (c->S->m[i], c->r), c->r),
1411  slim_nsize (p_GetCoeff (c->S->m[j], c->r),
1412  c->r), c->r);
1413  cs *= cs;
1414  return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs;
1415  }
1416  }
1417  if(c->eliminationProblem)
1418  {
1419 
1420  return (c->weighted_lengths[i] + c->weighted_lengths[j] - 2);
1421  }
1422  return c->lengths[i] + c->lengths[j] - 2;
1423 
1424 }
1425 
1427  int *ip)
1428 {
1429  p_Test (h, c->r);
1430  assume (h != NULL);
1431  poly got = gcd_of_terms (h, c->r);
1432  if((got != NULL) && (TEST_V_UPTORADICAL))
1433  {
1434  poly copy = p_Copy (got, c->r);
1435  //p_wrp(got,c->r);
1436  BOOLEAN changed = monomial_root (got, c->r);
1437  if(changed)
1438  {
1439  poly div_by = pMDivide (copy, got);
1440  poly iter = h;
1441  while(iter)
1442  {
1443  pExpVectorSub (iter, div_by);
1444  pIter (iter);
1445  }
1446  p_Delete (&div_by, c->r);
1447  PrintS ("U");
1448  }
1449  p_Delete (&copy, c->r);
1450  }
1451 
1452 #define ENLARGE(pointer, type) pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type))
1453 
1454 #define ENLARGE_ALIGN(pointer, type) {if(pointer)\
1455  pointer=(type*)omReallocAligned(pointer, c->array_lengths*sizeof(type));\
1456  else pointer=(type*)omAllocAligned(c->array_lengths*sizeof(type));}
1457 // BOOLEAN corr=lenS_correct(c->strat);
1458  int sugar;
1459  int ecart = 0;
1460  ++(c->n);
1461  ++(c->S->ncols);
1462  int i, j;
1463  i = c->n - 1;
1464  sorted_pair_node **nodes =
1465  (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i);
1466  int spc = 0;
1467  if(c->n > c->array_lengths)
1468  {
1469  c->array_lengths = c->array_lengths * 2;
1470  assume (c->array_lengths >= c->n);
1471  ENLARGE (c->T_deg, int);
1472  ENLARGE_ALIGN (c->tmp_pair_lm, poly);
1474 
1475  ENLARGE_ALIGN (c->short_Exps, long);
1476  ENLARGE (c->lengths, int);
1477 #ifndef HAVE_BOOST
1478 #ifndef USE_STDVECBOOL
1479 
1480  ENLARGE_ALIGN (c->states, char *);
1481 #endif
1482 #endif
1483  ENLARGE_ALIGN (c->gcd_of_terms, poly);
1484  //if (c->weighted_lengths!=NULL) {
1486  //}
1487  //ENLARGE_ALIGN(c->S->m,poly);
1488  }
1489  pEnlargeSet (&c->S->m, c->n - 1, 1);
1490  if(c->T_deg_full)
1491  ENLARGE (c->T_deg_full, int);
1492  sugar = c->T_deg[i] = c->pTotaldegree (h);
1493  if(c->T_deg_full)
1494  {
1495  sugar = c->T_deg_full[i] = c->pTotaldegree_full (h);
1496  ecart = sugar - c->T_deg[i];
1497  assume (ecart >= 0);
1498  }
1499  c->tmp_pair_lm[i] = pOne_Special (c->r);
1500 
1501  c->tmp_spn[i] = (sorted_pair_node *) omAlloc (sizeof (sorted_pair_node));
1502 
1503  c->lengths[i] = pLength (h);
1504 
1505  //necessary for correct weighted length
1506 
1508  {
1509  p_Cleardenom (h, c->r); //includes p_Content(h,c->r);
1510  }
1511  else
1512  pNorm (h);
1513  //pNormalize (h);
1514 
1515  c->weighted_lengths[i] = pQuality (h, c, c->lengths[i]);
1516  c->gcd_of_terms[i] = got;
1517 #ifdef HAVE_BOOST
1518  c->states.push_back (dynamic_bitset <> (i));
1519 
1520 #else
1521 #ifdef USE_STDVECBOOL
1522 
1523  c->states.push_back (vector < bool > (i));
1524 
1525 #else
1526  if(i > 0)
1527  c->states[i] = (char *) omAlloc (i * sizeof (char));
1528  else
1529  c->states[i] = NULL;
1530 #endif
1531 #endif
1532 
1533  c->S->m[i] = h;
1534  c->short_Exps[i] = p_GetShortExpVector (h, c->r);
1535 
1536 #undef ENLARGE
1537 #undef ENLARGE_ALIGN
1538  if(p_GetComp (h, currRing) <= c->syz_comp)
1539  {
1540  for(j = 0; j < i; j++)
1541  {
1542 
1543 
1544 #ifndef HAVE_BOOST
1545  c->states[i][j] = UNCALCULATED;
1546 #endif
1547  assume (p_LmDivisibleBy (c->S->m[i], c->S->m[j], c->r) ==
1548  p_LmShortDivisibleBy (c->S->m[i], c->short_Exps[i], c->S->m[j],
1549  ~(c->short_Exps[j]), c->r));
1550 
1551  if(__p_GetComp (c->S->m[i], c->r) != __p_GetComp (c->S->m[j], c->r))
1552  {
1553  //c->states[i][j]=UNCALCULATED;
1554  //WARNUNG: be careful
1555  continue;
1556  }
1557  else if((!c->nc) && (c->lengths[i] == 1) && (c->lengths[j] == 1))
1558  {
1559  c->states[i][j] = HASTREP;
1560  }
1561  else if(((!c->nc) || (c->is_homog && rIsSCA (c->r)))
1562  && (pHasNotCF (c->S->m[i], c->S->m[j])))
1563 // else if ((!(c->nc)) && (pHasNotCF(c->S->m[i],c->S->m[j])))
1564  {
1565  c->easy_product_crit++;
1566  c->states[i][j] = HASTREP;
1567  continue;
1568  }
1569  else
1571  (c->S->m[i], c->gcd_of_terms[i], c->S->m[j], c->gcd_of_terms[j],
1572  c))
1573  {
1574  c->states[i][j] = HASTREP;
1575  c->extended_product_crit++;
1576  //PrintS("E");
1577  }
1578  // if (c->states[i][j]==UNCALCULATED)
1579  // {
1580 
1581  if((TEST_V_FINDMONOM) && (!c->nc))
1582  {
1583  //PrintS("COMMU");
1584  // if (c->lengths[i]==c->lengths[j])
1585  // {
1586 // poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
1587 // if (short_s==NULL)
1588 // {
1589 // c->states[i][j]=HASTREP;
1590 // }
1591 // else
1592 // {
1593 // p_Delete(&short_s, currRing);
1594 // }
1595 // }
1596  if(c->lengths[i] + c->lengths[j] == 3)
1597  {
1598 
1599 
1600  poly short_s = ksCreateShortSpoly (c->S->m[i], c->S->m[j], c->r);
1601  if(short_s == NULL)
1602  {
1603  c->states[i][j] = HASTREP;
1604  }
1605  else
1606  {
1607  assume (pLength (short_s) == 1);
1608  if(TEST_V_UPTORADICAL)
1609  monomial_root (short_s, c->r);
1610  int iS = kFindDivisibleByInS_easy (c->strat, short_s,
1611  p_GetShortExpVector (short_s,
1612  c->r));
1613  if(iS < 0)
1614  {
1615  //PrintS("N");
1616  if(TRUE)
1617  {
1618  c->states[i][j] = HASTREP;
1619  add_later (short_s, "N", c);
1620  }
1621  else
1622  p_Delete (&short_s, currRing);
1623  }
1624  else
1625  {
1626  if(c->strat->lenS[iS] > 1)
1627  {
1628  //PrintS("O");
1629  if(TRUE)
1630  {
1631  c->states[i][j] = HASTREP;
1632  add_later (short_s, "O", c);
1633  }
1634  else
1635  p_Delete (&short_s, currRing);
1636  }
1637  else
1638  p_Delete (&short_s, currRing);
1639  c->states[i][j] = HASTREP;
1640  }
1641 
1642 
1643  }
1644  }
1645  }
1646  // if (short_s)
1647  // {
1648  assume (spc <= j);
1649  sorted_pair_node *s = c->tmp_spn[spc]; //(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
1650  s->i = si_max (i, j);
1651  s->j = si_min (i, j);
1652  assume (s->j == j);
1653  s->expected_length = pair_weighted_length (i, j, c); //c->lengths[i]+c->lengths[j]-2;
1654 
1655  poly lm = c->tmp_pair_lm[spc]; //=pOne_Special();
1656 
1657  pLcm (c->S->m[i], c->S->m[j], lm);
1658  pSetm (lm);
1659  p_Test (lm, c->r);
1660  s->deg = c->pTotaldegree (lm);
1661 
1662  if(c->T_deg_full) //Sugar
1663  {
1664  int t_i = c->T_deg_full[s->i] - c->T_deg[s->i];
1665  int t_j = c->T_deg_full[s->j] - c->T_deg[s->j];
1666  s->deg += si_max (t_i, t_j);
1667  //Print("\n max: %d\n",max(t_i,t_j));
1668  }
1669  p_Test (lm, c->r);
1670  s->lcm_of_lm = lm;
1671  // pDelete(&short_s);
1672  //assume(lm!=NULL);
1673  nodes[spc] = s;
1674  spc++;
1675 
1676  // }
1677  //else
1678  //{
1679  //c->states[i][j]=HASTREP;
1680  //}
1681  }
1682  } //if syz_comp end
1683 
1684  assume (spc <= i);
1685  //now ideal quotient crit
1686  qsort (nodes, spc, sizeof (sorted_pair_node *), iq_crit);
1687 
1688  sorted_pair_node **nodes_final =
1689  (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i);
1690  int spc_final = 0;
1691  j = 0;
1692  while(j < spc)
1693  {
1694  int lower = j;
1695  int upper;
1696  BOOLEAN has = FALSE;
1697  for(upper = lower + 1; upper < spc; upper++)
1698  {
1699  if(!pLmEqual (nodes[lower]->lcm_of_lm, nodes[upper]->lcm_of_lm))
1700  {
1701  break;
1702  }
1703  if(has_t_rep (nodes[upper]->i, nodes[upper]->j, c))
1704  has = TRUE;
1705  }
1706  upper = upper - 1;
1707  int z;
1708  assume (spc_final <= j);
1709  for(z = 0; z < spc_final; z++)
1710  {
1711  if(p_LmDivisibleBy
1712  (nodes_final[z]->lcm_of_lm, nodes[lower]->lcm_of_lm, c->r))
1713  {
1714  has = TRUE;
1715  break;
1716  }
1717  }
1718 
1719  if(has)
1720  {
1721  for(; lower <= upper; lower++)
1722  {
1723  //free_sorted_pair_node(nodes[lower],c->r);
1724  //omfree(nodes[lower]);
1725  nodes[lower] = NULL;
1726  }
1727  j = upper + 1;
1728  continue;
1729  }
1730  else
1731  {
1732  p_Test (nodes[lower]->lcm_of_lm, c->r);
1733  nodes[lower]->lcm_of_lm = pCopy (nodes[lower]->lcm_of_lm);
1734  assume (__p_GetComp (c->S->m[nodes[lower]->i], c->r) ==
1735  __p_GetComp (c->S->m[nodes[lower]->j], c->r));
1736  nodes_final[spc_final] =
1737  (sorted_pair_node *) omAlloc (sizeof (sorted_pair_node));
1738 
1739  *(nodes_final[spc_final++]) = *(nodes[lower]);
1740  //c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
1741  nodes[lower] = NULL;
1742  for(lower = lower + 1; lower <= upper; lower++)
1743  {
1744  // free_sorted_pair_node(nodes[lower],c->r);
1745  //omfree(nodes[lower]);
1746  nodes[lower] = NULL;
1747  }
1748  j = upper + 1;
1749  continue;
1750  }
1751  }
1752 
1753  // Print("i:%d,spc_final:%d",i,spc_final);
1754 
1755  assume (spc_final <= spc);
1756  omFree (nodes);
1757  nodes = NULL;
1758 
1759  add_to_reductors (c, h, c->lengths[c->n - 1], ecart, TRUE);
1760  //i=posInS(c->strat,c->strat->sl,h,0 ecart);
1761  if(!(c->nc))
1762  {
1763  if(c->lengths[c->n - 1] == 1)
1764  shorten_tails (c, c->S->m[c->n - 1]);
1765  }
1766  //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths
1767 
1768  //for(i=c->strat->sl; i>0;i--)
1769  // if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i);
1770  if(c->Rcounter > 50)
1771  {
1772  c->Rcounter = 0;
1773  cleanS (c->strat, c);
1774  }
1775 
1776 #ifdef HAVE_PLURAL
1777  // for SCA:
1778  // here write at the end of nodes_final[spc_final,...,spc_final+lmdeg-1]
1779  if(rIsSCA (c->r))
1780  {
1781  const poly pNext = pNext (h);
1782 
1783  if(pNext != NULL)
1784  {
1785  // for additional polynomials
1786  const unsigned int m_iFirstAltVar = scaFirstAltVar (c->r);
1787  const unsigned int m_iLastAltVar = scaLastAltVar (c->r);
1788 
1789  int N = // c->r->N;
1790  m_iLastAltVar - m_iFirstAltVar + 1; // should be enough
1791  // TODO: but we may also use got = gcd({m}_{m\in f}))!
1792 
1793  poly *array_arg = (poly *) omalloc (N * sizeof (poly)); // !
1794  int j = 0;
1795 
1796 
1797  for(unsigned short v = m_iFirstAltVar; v <= m_iLastAltVar; v++)
1798  // for all x_v | Ann(lm(h))
1799  if(p_GetExp (h, v, c->r)) // TODO: use 'got' here!
1800  {
1801  assume (p_GetExp (h, v, c->r) == 1);
1802 
1803  poly p = sca_pp_Mult_xi_pp (v, pNext, c->r); // x_v * h;
1804 
1805  if(p != NULL) // if (x_v * h != 0)
1806  array_arg[j++] = p;
1807  } // for all x_v | Ann(lm(h))
1808 
1809  c->introduceDelayedPairs (array_arg, j);
1810 
1811  omFree (array_arg); // !!!
1812  }
1813 // PrintS("Saturation - done!!!\n");
1814  }
1815 #endif // if SCAlgebra
1816 
1817 
1818  if(!ip)
1819  {
1820  qsort (nodes_final, spc_final, sizeof (sorted_pair_node *),
1822 
1823 
1824  c->apairs =
1825  spn_merge (c->apairs, c->pair_top + 1, nodes_final, spc_final, c);
1826  c->pair_top += spc_final;
1828  omFree (nodes_final);
1829  return NULL;
1830  }
1831  {
1832  *ip = spc_final;
1833  return nodes_final;
1834  }
1835 }
1836 
1837 static poly redNF2 (poly h, slimgb_alg * c, int &len, number & m, int n)
1838 {
1839  m = nInit (1);
1840  if(h == NULL)
1841  return NULL;
1842 
1843  assume (len == pLength (h));
1844  kStrategy strat = c->strat;
1845  if(0 > strat->sl)
1846  {
1847  return h;
1848  }
1849  int j;
1850 
1851  LObject P (h);
1852  P.SetShortExpVector ();
1853  P.bucket = kBucketCreate (currRing);
1854  // BOOLEAN corr=lenS_correct(strat);
1855  kBucketInit (P.bucket, P.p, len /*pLength(P.p) */ );
1856  //wlen_set lenSw=(wlen_set) c->strat->lenS;
1857  //FIXME: plainly wrong
1858  //strat->lenS;
1859  //if (strat->lenSw!=NULL)
1860  // lenSw=strat->lenSw;
1861  //int max_pos=simple_posInS(strat,P.p);
1862  loop
1863  {
1864  //int dummy=strat->sl;
1865  j = kFindDivisibleByInS_easy (strat, P.p, P.sev);
1866  //j=kFindDivisibleByInS(strat,&dummy,&P);
1867  if((j >= 0) && ((!n) ||
1868  ((strat->lenS[j] <= n) &&
1869  ((strat->lenSw == NULL) || (strat->lenSw[j] <= n)))))
1870  {
1871  nNormalize (pGetCoeff (P.p));
1872 #ifdef KDEBUG
1873  if(TEST_OPT_DEBUG)
1874  {
1875  PrintS ("red:");
1876  wrp (h);
1877  PrintS (" with ");
1878  wrp (strat->S[j]);
1879  }
1880 #endif
1881 
1882  number coef = kBucketPolyRed (P.bucket, strat->S[j],
1883  strat->lenS[j] /*pLength(strat->S[j]) */ ,
1884  strat->kNoether);
1885  number m2 = nMult (m, coef);
1886  nDelete (&m);
1887  m = m2;
1888  nDelete (&coef);
1889  h = kBucketGetLm (P.bucket);
1890 
1891  if(h == NULL)
1892  {
1893  len = 0;
1894  kBucketDestroy (&P.bucket);
1895  return NULL;
1896  }
1897  P.p = h;
1898  P.t_p = NULL;
1899  P.SetShortExpVector ();
1900 #ifdef KDEBUG
1901  if(TEST_OPT_DEBUG)
1902  {
1903  PrintS ("\nto:");
1904  wrp (h);
1905  PrintLn ();
1906  }
1907 #endif
1908  }
1909  else
1910  {
1911  kBucketClear (P.bucket, &(P.p), &len);
1912  kBucketDestroy (&P.bucket);
1913  pNormalize (P.p);
1914  assume (len == (pLength (P.p)));
1915  return P.p;
1916  }
1917  }
1918 }
1919 
1920 static poly redTailShort (poly h, kStrategy strat)
1921 {
1922  if(h == NULL)
1923  return NULL; //n_Init(1,currRing);
1924  if(TEST_V_MODPSOLVSB)
1925  {
1926  bit_reduce (pNext (h), strat->tailRing);
1927  }
1928  int i;
1929  int len = pLength (h);
1930  for(i = 0; i <= strat->sl; i++)
1931  {
1932  if((strat->lenS[i] > 2)
1933  || ((strat->lenSw != NULL) && (strat->lenSw[i] > 2)))
1934  break;
1935  }
1936  return (redNFTail (h, i - 1, strat, len));
1937 }
1938 
1939 static void line_of_extended_prod (int fixpos, slimgb_alg * c)
1940 {
1941  if(c->gcd_of_terms[fixpos] == NULL)
1942  {
1943  c->gcd_of_terms[fixpos] = gcd_of_terms (c->S->m[fixpos], c->r);
1944  if(c->gcd_of_terms[fixpos])
1945  {
1946  int i;
1947  for(i = 0; i < fixpos; i++)
1948  if((c->states[fixpos][i] != HASTREP)
1949  &&
1951  (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i],
1952  c->gcd_of_terms[i], c)))
1953  {
1954  c->states[fixpos][i] = HASTREP;
1955  c->extended_product_crit++;
1956  }
1957  for(i = fixpos + 1; i < c->n; i++)
1958  if((c->states[i][fixpos] != HASTREP)
1959  &&
1961  (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i],
1962  c->gcd_of_terms[i], c)))
1963  {
1964  c->states[i][fixpos] = HASTREP;
1965  c->extended_product_crit++;
1966  }
1967  }
1968  }
1969 }
1970 
1971 static void c_S_element_changed_hook (int pos, slimgb_alg * c)
1972 {
1973  length_one_crit (c, pos, c->lengths[pos]);
1974  if(!c->nc)
1975  line_of_extended_prod (pos, c);
1976 }
1977 
1979 {
1980 public:
1981  poly p;
1984  int n;
1985  poly_tree_node (int sn):l (NULL), r (NULL), n (sn)
1986  {
1987  }
1988 };
1990 {
1991 public:
1993  int n;
1994  int get_n (poly p);
1996  {
1997  }
1998 };
2000 {
2001  poly_tree_node **node = &top_level;
2002  while(*node != NULL)
2003  {
2004  int c = pLmCmp (p, (*node)->p);
2005  if(c == 0)
2006  return (*node)->n;
2007  if(c == -1)
2008  node = &((*node)->r);
2009  else
2010  node = &((*node)->l);
2011  }
2012  (*node) = new poly_tree_node (n);
2013  n++;
2014  (*node)->p = pLmInit (p);
2015  return (*node)->n;
2016 }
2017 
2018 //mac_polys exp are smaller iff they are greater by monomial ordering
2019 //corresponding to solving linear equations notation
2020 
2022 {
2023  red_object r2 = ro;
2024  ro.validate ();
2025  if((r2.p != ro.p) || (r2.sev != ro.sev))
2026  return FALSE;
2027  return TRUE;
2028 }
2029 
2030 int terms_sort_crit (const void *a, const void *b)
2031 {
2032  return -pLmCmp (*((poly *) a), *((poly *) b));
2033 }
2034 
2035 #if 0 // currently unused
2036 static void unify_terms (poly * terms, int &sum)
2037 {
2038  if(sum == 0)
2039  return;
2040  int last = 0;
2041  int curr = 1;
2042  while(curr < sum)
2043  {
2044  if(!(pLmEqual (terms[curr], terms[last])))
2045  {
2046  terms[++last] = terms[curr];
2047  }
2048  ++curr;
2049  }
2050  sum = last + 1;
2051 }
2052 #endif
2053 #if 0 // currently unused
2054 static void
2055 export_mat (number * number_array, int pn, int tn, const char *format_str,
2056  int mat_nr)
2057 {
2058  char matname[20];
2059  sprintf (matname, format_str, mat_nr);
2060  FILE *out = fopen (matname, "w");
2061  int i, j;
2062  fprintf (out, "mat=[\n");
2063  for(i = 0; i < pn; i++)
2064  {
2065  fprintf (out, "[\n");
2066  for(j = 0; j < tn; j++)
2067  {
2068  if(j > 0)
2069  {
2070  fprintf (out, ", ");
2071  }
2072  fprintf (out, "%i", npInt (number_array[i * tn + j], currRing));
2073  }
2074  if(i < pn - 1)
2075  fprintf (out, "],\n");
2076  else
2077  fprintf (out, "],\n");
2078  }
2079  fprintf (out, "]\n");
2080  fclose (out);
2081 }
2082 #endif
2083 //typedef unsigned short number_type;
2084 
2085 
2086 #ifdef USE_NORO
2087 #ifndef NORO_CACHE
2088 static void
2089 linalg_step_modp (poly * p, poly * p_out, int &pn, poly * terms, int tn,
2090  slimgb_alg * c)
2091 {
2092  static int export_n = 0;
2093  assume (terms[tn - 1] != NULL);
2094  assume (rField_is_Zp (c->r));
2095  //I don't do deletes, copies of number_types ...
2096  const number_type zero = 0; //npInit(0);
2097  int array_size = pn * tn;
2098  number_type *number_array =
2099  (number_type *) omalloc (pn * tn * sizeof (number_type));
2100  int i;
2101  for(i = 0; i < array_size; i++)
2102  {
2103  number_array[i] = zero;
2104  }
2105  for(i = 0; i < pn; i++)
2106  {
2107  poly h = p[i];
2108  //int base=tn*i;
2109  write_poly_to_row (number_array + tn * i, h, terms, tn, c->r);
2110 
2111  }
2112 #if 0
2113  //export matrix
2114  export_mat (number_array, pn, tn, "mat%i.py", ++export_n);
2115 #endif
2116  int rank = pn;
2117  simplest_gauss_modp (number_array, rank, tn);
2118  int act_row = 0;
2119  int p_pos = 0;
2120  for(i = 0; i < pn; i++)
2121  {
2122  poly h = NULL;
2123  int j;
2124  int base = tn * i;
2125  number *row = number_array + base;
2126  h = row_to_poly (row, terms, tn, c->r);
2127 
2128  if(h != NULL)
2129  {
2130  p_out[p_pos++] = h;
2131  }
2132  }
2133  pn = p_pos;
2134  //assert(p_pos==rank)
2135  while(p_pos < pn)
2136  {
2137  p_out[p_pos++] = NULL;
2138  }
2139 #if 0
2140  export_mat (number_array, pn, tn, "mat%i.py", ++export_n);
2141 #endif
2142 }
2143 #endif
2144 #endif
2145 static void mass_add (poly * p, int pn, slimgb_alg * c)
2146 {
2147  int j;
2148  int *ibuf = (int *) omalloc (pn * sizeof (int));
2149  sorted_pair_node ***sbuf =
2150  (sorted_pair_node ***) omalloc (pn * sizeof (sorted_pair_node **));
2151  for(j = 0; j < pn; j++)
2152  {
2153  p_Test (p[j], c->r);
2154  sbuf[j] = add_to_basis_ideal_quotient (p[j], c, ibuf + j);
2155  }
2156  int sum = 0;
2157  for(j = 0; j < pn; j++)
2158  {
2159  sum += ibuf[j];
2160  }
2161  sorted_pair_node **big_sbuf =
2162  (sorted_pair_node **) omalloc (sum * sizeof (sorted_pair_node *));
2163  int partsum = 0;
2164  for(j = 0; j < pn; j++)
2165  {
2166  memmove (big_sbuf + partsum, sbuf[j],
2167  ibuf[j] * sizeof (sorted_pair_node *));
2168  omFree (sbuf[j]);
2169  partsum += ibuf[j];
2170  }
2171 
2172  qsort (big_sbuf, sum, sizeof (sorted_pair_node *), tgb_pair_better_gen2);
2173  c->apairs = spn_merge (c->apairs, c->pair_top + 1, big_sbuf, sum, c);
2174  c->pair_top += sum;
2176  omFree (big_sbuf);
2177  omFree (sbuf);
2178  omFree (ibuf);
2179  //omfree(buf);
2180 #ifdef TGB_DEBUG
2181  int z;
2182  for(z = 1; z <= c->pair_top; z++)
2183  {
2184  assume (pair_better (c->apairs[z], c->apairs[z - 1], c));
2185  }
2186 #endif
2187 
2188 }
2189 
2190 #ifdef NORO_CACHE
2191 #ifndef NORO_NON_POLY
2192 void NoroCache::evaluateRows ()
2193 {
2194  //after that can evaluate placeholders
2195  int i;
2196  buffer = (number *) omAlloc (nIrreducibleMonomials * sizeof (number));
2197  for(i = 0; i < root.branches_len; i++)
2198  {
2199  evaluateRows (1, root.branches[i]);
2200  }
2201  omFree (buffer);
2202  buffer = NULL;
2203 }
2204 
2205 void NoroCache::evaluateRows (int level, NoroCacheNode * node)
2206 {
2207  assume (level >= 0);
2208  if(node == NULL)
2209  return;
2210  if(level < (currRing->N))
2211  {
2212  int i, sum;
2213  for(i = 0; i < node->branches_len; i++)
2214  {
2215  evaluateRows (level + 1, node->branches[i]);
2216  }
2217  }
2218  else
2219  {
2220  DataNoroCacheNode *dn = (DataNoroCacheNode *) node;
2221  if(dn->value_len != backLinkCode)
2222  {
2223  poly p = dn->value_poly;
2224 #ifndef NORO_SPARSE_ROWS_PRE
2225  dn->row = new DenseRow ();
2226  DenseRow *row = dn->row;
2227  memset (buffer, 0, sizeof (number) * nIrreducibleMonomials);
2228 
2229  if(p == NULL)
2230  {
2231  row->array = NULL;
2232  row->begin = 0;
2233  row->end = 0;
2234  return;
2235  }
2236  int i = 0;
2237  int idx;
2238  number *a = buffer;
2239  while(p)
2240  {
2242 
2243  idx = ref->term_index;
2244  assume (idx >= 0);
2245  a[idx] = p_GetCoeff (p, currRing);
2246  if(i == 0)
2247  row->begin = idx;
2248  i++;
2249  pIter (p);
2250  }
2251  row->end = idx + 1;
2252  assume (row->end > row->begin);
2253  int len = row->end - row->begin;
2254  row->array = (number *) omalloc ((len) * sizeof (number));
2255  memcpy (row->array, a + row->begin, len * sizeof (number));
2256 #else
2257  assume (dn->value_len == pLength (dn->value_poly));
2258  dn->row = new SparseRow (dn->value_len);
2259  SparseRow *row = dn->row;
2260  int i = 0;
2261  while(p)
2262  {
2264 
2265  int idx = ref->term_index;
2266  assume (idx >= 0);
2267  row->idx_array[i] = idx;
2268  row->coef_array[i] = p_GetCoeff (p, currRing);
2269  i++;
2270  pIter (p);
2271  }
2272  if(i != dn->value_len)
2273  {
2274  PrintS ("F4 calc wrong, as poly len was wrong\n");
2275  }
2276  assume (i == dn->value_len);
2277 #endif
2278  }
2279  }
2280 }
2281 
2282 void
2283  NoroCache::evaluatePlaceHolder (number * row,
2284  std::vector < NoroPlaceHolder >
2285  &place_holders)
2286 {
2287  int i;
2288  int s = place_holders.size ();
2289  for(i = 0; i < s; i++)
2290  {
2291  DataNoroCacheNode *ref = place_holders[i].ref;
2292  number coef = place_holders[i].coef;
2293  if(ref->value_len == backLinkCode)
2294  {
2295  row[ref->term_index] = npAddM (row[ref->term_index], coef);
2296  }
2297  else
2298  {
2299 #ifndef NORO_SPARSE_ROWS_PRE
2300  DenseRow *ref_row = ref->row;
2301  if(ref_row == NULL)
2302  continue;
2303  number *ref_begin = ref_row->array;
2304  number *ref_end = ref_row->array + (ref_row->end - ref_row->begin);
2305  number *my_pos = row + ref_row->begin;
2306  //TODO npisOne distinction
2307  if(!(npIsOne (coef)))
2308  {
2309  while(ref_begin != ref_end)
2310  {
2311 
2312  *my_pos = npAddM (*my_pos, npMult (coef, *ref_begin));
2313  ++ref_begin;
2314  ++my_pos;
2315  }
2316  }
2317  else
2318  {
2319  while(ref_begin != ref_end)
2320  {
2321 
2322  *my_pos = npAddM (*my_pos, *ref_begin);
2323  ++ref_begin;
2324  ++my_pos;
2325  }
2326  }
2327 
2328 #else
2329  SparseRow *ref_row = ref->row;
2330  if(ref_row == NULL)
2331  continue;
2332  int n = ref_row->len;
2333  int j;
2334  int *idx_array = ref_row->idx_array;
2335  number *coef_array = ref_row->coef_array;
2336  for(j = 0; j < n; j++)
2337  {
2338  int idx = idx_array[j];
2339  number ref_coef = coef_array[j];
2340  row[idx] = npAddM (row[idx], npMult (coef, ref_coef));
2341  }
2342 #endif
2343  }
2344  }
2345 }
2346 #endif
2347 
2348 //poly noro_red_non_unique(poly p, int &len, NoroCache* cache,slimgb_alg* c);
2349 
2350 #ifndef NORO_NON_POLY
2351 MonRedRes
2352 noro_red_mon (poly t, BOOLEAN force_unique, NoroCache * cache, slimgb_alg * c)
2353 {
2354  MonRedRes res_holder;
2355 
2356  //wrp(t);
2357  res_holder.changed = TRUE;
2358  if(force_unique)
2359  {
2360  DataNoroCacheNode *ref = cache->getCacheReference (t);
2361  if(ref != NULL)
2362  {
2363  res_holder.len = ref->value_len;
2364  if(res_holder.len == NoroCache::backLinkCode)
2365  {
2366  res_holder.len = 1;
2367  }
2368  res_holder.coef = p_GetCoeff (t, c->r);
2369  res_holder.p = ref->value_poly;
2370  res_holder.ref = ref;
2371  res_holder.onlyBorrowed = TRUE;
2372  res_holder.changed = TRUE;
2373  p_Delete (&t, c->r);
2374  return res_holder;
2375  }
2376  }
2377  else
2378  {
2379  BOOLEAN succ;
2380  poly cache_lookup = cache->lookup (t, succ, res_holder.len); //don't own this yet
2381  if(succ)
2382  {
2383  if(cache_lookup == t)
2384  {
2385  //know they are equal
2386  //res_holder.len=1;
2387 
2388  res_holder.changed = FALSE;
2389  res_holder.p = t;
2390  res_holder.coef = npInit (1);
2391 
2392  res_holder.onlyBorrowed = FALSE;
2393  return res_holder;
2394  }
2395 
2396  res_holder.coef = p_GetCoeff (t, c->r);
2397  p_Delete (&t, c->r);
2398 
2399  res_holder.p = cache_lookup;
2400 
2401  res_holder.onlyBorrowed = TRUE;
2402  return res_holder;
2403 
2404  }
2405  }
2406 
2407  unsigned long sev = p_GetShortExpVector (t, currRing);
2408  int i = kFindDivisibleByInS_easy (c->strat, t, sev);
2409  if(i >= 0)
2410  {
2411  number coef_bak = p_GetCoeff (t, c->r);
2412 
2413  p_SetCoeff (t, npInit (1), c->r);
2414  assume (npIsOne (p_GetCoeff (c->strat->S[i], c->r)));
2415  number coefstrat = p_GetCoeff (c->strat->S[i], c->r);
2416 
2417  //poly t_copy_mon=p_Copy(t,c->r);
2418  poly exp_diff = cache->temp_term;
2419  p_ExpVectorDiff (exp_diff, t, c->strat->S[i], c->r);
2420  p_SetCoeff (exp_diff, npNeg (nInvers (coefstrat)), c->r);
2421  // nInvers may be npInvers or nvInvers
2422  p_Setm (exp_diff, c->r);
2423  assume (c->strat->S[i] != NULL);
2424  //poly t_to_del=t;
2425  poly res;
2426  res = pp_Mult_mm (pNext (c->strat->S[i]), exp_diff, c->r);
2427 
2428  res_holder.len = c->strat->lenS[i] - 1;
2429  res = noro_red_non_unique (res, res_holder.len, cache, c);
2430 
2431  DataNoroCacheNode *ref = cache->insert (t, res, res_holder.len);
2432  p_Delete (&t, c->r);
2433  //p_Delete(&t_copy_mon,c->r);
2434  //res=pMult_nn(res,coef_bak);
2435  res_holder.changed = TRUE;
2436  res_holder.p = res;
2437  res_holder.coef = coef_bak;
2438  res_holder.onlyBorrowed = TRUE;
2439  res_holder.ref = ref;
2440  return res_holder;
2441  }
2442  else
2443  {
2444  number coef_bak = p_GetCoeff (t, c->r);
2445  number one = npInit (1);
2446  p_SetCoeff (t, one, c->r);
2447  res_holder.len = 1;
2448  if(!(force_unique))
2449  {
2450  res_holder.ref = cache->insert (t, t, res_holder.len);
2451  p_SetCoeff (t, coef_bak, c->r);
2452  //return t;
2453 
2454  //we need distinction
2455  res_holder.changed = FALSE;
2456  res_holder.p = t;
2457 
2458  res_holder.coef = npInit (1);
2459  res_holder.onlyBorrowed = FALSE;
2460  return res_holder;
2461  }
2462  else
2463  {
2464  res_holder.ref = cache->insertAndTransferOwnerShip (t, c->r);
2465  res_holder.coef = coef_bak;
2466  res_holder.onlyBorrowed = TRUE;
2467  res_holder.changed = FALSE;
2468  res_holder.p = t;
2469  return res_holder;
2470  }
2471  }
2472 
2473 }
2474 #endif
2475 //SparseRow* noro_red_to_non_poly(poly p, int &len, NoroCache* cache,slimgb_alg* c);
2476 #ifndef NORO_NON_POLY
2477 //len input and out: Idea: reverse addition
2478 poly noro_red_non_unique (poly p, int &len, NoroCache * cache, slimgb_alg * c)
2479 {
2480  assume (len == pLength (p));
2481  poly orig_p = p;
2482  if(p == NULL)
2483  {
2484  len = 0;
2485  return NULL;
2486  }
2487  kBucket_pt bucket = kBucketCreate (currRing);
2488  kBucketInit (bucket, NULL, 0);
2489  poly unchanged_head = NULL;
2490  poly unchanged_tail = NULL;
2491  int unchanged_size = 0;
2492 
2493  while(p)
2494  {
2495  poly t = p;
2496  pIter (p);
2497  pNext (t) = NULL;
2498 #ifndef SING_NDEBUG
2499  number coef_debug = p_GetCoeff (t, currRing);
2500 #endif
2501  MonRedRes red = noro_red_mon (t, FALSE, cache, c);
2502  if((!(red.changed)) && (!(red.onlyBorrowed)))
2503  {
2504  unchanged_size++;
2505  assume (npIsOne (red.coef));
2506  assume (p_GetCoeff (red.p, currRing) == coef_debug);
2507  if(unchanged_head)
2508  {
2509  pNext (unchanged_tail) = red.p;
2510  pIter (unchanged_tail);
2511  }
2512  else
2513  {
2514  unchanged_tail = red.p;
2515  unchanged_head = red.p;
2516  }
2517  }
2518  else
2519  {
2520  assume (red.len == pLength (red.p));
2521  if(red.onlyBorrowed)
2522  {
2523  if(npIsOne (red.coef))
2524  {
2525  t = p_Copy (red.p, currRing);
2526  }
2527  else
2528  t = __pp_Mult_nn (red.p, red.coef, currRing);
2529  }
2530  else
2531  {
2532  if(npIsOne (red.coef))
2533  t = red.p;
2534  else
2535  t = __p_Mult_nn (red.p, red.coef, currRing);
2536  }
2537  kBucket_Add_q (bucket, t, &red.len);
2538  }
2539  }
2540  poly res = NULL;
2541  len = 0;
2542  kBucket_Add_q (bucket, unchanged_head, &unchanged_size);
2543  kBucketClear (bucket, &res, &len);
2544  kBucketDestroy (&bucket);
2545  return res;
2546 }
2547 #endif
2548 #ifdef NORO_SPARSE_ROWS_PRE
2549 //len input and out: Idea: reverse addition
2550 
2551 /*template <class number_type> SparseRow<number_type>* noro_red_to_non_poly(poly p, int &len, NoroCache<number_type>* cache,slimgb_alg* c)
2552  * {
2553  if (n_GetChar(currRing->cf)<255)
2554  {
2555  return noro_red_to_non_poly_t<tgb_uint8>(p,len,cache,c);
2556  }
2557  else
2558  {
2559  if (n_GetChar(currRing->cf)<65000)
2560  {
2561  return noro_red_to_non_poly_t<tgb_uint16>(p,len,cache,c);
2562  }
2563  else
2564  {
2565  return noro_red_to_non_poly_t<tgb_uint32>(p,len,cache,c);
2566  }
2567  }
2568 }*/
2569 #endif
2570 //len input and out: Idea: reverse addition
2571 #ifndef NORO_NON_POLY
2572 std::vector < NoroPlaceHolder > noro_red (poly p, int &len, NoroCache * cache,
2573  slimgb_alg * c)
2574 {
2575  std::vector < NoroPlaceHolder > res;
2576  while(p)
2577  {
2578  poly t = p;
2579  pIter (p);
2580  pNext (t) = NULL;
2581 
2582  MonRedRes red = noro_red_mon (t, TRUE, cache, c);
2583  assume (red.onlyBorrowed);
2584  assume (red.coef);
2585  assume (red.ref);
2586  NoroPlaceHolder h;
2587  h.ref = red.ref;
2588  h.coef = red.coef;
2589  assume (!((h.ref->value_poly == NULL) && (h.ref->value_len != 0)));
2590  if(h.ref->value_poly)
2591  res.push_back (h);
2592  }
2593  return res;
2594 }
2595 #endif
2596 
2597 #endif
2598 #ifdef USE_NORO
2599 #ifndef NORO_CACHE
2600 void noro_step (poly * p, int &pn, slimgb_alg * c)
2601 {
2602  poly *reduced = (poly *) omalloc (pn * sizeof (poly));
2603  int j;
2604  int *reduced_len = (int *) omalloc (pn * sizeof (int));
2605  int reduced_c = 0;
2606  //if (TEST_OPT_PROT)
2607  // PrintS("reduced system:\n");
2608 #ifdef NORO_CACHE
2609  NoroCache cache;
2610 #endif
2611  for(j = 0; j < pn; j++)
2612  {
2613 
2614  poly h = p[j];
2615  int h_len = pLength (h);
2616 
2617  number coef;
2618 #ifndef NORO_CACHE
2619  h = redNF2 (p_Copy (h, c->r), c, h_len, coef, 0);
2620 #else
2621  h = noro_red (p_Copy (h, c->r), h_len, &cache, c);
2622  assume (pLength (h) == h_len);
2623 #endif
2624  if(h != NULL)
2625  {
2626 #ifndef NORO_CACHE
2627 
2628  h = redNFTail (h, c->strat->sl, c->strat, h_len);
2629  h_len = pLength (h);
2630 #endif
2631  reduced[reduced_c] = h;
2632  reduced_len[reduced_c] = h_len;
2633  reduced_c++;
2634  if(TEST_OPT_PROT)
2635  Print ("%d ", h_len);
2636  }
2637  }
2638  int reduced_sum = 0;
2639  for(j = 0; j < reduced_c; j++)
2640  {
2641  reduced_sum += reduced_len[j];
2642  }
2643  poly *terms = (poly *) omalloc (reduced_sum * sizeof (poly));
2644  int tc = 0;
2645  for(j = 0; j < reduced_c; j++)
2646  {
2647  poly h = reduced[j];
2648 
2649  while(h != NULL)
2650  {
2651  terms[tc++] = h;
2652  pIter (h);
2653  assume (tc <= reduced_sum);
2654  }
2655  }
2656  assume (tc == reduced_sum);
2657  qsort (terms, reduced_sum, sizeof (poly), terms_sort_crit);
2658  int nterms = reduced_sum;
2659  //if (TEST_OPT_PROT)
2660  //Print("orig estimation:%i\n",reduced_sum);
2661  unify_terms (terms, nterms);
2662  //if (TEST_OPT_PROT)
2663  // Print("actual number of columns:%i\n",nterms);
2664  int rank = reduced_c;
2665  linalg_step_modp (reduced, p, rank, terms, nterms, c);
2666  omFree (terms);
2667 
2668  pn = rank;
2669  omFree (reduced);
2670 
2671  if(TEST_OPT_PROT)
2672  PrintS ("\n");
2673 }
2674 #else
2675 
2676 #endif
2677 #endif
2678 static void go_on (slimgb_alg * c)
2679 {
2680  //set limit of 1000 for multireductions, at the moment for
2681  //programming reasons
2682 #ifdef USE_NORO
2683  //Print("module rank%d\n",c->S->rank);
2684  const BOOLEAN use_noro = c->use_noro;
2685 #else
2686  const BOOLEAN use_noro = FALSE;
2687 #endif
2688  int i = 0;
2689  c->average_length = 0;
2690  for(i = 0; i < c->n; i++)
2691  {
2692  c->average_length += c->lengths[i];
2693  }
2694  c->average_length = c->average_length / c->n;
2695  i = 0;
2696  int max_pairs = bundle_size;
2697 
2698 #ifdef USE_NORO
2699  if((use_noro) || (c->use_noro_last_block))
2700  max_pairs = bundle_size_noro;
2701 #endif
2702  poly *p = (poly *) omAlloc ((max_pairs + 1) * sizeof (poly)); //nullterminated
2703 
2704  int curr_deg = -1;
2705  while(i < max_pairs)
2706  {
2707  sorted_pair_node *s = top_pair (c); //here is actually chain criterium done
2708 
2709  if(!s)
2710  break;
2711 
2712  if(curr_deg >= 0)
2713  {
2714  if(s->deg > curr_deg)
2715  break;
2716  }
2717 
2718  else
2719  curr_deg = s->deg;
2720  quick_pop_pair (c);
2721  if(s->i >= 0)
2722  {
2723  //be careful replace_pair use createShortSpoly which is not noncommutative
2724  now_t_rep (s->i, s->j, c);
2725  replace_pair (s->i, s->j, c);
2726 
2727  if(s->i == s->j)
2728  {
2729  free_sorted_pair_node (s, c->r);
2730  continue;
2731  }
2732  now_t_rep (s->i, s->j, c);
2733  }
2734  poly h;
2735  if(s->i >= 0)
2736  {
2737 #ifdef HAVE_PLURAL
2738  if(c->nc)
2739  {
2740  h = nc_CreateSpoly (c->S->m[s->i], c->S->m[s->j] /*, NULL */ , c->r);
2741 
2742  if(h != NULL)
2743  p_Cleardenom (h, c->r);
2744  }
2745  else
2746 #endif
2747  h = ksOldCreateSpoly (c->S->m[s->i], c->S->m[s->j], NULL, c->r);
2748  p_Test (h, c->r);
2749  }
2750  else
2751  {
2752  h = s->lcm_of_lm;
2753  p_Test (h, c->r);
2754  }
2755  // if(s->i>=0)
2756 // now_t_rep(s->j,s->i,c);
2757  number coef;
2758  int mlen = pLength (h);
2759  p_Test (h, c->r);
2760  if((!c->nc) & (!(use_noro)))
2761  {
2762  h = redNF2 (h, c, mlen, coef, 2);
2763  redTailShort (h, c->strat);
2764  nDelete (&coef);
2765  }
2766  p_Test (h, c->r);
2767  free_sorted_pair_node (s, c->r);
2768  if(!h)
2769  continue;
2770  p[i] = h;
2771  i++;
2772  }
2773  p[i] = NULL;
2774 // pre_comp(p,i,c);
2775  if(i == 0)
2776  {
2777  omFree (p);
2778  return;
2779  }
2780 #ifdef TGB_RESORT_PAIRS
2781  c->replaced = new bool[c->n];
2782  c->used_b = FALSE;
2783 #endif
2784 
2785  c->normal_forms += i;
2786  int j;
2787 #ifdef USE_NORO
2788  //if ((!(c->nc))&&(rField_is_Zp(c->r)))
2789  //{
2790  if(use_noro)
2791  {
2792  int pn = i;
2793  if(pn == 0)
2794  {
2795  omFree (p);
2796  return;
2797  }
2798  {
2799  if(n_GetChar(currRing->cf) < 255)
2800  {
2801  noro_step < tgb_uint8 > (p, pn, c);
2802  }
2803  else
2804  {
2805  if(n_GetChar(currRing->cf) < 65000)
2806  {
2807  noro_step < tgb_uint16 > (p, pn, c);
2808  }
2809  else
2810  {
2811  noro_step < tgb_uint32 > (p, pn, c);
2812  }
2813  }
2814  }
2815 
2816  //if (TEST_OPT_PROT)
2817  //{
2818  // Print("reported rank:%i\n",pn);
2819  //}
2820  mass_add (p, pn, c);
2821  omFree (p);
2822  return;
2823  /*if (TEST_OPT_PROT)
2824  for(j=0;j<pn;j++)
2825  {
2826  p_wrp(p[j],c->r);
2827  } */
2828  }
2829 #endif
2830  red_object *buf = (red_object *) omAlloc (i * sizeof (red_object)); /*i>0*/
2831  for(j = 0; j < i; j++)
2832  {
2833  p_Test (p[j], c->r);
2834  buf[j].p = p[j];
2835  buf[j].sev = pGetShortExpVector (p[j]);
2836  buf[j].bucket = kBucketCreate (currRing);
2837  p_Test (p[j], c->r);
2838  int len = pLength (p[j]);
2839  kBucketInit (buf[j].bucket, buf[j].p, len);
2840  buf[j].initial_quality = buf[j].guess_quality (c);
2841  assume (buf[j].initial_quality >= 0);
2842  }
2843  omFree (p);
2844  qsort (buf, i, sizeof (red_object), red_object_better_gen);
2845 // Print("\ncurr_deg:%i\n",curr_deg);
2846  if(TEST_OPT_PROT)
2847  {
2848  Print ("%dM[%d,", curr_deg, i);
2849  }
2850 
2851  multi_reduction (buf, i, c);
2852 #ifdef TGB_RESORT_PAIRS
2853  if(c->used_b)
2854  {
2855  if(TEST_OPT_PROT)
2856  PrintS ("B");
2857  int e;
2858  for(e = 0; e <= c->pair_top; e++)
2859  {
2860  if(c->apairs[e]->i < 0)
2861  continue;
2862  assume (c->apairs[e]->j >= 0);
2863  if((c->replaced[c->apairs[e]->i]) || (c->replaced[c->apairs[e]->j]))
2864  {
2865  sorted_pair_node *s = c->apairs[e];
2866  s->expected_length = pair_weighted_length (s->i, s->j, c);
2867  }
2868  }
2869  qsort (c->apairs, c->pair_top + 1, sizeof (sorted_pair_node *),
2871  }
2872 #endif
2873 #ifdef TGB_DEBUG
2874  {
2875  int k;
2876  for(k = 0; k < i; k++)
2877  {
2878  assume (kFindDivisibleByInS_easy (c->strat, buf[k]) < 0);
2879  int k2;
2880  for(k2 = 0; k2 < i; k2++)
2881  {
2882  if(k == k2)
2883  continue;
2884  assume ((!(p_LmDivisibleBy (buf[k].p, buf[k2].p, c->r)))
2885  || (wrp (buf[k].p), Print (" k %d k2 %d ", k, k2),
2886  wrp (buf[k2].p), FALSE));
2887  }
2888  }
2889  }
2890 #endif
2891  //resort S
2892 
2893  if(TEST_OPT_PROT)
2894  Print ("%i]", i);
2895 
2896  poly *add_those = (poly *) omalloc (i * sizeof (poly));
2897  for(j = 0; j < i; j++)
2898  {
2899  int len;
2900  poly p;
2901  buf[j].flatten ();
2902  kBucketClear (buf[j].bucket, &p, &len);
2903  kBucketDestroy (&buf[j].bucket);
2904  p_Test (p, c->r);
2905  //if (!c->nc) {
2906  if((c->tailReductions) || (lies_in_last_dp_block (p, c)))
2907  {
2908  p = redNFTail (p, c->strat->sl, c->strat, 0);
2909  }
2910  else
2911  {
2912  p = redTailShort (p, c->strat);
2913  }
2914  //}
2915  p_Test (p, c->r);
2916  add_those[j] = p;
2917 
2918  //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j);
2919  }
2920  mass_add (add_those, i, c);
2921  omFree (add_those);
2922  omFree (buf);
2923 
2924  if(TEST_OPT_PROT)
2925  Print ("(%d)", c->pair_top + 1);
2926  //TODO: implement that while(!(idIs0(c->add_later)))
2927 #ifdef TGB_RESORT_PAIRS
2928  delete c->replaced;
2929  c->replaced = NULL;
2930  c->used_b = FALSE;
2931 #endif
2932  return;
2933 }
2934 
2935 #ifdef REDTAIL_S
2936 
2937 static poly redNFTail (poly h, const int sl, kStrategy strat, int len)
2938 {
2939  if(h == NULL)
2940  return NULL;
2941  pTest (h);
2942  if(0 > sl)
2943  return h;
2944  if(pNext (h) == NULL)
2945  return h;
2947 
2948  int j;
2949  poly res = h;
2950  poly act = res;
2951  LObject P (pNext (h));
2952  pNext (res) = NULL;
2953  P.bucket = kBucketCreate (currRing);
2954  len--;
2955  h = P.p;
2956  if(len <= 0)
2957  len = pLength (h);
2958  kBucketInit (P.bucket, h /*P.p */ , len /*pLength(P.p) */ );
2959  pTest (h);
2960  loop
2961  {
2962  P.p = h;
2963  P.t_p = NULL;
2964  P.SetShortExpVector ();
2965  loop
2966  {
2967  //int dummy=strat->sl;
2968  j = kFindDivisibleByInS_easy (strat, P.p, P.sev); //kFindDivisibleByInS(strat,&dummy,&P);
2969  if(j >= 0)
2970  {
2971 #ifdef REDTAIL_PROT
2972  PrintS ("r");
2973 #endif
2974  nNormalize (pGetCoeff (P.p));
2975 #ifdef KDEBUG
2976  if(TEST_OPT_DEBUG)
2977  {
2978  PrintS ("red tail:");
2979  wrp (h);
2980  PrintS (" with ");
2981  wrp (strat->S[j]);
2982  }
2983 #endif
2984  number coef;
2985  pTest (strat->S[j]);
2986 #ifdef HAVE_PLURAL
2987  if(nc)
2988  {
2989  nc_kBucketPolyRed_Z (P.bucket, strat->S[j], &coef);
2990  }
2991  else
2992 #endif
2993  coef = kBucketPolyRed (P.bucket, strat->S[j],
2994  strat->lenS[j] /*pLength(strat->S[j]) */ ,
2995  strat->kNoether);
2996  res=__p_Mult_nn (res, coef, currRing);
2997  nDelete (&coef);
2998  h = kBucketGetLm (P.bucket);
2999  if(h == NULL)
3000  {
3001 #ifdef REDTAIL_PROT
3002  PrintS (" ");
3003 #endif
3004  kBucketDestroy (&P.bucket);
3005  return res;
3006  }
3007  P.p = h;
3008  P.t_p = NULL;
3009  P.SetShortExpVector ();
3010 #ifdef KDEBUG
3011  if(TEST_OPT_DEBUG)
3012  {
3013  PrintS ("\nto tail:");
3014  wrp (h);
3015  PrintLn ();
3016  }
3017 #endif
3018  }
3019  else
3020  {
3021 #ifdef REDTAIL_PROT
3022  PrintS ("n");
3023 #endif
3024  break;
3025  }
3026  } /* end loop current mon */
3027  // poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
3028  //act->next=tmp;pIter(act);
3029  act->next = kBucketExtractLm (P.bucket);
3030  pIter (act);
3031  h = kBucketGetLm (P.bucket);
3032  if(h == NULL)
3033  {
3034 #ifdef REDTAIL_PROT
3035  PrintS (" ");
3036 #endif
3037  kBucketDestroy (&P.bucket);
3038  return res;
3039  }
3040  pTest (h);
3041  }
3042 }
3043 #endif
3044 
3045 
3046 //try to fill, return FALSE iff queue is empty
3047 
3048 //transfers ownership of m to mat
3050 {
3051  assume (mat->mp[row] == NULL);
3052  mat->mp[row] = m;
3053 #ifdef TGB_DEBUG
3054  mac_poly r = m;
3055  while(r)
3056  {
3057  assume (r->exp < mat->columns);
3058  r = r->next;
3059  }
3060 #endif
3061 }
3062 
3063 poly
3064 free_row_to_poly (tgb_sparse_matrix * mat, int row, poly * monoms,
3065  int monom_index)
3066 {
3067  poly p = NULL;
3068  poly *set_this = &p;
3069  mac_poly r = mat->mp[row];
3070  mat->mp[row] = NULL;
3071  while(r)
3072  {
3073  (*set_this) = pLmInit (monoms[monom_index - 1 - r->exp]);
3074  pSetCoeff ((*set_this), r->coef);
3075  set_this = &((*set_this)->next);
3076  mac_poly old = r;
3077  r = r->next;
3078  delete old;
3079 
3080  }
3081  return p;
3082 }
3083 
3084 static int poly_crit (const void *ap1, const void *ap2)
3085 {
3086  poly p1, p2;
3087  p1 = *((poly *) ap1);
3088  p2 = *((poly *) ap2);
3089 
3090  int c = pLmCmp (p1, p2);
3091  if(c != 0)
3092  return c;
3093  int l1 = pLength (p1);
3094  int l2 = pLength (p2);
3095  if(l1 < l2)
3096  return -1;
3097  if(l1 > l2)
3098  return 1;
3099  return 0;
3100 }
3101 
3103 {
3104  if(s == 0)
3105  return;
3106  sorted_pair_node **si_array =
3107  (sorted_pair_node **) omAlloc (s * sizeof (sorted_pair_node *));
3108 
3109  for(int i = 0; i < s; i++)
3110  {
3111  sorted_pair_node *si =
3112  (sorted_pair_node *) omAlloc (sizeof (sorted_pair_node));
3113  si->i = -1;
3114  si->j = -2;
3115  poly p = pa[i];
3116  simplify_poly (p, r);
3117  si->expected_length = pQuality (p, this, pLength (p));
3118  p_Test (p, r);
3119  si->deg = this->pTotaldegree_full (p);
3120  /*if (!rField_is_Zp(r))
3121  {
3122  p_Content(p,r);
3123  p_Cleardenom(p,r);
3124  } */
3125 
3126  si->lcm_of_lm = p;
3127 
3128  // c->apairs[n-1-i]=si;
3129  si_array[i] = si;
3130  }
3131 
3132  qsort (si_array, s, sizeof (sorted_pair_node *), tgb_pair_better_gen2);
3133  apairs = spn_merge (apairs, pair_top + 1, si_array, s, this);
3134  pair_top += s;
3135  omFree (si_array);
3136 }
3137 
3138 slimgb_alg::slimgb_alg (ideal I, int syz_comp, BOOLEAN F4, int deg_pos)
3139 {
3140  this->deg_pos = deg_pos;
3141  lastCleanedDeg = -1;
3142  completed = FALSE;
3143  this->syz_comp = syz_comp;
3144  r = currRing;
3145  nc = rIsPluralRing (r);
3147  //Print("last dp Block start: %i\n", this->lastDpBlockStart);
3148  is_homog = TRUE;
3149  {
3150  int hzz;
3151  for(hzz = 0; hzz < IDELEMS (I); hzz++)
3152  {
3153  assume (I->m[hzz] != NULL);
3154  int d = this->pTotaldegree (I->m[hzz]);
3155  poly t = I->m[hzz]->next;
3156  while(t)
3157  {
3158  if(d != this->pTotaldegree (t))
3159  {
3160  is_homog = FALSE;
3161  break;
3162  }
3163  t = t->next;
3164  }
3165  if(!(is_homog))
3166  break;
3167  }
3168  }
3169  eliminationProblem = ((!(is_homog)) && ((currRing->pLexOrder) || (I->rank > 1)));
3170  tailReductions = ((is_homog) || ((TEST_OPT_REDTAIL) && (!(I->rank > 1))));
3171  // Print("is homog:%d",c->is_homog);
3172  void *h;
3173  int i;
3174  to_destroy = NULL;
3175  easy_product_crit = 0;
3177  if(rField_is_Zp (r))
3179  else
3181  //not fully correct
3182  //(rChar()==0);
3183  F4_mode = F4;
3184 
3185  reduction_steps = 0;
3186  last_index = -1;
3187 
3188  F = NULL;
3189  F_minus = NULL;
3190 
3191  Rcounter = 0;
3192 
3193  soon_free = NULL;
3194 
3195  tmp_lm = pOne ();
3196 
3197  normal_forms = 0;
3198  current_degree = 1;
3199 
3200  max_pairs = 5 * IDELEMS (I);
3201 
3202  apairs =
3203  (sorted_pair_node **) omAlloc (sizeof (sorted_pair_node *) * max_pairs);
3204  pair_top = -1;
3205 
3206  int n = IDELEMS (I);
3207  array_lengths = n;
3208 
3209 
3210  i = 0;
3211  this->n = 0;
3212  T_deg = (int *) omAlloc (n * sizeof (int));
3213  if(eliminationProblem)
3214  T_deg_full = (int *) omAlloc (n * sizeof (int));
3215  else
3216  T_deg_full = NULL;
3217  tmp_pair_lm = (poly *) omAlloc (n * sizeof (poly));
3218  tmp_spn = (sorted_pair_node **) omAlloc (n * sizeof (sorted_pair_node *));
3219  lm_bin = omGetSpecBin (POLYSIZE + (r->ExpL_Size) * sizeof (long));
3220 #ifdef HEAD_BIN
3221  HeadBin = omGetSpecBin (POLYSIZE + (currRing->ExpL_Size) * sizeof (long));
3222 #endif
3223  /* omUnGetSpecBin(&(c->HeadBin)); */
3224 #ifndef HAVE_BOOST
3225 #ifdef USE_STDVECBOOL
3226 #else
3227  h = omAlloc (n * sizeof (char *));
3228 
3229  states = (char **) h;
3230 #endif
3231 #endif
3232  h = omAlloc (n * sizeof (int));
3233  lengths = (int *) h;
3235  gcd_of_terms = (poly *) omAlloc (n * sizeof (poly));
3236 
3237  short_Exps = (long *) omAlloc (n * sizeof (long));
3238  if(F4_mode)
3239  S = idInit (n, I->rank);
3240  else
3241  S = idInit (1, I->rank);
3242  strat = new skStrategy;
3243  if(eliminationProblem)
3244  strat->honey = TRUE;
3245  strat->syzComp = syz_comp;
3249  strat->tailRing = r;
3250  strat->enterS = enterSBba;
3251  strat->sl = -1;
3252  i = n;
3253  i = 1; //some strange bug else
3254  /* initS(c->S,NULL,c->strat); */
3255  /* intS start: */
3256  // i=((i+IDELEMS(c->S)+15)/16)*16;
3257  strat->ecartS = (intset) omAlloc (i * sizeof (int)); /*initec(i); */
3258  strat->sevS = (unsigned long *) omAlloc0 (i * sizeof (unsigned long));
3259  /*initsevS(i); */
3260  strat->S_2_R = (int *) omAlloc0 (i * sizeof (int)); /*initS_2_R(i); */
3261  strat->fromQ = NULL;
3262  strat->Shdl = idInit (1, 1);
3263  strat->S = strat->Shdl->m;
3264  strat->lenS = (int *) omAlloc0 (i * sizeof (int));
3266  strat->lenSw = (wlen_type *) omAlloc0 (i * sizeof (wlen_type));
3267  else
3268  strat->lenSw = NULL;
3269  assume (n > 0);
3270  add_to_basis_ideal_quotient (I->m[0], this, NULL);
3271 
3272  assume (strat->sl == IDELEMS (strat->Shdl) - 1);
3273  if(!(F4_mode))
3274  {
3275  poly *array_arg = I->m;
3276  array_arg++;
3277  introduceDelayedPairs (array_arg, n - 1);
3278  /*
3279  for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
3280  {
3281  // add_to_basis(I->m[i],-1,-1,c);
3282  si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
3283  si->i=-1;
3284  si->j=-2;
3285  si->expected_length=pQuality(I->m[i],this,pLength(I->m[i]));
3286  si->deg=pTotaldegree(I->m[i]);
3287  if (!rField_is_Zp(r))
3288  {
3289  p_Cleardenom(I->m[i], r);
3290  }
3291  si->lcm_of_lm=I->m[i];
3292 
3293  // c->apairs[n-1-i]=si;
3294  apairs[n-i-1]=si;
3295  ++(pair_top);
3296  } */
3297  }
3298  else
3299  {
3300  for(i = 1; i < n; i++) //the 1 is wanted, because first element is added to basis
3301  add_to_basis_ideal_quotient (I->m[i], this, NULL);
3302  }
3303  for(i = 0; i < IDELEMS (I); i++)
3304  {
3305  I->m[i] = NULL;
3306  }
3307  idDelete (&I);
3308  add_later = idInit (ADD_LATER_SIZE, S->rank);
3309 #ifdef USE_NORO
3310  use_noro = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r))
3311  && (!(eliminationProblem)) && (n_GetChar(currRing->cf) <= 32003));
3312  use_noro_last_block = false;
3313  if((!(use_noro)) && (lastDpBlockStart <= (currRing->N)))
3314  {
3315  use_noro_last_block = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r))
3316  && (n_GetChar(currRing->cf) <= 32003));
3317  }
3318 #else
3319  use_noro = false;
3320  use_noro_last_block = false;
3321 #endif
3322  //Print("NORO last block %i",use_noro_last_block);
3323  memset (add_later->m, 0, ADD_LATER_SIZE * sizeof (poly));
3324 }
3325 
3327 {
3328 
3329  if(!(completed))
3330  {
3331  poly *add = (poly *) omAlloc ((pair_top + 2) * sizeof (poly));
3332  int piter;
3333  int pos = 0;
3334  for(piter = 0; piter <= pair_top; piter++)
3335  {
3336  sorted_pair_node *s = apairs[piter];
3337  if(s->i < 0)
3338  {
3339  //delayed element
3340  if(s->lcm_of_lm != NULL)
3341  {
3342  add[pos] = s->lcm_of_lm;
3343  pos++;
3344  }
3345  }
3347  apairs[piter] = NULL;
3348  }
3349  pair_top = -1;
3350  add[pos] = NULL;
3351  pos = 0;
3352  while(add[pos] != NULL)
3353  {
3354  add_to_basis_ideal_quotient (add[pos], this, NULL);
3355  pos++;
3356  }
3357  for(piter = 0; piter <= pair_top; piter++)
3358  {
3359  sorted_pair_node *s = apairs[piter];
3360  assume (s->i >= 0);
3362  apairs[piter] = NULL;
3363  }
3364  pair_top = -1;
3365  }
3366  id_Delete (&add_later, r);
3367  int i, j;
3368  slimgb_alg *c = this;
3369  while(c->to_destroy)
3370  {
3371  pDelete (&(c->to_destroy->p));
3372  poly_list_node *old = c->to_destroy;
3373  c->to_destroy = c->to_destroy->next;
3374  omFree (old);
3375  }
3376  while(c->F)
3377  {
3378  for(i = 0; i < c->F->size; i++)
3379  {
3380  pDelete (&(c->F->mp[i].m));
3381  }
3382  omFree (c->F->mp);
3383  c->F->mp = NULL;
3384  mp_array_list *old = c->F;
3385  c->F = c->F->next;
3386  omFree (old);
3387  }
3388  while(c->F_minus)
3389  {
3390  for(i = 0; i < c->F_minus->size; i++)
3391  {
3392  pDelete (&(c->F_minus->p[i]));
3393  }
3394  omFree (c->F_minus->p);
3395  c->F_minus->p = NULL;
3396  poly_array_list *old = c->F_minus;
3397  c->F_minus = c->F_minus->next;
3398  omFree (old);
3399  }
3400 #ifndef HAVE_BOOST
3401 #ifndef USE_STDVECBOOL
3402  for(int z = 1 /* zero length at 0 */ ; z < c->n; z++)
3403  {
3404  omFree (c->states[z]);
3405  }
3406  omFree (c->states);
3407 #endif
3408 #endif
3409 
3410  omFree (c->lengths);
3411  omFree (c->weighted_lengths);
3412  for(int z = 0; z < c->n; z++)
3413  {
3414  pDelete (&c->tmp_pair_lm[z]);
3415  omFree (c->tmp_spn[z]);
3416  }
3417  omFree (c->tmp_pair_lm);
3418  omFree (c->tmp_spn);
3419 
3420  omFree (c->T_deg);
3421  omfree (c->T_deg_full); /*c->T_deg_full my be NULL*/
3422 
3423  omFree (c->strat->ecartS);
3424  omFree (c->strat->sevS);
3425 // initsevS(i);
3426  omFree (c->strat->S_2_R);
3427 
3428 
3429  omFree (c->strat->lenS);
3430 
3431  if(c->strat->lenSw)
3432  omFree (c->strat->lenSw);
3433 
3434  for(i = 0; i < c->n; i++)
3435  {
3436  if(c->gcd_of_terms[i])
3437  pDelete (&(c->gcd_of_terms[i]));
3438  }
3439  omFree (c->gcd_of_terms);
3440 
3441  omFree (c->apairs);
3442  if(TEST_OPT_PROT)
3443  {
3444  //Print("calculated %d NFs\n",c->normal_forms);
3445  Print ("\nNF:%i product criterion:%i, ext_product criterion:%i \n",
3447  }
3448 
3449  for(i = 0; i <= c->strat->sl; i++)
3450  {
3451  if(!c->strat->S[i])
3452  continue;
3453  BOOLEAN found = FALSE;
3454  for(j = 0; j < c->n; j++)
3455  {
3456  if(c->S->m[j] == c->strat->S[i])
3457  {
3458  found = TRUE;
3459  break;
3460  }
3461  }
3462  if(!found)
3463  pDelete (&c->strat->S[i]);
3464  }
3465 // for(i=0;i<c->n;i++)
3466 // {
3467 // if (c->rep[i]!=i)
3468 // {
3469 // // for(j=0;j<=c->strat->sl;j++)
3470 // {
3471 // // if(c->strat->S[j]==c->S->m[i])
3472 // {
3473 // // c->strat->S[j]=NULL;
3474 // // break;
3475 // // }
3476 // // }
3477 // // PrintS("R_delete");
3478 // pDelete(&c->S->m[i]);
3479 // }
3480 // }
3481 
3482  if(completed)
3483  {
3484  for(i = 0; i < c->n; i++)
3485  {
3486  assume (c->S->m[i] != NULL);
3487  if(p_GetComp (c->S->m[i], currRing) > this->syz_comp)
3488  continue;
3489  for(j = 0; j < c->n; j++)
3490  {
3491  if((c->S->m[j] == NULL) || (i == j))
3492  continue;
3493  assume (p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],
3494  c->S->m[i], ~c->short_Exps[i],
3495  c->r) == p_LmDivisibleBy (c->S->m[j],
3496  c->S->m[i],
3497  c->r));
3498  if(p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],
3499  c->S->m[i], ~c->short_Exps[i], c->r))
3500  {
3501  pDelete (&c->S->m[i]);
3502  break;
3503  }
3504  }
3505  }
3506  }
3507  omFree (c->short_Exps);
3508 
3509  ideal I = c->S;
3510  IDELEMS (I) = c->n;
3511  idSkipZeroes (I);
3512  for(i = 0; i <= c->strat->sl; i++)
3513  c->strat->S[i] = NULL;
3514  id_Delete (&c->strat->Shdl, c->r);
3515  pDelete (&c->tmp_lm);
3517  delete c->strat;
3518 }
3519 
3520 ideal t_rep_gb (const ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode)
3521 {
3522  assume (r == currRing);
3523  ring orig_ring = r;
3524  int pos;
3525  ring new_ring = rAssure_TDeg (orig_ring, pos);
3526  ideal s_h;
3527  if(orig_ring != new_ring)
3528  {
3529  rChangeCurrRing (new_ring);
3530  s_h = idrCopyR_NoSort (arg_I, orig_ring, new_ring);
3531  /*int i;
3532  for(i=0;i<IDELEMS(s_h);i++)
3533  {
3534  poly p=s_h->m[i];
3535  while(p)
3536  {
3537  p_Setm(p,new_ring);
3538  pIter(p);
3539  }
3540  } */
3541  }
3542  else
3543  {
3544  s_h = id_Copy (arg_I, orig_ring);
3545  }
3546  idTest (s_h);
3547 
3548  ideal s_result = do_t_rep_gb (new_ring, s_h, syz_comp, F4_mode, pos);
3549  ideal result;
3550  if(orig_ring != new_ring)
3551  {
3552  idTest (s_result);
3553  rChangeCurrRing (orig_ring);
3554  result = idrMoveR_NoSort (s_result, new_ring, orig_ring);
3555 
3556  idTest (result);
3557  //rChangeCurrRing(new_ring);
3558  rDelete(new_ring);
3559  //rChangeCurrRing(orig_ring);
3560  }
3561  else
3562  result = s_result;
3563  idTest (result);
3564  return result;
3565 }
3566 
3567 ideal
3568 do_t_rep_gb (ring /*r*/, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
3569 {
3570  // Print("QlogSize(0) %d, QlogSize(1) %d,QlogSize(-2) %d, QlogSize(5) %d\n", QlogSize(nlInit(0)),QlogSize(nlInit(1)),QlogSize(nlInit(-2)),QlogSize(nlInit(5)));
3571 
3572  if(TEST_OPT_PROT)
3573  if(F4_mode)
3574  PrintS ("F4 Modus\n");
3575 
3576  //debug_Ideal=arg_debug_Ideal;
3577  //if (debug_Ideal) PrintS("DebugIdeal received\n");
3578  // Print("Idelems %i \n----------\n",IDELEMS(arg_I));
3579  ideal I = arg_I;
3580  id_Compactify (I,currRing);
3581  if(idIs0 (I))
3582  return I;
3583  int i;
3584  for(i = 0; i < IDELEMS (I); i++)
3585  {
3586  assume (I->m[i] != NULL);
3587  simplify_poly (I->m[i], currRing);
3588  }
3589 
3590  qsort (I->m, IDELEMS (I), sizeof (poly), poly_crit);
3591  //Print("Idelems %i \n----------\n",IDELEMS(I));
3592  //slimgb_alg* c=(slimgb_alg*) omalloc(sizeof(slimgb_alg));
3593  //int syz_comp=arg_I->rank;
3594  slimgb_alg *c = new slimgb_alg (I, syz_comp, F4_mode, deg_pos);
3595 
3596  while((c->pair_top >= 0)
3597  && ((!(TEST_OPT_DEGBOUND))
3598  || (c->apairs[c->pair_top]->deg <= Kstd1_deg)))
3599  {
3600 #ifdef HAVE_F4
3601  if(F4_mode)
3602  go_on_F4 (c);
3603  else
3604 #endif
3605  go_on (c);
3606  }
3607  if(c->pair_top < 0)
3608  c->completed = TRUE;
3609  I = c->S;
3610  delete c;
3611  if(TEST_OPT_REDSB)
3612  {
3613  ideal erg = kInterRed (I, NULL);
3614  assume (I != erg);
3615  id_Delete (&I, currRing);
3616  return erg;
3617  }
3618  //qsort(I->m, IDELEMS(I),sizeof(poly),pLmCmp_func);
3619  assume (I->rank >= id_RankFreeModule (I,currRing));
3620  return (I);
3621 }
3622 
3623 void now_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * c)
3624 {
3625  int i, j;
3626  if(arg_i == arg_j)
3627  {
3628  return;
3629  }
3630  if(arg_i > arg_j)
3631  {
3632  i = arg_j;
3633  j = arg_i;
3634  }
3635  else
3636  {
3637  i = arg_i;
3638  j = arg_j;
3639  }
3640  c->states[j][i] = HASTREP;
3641 }
3642 
3643 static BOOLEAN
3644 has_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * state)
3645 {
3646  assume (0 <= arg_i);
3647  assume (0 <= arg_j);
3648  assume (arg_i < state->n);
3649  assume (arg_j < state->n);
3650  if(arg_i == arg_j)
3651  {
3652  return (TRUE);
3653  }
3654  if(arg_i > arg_j)
3655  {
3656  return (state->states[arg_i][arg_j] == HASTREP);
3657  }
3658  else
3659  {
3660  return (state->states[arg_j][arg_i] == HASTREP);
3661  }
3662 }
3663 
3664 #if 0 // unused
3665 static int pLcmDeg (poly a, poly b)
3666 {
3667  int i;
3668  int n = 0;
3669  for(i = (currRing->N); i; i--)
3670  {
3671  n += si_max (pGetExp (a, i), pGetExp (b, i));
3672  }
3673  return n;
3674 }
3675 #endif
3676 
3677 static void shorten_tails (slimgb_alg * c, poly monom)
3678 {
3679  return;
3680 // BOOLEAN corr=lenS_correct(c->strat);
3681  for(int i = 0; i < c->n; i++)
3682  {
3683  //enter tail
3684 
3685  if(c->S->m[i] == NULL)
3686  continue;
3687  poly tail = c->S->m[i]->next;
3688  poly prev = c->S->m[i];
3689  BOOLEAN did_something = FALSE;
3690  while((tail != NULL) && (pLmCmp (tail, monom) >= 0))
3691  {
3692  if(p_LmDivisibleBy (monom, tail, c->r))
3693  {
3694  did_something = TRUE;
3695  prev->next = tail->next;
3696  tail->next = NULL;
3697  p_Delete (&tail, c->r);
3698  tail = prev;
3699  //PrintS("Shortened");
3700  c->lengths[i]--;
3701  }
3702  prev = tail;
3703  tail = tail->next;
3704  }
3705  if(did_something)
3706  {
3707  int new_pos;
3708  wlen_type q;
3709  q = pQuality (c->S->m[i], c, c->lengths[i]);
3710  new_pos = simple_posInS (c->strat, c->S->m[i], c->lengths[i], q);
3711 
3712  int old_pos = -1;
3713  //assume new_pos<old_pos
3714  for(int z = 0; z <= c->strat->sl; z++)
3715  {
3716  if(c->strat->S[z] == c->S->m[i])
3717  {
3718  old_pos = z;
3719  break;
3720  }
3721  }
3722  if(old_pos == -1)
3723  for(int z = new_pos - 1; z >= 0; z--)
3724  {
3725  if(c->strat->S[z] == c->S->m[i])
3726  {
3727  old_pos = z;
3728  break;
3729  }
3730  }
3731  assume (old_pos >= 0);
3732  assume (new_pos <= old_pos);
3733  assume (pLength (c->strat->S[old_pos]) == c->lengths[i]);
3734  c->strat->lenS[old_pos] = c->lengths[i];
3735  if(c->strat->lenSw)
3736  c->strat->lenSw[old_pos] = q;
3737  if(new_pos < old_pos)
3738  move_forward_in_S (old_pos, new_pos, c->strat);
3739  length_one_crit (c, i, c->lengths[i]);
3740  }
3741  }
3742 }
3743 
3744 #if 0 // currently unused
3745 static sorted_pair_node *pop_pair (slimgb_alg * c)
3746 {
3748 
3749  if(c->pair_top < 0)
3750  return NULL;
3751  else
3752  return (c->apairs[c->pair_top--]);
3753 }
3754 #endif
3755 
3756 void slimgb_alg::cleanDegs (int lower, int upper)
3757 {
3758  assume (is_homog);
3759  int deg;
3760  if(TEST_OPT_PROT)
3761  {
3762  PrintS ("C");
3763  }
3764  for(deg = lower; deg <= upper; deg++)
3765  {
3766  int i;
3767  for(i = 0; i < n; i++)
3768  {
3769  if(T_deg[i] == deg)
3770  {
3771  poly h;
3772  h = S->m[i];
3773  h = redNFTail (h, strat->sl, strat, lengths[i]);
3775  {
3776  p_Cleardenom (h, r); //includes p_Content(h,r);
3777  }
3778  else
3779  pNorm (h);
3780  //TODO:GCD of TERMS
3781  poly got =::gcd_of_terms (h, r);
3782  p_Delete (&gcd_of_terms[i], r);
3783  gcd_of_terms[i] = got;
3784  int len = pLength (h);
3785  wlen_type wlen = pQuality (h, this, len);
3786  if(weighted_lengths)
3787  weighted_lengths[i] = wlen;
3788  lengths[i] = len;
3789  assume (h == S->m[i]);
3790  int j;
3791  for(j = 0; j <= strat->sl; j++)
3792  {
3793  if(h == strat->S[j])
3794  {
3795  int new_pos = simple_posInS (strat, h, len, wlen);
3796  if(strat->lenS)
3797  {
3798  strat->lenS[j] = len;
3799  }
3800  if(strat->lenSw)
3801  {
3802  strat->lenSw[j] = wlen;
3803  }
3804  if(new_pos < j)
3805  {
3806  move_forward_in_S (j, new_pos, strat);
3807  }
3808  else
3809  {
3810  if(new_pos > j)
3811  new_pos = new_pos - 1; //is identical with one element
3812  if(new_pos > j)
3813  move_backward_in_S (j, new_pos, strat);
3814  }
3815  break;
3816  }
3817  }
3818  }
3819  }
3820  }
3821  {
3822  int i, j;
3823  for(i = 0; i < this->n; i++)
3824  {
3825  for(j = 0; j < i; j++)
3826  {
3827  if(T_deg[i] + T_deg[j] <= upper)
3828  {
3829  now_t_rep (i, j, this);
3830  }
3831  }
3832  }
3833  }
3834  //TODO resort and update strat->S,strat->lenSw
3835  //TODO mark pairs
3836 }
3837 
3839 {
3840  while(c->pair_top >= 0)
3841  {
3842  super_clean_top_of_pair_list (c); //yeah, I know, it's odd that I use a different proc here
3843  if((c->is_homog) && (c->pair_top >= 0)
3844  && (c->apairs[c->pair_top]->deg >= c->lastCleanedDeg + 2))
3845  {
3846  int upper = c->apairs[c->pair_top]->deg - 1;
3847  c->cleanDegs (c->lastCleanedDeg + 1, upper);
3848  c->lastCleanedDeg = upper;
3849  }
3850  else
3851  {
3852  break;
3853  }
3854  }
3855 
3856  if(c->pair_top < 0)
3857  return NULL;
3858  else
3859  return (c->apairs[c->pair_top]);
3860 }
3861 
3863 {
3864  if(c->pair_top < 0)
3865  return NULL;
3866  else
3867  return (c->apairs[c->pair_top--]);
3868 }
3869 
3871 {
3872  while((c->pair_top >= 0)
3873  && (c->apairs[c->pair_top]->i >= 0)
3874  &&
3876  (c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i, c)))
3877  {
3878  free_sorted_pair_node (c->apairs[c->pair_top], c->r);
3879  c->pair_top--;
3880  }
3881 }
3882 
3884 {
3885  while((c->pair_top >= 0) && (c->apairs[c->pair_top]->i >= 0)
3886  &&
3887  (!state_is
3888  (UNCALCULATED, c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,
3889  c)))
3890  {
3891  free_sorted_pair_node (c->apairs[c->pair_top], c->r);
3892  c->pair_top--;
3893  }
3894 }
3895 
3896 static BOOLEAN
3897 state_is (calc_state state, const int &arg_i, const int &arg_j,
3898  slimgb_alg * c)
3899 {
3900  assume (0 <= arg_i);
3901  assume (0 <= arg_j);
3902  assume (arg_i < c->n);
3903  assume (arg_j < c->n);
3904  if(arg_i == arg_j)
3905  {
3906  return (TRUE);
3907  }
3908  if(arg_i > arg_j)
3909  {
3910  return (c->states[arg_i][arg_j] == state);
3911  }
3912  else
3913  return (c->states[arg_j][arg_i] == state);
3914 }
3915 
3917 {
3918  if(s->i >= 0)
3919  p_Delete (&s->lcm_of_lm, r);
3920  omFree (s);
3921 }
3922 
3923 static BOOLEAN
3925 {
3926  if(a->deg < b->deg)
3927  return TRUE;
3928  if(a->deg > b->deg)
3929  return FALSE;
3930 
3931  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
3932  if(comp == 1)
3933  return FALSE;
3934  if(-1 == comp)
3935  return TRUE;
3936  if(a->expected_length < b->expected_length)
3937  return TRUE;
3938  if(a->expected_length > b->expected_length)
3939  return FALSE;
3940  if(a->i + a->j < b->i + b->j)
3941  return TRUE;
3942  if(a->i + a->j > b->i + b->j)
3943  return FALSE;
3944  if(a->i < b->i)
3945  return TRUE;
3946  if(a->i > b->i)
3947  return FALSE;
3948  return TRUE;
3949 }
3950 
3951 static int tgb_pair_better_gen (const void *ap, const void *bp)
3952 {
3953  sorted_pair_node *a = *((sorted_pair_node **) ap);
3954  sorted_pair_node *b = *((sorted_pair_node **) bp);
3955  assume ((a->i > a->j) || (a->i < 0));
3956  assume ((b->i > b->j) || (b->i < 0));
3957  if(a->deg < b->deg)
3958  return -1;
3959  if(a->deg > b->deg)
3960  return 1;
3961 
3962  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
3963 
3964  if(comp == 1)
3965  return 1;
3966  if(-1 == comp)
3967  return -1;
3968  if(a->expected_length < b->expected_length)
3969  return -1;
3970  if(a->expected_length > b->expected_length)
3971  return 1;
3972  if(a->i + a->j < b->i + b->j)
3973  return -1;
3974  if(a->i + a->j > b->i + b->j)
3975  return 1;
3976  if(a->i < b->i)
3977  return -1;
3978  if(a->i > b->i)
3979  return 1;
3980  return 0;
3981 }
3982 
3983 static poly gcd_of_terms (poly p, ring r)
3984 {
3985  int max_g_0 = 0;
3986  assume (p != NULL);
3987  int i;
3988  poly m = pOne ();
3989  poly t;
3990  for(i = (currRing->N); i; i--)
3991  {
3992  pSetExp (m, i, pGetExp (p, i));
3993  if(max_g_0 == 0)
3994  if(pGetExp (m, i) > 0)
3995  max_g_0 = i;
3996  }
3997 
3998  t = p->next;
3999  while(t != NULL)
4000  {
4001  if(max_g_0 == 0)
4002  break;
4003  for(i = max_g_0; i; i--)
4004  {
4005  pSetExp (m, i, si_min (pGetExp (t, i), pGetExp (m, i)));
4006  if(max_g_0 == i)
4007  if(pGetExp (m, i) == 0)
4008  max_g_0 = 0;
4009  if((max_g_0 == 0) && (pGetExp (m, i) > 0))
4010  {
4011  max_g_0 = i;
4012  }
4013  }
4014  t = t->next;
4015  }
4016  p_Setm (m, r);
4017  if(max_g_0 > 0)
4018  return m;
4019  pDelete (&m);
4020  return NULL;
4021 }
4022 
4023 static inline BOOLEAN pHasNotCFExtended (poly p1, poly p2, poly m)
4024 {
4025 
4026  if(pGetComp (p1) > 0 || pGetComp (p2) > 0)
4027  return FALSE;
4028  int i = 1;
4029  loop
4030  {
4031  if((pGetExp (p1, i) - pGetExp (m, i) > 0)
4032  && (pGetExp (p2, i) - pGetExp (m, i) > 0))
4033  return FALSE;
4034  if(i == (currRing->N))
4035  return TRUE;
4036  i++;
4037  }
4038 }
4039 
4040 //for impl reasons may return false if the the normal product criterion matches
4041 static inline BOOLEAN
4042 extended_product_criterion (poly p1, poly gcd1, poly p2, poly gcd2,
4043  slimgb_alg * c)
4044 {
4045  if(c->nc)
4046  return FALSE;
4047  if(gcd1 == NULL)
4048  return FALSE;
4049  if(gcd2 == NULL)
4050  return FALSE;
4051  gcd1->next = gcd2; //may ordered incorrect
4052  poly m = gcd_of_terms (gcd1, c->r);
4053  gcd1->next = NULL;
4054  if(m == NULL)
4055  return FALSE;
4056 
4057  BOOLEAN erg = pHasNotCFExtended (p1, p2, m);
4058  pDelete (&m);
4059  return erg;
4060 }
4061 
4062 #if 0 //currently unused
4063 static poly kBucketGcd (kBucket * b, ring r)
4064 {
4065  int s = 0;
4066  int i;
4067  poly m, n;
4068  BOOLEAN initialized = FALSE;
4069  for(i = MAX_BUCKET - 1; i >= 0; i--)
4070  {
4071  if(b->buckets[i] != NULL)
4072  {
4073  if(!initialized)
4074  {
4075  m = gcd_of_terms (b->buckets[i], r);
4076  initialized = TRUE;
4077  if(m == NULL)
4078  return NULL;
4079  }
4080  else
4081  {
4082  n = gcd_of_terms (b->buckets[i], r);
4083  if(n == NULL)
4084  {
4085  pDelete (&m);
4086  return NULL;
4087  }
4088  n->next = m;
4089  poly t = gcd_of_terms (n, r);
4090  n->next = NULL;
4091  pDelete (&m);
4092  pDelete (&n);
4093  m = t;
4094  if(m == NULL)
4095  return NULL;
4096 
4097  }
4098  }
4099  }
4100  return m;
4101 }
4102 #endif
4103 
4104 static inline wlen_type quality_of_pos_in_strat_S (int pos, slimgb_alg * c)
4105 {
4106  if(c->strat->lenSw != NULL)
4107  return c->strat->lenSw[pos];
4108  return c->strat->lenS[pos];
4109 }
4110 
4111 #ifdef HAVE_PLURAL
4112 static inline wlen_type
4114  //meant only for nc
4115 {
4116  poly m = pOne ();
4117  pExpVectorDiff (m, high, c->strat->S[pos]);
4118  poly product = nc_mm_Mult_pp (m, c->strat->S[pos], c->r);
4119  wlen_type erg = pQuality (product, c);
4120  pDelete (&m);
4121  pDelete (&product);
4122  return erg;
4123 }
4124 #endif
4125 
4126 static void
4128  find_erg & erg)
4129 {
4130  erg.expand = NULL;
4131  BOOLEAN swap_roles; //from reduce_by, to_reduce_u if fromS
4132  if(erg.fromS)
4133  {
4134  if(pLmEqual (c->strat->S[erg.reduce_by], los[erg.to_reduce_u].p))
4135  {
4136  wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
4137  int best = erg.to_reduce_u + 1;
4138 /*
4139  for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--)
4140  {
4141  int qc=los[i].guess_quality(c);
4142  if (qc<quality_a)
4143  {
4144  best=i;
4145  quality_a=qc;
4146  }
4147  }
4148  if(best!=erg.to_reduce_u+1)
4149  {*/
4150  wlen_type qc;
4151  best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);
4152  if(qc < quality_a)
4153  {
4154  los[best].flatten ();
4155  int b_pos = kBucketCanonicalize (los[best].bucket);
4156  los[best].p = los[best].bucket->buckets[b_pos];
4157  qc = pQuality (los[best].bucket->buckets[b_pos], c);
4158  if(qc < quality_a)
4159  {
4160  red_object h = los[erg.to_reduce_u];
4161  los[erg.to_reduce_u] = los[best];
4162  los[best] = h;
4163  swap_roles = TRUE;
4164  }
4165  else
4166  swap_roles = FALSE;
4167  }
4168  else
4169  {
4170  swap_roles = FALSE;
4171  }
4172  }
4173  else
4174  {
4175  if(erg.to_reduce_u > erg.to_reduce_l)
4176  {
4177  wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
4178 #ifdef HAVE_PLURAL
4179  if((c->nc) && (!(rIsSCA (c->r))))
4180  quality_a =
4182  los[erg.to_reduce_u].p, c);
4183 #endif
4184  int best = erg.to_reduce_u + 1;
4185  wlen_type qc;
4186  best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);
4187  assume (qc == los[best].guess_quality (c));
4188  if(qc < quality_a)
4189  {
4190  los[best].flatten ();
4191  int b_pos = kBucketCanonicalize (los[best].bucket);
4192  los[best].p = los[best].bucket->buckets[b_pos];
4193  qc = pQuality (los[best].bucket->buckets[b_pos], c);
4194  //(best!=erg.to_reduce_u+1)
4195  if(qc < quality_a)
4196  {
4197  red_object h = los[erg.to_reduce_u];
4198  los[erg.to_reduce_u] = los[best];
4199  los[best] = h;
4200  erg.reduce_by = erg.to_reduce_u;
4201  erg.fromS = FALSE;
4202  erg.to_reduce_u--;
4203  }
4204  }
4205  }
4206  else
4207  {
4208  assume (erg.to_reduce_u == erg.to_reduce_l);
4209  wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
4210  wlen_type qc = los[erg.to_reduce_u].guess_quality (c);
4211  if(qc < 0)
4212  PrintS ("Wrong wlen_type");
4213  if(qc < quality_a)
4214  {
4215  int best = erg.to_reduce_u;
4216  los[best].flatten ();
4217  int b_pos = kBucketCanonicalize (los[best].bucket);
4218  los[best].p = los[best].bucket->buckets[b_pos];
4219  qc = pQuality (los[best].bucket->buckets[b_pos], c);
4220  assume (qc >= 0);
4221  if(qc < quality_a)
4222  {
4223  BOOLEAN exp = FALSE;
4224  if(qc <= 2)
4225  {
4226  //Print("\n qc is %lld \n",qc);
4227  exp = TRUE;
4228  }
4229  else
4230  {
4231  if(qc < quality_a / 2)
4232  exp = TRUE;
4233  else if(erg.reduce_by < c->n / 4)
4234  exp = TRUE;
4235  }
4236  if(exp)
4237  {
4238  poly clear_into;
4239  los[erg.to_reduce_u].flatten ();
4240  kBucketClear (los[erg.to_reduce_u].bucket, &clear_into,
4241  &erg.expand_length);
4242  erg.expand = pCopy (clear_into);
4243  kBucketInit (los[erg.to_reduce_u].bucket, clear_into,
4244  erg.expand_length);
4245  if(TEST_OPT_PROT)
4246  PrintS ("e");
4247  }
4248  }
4249  }
4250  }
4251 
4252  swap_roles = FALSE;
4253  return;
4254  }
4255  }
4256  else
4257  {
4258  if(erg.reduce_by > erg.to_reduce_u)
4259  {
4260  //then lm(rb)>= lm(tru) so =
4261  assume (erg.reduce_by == erg.to_reduce_u + 1);
4262  int best = erg.reduce_by;
4263  wlen_type quality_a = los[erg.reduce_by].guess_quality (c);
4264  wlen_type qc;
4265  best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);
4266 
4267  if(qc < quality_a)
4268  {
4269  red_object h = los[erg.reduce_by];
4270  los[erg.reduce_by] = los[best];
4271  los[best] = h;
4272  }
4273  swap_roles = FALSE;
4274  return;
4275  }
4276  else
4277  {
4278  assume (!pLmEqual (los[erg.reduce_by].p, los[erg.to_reduce_l].p));
4279  assume (erg.to_reduce_u == erg.to_reduce_l);
4280  //further assume, that reduce_by is the above all other polys
4281  //with same leading term
4282  int il = erg.reduce_by;
4283  wlen_type quality_a = los[erg.reduce_by].guess_quality (c);
4284  wlen_type qc;
4285  while((il > 0) && pLmEqual (los[il - 1].p, los[il].p))
4286  {
4287  il--;
4288  qc = los[il].guess_quality (c);
4289  if(qc < quality_a)
4290  {
4291  quality_a = qc;
4292  erg.reduce_by = il;
4293  }
4294  }
4295  swap_roles = FALSE;
4296  }
4297  }
4298  if(swap_roles)
4299  {
4300  if(TEST_OPT_PROT)
4301  PrintS ("b");
4302  poly clear_into;
4303  int new_length;
4304  int bp = erg.to_reduce_u; //bucket_positon
4305  //kBucketClear(los[bp].bucket,&clear_into,&new_length);
4306  new_length = los[bp].clear_to_poly ();
4307  clear_into = los[bp].p;
4308  poly p = c->strat->S[erg.reduce_by];
4309  int j = erg.reduce_by;
4310  int old_length = c->strat->lenS[j]; // in view of S
4311  los[bp].p = p;
4312  kBucketInit (los[bp].bucket, p, old_length);
4313  wlen_type qal = pQuality (clear_into, c, new_length);
4314  int pos_in_c = -1;
4315  int z;
4316  int new_pos;
4317  new_pos = simple_posInS (c->strat, clear_into, new_length, qal);
4318  assume (new_pos <= j);
4319  for(z = c->n; z; z--)
4320  {
4321  if(p == c->S->m[z - 1])
4322  {
4323  pos_in_c = z - 1;
4324  break;
4325  }
4326  }
4327 
4328  int tdeg_full = -1;
4329  int tdeg = -1;
4330  if(pos_in_c >= 0)
4331  {
4332 #ifdef TGB_RESORT_PAIRS
4333  c->used_b = TRUE;
4334  c->replaced[pos_in_c] = TRUE;
4335 #endif
4336  tdeg = c->T_deg[pos_in_c];
4337  c->S->m[pos_in_c] = clear_into;
4338  c->lengths[pos_in_c] = new_length;
4339  c->weighted_lengths[pos_in_c] = qal;
4340  if(c->gcd_of_terms[pos_in_c] == NULL)
4341  c->gcd_of_terms[pos_in_c] = gcd_of_terms (clear_into, c->r);
4342  if(c->T_deg_full)
4343  tdeg_full = c->T_deg_full[pos_in_c] =
4344  c->pTotaldegree_full (clear_into);
4345  else
4346  tdeg_full = tdeg;
4347  c_S_element_changed_hook (pos_in_c, c);
4348  }
4349  else
4350  {
4351  if(c->eliminationProblem)
4352  {
4353  tdeg_full = c->pTotaldegree_full (clear_into);
4354  tdeg = c->pTotaldegree (clear_into);
4355  }
4356  }
4357  c->strat->S[j] = clear_into;
4358  c->strat->lenS[j] = new_length;
4359 
4360  assume (pLength (clear_into) == new_length);
4361  if(c->strat->lenSw != NULL)
4362  c->strat->lenSw[j] = qal;
4364  {
4365  p_Cleardenom (clear_into, c->r); //should be unnecessary
4366  //includes p_Content(clear_into, c->r);
4367  }
4368  else
4369  pNorm (clear_into);
4370 #ifdef FIND_DETERMINISTIC
4371  erg.reduce_by = j;
4372  //resort later see diploma thesis, find_in_S must be deterministic
4373  //during multireduction if spolys are only in the span of the
4374  //input polys
4375 #else
4376  if(new_pos < j)
4377  {
4378  if(c->strat->honey)
4379  c->strat->ecartS[j] = tdeg_full - tdeg;
4380  move_forward_in_S (j, new_pos, c->strat);
4381  erg.reduce_by = new_pos;
4382  }
4383 #endif
4384  }
4385 }
4386 
4387 static int fwbw (red_object * los, int i)
4388 {
4389  int i2 = i;
4390  int step = 1;
4391 
4392  BOOLEAN bw = FALSE;
4393  BOOLEAN incr = TRUE;
4394 
4395  while(1)
4396  {
4397  if(!bw)
4398  {
4399  step = si_min (i2, step);
4400  if(step == 0)
4401  break;
4402  i2 -= step;
4403 
4404  if(!pLmEqual (los[i].p, los[i2].p))
4405  {
4406  bw = TRUE;
4407  incr = FALSE;
4408  }
4409  else
4410  {
4411  if((!incr) && (step == 1))
4412  break;
4413  }
4414  }
4415  else
4416  {
4417  step = si_min (i - i2, step);
4418  if(step == 0)
4419  break;
4420  i2 += step;
4421  if(pLmEqual (los[i].p, los[i2].p))
4422  {
4423  if(step == 1)
4424  break;
4425  else
4426  {
4427  bw = FALSE;
4428  }
4429  }
4430  }
4431  if(incr)
4432  step *= 2;
4433  else
4434  {
4435  if(step % 2 == 1)
4436  step = (step + 1) / 2;
4437  else
4438  step /= 2;
4439  }
4440  }
4441  return i2;
4442 }
4443 
4444 static void
4445 canonicalize_region (red_object * los, int l, int u, slimgb_alg * /*c*/)
4446 {
4447  assume (l <= u + 1);
4448  int i;
4449  for(i = l; i <= u; i++)
4450  {
4451  kBucketCanonicalize (los[i].bucket);
4452  }
4453 }
4454 
4455 #ifdef SING_NDEBUG
4456 static void
4457 multi_reduction_find (red_object * los, int /*losl*/, slimgb_alg * c, int startf,
4458  find_erg & erg)
4459 #else
4460 static void
4461 multi_reduction_find (red_object * los, int losl, slimgb_alg * c, int startf,
4462  find_erg & erg)
4463 #endif
4464 {
4465  kStrategy strat = c->strat;
4466 
4467  #ifndef SING_NDEBUG
4468  assume (startf <= losl);
4469  assume ((startf == losl - 1)
4470  || (pLmCmp (los[startf].p, los[startf + 1].p) == -1));
4471  #endif
4472  int i = startf;
4473 
4474  int j;
4475  while(i >= 0)
4476  {
4477  #ifndef SING_NDEBUG
4478  assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) <= 0));
4479  #endif
4480  assume (is_valid_ro (los[i]));
4481  j = kFindDivisibleByInS_easy (strat, los[i]);
4482  if(j >= 0)
4483  {
4484  erg.to_reduce_u = i;
4485  erg.reduce_by = j;
4486  erg.fromS = TRUE;
4487  int i2 = fwbw (los, i);
4488  assume (pLmEqual (los[i].p, los[i2].p));
4489  assume ((i2 == 0) || (!pLmEqual (los[i2].p, los[i2 - 1].p)));
4490  assume (i >= i2);
4491 
4492  erg.to_reduce_l = i2;
4493  #ifndef SING_NDEBUG
4494  assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) == -1));
4495  #endif
4496  canonicalize_region (los, erg.to_reduce_u + 1, startf, c);
4497  return;
4498  }
4499  else /*if(j < 0)*/
4500  {
4501  //not reduceable, try to use this for reducing higher terms
4502  int i2 = fwbw (los, i);
4503  assume (pLmEqual (los[i].p, los[i2].p));
4504  assume ((i2 == 0) || (!pLmEqual (los[i2].p, los[i2 - 1].p)));
4505  assume (i >= i2);
4506  if(i2 != i)
4507  {
4508  erg.to_reduce_u = i - 1;
4509  erg.to_reduce_l = i2;
4510  erg.reduce_by = i;
4511  erg.fromS = FALSE;
4512  #ifndef SING_NDEBUG
4513  assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) == -1));
4514  #endif
4515  canonicalize_region (los, erg.to_reduce_u + 1, startf, c);
4516  return;
4517  }
4518  i--;
4519  }
4520  }
4521  erg.reduce_by = -1; //error code
4522  return;
4523 }
4524 
4525 // nicht reduzierbare eintrage in ergnisliste schreiben
4526 // nullen loeschen
4527 // while(finde_groessten leitterm reduzierbar(c,erg))
4528 // {
4529 
4530 static int
4531 multi_reduction_clear_zeroes (red_object * los, int losl, int l, int u)
4532 {
4533  int deleted = 0;
4534  int i = l;
4535  int last = -1;
4536  while(i <= u)
4537  {
4538  if(los[i].p == NULL)
4539  {
4540  kBucketDestroy (&los[i].bucket);
4541 // delete los[i];//here we assume los are constructed with new
4542  //destroy resources, must be added here
4543  if(last >= 0)
4544  {
4545  memmove (los + (int) (last + 1 - deleted), los + (last + 1),
4546  sizeof (red_object) * (i - 1 - last));
4547  }
4548  last = i;
4549  deleted++;
4550  }
4551  i++;
4552  }
4553  if((last >= 0) && (last != losl - 1))
4554  memmove (los + (int) (last + 1 - deleted), los + last + 1,
4555  sizeof (red_object) * (losl - 1 - last));
4556  return deleted;
4557 }
4558 
4560 {
4561  int an = 0;
4562  int en = top;
4563  if(top == -1)
4564  return 0;
4565  if(pLmCmp (key->p, a[top].p) == 1)
4566  return top + 1;
4567  int i;
4568  loop
4569  {
4570  if(an >= en - 1)
4571  {
4572  if(pLmCmp (key->p, a[an].p) == -1)
4573  return an;
4574  return en;
4575  }
4576  i = (an + en) / 2;
4577  if(pLmCmp (key->p, a[i].p) == -1)
4578  en = i;
4579  else
4580  an = i;
4581  }
4582 }
4583 
4584 static void sort_region_down (red_object * los, int l, int u, slimgb_alg * /*c*/)
4585 {
4586  int r_size = u - l + 1;
4587  qsort (los + l, r_size, sizeof (red_object), red_object_better_gen);
4588  int i;
4589  int *new_indices = (int *) omalloc ((r_size) * sizeof (int));
4590  int bound = 0;
4591  BOOLEAN at_end = FALSE;
4592  for(i = l; i <= u; i++)
4593  {
4594  if(!(at_end))
4595  {
4596  bound = new_indices[i - l] =
4597  bound + search_red_object_pos (los + bound, l - bound - 1, los + i);
4598  if(bound == l)
4599  at_end = TRUE;
4600  }
4601  else
4602  {
4603  new_indices[i - l] = l;
4604  }
4605  }
4606  red_object *los_region =
4607  (red_object *) omalloc (sizeof (red_object) * (u - l + 1));
4608  for(int i = 0; i < r_size; i++)
4609  {
4610  new_indices[i] += i;
4611  los_region[i] = los[l + i];
4612  assume ((i == 0) || (new_indices[i] > new_indices[i - 1]));
4613  }
4614 
4615  i = r_size - 1;
4616  int j = u;
4617  int j2 = l - 1;
4618  while(i >= 0)
4619  {
4620  if(new_indices[i] == j)
4621  {
4622  los[j] = los_region[i];
4623  i--;
4624  j--;
4625  }
4626  else
4627  {
4628  assume (new_indices[i] < j);
4629  los[j] = los[j2];
4630  assume (j2 >= 0);
4631  j2--;
4632  j--;
4633  }
4634  }
4635  omFree (los_region);
4636  omFree (new_indices);
4637 }
4638 
4639 //assume that los is ordered ascending by leading term, all non zero
4640 static void multi_reduction (red_object * los, int &losl, slimgb_alg * c)
4641 {
4642  poly *delay = (poly *) omAlloc (losl * sizeof (poly));
4643  int delay_s = 0;
4644  //initialize;
4645  assume (c->strat->sl >= 0);
4646  assume (losl > 0);
4647  int i;
4648  wlen_type max_initial_quality = 0;
4649 
4650  for(i = 0; i < losl; i++)
4651  {
4652  los[i].sev = pGetShortExpVector (los[i].p);
4653 //SetShortExpVector();
4654  los[i].p = kBucketGetLm (los[i].bucket);
4655  if(los[i].initial_quality > max_initial_quality)
4656  max_initial_quality = los[i].initial_quality;
4657  // else
4658 // Print("init2_qal=%lld;", los[i].initial_quality);
4659 // Print("initial_quality=%lld;",max_initial_quality);
4660  }
4661 
4662  int curr_pos = losl - 1;
4663 
4664 // nicht reduzierbare eintrage in ergnisliste schreiben
4665  // nullen loeschen
4666  while(curr_pos >= 0)
4667  {
4668  if((c->use_noro_last_block)
4669  && (lies_in_last_dp_block (los[curr_pos].p, c)))
4670  {
4671  int pn_noro = curr_pos + 1;
4672  poly *p_noro = (poly *) omAlloc (pn_noro * sizeof (poly));
4673  for(i = 0; i < pn_noro; i++)
4674  {
4675  int dummy_len;
4676  poly p;
4677  los[i].p = NULL;
4678  kBucketClear (los[i].bucket, &p, &dummy_len);
4679  p_noro[i] = p;
4680  }
4681  if(n_GetChar(currRing->cf) < 255)
4682  {
4683  noro_step < tgb_uint8 > (p_noro, pn_noro, c);
4684  }
4685  else
4686  {
4687  if(n_GetChar(currRing->cf) < 65000)
4688  {
4689  noro_step < tgb_uint16 > (p_noro, pn_noro, c);
4690  }
4691  else
4692  {
4693  noro_step < tgb_uint32 > (p_noro, pn_noro, c);
4694  }
4695  }
4696  for(i = 0; i < pn_noro; i++)
4697  {
4698  los[i].p = p_noro[i];
4699  los[i].sev = pGetShortExpVector (los[i].p);
4700  //ignore quality
4701  kBucketInit (los[i].bucket, los[i].p, pLength (los[i].p));
4702  }
4703  qsort (los, pn_noro, sizeof (red_object), red_object_better_gen);
4704  int deleted =
4705  multi_reduction_clear_zeroes (los, losl, pn_noro, curr_pos);
4706  losl -= deleted;
4707  curr_pos -= deleted;
4708  break;
4709  }
4710  find_erg erg;
4711 
4712  multi_reduction_find (los, losl, c, curr_pos, erg); //last argument should be curr_pos
4713  if(erg.reduce_by < 0)
4714  break;
4715 
4716  erg.expand = NULL;
4717 
4718  multi_reduction_lls_trick (los, losl, c, erg);
4719 
4720  int i;
4721  // wrp(los[erg.to_reduce_u].p);
4722  //PrintLn();
4723  multi_reduce_step (erg, los, c);
4724 
4725 
4726  if(!TEST_OPT_REDTHROUGH)
4727  {
4728  for(i = erg.to_reduce_l; i <= erg.to_reduce_u; i++)
4729  {
4730  if(los[i].p != NULL) //the check (los[i].p!=NULL) might be invalid
4731  {
4732  //
4733  assume (los[i].initial_quality > 0);
4734  if(los[i].guess_quality (c)
4735  > 1.5 * delay_factor * max_initial_quality)
4736  {
4737  if(TEST_OPT_PROT)
4738  PrintS ("v");
4739  los[i].canonicalize ();
4740  if(los[i].guess_quality (c) > delay_factor * max_initial_quality)
4741  {
4742  if(TEST_OPT_PROT)
4743  PrintS (".");
4744  los[i].clear_to_poly ();
4745  //delay.push_back(los[i].p);
4746  delay[delay_s] = los[i].p;
4747  delay_s++;
4748  los[i].p = NULL;
4749  }
4750  }
4751  }
4752  }
4753  }
4754  int deleted = multi_reduction_clear_zeroes (los, losl, erg.to_reduce_l,
4755  erg.to_reduce_u);
4756  if(erg.fromS == FALSE)
4757  curr_pos = si_max (erg.to_reduce_u, erg.reduce_by);
4758  else
4759  curr_pos = erg.to_reduce_u;
4760  losl -= deleted;
4761  curr_pos -= deleted;
4762 
4763  //Print("deleted %i \n",deleted);
4764  if((TEST_V_UPTORADICAL) && (!(erg.fromS)))
4765  sort_region_down (los, si_min (erg.to_reduce_l, erg.reduce_by),
4766  (si_max (erg.to_reduce_u, erg.reduce_by)) - deleted,
4767  c);
4768  else
4769  sort_region_down (los, erg.to_reduce_l, erg.to_reduce_u - deleted, c);
4770 
4771  if(erg.expand)
4772  {
4773 #ifdef FIND_DETERMINISTIC
4774  int i;
4775  for(i = 0; c->expandS[i]; i++) ;
4776  c->expandS = (poly *) omrealloc (c->expandS, (i + 2) * sizeof (poly));
4777  c->expandS[i] = erg.expand;
4778  c->expandS[i + 1] = NULL;
4779 #else
4780  int ecart = 0;
4781  if(c->eliminationProblem)
4782  {
4783  ecart =
4784  c->pTotaldegree_full (erg.expand) - c->pTotaldegree (erg.expand);
4785  }
4786  add_to_reductors (c, erg.expand, erg.expand_length, ecart);
4787 #endif
4788  }
4789  }
4790 
4791  //sorted_pair_node** pairs=(sorted_pair_node**)
4792  // omalloc(delay_s*sizeof(sorted_pair_node*));
4793  c->introduceDelayedPairs (delay, delay_s);
4794  /*
4795  for(i=0;i<delay_s;i++)
4796  {
4797  poly p=delay[i];
4798  //if (rPar(c->r)==0)
4799  simplify_poly(p,c->r);
4800  sorted_pair_node* si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
4801  si->i=-1;
4802  si->j=-1;
4803  if (!rField_is_Zp(c->r))
4804  {
4805  if (!c->nc)
4806  p=redTailShort(p, c->strat);
4807  p_Cleardenom(p, c->r);
4808  p_Content(p, c->r);
4809  }
4810  si->expected_length=pQuality(p,c,pLength(p));
4811  si->deg=pTotaldegree(p);
4812  si->lcm_of_lm=p;
4813  pairs[i]=si;
4814  }
4815  qsort(pairs,delay_s,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
4816  c->apairs=spn_merge(c->apairs,c->pair_top+1,pairs,delay_s,c);
4817  c->pair_top+=delay_s; */
4818  omFree (delay);
4819  //omfree(pairs);
4820  return;
4821 }
4822 
4824 {
4825  assume (p == kBucketGetLm (bucket));
4826 }
4827 
4829 {
4830  p = kBucketGetLm (bucket);
4831  if(p)
4832  sev = pGetShortExpVector (p);
4833 }
4834 
4836 {
4837  flatten ();
4838  int l;
4839  kBucketClear (bucket, &p, &l);
4840  return l;
4841 }
4842 
4843 void reduction_step::reduce (red_object * /*r*/, int /*l*/, int /*u*/)
4844 {
4845 }
4846 
4848 {
4849  number coef;
4850 #ifdef HAVE_PLURAL
4851  if(c->nc)
4852  nc_kBucketPolyRed_Z (ro.bucket, p, &coef);
4853  else
4854 #endif
4855  coef = kBucketPolyRed (ro.bucket, p, p_len, c->strat->kNoether);
4856  nDelete (&coef);
4857 }
4858 
4859 void simple_reducer::reduce (red_object * r, int l, int u)
4860 {
4861  this->pre_reduce (r, l, u);
4862  int i;
4863 //debug start
4864 
4865  if(c->eliminationProblem)
4866  {
4867  assume (p_LmEqual (r[l].p, r[u].p, c->r));
4868  /*int lm_deg=pTotaldegree(r[l].p);
4869  reducer_deg=lm_deg+pTotaldegree_full(p)-pTotaldegree(p); */
4870  }
4871 
4872  for(i = l; i <= u; i++)
4873  {
4874  this->do_reduce (r[i]);
4875  }
4876  for(i = l; i <= u; i++)
4877  {
4878  kBucketSimpleContent (r[i].bucket);
4879  r[i].validate ();
4880  }
4881 }
4882 
4884 {
4885 }
4886 
4888 {
4889  if(fill_back != NULL)
4890  {
4892  }
4893  fill_back = NULL;
4894 }
4895 
4897 {
4898  static int id = 0;
4899  id++;
4900  unsigned long sev;
4901  BOOLEAN lt_changed = FALSE;
4902  int rn = erg.reduce_by;
4903  poly red;
4904  int red_len;
4905  simple_reducer *pointer;
4906  BOOLEAN work_on_copy = FALSE;
4907  if(erg.fromS)
4908  {
4909  red = c->strat->S[rn];
4910  red_len = c->strat->lenS[rn];
4911  assume (red_len == pLength (red));
4912  }
4913  else
4914  {
4915  r[rn].flatten ();
4916  kBucketClear (r[rn].bucket, &red, &red_len);
4917 
4919  {
4920  p_Cleardenom (red, c->r); //should be unnecessary
4921  //includes p_Content(red, c->r);
4922  }
4923  //pNormalize (red);
4924 
4925  if((!(erg.fromS)) && (TEST_V_UPTORADICAL))
4926  {
4927  if(polynomial_root (red, c->r))
4928  lt_changed = TRUE;
4929  sev = p_GetShortExpVector (red, c->r);
4930  }
4931  red_len = pLength (red);
4932  }
4933  if(((TEST_V_MODPSOLVSB) && (red_len > 1))
4934  || ((c->nc) || (erg.to_reduce_u - erg.to_reduce_l > 5)))
4935  {
4936  work_on_copy = TRUE;
4937  // poly m=pOne();
4938  poly m = c->tmp_lm;
4939  pSetCoeff (m, nInit (1));
4940  pSetComp (m, 0);
4941  for(int i = 1; i <= (currRing->N); i++)
4942  pSetExp (m, i, (pGetExp (r[erg.to_reduce_l].p, i) - pGetExp (red, i)));
4943  pSetm (m);
4944  poly red_cp;
4945 #ifdef HAVE_PLURAL
4946  if(c->nc)
4947  red_cp = nc_mm_Mult_pp (m, red, c->r);
4948  else
4949 #endif
4950  red_cp = ppMult_mm (red, m);
4951  if(!erg.fromS)
4952  {
4953  kBucketInit (r[rn].bucket, red, red_len);
4954  }
4955  //now reduce the copy
4956  //static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n)
4957 
4958  if(!c->nc)
4959  redTailShort (red_cp, c->strat);
4960  //number mul;
4961  // red_len--;
4962 // red_cp->next=redNF2(red_cp->next,c,red_len,mul,c->average_length);
4963 // pSetCoeff(red_cp,nMult(red_cp->coef,mul));
4964 // nDelete(&mul);
4965 // red_len++;
4966  red = red_cp;
4967  red_len = pLength (red);
4968  // pDelete(&m);
4969  }
4970 
4971  assume (red_len == pLength (red));
4972 
4973  int reducer_deg = 0;
4974  if(c->eliminationProblem)
4975  {
4976  int lm_deg = c->pTotaldegree (r[erg.to_reduce_l].p);
4977  int ecart;
4978  if(erg.fromS)
4979  {
4980  ecart = c->strat->ecartS[erg.reduce_by];
4981  }
4982  else
4983  {
4984  ecart = c->pTotaldegree_full (red) - lm_deg;
4985  }
4986  reducer_deg = lm_deg + ecart;
4987  }
4988  pointer = new simple_reducer (red, red_len, reducer_deg, c);
4989 
4990  if((!work_on_copy) && (!erg.fromS))
4991  pointer->fill_back = r[rn].bucket;
4992  else
4993  pointer->fill_back = NULL;
4994  pointer->reduction_id = id;
4995  pointer->c = c;
4996 
4997  pointer->reduce (r, erg.to_reduce_l, erg.to_reduce_u);
4998  if(work_on_copy)
4999  pDelete (&pointer->p);
5000  delete pointer;
5001  if(lt_changed)
5002  {
5003  assume (!erg.fromS);
5004  r[erg.reduce_by].sev = sev;
5005  }
5006 }
5007 
5008 void simple_reducer::pre_reduce (red_object * /*r*/, int /*l*/, int /*u*/)
5009 {
5010 }
5011 
5012 #if 0
5013 template int pos_helper<int, int*>(skStrategy*, spolyrec*, int, int*, spolyrec**);
5014 template int pos_helper<long, long*>(skStrategy*, spolyrec*, long, long*, spolyrec**);
5015 
5016 template void noro_step<unsigned char>(spolyrec**, int&, slimgb_alg*);
5017 template void noro_step<unsigned int>(spolyrec**, int&, slimgb_alg*);
5018 template void noro_step<unsigned short>(spolyrec**, int&, slimgb_alg*);
5019 
5020 
5021 template int term_nodes_sort_crit<unsigned char>(void const*, void const*);
5022 template int term_nodes_sort_crit<unsigned int>(void const*, void const*);
5023 template int term_nodes_sort_crit<unsigned short>(void const*, void const*);
5024 
5025 template spolyrec* row_to_poly<unsigned char>(unsigned char*, spolyrec**, int, ip_sring*);
5026 template spolyrec* row_to_poly<unsigned int>(unsigned int*, spolyrec**, int, ip_sring*);
5027 template spolyrec* row_to_poly<unsigned short>(unsigned short*, spolyrec**, int, ip_sring*);
5028 
5029 template void simplest_gauss_modp<unsigned char>(unsigned char*, int, int);
5030 template void simplest_gauss_modp<unsigned int>(unsigned int*, int, int);
5031 template void simplest_gauss_modp<unsigned short>(unsigned short*, int, int);
5032 
5033 
5034 template int modP_lastIndexRow<unsigned char>(unsigned char*, int);
5035 template int modP_lastIndexRow<unsigned int>(unsigned int*, int);
5036 template int modP_lastIndexRow<unsigned short>(unsigned short*, int);
5037 
5038 template SparseRow<unsigned char>* noro_red_to_non_poly_t<unsigned char>(spolyrec*, int&, NoroCache<unsigned char>*, slimgb_alg*);
5039 template SparseRow<unsigned int>* noro_red_to_non_poly_t<unsigned int>(spolyrec*, int&, NoroCache<unsigned int>*, slimgb_alg*);
5040 template SparseRow<unsigned short>* noro_red_to_non_poly_t<unsigned short>(spolyrec*, int&, NoroCache<unsigned short>*, slimgb_alg*);
5041 
5042 
5043 template MonRedResNP<unsigned char> noro_red_mon_to_non_poly<unsigned char>(spolyrec*, NoroCache<unsigned char>*, slimgb_alg*);
5044 template MonRedResNP<unsigned int> noro_red_mon_to_non_poly<unsigned int>(spolyrec*, NoroCache<unsigned int>*, slimgb_alg*);
5045 template MonRedResNP<unsigned short> noro_red_mon_to_non_poly<unsigned short>(spolyrec*, NoroCache<unsigned short>*, slimgb_alg*);
5046 
5047 template SparseRow<unsigned char>* noro_red_to_non_poly_dense<unsigned char>(MonRedResNP<unsigned char>*, int, NoroCache<unsigned char>*);
5048 template SparseRow<unsigned char>* noro_red_to_non_poly_sparse<unsigned char>(MonRedResNP<unsigned char>*, int, NoroCache<unsigned char>*);
5049 template SparseRow<unsigned int>* noro_red_to_non_poly_dense<unsigned int>(MonRedResNP<unsigned int>*, int, NoroCache<unsigned int>*);
5050 template SparseRow<unsigned int>* noro_red_to_non_poly_sparse<unsigned int>(MonRedResNP<unsigned int>*, int, NoroCache<unsigned int>*);
5051 template SparseRow<unsigned short>* noro_red_to_non_poly_dense<unsigned short>(MonRedResNP<unsigned short>*, int, NoroCache<unsigned short>*);
5052 template SparseRow<unsigned short>* noro_red_to_non_poly_sparse<unsigned short>(MonRedResNP<unsigned short>*, int, NoroCache<unsigned short>*);
5053 
5054 
5055 
5056 template class DataNoroCacheNode<unsigned char>;
5057 template class DataNoroCacheNode<unsigned int>;
5058 template class DataNoroCacheNode<unsigned short>;
5059 
5060 template class NoroCache<unsigned char>;
5061 template class NoroCache<unsigned int>;
5062 template class NoroCache<unsigned short>;
5063 
5064 
5065 
5066 template void add_coef_times_dense<unsigned char>(unsigned char*, int, unsigned char const*, int, snumber*);
5067 template void add_coef_times_dense<unsigned int>(unsigned int*, int, unsigned int const*, int, snumber*);
5068 template void add_coef_times_dense<unsigned short>(unsigned short*, int, unsigned short const*, int, snumber*);
5069 template void add_coef_times_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*, snumber*);
5070 template void add_coef_times_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*, snumber*);
5071 template void add_coef_times_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*, snumber*);
5072 template void add_dense<unsigned char>(unsigned char*, int, unsigned char const*, int);
5073 template void add_dense<unsigned int>(unsigned int*, int, unsigned int const*, int);
5074 template void add_dense<unsigned short>(unsigned short*, int, unsigned short const*, int);
5075 template void add_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*);
5076 template void add_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*);
5077 template void add_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*);
5078 
5079 
5080 template void sub_dense<unsigned char>(unsigned char*, int, unsigned char const*, int);
5081 template void sub_dense<unsigned int>(unsigned int*, int, unsigned int const*, int);
5082 template void sub_dense<unsigned short>(unsigned short*, int, unsigned short const*, int);
5083 template void sub_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*);
5084 template void sub_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*);
5085 template void sub_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*);
5086 template void write_coef_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int);
5087 template void write_coef_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int);
5088 template void write_coef_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int);
5089 template void write_coef_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int);
5090 template void write_coef_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int);
5091 template void write_coef_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int);
5092 template void write_coef_times_xx_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int, snumber*);
5093 template void write_coef_times_xx_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int, snumber*);
5094 template void write_coef_times_xx_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int, snumber*);
5095 template void write_coef_times_xx_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int, snumber*);
5096 template void write_coef_times_xx_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int, snumber*);
5097 template void write_coef_times_xx_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int, snumber*);
5098 template void write_minus_coef_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int);
5099 template void write_minus_coef_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int);
5100 template void write_minus_coef_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int);
5101 template void write_minus_coef_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int);
5102 template void write_minus_coef_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int);
5103 template void write_minus_coef_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int);
5104 
5105 
5106 template class std::vector<DataNoroCacheNode<unsigned char>*>;
5107 template class std::vector<DataNoroCacheNode<unsigned int>*>;
5108 template class std::vector<DataNoroCacheNode<unsigned short>*>;
5109 template class std::vector<PolySimple>;
5110 
5114 
5115 template void std::sort_heap<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5116 template void std::sort_heap<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5117 template void std::sort_heap<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5118 
5119 template void std::make_heap<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5120 template void std::make_heap<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5121 template void std::make_heap<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5122 #endif
5123 
5124 #if 0
5125 template void std::__final_insertion_sort<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5126 template void std::__final_insertion_sort<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5127 template void std::__final_insertion_sort<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5128 
5129 template void std::__introsort_loop<CoefIdx<unsigned char>*, long>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, long);
5130 template void std::__introsort_loop<CoefIdx<unsigned int>*, long>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, long);
5131 template void std::__introsort_loop<CoefIdx<unsigned short>*, long>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, long);
5132 
5133 template void std::__heap_select<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5134 template void std::__heap_select<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5135 template void std::__heap_select<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5136 
5137 template void std::__insertion_sort<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5138 template void std::__insertion_sort<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5139 template void std::__insertion_sort<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5140 
5141 template void std::__move_median_first<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5142 template void std::__move_median_first<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5143 template void std::__move_median_first<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5144 
5145 template void std::__unguarded_linear_insert<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*);
5146 template void std::__unguarded_linear_insert<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*);
5147 template void std::__unguarded_linear_insert<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*);
5148 
5149 template void std::__adjust_heap<CoefIdx<unsigned char>*, long, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, long, long, CoefIdx<unsigned char>);
5150 template void std::__adjust_heap<CoefIdx<unsigned int>*, long, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, long, long, CoefIdx<unsigned int>);
5151 template void std::__adjust_heap<CoefIdx<unsigned short>*, long, CoefIdx<unsigned short> >(CoefIdx<unsigned short>*, long, long, CoefIdx<unsigned short>);
5152 
5153 template void std::__push_heap<CoefIdx<unsigned char>*, long, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, long, long, CoefIdx<unsigned char>);
5154 template void std::__push_heap<CoefIdx<unsigned int>*, long, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, long, long, CoefIdx<unsigned int>);
5155 template void std::__push_heap<CoefIdx<unsigned short>*, long, CoefIdx<unsigned short> >(CoefIdx<unsigned short>*, long, long, CoefIdx<unsigned short>);
5156 
5157 template CoefIdx<unsigned char>* std::__unguarded_partition<CoefIdx<unsigned char>*, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char> const&);
5158 template CoefIdx<unsigned int>* std::__unguarded_partition<CoefIdx<unsigned int>*, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int> const&);
5159 template CoefIdx<unsigned short>* std::__unguarded_partition<CoefIdx<unsigned short>*, CoefIdx<unsigned short> >(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, CoefIdx<unsigned short> const&);
5160 
5161 #endif
5162 
kBucketSimpleContent
void kBucketSimpleContent(kBucket_pt bucket)
Definition: kbuckets.cc:1177
si_min
static int si_min(const int a, const int b)
Definition: auxiliary.h:139
FALSE
#define FALSE
Definition: auxiliary.h:94
terms_sort_crit
int terms_sort_crit(const void *a, const void *b)
Definition: tgb.cc:2030
poly_list_node::next
poly_list_node * next
Definition: tgb_internal.h:185
CoefIdx
Definition: tgb_internal.h:1185
rRing_has_CompLastBlock
BOOLEAN rRing_has_CompLastBlock(ring r)
Definition: ring.cc:5112
skStrategy
Definition: kutil.h:262
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
slimgb_alg::pTotaldegree
unsigned long pTotaldegree(poly p)
Definition: tgb_internal.h:289
free_row_to_poly
poly free_row_to_poly(tgb_sparse_matrix *mat, int row, poly *monoms, int monom_index)
Definition: tgb.cc:3064
red_object::flatten
void flatten()
Definition: tgb.cc:4823
mac_poly_r::next
mac_poly_r * next
Definition: tgbgauss.h:51
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:51
skStrategy::fromQ
intset fromQ
Definition: kutil.h:312
initBuchMoraCrit
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9570
p_GetComp
#define p_GetComp(p, r)
Definition: monomials.h:65
nNormalize
#define nNormalize(n)
Definition: numbers.h:31
pLmEqual
#define pLmEqual(p1, p2)
Definition: polys.h:111
tgb_internal.h
simple_reducer
Definition: tgb_internal.h:360
slimgb_alg::reduction_steps
unsigned int reduction_steps
Definition: tgb_internal.h:260
kFindDivisibleByInS_easy
int kFindDivisibleByInS_easy(kStrategy strat, const red_object &obj)
Definition: tgb.cc:685
pGetComp
#define pGetComp(p)
Component.
Definition: polys.h:37
red_object::clear_to_poly
int clear_to_poly()
Definition: tgb.cc:4835
sorted_pair_node::lcm_of_lm
poly lcm_of_lm
Definition: tgb_internal.h:162
p_GetExp
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:470
simplify_poly
static void simplify_poly(poly p, ring r)
Definition: tgb.cc:59
j
int j
Definition: facHensel.cc:105
pNorm
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:357
omFree
#define omFree(addr)
Definition: omAllocDecl.h:261
slimgb_alg::introduceDelayedPairs
void introduceDelayedPairs(poly *pa, int s)
Definition: tgb.cc:3102
skStrategy::enterS
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:277
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:102
pHasNotCF
#define pHasNotCF(p1, p2)
Definition: polys.h:257
k
int k
Definition: cfEzgcd.cc:92
idDelete
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
NoroCache::nIrreducibleMonomials
int nIrreducibleMonomials
Definition: tgb_internal.h:706
idrCopyR_NoSort
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:205
tgb_sparse_matrix
Definition: tgbgauss.h:60
TEST_OPT_REDTAIL
#define TEST_OPT_REDTAIL
Definition: options.h:115
poly_tree_node::r
poly_tree_node * r
Definition: tgb.cc:1983
elength_is_normal_length
static BOOLEAN elength_is_normal_length(poly p, slimgb_alg *c)
Definition: tgb.cc:371
poly_tree_node::l
poly_tree_node * l
Definition: tgb.cc:1982
ppMult_mm
#define ppMult_mm(p, m)
Definition: polys.h:196
p_ExpVectorDiff
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1411
slimgb_alg::apairs
sorted_pair_node ** apairs
Definition: tgb_internal.h:244
free_sorted_pair_node
void free_sorted_pair_node(sorted_pair_node *s, const ring r)
Definition: tgb.cc:3916
noro_step< tgb_uint16 >
template void noro_step< tgb_uint16 >(poly *p, int &pn, slimgb_alg *c)
tgb_sparse_matrix::columns
int columns
Definition: tgbgauss.h:65
find_erg::fromS
BOOLEAN fromS
Definition: tgb_internal.h:393
sorted_pair_node::deg
int deg
Definition: tgb_internal.h:165
pOne_Special
static poly pOne_Special(const ring r=currRing)
Definition: tgb.cc:142
rChangeCurrRing
void rChangeCurrRing(ring r)
Definition: polys.cc:15
TEST_OPT_DEGBOUND
#define TEST_OPT_DEGBOUND
Definition: options.h:112
bit_reduce
void bit_reduce(poly &f, ring r)
Definition: digitech.cc:15
result
return result
Definition: facAbsBiFact.cc:76
n_GetChar
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition: coeffs.h:444
omGetSpecBin
#define omGetSpecBin(size)
Definition: omBin.h:11
NoroCacheNode
Definition: tgb_internal.h:432
simple_reducer::p
poly p
Definition: tgb_internal.h:363
skStrategy::ecartS
intset ecartS
Definition: kutil.h:300
polynomial_root
static BOOLEAN polynomial_root(poly h, ring r)
Definition: tgb.cc:109
slimgb_alg::tailReductions
BOOLEAN tailReductions
Definition: tgb_internal.h:282
find_erg::reduce_by
int reduce_by
Definition: tgb_internal.h:392
pGetExp
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
idrMoveR_NoSort
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:261
slimgb_alg::tmp_lm
poly tmp_lm
Definition: tgb_internal.h:238
pEnlargeSet
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3647
npIsOne
BOOLEAN npIsOne(number a, const coeffs r)
calc_state
calc_state
Definition: tgb_internal.h:325
DenseRow::begin
int begin
Definition: tgb_internal.h:503
number_array
number * number_array
Definition: ntupel.cc:26
slimgb_alg::tmp_spn
sorted_pair_node ** tmp_spn
Definition: tgb_internal.h:240
reduction_step::c
slimgb_alg * c
Definition: tgb_internal.h:357
CxxTest::base
char N base
Definition: ValueTraits.h:144
simple_reducer::do_reduce
virtual void do_reduce(red_object &ro)
Definition: tgb.cc:4847
exp_number_builder::exp_number_builder
exp_number_builder()
Definition: tgb.cc:1995
skStrategy::S
polyset S
Definition: kutil.h:297
kBucketPolyRed
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1076
pair_weighted_length
static wlen_type pair_weighted_length(int i, int j, slimgb_alg *c)
Definition: tgb.cc:1373
skStrategy::lenS
intset lenS
Definition: kutil.h:310
sorted_pair_node::i
int i
Definition: tgb_internal.h:163
tdeg
int tdeg(poly p)
Definition: walkSupport.cc:35
MAX_BUCKET
#define MAX_BUCKET
Bucket definition (should be no one elses business, though)
Definition: kbuckets.h:175
omAllocAligned
#define omAllocAligned
Definition: omAllocDecl.h:273
slimgb_alg::use_noro_last_block
BOOLEAN use_noro_last_block
Definition: tgb_internal.h:278
skStrategy::tailRing
ring tailRing
Definition: kutil.h:336
slimgb_alg::weighted_lengths
wlen_type * weighted_lengths
Definition: tgb_internal.h:233
noro_step
void noro_step(poly *p, int &pn, slimgb_alg *c)
Definition: tgb_internal.h:1801
replace_pair
static void replace_pair(int &i, int &j, slimgb_alg *c)
Definition: tgb.cc:1215
slimgb_alg::T_deg_full
int * T_deg_full
Definition: tgb_internal.h:237
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
lies_in_last_dp_block
static BOOLEAN lies_in_last_dp_block(poly p, slimgb_alg *c)
Definition: tgb.cc:399
tgb.h
nlQlogSize
static FORCE_INLINE int nlQlogSize(number n, const coeffs r)
only used by slimgb (tgb.cc)
Definition: longrat.h:75
NoroCache::lookup
poly lookup(poly term, BOOLEAN &succ, int &len)
Definition: tgb_internal.h:1965
now_t_rep
void now_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *c)
Definition: tgb.cc:3623
slimgb_alg::pTotaldegree_full
int pTotaldegree_full(poly p)
Definition: tgb_internal.h:297
mp_array_list::mp
monom_poly * mp
Definition: tgb_internal.h:201
sorted_pair_node
Definition: tgb_internal.h:158
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
__p_GetComp
#define __p_GetComp(p, r)
Definition: monomials.h:64
red_object::bucket
kBucket_pt bucket
Definition: tgb_internal.h:312
red_object::canonicalize
void canonicalize()
Definition: tgb.cc:871
clean_top_of_pair_list
void clean_top_of_pair_list(slimgb_alg *c)
Definition: tgb.cc:3883
UNCALCULATED
@ UNCALCULATED
Definition: tgb_internal.h:327
do_pELength
static wlen_type do_pELength(poly p, slimgb_alg *c, int dlm=-1)
Definition: tgb.cc:446
TEST_OPT_DEBUG
#define TEST_OPT_DEBUG
Definition: options.h:107
tgb_pair_better_gen
static int tgb_pair_better_gen(const void *ap, const void *bp)
Definition: tgb.cc:3951
p_Test
#define p_Test(p, r)
Definition: p_polys.h:164
slimgb_alg::r
ring r
Definition: tgb_internal.h:231
pGetShortExpVector
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition: polys.h:152
options.h
has_t_rep
static BOOLEAN has_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *state)
Definition: tgb.cc:3644
ADD_LATER_SIZE
#define ADD_LATER_SIZE
Definition: tgb.cc:39
idTest
#define idTest(id)
Definition: ideals.h:47
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:988
skStrategy::sevS
unsigned long * sevS
Definition: kutil.h:313
kBucketGetLm
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:503
redNFTail
static poly redNFTail(poly h, const int sl, kStrategy strat, int len)
Definition: tgb.cc:2937
pDelete
#define pDelete(p_ptr)
Definition: polys.h:181
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
make_connections
static int * make_connections(int from, int to, poly bound, slimgb_alg *c)
Definition: tgb.cc:1101
pHasNotCFExtended
static BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m)
Definition: tgb.cc:4023
skStrategy::honey
char honey
Definition: kutil.h:371
slimgb_alg::normal_forms
int normal_forms
Definition: tgb_internal.h:265
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
row_to_poly
poly row_to_poly(number_type *row, poly *terms, int tn, ring r)
Definition: tgb_internal.h:1484
slimgb_alg::n
int n
Definition: tgb_internal.h:261
idIs0
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
Definition: simpleideals.cc:768
slimgb_alg::soon_free
int_pair_node * soon_free
Definition: tgb_internal.h:243
loop
#define loop
Definition: structs.h:78
pSetComp
#define pSetComp(p, v)
Definition: polys.h:38
NoroCache::backLinkCode
static const int backLinkCode
Definition: tgb_internal.h:606
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
init_with_mac_poly
void init_with_mac_poly(tgb_sparse_matrix *mat, int row, mac_poly m)
Definition: tgb.cc:3049
multi_reduction
static void multi_reduction(red_object *los, int &losl, slimgb_alg *c)
Definition: tgb.cc:4640
search_red_object_pos
int search_red_object_pos(red_object *a, int top, red_object *key)
Definition: tgb.cc:4559
tgb_sparse_matrix::mp
mac_poly * mp
Definition: tgbgauss.h:64
TEST_OPT_REDSB
#define TEST_OPT_REDSB
Definition: options.h:103
b
CanonicalForm b
Definition: cfModGcd.cc:4044
__p_Mult_nn
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:928
red_object_better_gen
static int red_object_better_gen(const void *ap, const void *bp)
Definition: tgb.cc:665
npInit
number npInit(long i, const coeffs r)
Definition: modulop.cc:114
top_pair
sorted_pair_node * top_pair(slimgb_alg *c)
Definition: tgb.cc:3838
write_poly_to_row
void write_poly_to_row(number_type *row, poly h, poly *terms, int tn, ring r)
Definition: tgb_internal.h:1469
ap
Definition: ap.h:39
find_best
int find_best(red_object *r, int l, int u, wlen_type &w, slimgb_alg *c)
returns position sets w as weight
Definition: tgb.cc:854
p_LmDivisibleBy
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1821
slimgb_alg::cleanDegs
void cleanDegs(int lower, int upper)
Definition: tgb.cc:3756
pTotaldegree
static long pTotaldegree(poly p)
Definition: polys.h:276
monom_poly::m
poly m
Definition: tgb_internal.h:196
find_erg::expand
poly expand
Definition: tgb_internal.h:388
slimgb_alg::Rcounter
int Rcounter
Definition: tgb_internal.h:267
p_LmEqual
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1649
found
bool found
Definition: facFactorize.cc:56
NoroCache::buffer
number * buffer
Definition: tgb_internal.h:755
p_SetExp
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:489
do_t_rep_gb
ideal do_t_rep_gb(ring, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
Definition: tgb.cc:3568
rIsPluralRing
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:398
NoroCacheNode::branches_len
int branches_len
Definition: tgb_internal.h:436
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:193
move_backward_in_S
static void move_backward_in_S(int old_pos, int new_pos, kStrategy strat)
Definition: tgb.cc:1064
slimgb_alg::F4_mode
BOOLEAN F4_mode
Definition: tgb_internal.h:284
ksCreateShortSpoly
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
Definition: kspoly.cc:998
simplest_gauss_modp
void simplest_gauss_modp(number_type *a, int nrows, int ncols)
Definition: tgb_internal.h:1778
pi
#define pi
Definition: libparse.cc:1143
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:813
NoroCache::insertAndTransferOwnerShip
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
Definition: tgb_internal.h:647
currRing
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
slimgb_alg::~slimgb_alg
virtual ~slimgb_alg()
Definition: tgb.cc:3326
slimgb_alg::add_later
ideal add_later
Definition: tgb_internal.h:229
DataNoroCacheNode::term_index
int term_index
Definition: tgb_internal.h:557
digitech.h
rVar
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:508
quality_of_pos_in_strat_S_mult_high
static wlen_type quality_of_pos_in_strat_S_mult_high(int pos, poly high, slimgb_alg *c)
Definition: tgb.cc:4113
kEBucketLength
wlen_type kEBucketLength(kBucket *b, poly lm, slimgb_alg *ca)
Definition: tgb.cc:494
TRUE
#define TRUE
Definition: auxiliary.h:98
TEST_OPT_INTSTRATEGY
#define TEST_OPT_INTSTRATEGY
Definition: options.h:109
i
int i
Definition: cfEzgcd.cc:125
npAddM
static number npAddM(number a, number b, const coeffs r)
Definition: modulop.h:125
id_Delete
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
Definition: simpleideals.cc:114
add_later
static void add_later(poly p, const char *prot, slimgb_alg *c)
Definition: tgb.cc:1292
tgb_pair_better_gen2
int tgb_pair_better_gen2(const void *ap, const void *bp)
Definition: tgb.cc:680
find_erg::expand_length
int expand_length
Definition: tgb_internal.h:389
poly_array_list::size
int size
Definition: tgb_internal.h:210
res
CanonicalForm res
Definition: facAbsFact.cc:64
act
static scmon act
Definition: hdegree.cc:1078
kBucket_Add_q
void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
Add to Bucket a poly ,i.e. Bpoly == q+Bpoly.
Definition: kbuckets.cc:651
skStrategy::sl
int sl
Definition: kutil.h:341
poly_list_node::p
poly p
Definition: tgb_internal.h:184
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:213
prCopy.h
id_RankFreeModule
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
Definition: simpleideals.cc:782
add
static unsigned add[]
Definition: misc_ip.cc:122
mac_poly_r
Definition: tgbgauss.h:44
monomial_root
static BOOLEAN monomial_root(poly m, ring r)
Definition: tgb.cc:89
buf
int status int void * buf
Definition: si_signals.h:59
enterSBba
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9050
slimgb_alg::nc
BOOLEAN nc
Definition: tgb_internal.h:285
DenseRow::end
int end
Definition: tgb_internal.h:504
PrintS
void PrintS(const char *s)
Definition: reporter.cc:284
pELength
wlen_type pELength(poly p, slimgb_alg *c, ring)
Definition: tgb.cc:471
redNF2
static poly redNF2(poly h, slimgb_alg *c, int &len, number &m, int n=0)
Definition: tgb.cc:1837
sorted_pair_node::j
int j
Definition: tgb_internal.h:164
length_one_crit
static void length_one_crit(slimgb_alg *c, int pos, int len)
Definition: tgb.cc:1005
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
pTest
#define pTest(p)
Definition: polys.h:409
pExpVectorDiff
#define pExpVectorDiff(pr, p1, p2)
Definition: polys.h:91
multi_reduction_lls_trick
static void multi_reduction_lls_trick(red_object *los, int, slimgb_alg *c, find_erg &erg)
Definition: tgb.cc:4127
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:490
pLcm
#define pLcm(a, b, m)
Definition: polys.h:289
t_rep_gb
ideal t_rep_gb(const ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode)
Definition: tgb.cc:3520
npMult
#define npMult
Definition: tgb_internal.h:78
reduction_step::~reduction_step
virtual ~reduction_step()
Definition: tgb.cc:4883
omFreeBinAddr
#define omFreeBinAddr(addr)
Definition: omAllocDecl.h:258
slimgb_alg::short_Exps
long * short_Exps
Definition: tgb_internal.h:234
poly_tree_node::n
int n
Definition: tgb.cc:1984
skStrategy::Shdl
ideal Shdl
Definition: kutil.h:294
poly_tree_node::p
poly p
Definition: tgb.cc:1981
scaFirstAltVar
static short scaFirstAltVar(ring r)
Definition: sca.h:18
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition: simpleideals.cc:172
SparseRow
Definition: tgb_internal.h:514
slimgb_alg::T_deg
int * T_deg
Definition: tgb_internal.h:236
slimgb_alg::slimgb_alg
slimgb_alg(ideal I, int syz_comp, BOOLEAN F4, int deg_pos)
Definition: tgb.cc:3138
super_clean_top_of_pair_list
static void super_clean_top_of_pair_list(slimgb_alg *c)
Definition: tgb.cc:3870
get_last_dp_block_start
static int get_last_dp_block_start(ring r)
Definition: tgb.cc:427
NoroCache::getCacheReference
DataNoroCacheNode< number_type > * getCacheReference(poly term)
Definition: tgb_internal.h:1950
h
static Poly * h
Definition: janet.cc:972
mod2.h
sca.h
coeff_mult_size_estimate
static wlen_type coeff_mult_size_estimate(int s1, int s2, ring r)
Definition: tgb.cc:1365
posInPairs
static int posInPairs(sorted_pair_node **p, int pn, sorted_pair_node *qe, slimgb_alg *c, int an=0)
Definition: tgb.cc:711
omrealloc
#define omrealloc(addr, size)
Definition: omAllocDecl.h:233
SparseRow::coef_array
number_type * coef_array
Definition: tgb_internal.h:518
rAssure_TDeg
ring rAssure_TDeg(ring r, int &pos)
Definition: ring.cc:4463
intset
int * intset
Definition: kutil.h:49
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
pOne
#define pOne()
Definition: polys.h:309
is_valid_ro
BOOLEAN is_valid_ro(red_object &ro)
Definition: tgb.cc:2021
DenseRow::array
number * array
Definition: tgb_internal.h:502
ip_sring
Definition: ring.h:248
NoroCache::root
NoroCacheNode root
Definition: tgb_internal.h:754
DataNoroCacheNode::value_poly
poly value_poly
Definition: tgb_internal.h:551
NoroCache::insert
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
Definition: tgb_internal.h:607
pos_helper
int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set)
Definition: tgb_internal.h:397
pIter
#define pIter(p)
Definition: monomials.h:38
p_Cleardenom
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2782
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:210
slimgb_alg::extended_product_crit
int extended_product_crit
Definition: tgb_internal.h:272
omTypeAllocBin
#define omTypeAllocBin(type, addr, bin)
Definition: omAllocDecl.h:203
slimgb_alg::isDifficultField
BOOLEAN isDifficultField
Definition: tgb_internal.h:279
delay_factor
static const int delay_factor
Definition: tgb.cc:38
multi_reduction_clear_zeroes
static int multi_reduction_clear_zeroes(red_object *los, int losl, int l, int u)
Definition: tgb.cc:4531
mp_array_list::size
int size
Definition: tgb_internal.h:202
trivial_syzygie
static BOOLEAN trivial_syzygie(int pos1, int pos2, poly bound, slimgb_alg *c)
Definition: tgb.cc:800
initBuchMoraPos
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9721
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:538
DataNoroCacheNode
Definition: tgb_internal.h:123
spolyrec
Definition: monomials.h:23
c_S_element_changed_hook
static void c_S_element_changed_hook(int pos, slimgb_alg *c)
Definition: tgb.cc:1971
slimgb_alg::pair_top
int pair_top
Definition: tgb_internal.h:270
slimgb_alg::strat
kStrategy strat
Definition: tgb_internal.h:235
p_Init
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1257
slimgb_alg::expandS
poly * expandS
Definition: tgb_internal.h:241
go_on
static void go_on(slimgb_alg *c)
Definition: tgb.cc:2678
reduction_step::reduction_id
int reduction_id
Definition: tgb_internal.h:358
exp_number_builder
Definition: tgb.cc:1989
TEST_V_COEFSTRAT
#define TEST_V_COEFSTRAT
Definition: options.h:137
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:518
skStrategy::lenSw
wlen_set lenSw
Definition: kutil.h:311
pMDivide
#define pMDivide(a, b)
Definition: polys.h:287
sca_pp_Mult_xi_pp
poly sca_pp_Mult_xi_pp(short i, const poly pPoly, const ring rRing)
Definition: sca.cc:1203
poly_array_list::p
poly * p
Definition: tgb_internal.h:209
rBlocks
static int rBlocks(ring r)
Definition: ring.h:558
__pp_Mult_nn
#define __pp_Mult_nn(p, n, r)
Definition: p_polys.h:959
skStrategy::S_2_R
int * S_2_R
Definition: kutil.h:335
pExpVectorSub
#define pExpVectorSub(p1, p2)
Definition: polys.h:88
ENLARGE
#define ENLARGE(pointer, type)
sort
void sort(CFArray &A, int l=0)
quick sort A
Definition: facSparseHensel.h:114
pLmInit
#define pLmInit(p)
like pInit, except that expvector is initialized to that of p, p must be != NULL
Definition: polys.h:64
simple_reducer::~simple_reducer
~simple_reducer()
Definition: tgb.cc:4887
last
static poly last
Definition: hdegree.cc:1077
skStrategy::syzComp
int syzComp
Definition: kutil.h:347
quality_of_pos_in_strat_S
static wlen_type quality_of_pos_in_strat_S(int pos, slimgb_alg *c)
Definition: tgb.cc:4104
SparseRow::len
int len
Definition: tgb_internal.h:519
Kstd1_deg
int Kstd1_deg
Definition: kstd1.h:47
snumber
'SR_INT' is the type of those integers small enough to fit into 29 bits.
Definition: longrat.h:47
ringorder_dp
@ ringorder_dp
Definition: ring.h:79
mass_add
static void mass_add(poly *p, int pn, slimgb_alg *c)
Definition: tgb.cc:2145
wlen_type
int64 wlen_type
Definition: kutil.h:50
pTotaldegree_full
static int pTotaldegree_full(poly p)
Definition: tgb.cc:579
cleanS
static void cleanS(kStrategy strat, slimgb_alg *c)
Definition: tgb.cc:919
slimgb_alg::F
mp_array_list * F
Definition: tgb_internal.h:253
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
simple_posInS
static int simple_posInS(kStrategy strat, poly p, int len, wlen_type wlen)
Definition: tgb.cc:1308
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
slimgb_alg::current_degree
int current_degree
Definition: tgb_internal.h:266
mp_array_list::next
mp_array_list * next
Definition: tgb_internal.h:203
rDelete
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:437
npInt
long npInt(number &n, const coeffs r)
Definition: modulop.cc:128
slimgb_alg::deg_pos
int deg_pos
Definition: tgb_internal.h:276
slimgb_alg::lastDpBlockStart
int lastDpBlockStart
Definition: tgb_internal.h:274
mac_poly_r::exp
int exp
Definition: tgbgauss.h:52
good_has_t_rep
BOOLEAN good_has_t_rep(int i, int j, slimgb_alg *c)
Definition: tgb.cc:876
slimgb_alg::is_homog
BOOLEAN is_homog
Definition: tgb_internal.h:281
omBin
omBin_t * omBin
Definition: omStructs.h:12
nMult
#define nMult(n1, n2)
Definition: numbers.h:18
slimgb_alg::S
ideal S
Definition: tgb_internal.h:230
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:858
poly_tree_node
Definition: tgb.cc:1978
lm_bin
static omBin lm_bin
Definition: tgb.cc:41
spn_merge
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
Definition: tgb.cc:751
DataNoroCacheNode::value_len
int value_len
Definition: tgb_internal.h:550
quick_pop_pair
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
Definition: tgb.cc:3862
state_is
static BOOLEAN state_is(calc_state state, const int &i, const int &j, slimgb_alg *c)
Definition: tgb.cc:3897
poly_array_list::next
poly_array_list * next
Definition: tgb_internal.h:211
bundle_size
static const int bundle_size
Definition: tgb.cc:36
TEST_V_MODPSOLVSB
#define TEST_V_MODPSOLVSB
Definition: options.h:136
NoroCache
Definition: tgb_internal.h:590
slimgb_alg::lastCleanedDeg
int lastCleanedDeg
Definition: tgb_internal.h:275
HASTREP
@ HASTREP
Definition: tgb_internal.h:328
red_object::initial_quality
wlen_type initial_quality
Definition: tgb_internal.h:317
SparseRow::idx_array
int * idx_array
Definition: tgb_internal.h:517
nc.h
simple_reducer::reduce
virtual void reduce(red_object *r, int l, int u)
we assume hat all occuring red_objects have same lm, and all occ. lm's in r[l...u] are the same,...
Definition: tgb.cc:4859
reduction_step
makes on each red_object in a region a single_step
Definition: tgb_internal.h:349
red_object::guess_quality
wlen_type guess_quality(slimgb_alg *c)
Definition: tgb.cc:591
poly_array_list
Definition: tgb_internal.h:207
si_max
static int si_max(const int a, const int b)
Definition: auxiliary.h:138
omUnGetSpecBin
#define omUnGetSpecBin(bin_ptr)
Definition: omBin.h:14
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
mp_array_list
Definition: tgb_internal.h:199
slimgb_alg::use_noro
BOOLEAN use_noro
Definition: tgb_internal.h:277
pSLength
static wlen_type pSLength(poly p, int l)
Definition: tgb.cc:197
reduction_step::reduce
virtual void reduce(red_object *r, int l, int u)
we assume hat all occuring red_objects have same lm, and all occ. lm's in r[l...u] are the same,...
Definition: tgb.cc:4843
Print
#define Print
Definition: emacs.cc:80
nInvers
#define nInvers(a)
Definition: numbers.h:34
slimgb_alg
Definition: tgb_internal.h:213
omalloc
#define omalloc(size)
Definition: omAllocDecl.h:228
find_erg::to_reduce_l
int to_reduce_l
Definition: tgb_internal.h:391
line_of_extended_prod
static void line_of_extended_prod(int fixpos, slimgb_alg *c)
Definition: tgb.cc:1939
pQuality
static wlen_type pQuality(poly p, slimgb_alg *c, int l=-1)
Definition: tgb.cc:544
add_to_basis_ideal_quotient
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
Definition: tgb.cc:1426
omSizeWOfBin
#define omSizeWOfBin(bin_ptr)
Definition: omAllocPrivate.h:100
scaLastAltVar
static short scaLastAltVar(ring r)
Definition: sca.h:25
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:37
slimgb_alg::average_length
int average_length
Definition: tgb_internal.h:273
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:413
slimgb_alg::states
char ** states
Definition: tgb_internal.h:224
pSetCoeff0
#define pSetCoeff0(p, n)
Definition: monomials.h:60
multi_reduction_find
static void multi_reduction_find(red_object *los, int, slimgb_alg *c, int startf, find_erg &erg)
Definition: tgb.cc:4457
exp_number_builder::top_level
poly_tree_node * top_level
Definition: tgb.cc:1992
add_to_reductors
static int add_to_reductors(slimgb_alg *c, poly h, int len, int ecart, BOOLEAN simplified=FALSE)
Definition: tgb.cc:965
poly_crit
static int poly_crit(const void *ap1, const void *ap2)
Definition: tgb.cc:3084
m
int m
Definition: cfEzgcd.cc:121
skStrategy::kNoether
poly kNoether
Definition: kutil.h:321
poly_tree_node::poly_tree_node
poly_tree_node(int sn)
Definition: tgb.cc:1985
slimgb_alg::tmp_pair_lm
poly * tmp_pair_lm
Definition: tgb_internal.h:239
bucket_guess
static int bucket_guess(kBucket *bucket)
Definition: tgb.cc:952
ENLARGE_ALIGN
#define ENLARGE_ALIGN(pointer, type)
assume
#define assume(x)
Definition: mod2.h:390
fwbw
static int fwbw(red_object *los, int i)
Definition: tgb.cc:4387
NULL
#define NULL
Definition: omList.c:10
kSBucketLength
wlen_type kSBucketLength(kBucket *b, poly lm=NULL)
TODO CoefBuckets bercksichtigen.
Definition: tgb.cc:221
red_object::p
poly p
Definition: tgb_internal.h:313
red_object
Definition: tgb_internal.h:309
pSetm
#define pSetm(p)
Definition: polys.h:265
nc_mm_Mult_pp
static poly nc_mm_Mult_pp(const poly m, const poly p, const ring r)
Definition: nc.h:224
iq_crit
static int iq_crit(const void *ap, const void *bp)
Definition: tgb.cc:1340
mflush
#define mflush()
Definition: reporter.h:57
pLmShortDivisibleBy
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition: polys.h:146
slimgb_alg::array_lengths
int array_lengths
Definition: tgb_internal.h:264
l
int l
Definition: cfEzgcd.cc:93
lenS_correct
BOOLEAN lenS_correct(kStrategy strat)
Definition: tgb.cc:907
slimgb_alg::lengths
int * lengths
Definition: tgb_internal.h:232
canonicalize_region
static void canonicalize_region(red_object *los, int l, int u, slimgb_alg *)
Definition: tgb.cc:4445
nDelete
#define nDelete(n)
Definition: numbers.h:17
tgbgauss.h
slim_nsize
int slim_nsize(number n, ring r)
Definition: tgb.cc:73
sort_region_down
static void sort_region_down(red_object *los, int l, int u, slimgb_alg *)
Definition: tgb.cc:4584
kBucket
Definition: kbuckets.h:178
slimgb_alg::completed
BOOLEAN completed
Definition: tgb_internal.h:280
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:234
LObject
class sLObject LObject
Definition: kutil.h:54
pair_better
static BOOLEAN pair_better(sorted_pair_node *a, sorted_pair_node *b, slimgb_alg *c=NULL)
Definition: tgb.cc:3924
red_object::validate
void validate()
Definition: tgb.cc:4828
pSetExp
#define pSetExp(p, i, v)
Definition: polys.h:42
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
MonRedResNP
Definition: tgb_internal.h:146
TEST_OPT_REDTHROUGH
#define TEST_OPT_REDTHROUGH
Definition: options.h:120
slimgb_alg::eliminationProblem
BOOLEAN eliminationProblem
Definition: tgb_internal.h:283
p
int p
Definition: cfModGcd.cc:4019
longrat.h
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:206
skStrategy::initEcart
void(* initEcart)(TObject *L)
Definition: kutil.h:271
simple_reducer::fill_back
kBucket_pt fill_back
Definition: tgb_internal.h:364
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
exp_number_builder::n
int n
Definition: tgb.cc:1993
nInit
#define nInit(i)
Definition: numbers.h:25
p_Init_Special
static poly p_Init_Special(const ring r)
Definition: tgb.cc:137
pLmCmp
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
noro_step< tgb_uint8 >
template void noro_step< tgb_uint8 >(poly *p, int &pn, slimgb_alg *c)
slimgb_alg::syz_comp
int syz_comp
array_lengths should be greater equal n;
Definition: tgb_internal.h:263
slimgb_alg::gcd_of_terms
poly * gcd_of_terms
Definition: tgb_internal.h:242
DataNoroCacheNode::row
SparseRow< number_type > * row
Definition: tgb_internal.h:553
initEcartBBA
void initEcartBBA(TObject *h)
Definition: kutil.cc:1265
pCopy
#define pCopy(p)
return a copy of the poly
Definition: polys.h:180
find_erg
Definition: tgb_internal.h:386
IDELEMS
#define IDELEMS(i)
Definition: simpleideals.h:26
nc_CreateSpoly
static poly nc_CreateSpoly(const poly p1, const poly p2, const ring r)
Definition: nc.h:241
slimgb_alg::easy_product_crit
int easy_product_crit
Definition: tgb_internal.h:271
pNormalize
#define pNormalize(p)
Definition: polys.h:311
slimgb_alg::F_minus
poly_array_list * F_minus
Definition: tgb_internal.h:254
poly_list_node
Definition: tgb_internal.h:182
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: facSparseHensel.h:25
mac_poly_r::coef
number coef
Definition: tgbgauss.h:50
id_Copy
ideal id_Copy(ideal h1, const ring r)
copy an ideal
Definition: simpleideals.cc:404
deleteInS
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1069
id_Compactify
void id_Compactify(ideal id, const ring r)
Definition: simpleideals.cc:1087
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:45
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition: facFqBivarUtil.cc:364
sorted_pair_node::expected_length
wlen_type expected_length
Definition: tgb_internal.h:161
PrintLn
void PrintLn()
Definition: reporter.cc:310
n_Size
static FORCE_INLINE int n_Size(number n, const coeffs r)
return a non-negative measure for the complexity of n; return 0 only when n represents zero; (used fo...
Definition: coeffs.h:570
kInterRed
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3380
rIsSCA
static bool rIsSCA(const ring r)
Definition: nc.h:190
multi_reduce_step
static void multi_reduce_step(find_erg &erg, red_object *r, slimgb_alg *c)
Definition: tgb.cc:4896
DenseRow
Definition: tgb_internal.h:500
p_GetShortExpVector
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4679
npNeg
number npNeg(number c, const coeffs r)
Definition: modulop.cc:200
rField_is_Zp
static BOOLEAN rField_is_Zp(const ring r)
Definition: ring.h:491
TEST_V_FINDMONOM
#define TEST_V_FINDMONOM
Definition: options.h:139
shorten_tails
static void shorten_tails(slimgb_alg *c, poly monom)
Definition: tgb.cc:3677
NoroCache::temp_term
poly temp_term
Definition: tgb_internal.h:593
gcd_of_terms
static poly gcd_of_terms(poly p, ring r)
Definition: tgb.cc:3983
simple_reducer::p_len
int p_len
Definition: tgb_internal.h:365
clearS
static void clearS(poly p, unsigned long p_sev, int l, int *at, int *k, kStrategy strat)
Definition: tgb.cc:1323
pNext
#define pNext(p)
Definition: monomials.h:37
POLYSIZE
#define POLYSIZE
Definition: monomials.h:234
wlen_set
wlen_type * wlen_set
Definition: kutil.h:51
TEST_V_UPTORADICAL
#define TEST_V_UPTORADICAL
Definition: options.h:138
redTailShort
static poly redTailShort(poly h, kStrategy strat)
Definition: tgb.cc:1920
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:211
p_LmShortDivisibleBy
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1855
find_erg::to_reduce_u
int to_reduce_u
Definition: tgb_internal.h:390
exp_number_builder::get_n
int get_n(poly p)
Definition: tgb.cc:1999
nc_kBucketPolyRed_Z
static void nc_kBucketPolyRed_Z(kBucket_pt b, poly p, number *c)
Definition: nc.h:286
slimgb_alg::last_index
int last_index
Definition: tgb_internal.h:268
noro_step< tgb_uint32 >
template void noro_step< tgb_uint32 >(poly *p, int &pn, slimgb_alg *c)
simple_reducer::pre_reduce
virtual void pre_reduce(red_object *r, int l, int u)
Definition: tgb.cc:5008
move_forward_in_S
static void move_forward_in_S(int old_pos, int new_pos, kStrategy strat)
Definition: tgb.cc:1027
nSize
#define nSize(n)
Definition: numbers.h:40
bundle_size_noro
static const int bundle_size_noro
Definition: tgb.cc:37
ascending
static BOOLEAN ascending(int *i, int top)
Definition: tgb.cc:742
ksOldCreateSpoly
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether, ring r)
Definition: kInline.h:1069
red_object::sev
unsigned long sev
Definition: tgb_internal.h:314
rField_is_Q
static BOOLEAN rField_is_Q(const ring r)
Definition: ring.h:497
NoroCacheNode::branches
NoroCacheNode ** branches
Definition: tgb_internal.h:435
wrp
void wrp(poly p)
Definition: polys.h:304
omfree
#define omfree(addr)
Definition: omAllocDecl.h:237
slimgb_alg::max_pairs
int max_pairs
Definition: tgb_internal.h:269
slimgb_alg::to_destroy
poly_list_node * to_destroy
Definition: tgb_internal.h:251
extended_product_criterion
static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg *c)
Definition: tgb.cc:4042