My Project
Loading...
Searching...
No Matches
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))
36static const int bundle_size = 100;
37static const int bundle_size_noro = 10000;
38static const int delay_factor = 3;
39#define ADD_LATER_SIZE 500
40#if 1
42static void add_to_reductors(slimgb_alg* c, poly h, int len, int ecart, BOOLEAN simplified=FALSE);
43static void multi_reduction(red_object* los, int & losl, slimgb_alg* c);
44static void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c);
45static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c);
46static poly gcd_of_terms(poly p, ring r);
47static int tgb_pair_better_gen(const void* ap,const void* bp);
49static BOOLEAN state_is(calc_state state, const int & i, const int & j, slimgb_alg* c);
51static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen);
52static int* make_connections(int from, int to, poly bound, slimgb_alg* c);
53static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state);
54static void shorten_tails(slimgb_alg* c, poly monom);
55static poly redNF2 (poly h,slimgb_alg* c , int &len, number& m,int n=0);
56static poly redNFTail (poly h,const int sl,kStrategy strat, int len);
57static int bucket_guess(kBucket* bucket);
58
59static 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
73int 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
89static 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
109static 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
137static inline poly p_Init_Special (const ring r)
138{
139 return p_Init (r, lm_bin);
140}
141
142static 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
160static inline int pSLength (poly p, int l)
161{
162 return l;
163}
164
165static 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.
173int 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
184int 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
197static inline wlen_type pSLength (poly p, int l)
198{
199 wlen_type c;
200 number coef = pGetCoeff (p);
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));
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 {
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
275static inline wlen_type pSLength (poly p, int l)
276{
277 int c;
278 number coef = pGetCoeff (p);
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
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));
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 {
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.)
343int 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
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
427static 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
446static 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
512static 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
521static 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);
532 {
533 cs = nlQlogSize (coef, currRing->cf);
534 }
535 else
536 cs = nSize (coef);
537 wlen_type erg = cs;
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));
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 {
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;
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
612 }
613 return s;
614}
615
616#if 0 //currently unused
617static void finalize_reduction_step (reduction_step * r)
618{
619 delete r;
620}
621#endif
622#if 0 //currently unused
623static 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
630static 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
636static 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
645int 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
663int 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
675static 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
707static 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
763static BOOLEAN
764trivial_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
818int 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
883static 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
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
916static 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
928static void
929add_to_reductors (slimgb_alg * c, poly h, int len, int ecart,
930 BOOLEAN simplified)
931{
932 //inDebug(h);
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
968static 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
990static 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
1027static 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
1064static 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
1168static 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
1178static 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
1255static 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
1271static 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 */
1285static inline void
1286clearS (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
1303static int iq_crit (const void *ap, const void *bp)
1304{
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
1328static 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;
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);
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 {
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] =
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
1800static 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
1883static poly redTailShort (poly h, kStrategy strat)
1884{
1885 if(h == NULL)
1886 return NULL; //n_Init(1,currRing);
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
1902static 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;
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;
1929 }
1930 }
1931 }
1932}
1933
1934static 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{
1943public:
1944 poly p;
1947 int n;
1948 poly_tree_node (int sn):l (NULL), r (NULL), n (sn)
1949 {
1950 }
1951};
1953{
1954public:
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
1993int terms_sort_crit (const void *a, const void *b)
1994{
1995 return -pLmCmp (*((poly *) a), *((poly *) b));
1996}
1997
1998#if 0 // currently unused
1999static 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
2017static void
2018export_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
2051static void
2052linalg_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;
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
2108static 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
2155void 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
2168void 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
2245void
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
2396MonRedRes
2397noro_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
2523poly 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 }
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
2617std::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
2645void 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
2723static 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 {
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);
2813 if(!h)
2814 continue;
2815
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 {
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 {
2974 {
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
3002static 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
3128poly
3129free_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
3149static 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 =
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
3203slimgb_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;
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 =
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));
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;
3309 strat->honey = TRUE;
3314 strat->tailRing = r;
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);
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;
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
3585ideal 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
3632ideal
3633do_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;
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
3688void 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
3708static BOOLEAN
3709has_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
3729static 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
3797static 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
3808void 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);
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 {
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 {
3944 c->pair_top--;
3945 }
3946}
3947
3948static BOOLEAN
3949state_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
3975static 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
4003static int tgb_pair_better_gen (const void *ap, const void *bp)
4004{
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
4035static 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
4075static 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
4093static inline BOOLEAN
4094extended_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
4115static 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
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
4164static 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
4178static 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
4439static 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
4496static void
4497canonicalize_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
4508static void
4509multi_reduction_find (red_object * los, int /*losl*/, slimgb_alg * c, int startf,
4510 find_erg & erg)
4511#else
4512static void
4513multi_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
4582static int
4583multi_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
4637static 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
4693static 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
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)))
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)
4887}
4888
4890{
4891 flatten ();
4892 int l;
4893 kBucketClear (bucket, &p, &l);
4894 return l;
4895}
4896
4897void 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
4914{
4915 this->pre_reduce (r, l, u);
4916 int i;
4917//debug start
4918
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
5062void simple_reducer::pre_reduce (red_object * /*r*/, int /*l*/, int /*u*/)
5063{
5064}
5065
5066#if 0
5067template int pos_helper<int, int*>(skStrategy*, spolyrec*, int, int*, spolyrec**);
5068template int pos_helper<long, long*>(skStrategy*, spolyrec*, long, long*, spolyrec**);
5069
5070template void noro_step<unsigned char>(spolyrec**, int&, slimgb_alg*);
5071template void noro_step<unsigned int>(spolyrec**, int&, slimgb_alg*);
5072template void noro_step<unsigned short>(spolyrec**, int&, slimgb_alg*);
5073
5074
5075template int term_nodes_sort_crit<unsigned char>(void const*, void const*);
5076template int term_nodes_sort_crit<unsigned int>(void const*, void const*);
5077template int term_nodes_sort_crit<unsigned short>(void const*, void const*);
5078
5079template spolyrec* row_to_poly<unsigned char>(unsigned char*, spolyrec**, int, ip_sring*);
5080template spolyrec* row_to_poly<unsigned int>(unsigned int*, spolyrec**, int, ip_sring*);
5081template spolyrec* row_to_poly<unsigned short>(unsigned short*, spolyrec**, int, ip_sring*);
5082
5083template void simplest_gauss_modp<unsigned char>(unsigned char*, int, int);
5084template void simplest_gauss_modp<unsigned int>(unsigned int*, int, int);
5085template void simplest_gauss_modp<unsigned short>(unsigned short*, int, int);
5086
5087
5088template int modP_lastIndexRow<unsigned char>(unsigned char*, int);
5089template int modP_lastIndexRow<unsigned int>(unsigned int*, int);
5090template int modP_lastIndexRow<unsigned short>(unsigned short*, int);
5091
5092template SparseRow<unsigned char>* noro_red_to_non_poly_t<unsigned char>(spolyrec*, int&, NoroCache<unsigned char>*, slimgb_alg*);
5093template SparseRow<unsigned int>* noro_red_to_non_poly_t<unsigned int>(spolyrec*, int&, NoroCache<unsigned int>*, slimgb_alg*);
5094template SparseRow<unsigned short>* noro_red_to_non_poly_t<unsigned short>(spolyrec*, int&, NoroCache<unsigned short>*, slimgb_alg*);
5095
5096
5097template MonRedResNP<unsigned char> noro_red_mon_to_non_poly<unsigned char>(spolyrec*, NoroCache<unsigned char>*, slimgb_alg*);
5098template MonRedResNP<unsigned int> noro_red_mon_to_non_poly<unsigned int>(spolyrec*, NoroCache<unsigned int>*, slimgb_alg*);
5099template MonRedResNP<unsigned short> noro_red_mon_to_non_poly<unsigned short>(spolyrec*, NoroCache<unsigned short>*, slimgb_alg*);
5100
5101template SparseRow<unsigned char>* noro_red_to_non_poly_dense<unsigned char>(MonRedResNP<unsigned char>*, int, NoroCache<unsigned char>*);
5102template SparseRow<unsigned char>* noro_red_to_non_poly_sparse<unsigned char>(MonRedResNP<unsigned char>*, int, NoroCache<unsigned char>*);
5103template SparseRow<unsigned int>* noro_red_to_non_poly_dense<unsigned int>(MonRedResNP<unsigned int>*, int, NoroCache<unsigned int>*);
5104template SparseRow<unsigned int>* noro_red_to_non_poly_sparse<unsigned int>(MonRedResNP<unsigned int>*, int, NoroCache<unsigned int>*);
5105template SparseRow<unsigned short>* noro_red_to_non_poly_dense<unsigned short>(MonRedResNP<unsigned short>*, int, NoroCache<unsigned short>*);
5106template SparseRow<unsigned short>* noro_red_to_non_poly_sparse<unsigned short>(MonRedResNP<unsigned short>*, int, NoroCache<unsigned short>*);
5107
5108
5109
5111template class DataNoroCacheNode<unsigned int>;
5113
5114template class NoroCache<unsigned char>;
5115template class NoroCache<unsigned int>;
5116template class NoroCache<unsigned short>;
5117
5118
5119
5120template void add_coef_times_dense<unsigned char>(unsigned char*, int, unsigned char const*, int, snumber*);
5121template void add_coef_times_dense<unsigned int>(unsigned int*, int, unsigned int const*, int, snumber*);
5122template void add_coef_times_dense<unsigned short>(unsigned short*, int, unsigned short const*, int, snumber*);
5123template void add_coef_times_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*, snumber*);
5124template void add_coef_times_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*, snumber*);
5125template void add_coef_times_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*, snumber*);
5126template void add_dense<unsigned char>(unsigned char*, int, unsigned char const*, int);
5127template void add_dense<unsigned int>(unsigned int*, int, unsigned int const*, int);
5128template void add_dense<unsigned short>(unsigned short*, int, unsigned short const*, int);
5129template void add_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*);
5130template void add_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*);
5131template void add_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*);
5132
5133
5134template void sub_dense<unsigned char>(unsigned char*, int, unsigned char const*, int);
5135template void sub_dense<unsigned int>(unsigned int*, int, unsigned int const*, int);
5136template void sub_dense<unsigned short>(unsigned short*, int, unsigned short const*, int);
5137template void sub_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*);
5138template void sub_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*);
5139template void sub_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*);
5140template void write_coef_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int);
5141template void write_coef_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int);
5142template void write_coef_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int);
5143template void write_coef_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int);
5144template void write_coef_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int);
5145template void write_coef_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int);
5146template void write_coef_times_xx_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int, snumber*);
5147template void write_coef_times_xx_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int, snumber*);
5148template void write_coef_times_xx_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int, snumber*);
5149template void write_coef_times_xx_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int, snumber*);
5150template void write_coef_times_xx_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int, snumber*);
5151template void write_coef_times_xx_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int, snumber*);
5152template void write_minus_coef_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int);
5153template void write_minus_coef_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int);
5154template void write_minus_coef_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int);
5155template void write_minus_coef_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int);
5156template void write_minus_coef_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int);
5157template void write_minus_coef_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int);
5158
5159
5160template class std::vector<DataNoroCacheNode<unsigned char>*>;
5161template class std::vector<DataNoroCacheNode<unsigned int>*>;
5162template class std::vector<DataNoroCacheNode<unsigned short>*>;
5163template class std::vector<PolySimple>;
5164
5165template void std::sort( CoefIdx<unsigned char>* , CoefIdx<unsigned char>* );
5166template void std::sort( CoefIdx<unsigned int>* , CoefIdx<unsigned int>* );
5167template void std::sort( CoefIdx<unsigned short>*, CoefIdx<unsigned short>* );
5168
5169template void std::sort_heap<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5170template void std::sort_heap<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5171template void std::sort_heap<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5172
5173template void std::make_heap<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5174template void std::make_heap<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5175template void std::make_heap<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5176#endif
5177
5178#if 0
5179template void std::__final_insertion_sort<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5180template void std::__final_insertion_sort<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5181template void std::__final_insertion_sort<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5182
5183template void std::__introsort_loop<CoefIdx<unsigned char>*, long>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, long);
5184template void std::__introsort_loop<CoefIdx<unsigned int>*, long>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, long);
5185template void std::__introsort_loop<CoefIdx<unsigned short>*, long>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, long);
5186
5187template void std::__heap_select<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5188template void std::__heap_select<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5189template void std::__heap_select<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5190
5191template void std::__insertion_sort<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5192template void std::__insertion_sort<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5193template void std::__insertion_sort<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5194
5195template void std::__move_median_first<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5196template void std::__move_median_first<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5197template void std::__move_median_first<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5198
5199template void std::__unguarded_linear_insert<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*);
5200template void std::__unguarded_linear_insert<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*);
5201template void std::__unguarded_linear_insert<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*);
5202
5203template void std::__adjust_heap<CoefIdx<unsigned char>*, long, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, long, long, CoefIdx<unsigned char>);
5204template void std::__adjust_heap<CoefIdx<unsigned int>*, long, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, long, long, CoefIdx<unsigned int>);
5205template void std::__adjust_heap<CoefIdx<unsigned short>*, long, CoefIdx<unsigned short> >(CoefIdx<unsigned short>*, long, long, CoefIdx<unsigned short>);
5206
5207template void std::__push_heap<CoefIdx<unsigned char>*, long, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, long, long, CoefIdx<unsigned char>);
5208template void std::__push_heap<CoefIdx<unsigned int>*, long, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, long, long, CoefIdx<unsigned int>);
5209template void std::__push_heap<CoefIdx<unsigned short>*, long, CoefIdx<unsigned short> >(CoefIdx<unsigned short>*, long, long, CoefIdx<unsigned short>);
5210
5211template CoefIdx<unsigned char>* std::__unguarded_partition<CoefIdx<unsigned char>*, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char> const&);
5212template CoefIdx<unsigned int>* std::__unguarded_partition<CoefIdx<unsigned int>*, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int> const&);
5213template 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:4077
CanonicalForm b
Definition: cfModGcd.cc:4102
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 > * getCacheReference(poly term)
NoroCacheNode root
Definition: tgb_internal.h:740
poly lookup(poly term, BOOLEAN &succ, int &len)
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
Definition: tgb_internal.h:633
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
STATIC_VAR omBin lm_bin
Definition: fast_mult.cc:429
#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:1205
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:1210
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:9884
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9732
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1163
void initEcartBBA(TObject *h)
Definition: kutil.cc:1392
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9085
wlen_type * wlen_set
Definition: kutil.h:55
int64 wlen_type
Definition: kutil.h:54
int * intset
Definition: kutil.h:53
poly redNFTail(poly h, const int sl, kStrategy strat)
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:107
#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
#define pSetCoeff0(p, n)
Definition: monomials.h:59
#define p_GetCoeff(p, r)
Definition: monomials.h:50
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 __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:75
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
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
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 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
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
Definition: tgb.cc:1389
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
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
Definition: tgb.cc:3914
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
static void c_S_element_changed_hook(int pos, slimgb_alg *c)
Definition: tgb.cc:1934
sorted_pair_node * top_pair(slimgb_alg *c)
Definition: tgb.cc:3890
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
static wlen_type do_pELength(poly p, slimgb_alg *c, int dlm=-1)
Definition: tgb.cc:446
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
int tgb_pair_better_gen2(const void *ap, const void *bp)
Definition: tgb.cc:645
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
Definition: tgb.cc:716
void now_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *c)
Definition: tgb.cc:3688
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
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
Definition: tgb.cc:1389
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 free_sorted_pair_node(sorted_pair_node *s, const ring r)
Definition: tgb.cc:3968
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