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