34#define BUCKETS_FOR_NORO_RED 1
35#define SR_HDL(A) ((long)(A))
39#define ADD_LATER_SIZE 500
153#define degbound(p) assume(pTotaldegree(p)<10)
240 for(
i =
b->buckets_used;
i >= 0;
i--)
243 s +=
b->buckets_length[
i] ;
245#ifdef HAVE_COEF_BUCKETS
247 if(
b->coef[0] !=
NULL)
313 for(
i =
b->buckets_used;
i >= 0;
i--)
316 s +=
b->buckets_length[
i] ;
318#ifdef HAVE_COEF_BUCKETS
320 if(
b->coef[0] !=
NULL)
442 return r->block0[last_block];
516 for(
i =
b->buckets_used;
i >= 0;
i--)
524 s +=
b->buckets_length[
i];
614#ifdef HAVE_COEF_BUCKETS
658static int LObject_better_gen (
const void *
ap,
const void *bp)
671static int pLmCmp_func_inverted (
const void *ap1,
const void *ap2)
674 p1 = *((poly *) ap1);
675 p2 = *((poly *) ap2);
689 long not_sev = ~obj.sev;
690 for(
int i = 0;
i <= strat->
sl;
i++)
702 for(
int i = 0;
i <= strat->
sl;
i++)
746 if(
i[top] <
i[top - 1])
755 int *a = (
int *)
omalloc (qn *
sizeof (
int));
770 for(
i = 0;
i < qn;
i++)
785 for(
i = qn - 1;
i >= 0;
i--)
792 memmove (
p + a[
i] + (1 +
i),
p + a[
i],
size);
802 poly p1 = c->
S->m[pos1];
803 poly p2 = c->
S->m[pos2];
812 if((gcd1 !=
NULL) && (gcd2 !=
NULL))
859 for(
i =
l + 1;
i <= u;
i++)
893 for(
int n = 0; ((n < c->
n) && (i_con[n] >= 0)); n++)
910 for(
i = 0;
i <= strat->
sl;
i++)
923 while(i <= strat->sl)
926 P.sev = strat->
sevS[
i];
935 for(
j = 0;
j < c->
n;
j++)
937 if(c->
S->m[
j] == P.p)
956 for(
i = bucket->buckets_used;
i >= 0;
i--)
958 if(bucket->buckets[
i])
959 sum += bucket->buckets_length[
i];
978 memset (&P, 0,
sizeof (P));
982 P.FDeg = c->
r->pFDeg (P.p, c->
r);
1012 for(
i = 0;
i < pos;
i++)
1017 for(
i = pos + 1;
i < c->
n;
i++)
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];
1038 length_w = strat->
lenSw[old_pos];
1040 for(
i = old_pos;
i > new_pos;
i--)
1042 strat->
S[
i] = strat->
S[
i - 1];
1048 for(
i = old_pos;
i > new_pos;
i--)
1051 for(
i = old_pos;
i > new_pos;
i--)
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;
1060 strat->
lenSw[new_pos] = length_w;
1066 assume (old_pos <= new_pos);
1067 poly
p = strat->
S[old_pos];
1068 int ecart = strat->
ecartS[old_pos];
1069 long sev = strat->
sevS[old_pos];
1070 int s_2_r = strat->
S_2_R[old_pos];
1075 length_w = strat->
lenSw[old_pos];
1077 for(
i = old_pos;
i < new_pos;
i++)
1079 strat->
S[
i] = strat->
S[
i + 1];
1085 for(
i = old_pos;
i < new_pos;
i++)
1088 for(
i = old_pos;
i < new_pos;
i++)
1091 strat->
S[new_pos] =
p;
1092 strat->
ecartS[new_pos] = ecart;
1093 strat->
sevS[new_pos] = sev;
1094 strat->
S_2_R[new_pos] = s_2_r;
1097 strat->
lenSw[new_pos] = length_w;
1104 int *cans = (
int *)
omAlloc (c->
n * sizeof (
int));
1105 int *connected = (
int *)
omAlloc (c->
n * sizeof (
int));
1107 int cans_length = 1;
1108 connected[0] = from;
1109 int last_cans_pos = -1;
1110 int connected_length = 1;
1111 long neg_bounds_short = ~p_GetShortExpVector (
bound, c->
r);
1113 int not_yet_found = cans_length;
1114 int con_checked = 0;
1119 if((con_checked < connected_length) && (not_yet_found > 0))
1121 pos = connected[con_checked];
1122 for(
int i = 0;
i < cans_length;
i++)
1131 connected[connected_length] = cans[
i];
1136 if(connected[connected_length - 1] == to)
1138 if(connected_length < c->n)
1140 connected[connected_length] = -1;
1151 for(last_cans_pos++; last_cans_pos <= c->
n; last_cans_pos++)
1153 if(last_cans_pos == c->
n)
1155 if(connected_length < c->n)
1157 connected[connected_length] = -1;
1162 if((last_cans_pos == from) || (last_cans_pos == to))
1166 neg_bounds_short, c->
r))
1168 cans[cans_length] = last_cans_pos;
1174 for(
int i = 0;
i < con_checked;
i++)
1176 if(
has_t_rep (connected[
i], last_cans_pos, c))
1178 connected[connected_length] = last_cans_pos;
1180 cans[cans_length - 1] = -1;
1182 if(connected[connected_length - 1] == to)
1184 if(connected_length < c->n)
1186 connected[connected_length] = -1;
1196 if(connected_length < c->n)
1198 connected[connected_length] = -1;
1205static inline poly p_MoveHead (poly
p,
omBin b)
1228 for(
int n = 0; ((n < c->
n) && (i_con[n] >= 0)); n++)
1259 sugar +=
si_max (t_i, t_j);
1263 for(
int m = 0; ((
m < c->
n) && (i_con[
m] >= 0));
m++)
1274 for(
int m = 0; ((
m < c->
n) && (j_con[
m] >= 0));
m++)
1328 if(
l >= strat->
lenS[*at])
1388 res *= el1 + el2 - 2;
1452#define ENLARGE(pointer, type) pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type))
1454#define ENLARGE_ALIGN(pointer, type) {if(pointer)\
1455 pointer=(type*)omReallocAligned(pointer, c->array_lengths*sizeof(type));\
1456 else pointer=(type*)omAllocAligned(c->array_lengths*sizeof(type));}
1478#ifndef USE_STDVECBOOL
1496 ecart = sugar - c->
T_deg[
i];
1518 c->
states.push_back (dynamic_bitset <> (
i));
1521#ifdef USE_STDVECBOOL
1523 c->
states.push_back (vector < bool > (
i));
1540 for(
j = 0;
j <
i;
j++)
1697 for(upper = lower + 1; upper < spc; upper++)
1699 if(!
pLmEqual (nodes[lower]->lcm_of_lm, nodes[upper]->lcm_of_lm))
1703 if(
has_t_rep (nodes[upper]->
i, nodes[upper]->
j, c))
1709 for(z = 0; z < spc_final; z++)
1712 (nodes_final[z]->lcm_of_lm, nodes[lower]->lcm_of_lm, c->
r))
1721 for(; lower <= upper; lower++)
1725 nodes[lower] =
NULL;
1732 p_Test (nodes[lower]->lcm_of_lm, c->
r);
1736 nodes_final[spc_final] =
1739 *(nodes_final[spc_final++]) = *(nodes[lower]);
1741 nodes[lower] =
NULL;
1742 for(lower = lower + 1; lower <= upper; lower++)
1746 nodes[lower] =
NULL;
1755 assume (spc_final <= spc);
1790 m_iLastAltVar - m_iFirstAltVar + 1;
1793 poly *array_arg = (poly *)
omalloc (
N *
sizeof (poly));
1797 for(
unsigned short v = m_iFirstAltVar;
v <= m_iLastAltVar;
v++)
1852 P.SetShortExpVector ();
1867 if((
j >= 0) && ((!n) ||
1868 ((strat->
lenS[
j] <= n) &&
1885 number m2 =
nMult (
m, coef);
1899 P.SetShortExpVector ();
1930 for(
i = 0;
i <= strat->
sl;
i++)
1932 if((strat->
lenS[
i] > 2)
1947 for(
i = 0;
i < fixpos;
i++)
1957 for(
i = fixpos + 1;
i < c->
n;
i++)
2002 while(*node !=
NULL)
2004 int c =
pLmCmp (
p, (*node)->p);
2008 node = &((*node)->r);
2010 node = &((*node)->l);
2025 if((r2.
p != ro.
p) || (r2.
sev != ro.
sev))
2032 return -
pLmCmp (*((poly *) a), *((poly *)
b));
2036static void unify_terms (poly * terms,
int &sum)
2046 terms[++
last] = terms[curr];
2055export_mat (number *
number_array,
int pn,
int tn,
const char *format_str,
2059 sprintf (matname, format_str, mat_nr);
2060 FILE *out = fopen (matname,
"w");
2062 fprintf (out,
"mat=[\n");
2063 for(
i = 0;
i < pn;
i++)
2065 fprintf (out,
"[\n");
2066 for(
j = 0;
j < tn;
j++)
2070 fprintf (out,
", ");
2075 fprintf (out,
"],\n");
2077 fprintf (out,
"],\n");
2079 fprintf (out,
"]\n");
2089linalg_step_modp (poly *
p, poly * p_out,
int &pn, poly * terms,
int tn,
2096 const number_type zero = 0;
2097 int array_size = pn * tn;
2099 (number_type *)
omalloc (pn * tn *
sizeof (number_type));
2101 for(
i = 0;
i < array_size;
i++)
2105 for(
i = 0;
i < pn;
i++)
2114 export_mat (
number_array, pn, tn,
"mat%i.py", ++export_n);
2120 for(
i = 0;
i < pn;
i++)
2137 p_out[p_pos++] =
NULL;
2140 export_mat (
number_array, pn, tn,
"mat%i.py", ++export_n);
2148 int *ibuf = (
int *)
omalloc (pn *
sizeof (
int));
2151 for(
j = 0;
j < pn;
j++)
2157 for(
j = 0;
j < pn;
j++)
2164 for(
j = 0;
j < pn;
j++)
2166 memmove (big_sbuf + partsum, sbuf[
j],
2191#ifndef NORO_NON_POLY
2192void NoroCache::evaluateRows ()
2224#ifndef NORO_SPARSE_ROWS_PRE
2254 row->
array = (number *)
omalloc ((len) *
sizeof (number));
2255 memcpy (row->
array, a + row->
begin, len * sizeof (number));
2274 PrintS (
"F4 calc wrong, as poly len was wrong\n");
2283 NoroCache::evaluatePlaceHolder (number * row,
2284 std::vector < NoroPlaceHolder >
2288 int s = place_holders.size ();
2292 for(
i = 0;
i <
s;
i++)
2295 number coef = place_holders[
i].coef;
2302 #ifndef NORO_SPARSE_ROWS_PRE
2306 number *ref_begin = ref_row->
array;
2307 number *ref_end = ref_row->
array + (ref_row->
end - ref_row->
begin);
2308 number *my_pos = row + ref_row->
begin;
2312 while(ref_begin != ref_end)
2321 while(ref_begin != ref_end)
2324 *my_pos =
npAddM (*my_pos, *ref_begin);
2333 int n = ref_row->
len;
2339 for(
j = 0;
j < n;
j++)
2341 int idx = idx_array[
j];
2342 number ref_coef = coef_array[
j];
2348 for(
j = 0;
j < n;
j++)
2350 int idx = idx_array[
j];
2351 number ref_coef = coef_array[
j];
2352 row[idx] =
npAddM (row[idx], ref_coef);
2361 for(
i = 0;
i <
s;
i++)
2364 number coef = place_holders[
i].coef;
2371 #ifndef NORO_SPARSE_ROWS_PRE
2375 number *ref_begin = ref_row->
array;
2376 number *ref_end = ref_row->
array + (ref_row->
end - ref_row->
begin);
2377 number *my_pos = row + ref_row->
begin;
2381 while(ref_begin != ref_end)
2390 while(ref_begin != ref_end)
2392 *my_pos =
npAddM (*my_pos, *ref_begin);
2401 int n = ref_row->
len;
2407 for(
j = 0;
j < n;
j++)
2409 int idx = idx_array[
j];
2410 number ref_coef = coef_array[
j];
2416 for(
j = 0;
j < n;
j++)
2418 int idx = idx_array[
j];
2419 number ref_coef = coef_array[
j];
2420 row[idx] =
npAddM (row[idx], ref_coef);
2432#ifndef NORO_NON_POLY
2436 MonRedRes res_holder;
2439 res_holder.changed =
TRUE;
2452 res_holder.ref = ref;
2453 res_holder.onlyBorrowed =
TRUE;
2454 res_holder.changed =
TRUE;
2462 poly cache_lookup = cache->
lookup (t, succ, res_holder.len);
2465 if(cache_lookup == t)
2470 res_holder.changed =
FALSE;
2472 res_holder.coef =
npInit (1);
2474 res_holder.onlyBorrowed =
FALSE;
2481 res_holder.p = cache_lookup;
2483 res_holder.onlyBorrowed =
TRUE;
2511 res = noro_red_non_unique (
res, res_holder.len, cache, c);
2517 res_holder.changed =
TRUE;
2519 res_holder.coef = coef_bak;
2520 res_holder.onlyBorrowed =
TRUE;
2521 res_holder.ref = ref;
2532 res_holder.ref = cache->
insert (t, t, res_holder.len);
2537 res_holder.changed =
FALSE;
2540 res_holder.coef =
npInit (1);
2541 res_holder.onlyBorrowed =
FALSE;
2547 res_holder.coef = coef_bak;
2548 res_holder.onlyBorrowed =
TRUE;
2549 res_holder.changed =
FALSE;
2558#ifndef NORO_NON_POLY
2571 poly unchanged_head =
NULL;
2572 poly unchanged_tail =
NULL;
2573 int unchanged_size = 0;
2583 MonRedRes red = noro_red_mon (t,
FALSE, cache, c);
2584 if((!(red.changed)) && (!(red.onlyBorrowed)))
2591 pNext (unchanged_tail) = red.p;
2592 pIter (unchanged_tail);
2596 unchanged_tail = red.p;
2597 unchanged_head = red.p;
2603 if(red.onlyBorrowed)
2630#ifdef NORO_SPARSE_ROWS_PRE
2653#ifndef NORO_NON_POLY
2654std::vector < NoroPlaceHolder > noro_red (poly
p,
int &len,
NoroCache * cache,
2657 std::vector < NoroPlaceHolder >
res;
2664 MonRedRes red = noro_red_mon (t,
TRUE, cache, c);
2665 assume (red.onlyBorrowed);
2671 assume (!((
h.ref->value_poly ==
NULL) && (
h.ref->value_len != 0)));
2672 if(
h.ref->value_poly)
2684 poly *reduced = (poly *)
omalloc (pn *
sizeof (poly));
2686 int *reduced_len = (
int *)
omalloc (pn *
sizeof (
int));
2693 for(
j = 0;
j < pn;
j++)
2703 h = noro_red (
p_Copy (
h, c->
r), h_len, &cache, c);
2713 reduced[reduced_c] =
h;
2714 reduced_len[reduced_c] = h_len;
2717 Print (
"%d ", h_len);
2720 int reduced_sum = 0;
2721 for(
j = 0;
j < reduced_c;
j++)
2723 reduced_sum += reduced_len[
j];
2725 poly *terms = (poly *)
omalloc (reduced_sum *
sizeof (poly));
2727 for(
j = 0;
j < reduced_c;
j++)
2729 poly
h = reduced[
j];
2735 assume (tc <= reduced_sum);
2738 assume (tc == reduced_sum);
2740 int nterms = reduced_sum;
2743 unify_terms (terms, nterms);
2746 int rank = reduced_c;
2747 linalg_step_modp (reduced,
p, rank, terms, nterms, c);
2772 for(
i = 0;
i < c->
n;
i++)
2784 poly *
p = (poly *)
omAlloc ((max_pairs + 1) *
sizeof (poly));
2787 while(
i < max_pairs)
2796 if(
s->deg > curr_deg)
2842 if((!c->
nc) & (!(use_noro)))
2862#ifdef TGB_RESORT_PAIRS
2863 c->replaced =
new bool[c->
n];
2913 for(
j = 0;
j <
i;
j++)
2922 buf[
j].initial_quality =
buf[
j].guess_quality (c);
2930 Print (
"%dM[%d,", curr_deg,
i);
2934#ifdef TGB_RESORT_PAIRS
2945 if((c->replaced[c->
apairs[e]->
i]) || (c->replaced[c->
apairs[e]->
j]))
2958 for(
k = 0;
k <
i;
k++)
2962 for(k2 = 0; k2 <
i; k2++)
2978 poly *add_those = (poly *)
omalloc (
i *
sizeof (poly));
2979 for(
j = 0;
j <
i;
j++)
3009#ifdef TGB_RESORT_PAIRS
3046 P.SetShortExpVector ();
3091 P.SetShortExpVector ();
3150 poly *set_this = &
p;
3155 (*set_this) =
pLmInit (monoms[monom_index - 1 - r->
exp]);
3157 set_this = &((*set_this)->next);
3169 p1 = *((poly *) ap1);
3170 p2 = *((poly *) ap2);
3191 for(
int i = 0;
i <
s;
i++)
3233 for(hzz = 0; hzz <
IDELEMS (I); hzz++)
3237 poly t = I->m[hzz]->next;
3307#ifdef USE_STDVECBOOL
3357 poly *array_arg = I->m;
3382 for(
i = 1;
i <
n;
i++)
3416 for(piter = 0; piter <=
pair_top; piter++)
3422 if(
s->lcm_of_lm !=
NULL)
3424 add[pos] =
s->lcm_of_lm;
3439 for(piter = 0; piter <=
pair_top; piter++)
3483#ifndef USE_STDVECBOOL
3484 for(
int z = 1 ; z < c->
n; z++)
3494 for(
int z = 0; z < c->
n; z++)
3516 for(
i = 0;
i < c->
n;
i++)
3527 Print (
"\nNF:%i product criterion:%i, ext_product criterion:%i \n",
3536 for(
j = 0;
j < c->
n;
j++)
3566 for(
i = 0;
i < c->
n;
i++)
3571 for(
j = 0;
j < c->
n;
j++)
3573 if((c->
S->m[
j] ==
NULL) || (
i ==
j))
3609 if(orig_ring != new_ring)
3626 s_h =
id_Copy (arg_I, orig_ring);
3630 ideal s_result =
do_t_rep_gb (new_ring, s_h, syz_comp, F4_mode, pos);
3632 if(orig_ring != new_ring)
3730 assume (arg_i < state->n);
3731 assume (arg_j < state->n);
3747static int pLcmDeg (poly a, poly
b)
3763 for(
int i = 0;
i < c->
n;
i++)
3769 poly tail = c->
S->m[
i]->next;
3770 poly prev = c->
S->m[
i];
3772 while((tail !=
NULL) && (
pLmCmp (tail, monom) >= 0))
3776 did_something =
TRUE;
3777 prev->next = tail->next;
3796 for(
int z = 0; z <= c->
strat->
sl; z++)
3805 for(
int z = new_pos - 1; z >= 0; z--)
3814 assume (new_pos <= old_pos);
3819 if(new_pos < old_pos)
3846 for(deg = lower; deg <= upper; deg++)
3849 for(
i = 0;
i <
n;
i++)
3893 new_pos = new_pos - 1;
3905 for(
i = 0;
i < this->
n; i++)
3907 for(
j = 0;
j <
i;
j++)
3992 return (c->
states[arg_i][arg_j] == state);
3995 return (c->
states[arg_j][arg_i] == state);
4022 if(a->
i + a->
j <
b->i +
b->j)
4024 if(a->
i + a->
j >
b->i +
b->j)
4054 if(a->
i + a->
j <
b->i +
b->j)
4056 if(a->
i + a->
j >
b->i +
b->j)
4085 for(
i = max_g_0;
i;
i--)
4091 if((max_g_0 == 0) && (
pGetExp (
m,
i) > 0))
4145static poly kBucketGcd (
kBucket *
b, ring r)
4153 if(
b->buckets[
i] !=
NULL)
4238 los[best].
p = los[best].
bucket->buckets[b_pos];
4239 qc =
pQuality (los[best].bucket->buckets[b_pos], c);
4269 assume (qc == los[best].guess_quality (c));
4274 los[best].
p = los[best].
bucket->buckets[b_pos];
4275 qc =
pQuality (los[best].bucket->buckets[b_pos], c);
4294 PrintS (
"Wrong wlen_type");
4300 los[best].
p = los[best].
bucket->buckets[b_pos];
4301 qc =
pQuality (los[best].bucket->buckets[b_pos], c);
4313 if(qc < quality_a / 2)
4367 while((il > 0) &&
pLmEqual (los[il - 1].
p, los[il].
p))
4389 clear_into = los[bp].
p;
4401 for(z = c->
n; z; z--)
4403 if(
p == c->
S->m[z - 1])
4414#ifdef TGB_RESORT_PAIRS
4416 c->replaced[pos_in_c] =
TRUE;
4419 c->
S->m[pos_in_c] = clear_into;
4420 c->
lengths[pos_in_c] = new_length;
4452#ifdef FIND_DETERMINISTIC
4481 step =
si_min (i2, step);
4493 if((!incr) && (step == 1))
4518 step = (step + 1) / 2;
4531 for(
i =
l;
i <= u;
i++)
4551 assume ((startf == losl - 1)
4552 || (
pLmCmp (los[startf].
p, los[startf + 1].
p) == -1));
4569 int i2 =
fwbw (los,
i);
4584 int i2 =
fwbw (los,
i);
4627 memmove (los + (
int) (
last + 1 - deleted), los + (
last + 1),
4635 if((
last >= 0) && (
last != losl - 1))
4636 memmove (los + (
int) (
last + 1 - deleted), los +
last + 1,
4668 int r_size = u -
l + 1;
4671 int *new_indices = (
int *)
omalloc ((r_size) *
sizeof (int));
4674 for(
i =
l;
i <= u;
i++)
4685 new_indices[
i -
l] =
l;
4690 for(
int i = 0;
i < r_size;
i++)
4692 new_indices[
i] +=
i;
4693 los_region[
i] = los[
l +
i];
4694 assume ((
i == 0) || (new_indices[
i] > new_indices[
i - 1]));
4702 if(new_indices[
i] ==
j)
4704 los[
j] = los_region[
i];
4724 poly *delay = (poly *)
omAlloc (losl *
sizeof (poly));
4732 for(
i = 0;
i < losl;
i++)
4737 if(los[
i].initial_quality > max_initial_quality)
4744 int curr_pos = losl - 1;
4748 while(curr_pos >= 0)
4753 int pn_noro = curr_pos + 1;
4754 poly *p_noro = (poly *)
omAlloc (pn_noro *
sizeof (poly));
4755 for(
i = 0;
i < pn_noro;
i++)
4778 for(
i = 0;
i < pn_noro;
i++)
4780 los[
i].
p = p_noro[
i];
4789 curr_pos -= deleted;
4815 assume (los[
i].initial_quality > 0);
4816 if(los[
i].guess_quality (c)
4822 if(los[
i].guess_quality (c) >
delay_factor * max_initial_quality)
4828 delay[delay_s] = los[
i].
p;
4843 curr_pos -= deleted;
4855#ifdef FIND_DETERMINISTIC
4954 for(
i =
l;
i <= u;
i++)
4958 for(
i =
l;
i <= u;
i++)
5018 work_on_copy =
TRUE;
5055 int reducer_deg = 0;
5068 reducer_deg = lm_deg + ecart;
5072 if((!work_on_copy) && (!erg.
fromS))
5103template int term_nodes_sort_crit<unsigned char>(
void const*,
void const*);
5104template int term_nodes_sort_crit<unsigned int>(
void const*,
void const*);
5105template int term_nodes_sort_crit<unsigned short>(
void const*,
void const*);
5111template void simplest_gauss_modp<unsigned char>(
unsigned char*,
int,
int);
5112template void simplest_gauss_modp<unsigned int>(
unsigned int*,
int,
int);
5113template void simplest_gauss_modp<unsigned short>(
unsigned short*,
int,
int);
5116template int modP_lastIndexRow<unsigned char>(
unsigned char*,
int);
5117template int modP_lastIndexRow<unsigned int>(
unsigned int*,
int);
5118template int modP_lastIndexRow<unsigned short>(
unsigned short*,
int);
5148template void add_coef_times_dense<unsigned char>(
unsigned char*,
int,
unsigned char const*,
int,
snumber*);
5149template void add_coef_times_dense<unsigned int>(
unsigned int*,
int,
unsigned int const*,
int,
snumber*);
5150template void add_coef_times_dense<unsigned short>(
unsigned short*,
int,
unsigned short const*,
int,
snumber*);
5154template void add_dense<unsigned char>(
unsigned char*,
int,
unsigned char const*,
int);
5155template void add_dense<unsigned int>(
unsigned int*,
int,
unsigned int const*,
int);
5156template void add_dense<unsigned short>(
unsigned short*,
int,
unsigned short const*,
int);
5162template void sub_dense<unsigned char>(
unsigned char*,
int,
unsigned char const*,
int);
5163template void sub_dense<unsigned int>(
unsigned int*,
int,
unsigned int const*,
int);
5164template void sub_dense<unsigned short>(
unsigned short*,
int,
unsigned short const*,
int);
5168template void write_coef_idx_to_buffer_dense<unsigned char>(
CoefIdx<unsigned char>*,
int&,
unsigned char*,
int);
5169template void write_coef_idx_to_buffer_dense<unsigned int>(
CoefIdx<unsigned int>*,
int&,
unsigned int*,
int);
5170template void write_coef_idx_to_buffer_dense<unsigned short>(
CoefIdx<unsigned short>*,
int&,
unsigned short*,
int);
5171template void write_coef_idx_to_buffer<unsigned char>(
CoefIdx<unsigned char>*,
int&,
int*,
unsigned char*,
int);
5172template void write_coef_idx_to_buffer<unsigned int>(
CoefIdx<unsigned int>*,
int&,
int*,
unsigned int*,
int);
5173template void write_coef_idx_to_buffer<unsigned short>(
CoefIdx<unsigned short>*,
int&,
int*,
unsigned short*,
int);
5180template void write_minus_coef_idx_to_buffer_dense<unsigned char>(
CoefIdx<unsigned char>*,
int&,
unsigned char*,
int);
5181template void write_minus_coef_idx_to_buffer_dense<unsigned int>(
CoefIdx<unsigned int>*,
int&,
unsigned int*,
int);
5182template void write_minus_coef_idx_to_buffer_dense<unsigned short>(
CoefIdx<unsigned short>*,
int&,
unsigned short*,
int);
5183template void write_minus_coef_idx_to_buffer<unsigned char>(
CoefIdx<unsigned char>*,
int&,
int*,
unsigned char*,
int);
5184template void write_minus_coef_idx_to_buffer<unsigned int>(
CoefIdx<unsigned int>*,
int&,
int*,
unsigned int*,
int);
5185template void write_minus_coef_idx_to_buffer<unsigned short>(
CoefIdx<unsigned short>*,
int&,
int*,
unsigned short*,
int);
5188template class std::vector<DataNoroCacheNode<unsigned char>*>;
5189template class std::vector<DataNoroCacheNode<unsigned int>*>;
5190template class std::vector<DataNoroCacheNode<unsigned short>*>;
5191template class std::vector<PolySimple>;
static int si_max(const int a, const int b)
static int si_min(const int a, const int b)
const CanonicalForm CFMap CFMap & N
static CanonicalForm bound(const CFMatrix &M)
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
NoroCacheNode ** branches
int nIrreducibleMonomials
DataNoroCacheNode< number_type > * getCacheReference(poly term)
poly lookup(poly term, BOOLEAN &succ, int &len)
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
static const int backLinkCode
poly_tree_node * top_level
wlen_type initial_quality
wlen_type guess_quality(slimgb_alg *c)
makes on each red_object in a region a single_step
virtual ~reduction_step()
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,...
virtual void pre_reduce(red_object *r, int l, int u)
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,...
virtual void do_reduce(red_object &ro)
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
void(* initEcart)(TObject *L)
unsigned long pTotaldegree(poly p)
int_pair_node * soon_free
sorted_pair_node ** apairs
BOOLEAN use_noro_last_block
int extended_product_crit
sorted_pair_node ** tmp_spn
void introduceDelayedPairs(poly *pa, int s)
unsigned int reduction_steps
poly_array_list * F_minus
slimgb_alg(ideal I, int syz_comp, BOOLEAN F4, int deg_pos)
void cleanDegs(int lower, int upper)
int syz_comp
array_lengths should be greater equal n;
int pTotaldegree_full(poly p)
BOOLEAN eliminationProblem
wlen_type * weighted_lengths
poly_list_node * to_destroy
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...
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
BOOLEAN pa(leftv res, leftv args)
void bit_reduce(poly &f, ring r)
const CanonicalForm int s
const Variable & v
< [in] a sqrfree bivariate poly
CFArray copy(const CFList &list)
write elements of list into an array
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
void sort(CFArray &A, int l=0)
quick sort A
#define idDelete(H)
delete an ideal
ideal id_Copy(ideal h1, const ring r)
copy an ideal
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN length(leftv result, leftv arg)
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether, ring r)
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
void kBucketDestroy(kBucket_pt *bucket_pt)
void kBucketInit(kBucket_pt bucket, poly lm, int length)
poly kBucketExtractLm(kBucket_pt bucket)
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
Add to Bucket a poly ,i.e. Bpoly == q+Bpoly.
const poly kBucketGetLm(kBucket_pt bucket)
void kBucketSimpleContent(kBucket_pt bucket)
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)
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
ideal kInterRed(ideal F, ideal Q)
void initBuchMoraPos(kStrategy strat)
void initBuchMoraCrit(kStrategy strat)
void deleteInS(int i, kStrategy strat)
void initEcartBBA(TObject *h)
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
static poly nc_mm_Mult_pp(const poly m, const poly p, const ring r)
static bool rIsSCA(const ring r)
static poly nc_CreateSpoly(const poly p1, const poly p2, const ring r)
static void nc_kBucketPolyRed_Z(kBucket_pt b, poly p, number *c)
poly sca_pp_Mult_xi_pp(short i, const poly pPoly, const ring rRing)
static FORCE_INLINE int nlQlogSize(number n, const coeffs r)
only used by slimgb (tgb.cc)
'SR_INT' is the type of those integers small enough to fit into 29 bits.
STATIC_VAR unsigned add[]
number npNeg(number c, const coeffs r)
long npInt(number &n, const coeffs r)
static BOOLEAN npIsOne(number a, const coeffs)
static number npAddM(number a, number b, const coeffs r)
static number npInit(long i, const coeffs r)
static number nvMult(number a, number b, const coeffs r)
static number npMult(number a, number b, const coeffs r)
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
#define __p_GetComp(p, r)
gmp_float exp(const gmp_float &a)
#define omrealloc(addr, size)
#define omTypeAllocBin(type, addr, bin)
#define omFreeBinAddr(addr)
#define omSizeWOfBin(bin_ptr)
#define omGetSpecBin(size)
#define omUnGetSpecBin(bin_ptr)
#define TEST_OPT_INTSTRATEGY
#define TEST_V_UPTORADICAL
#define TEST_OPT_DEGBOUND
#define TEST_OPT_REDTHROUGH
#define TEST_V_MODPSOLVSB
unsigned long p_GetShortExpVector(const poly p, const ring r)
poly p_Cleardenom(poly p, const ring r)
void pEnlargeSet(poly **p, int l, int increment)
#define p_LmEqual(p1, p2, r)
#define __pp_Mult_nn(p, n, r)
static poly pp_Mult_mm(poly p, poly m, const ring r)
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
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
static void p_Setm(poly p, const ring r)
static number p_SetCoeff(poly p, number n, ring r)
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
static void p_Delete(poly *p, const ring r)
static unsigned pLength(poly a)
static poly p_Init(const ring r, omBin bin)
static poly p_Copy(poly p, const ring r)
returns a copy of p
#define __p_Mult_nn(p, n, r)
void rChangeCurrRing(ring r)
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
static long pTotaldegree(poly p)
#define pHasNotCF(p1, p2)
#define pExpVectorDiff(pr, p1, p2)
#define pGetComp(p)
Component.
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
#define pExpVectorSub(p1, p2)
#define pLmInit(p)
like pInit, except that expvector is initialized to that of p, p must be != NULL
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
#define pGetExp(p, i)
Exponent.
void pNorm(poly p, const ring R=currRing)
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
#define pCopy(p)
return a copy of the poly
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
void PrintS(const char *s)
ring rAssure_TDeg(ring r, int &pos)
BOOLEAN rRing_has_CompLastBlock(const ring r)
void rDelete(ring r)
unconditionally deletes fields in r
static int rBlocks(ring r)
static BOOLEAN rField_is_Zp(const ring r)
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
static BOOLEAN rField_is_Q(const ring r)
static short rVar(const ring r)
#define rVar(r) (r->N)
static short scaLastAltVar(ring r)
static short scaFirstAltVar(ring r)
ideal idInit(int idsize, int rank)
initialise an ideal / module
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)
static int fwbw(red_object *los, int i)
BOOLEAN is_valid_ro(red_object &ro)
static poly redNFTail(poly h, const int sl, kStrategy strat, int len)
ideal t_rep_gb(const ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode)
static void shorten_tails(slimgb_alg *c, poly monom)
static void go_on(slimgb_alg *c)
static poly gcd_of_terms(poly p, ring r)
BOOLEAN good_has_t_rep(int i, int j, slimgb_alg *c)
static int add_to_reductors(slimgb_alg *c, poly h, int len, int ecart, BOOLEAN simplified=FALSE)
int tgb_pair_better_gen2(const void *ap, const void *bp)
static const int bundle_size
static int tgb_pair_better_gen(const void *ap, const void *bp)
static void clearS(poly p, unsigned long p_sev, int l, int *at, int *k, kStrategy strat)
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
static wlen_type pair_weighted_length(int i, int j, slimgb_alg *c)
static void move_forward_in_S(int old_pos, int new_pos, kStrategy strat)
void now_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *c)
void clean_top_of_pair_list(slimgb_alg *c)
#define ENLARGE(pointer, type)
static void mass_add(poly *p, int pn, slimgb_alg *c)
static int get_last_dp_block_start(ring r)
static wlen_type coeff_mult_size_estimate(int s1, int s2, ring r)
int find_best(red_object *r, int l, int u, wlen_type &w, slimgb_alg *c)
returns position sets w as weight
static BOOLEAN monomial_root(poly m, ring r)
int search_red_object_pos(red_object *a, int top, red_object *key)
static int * make_connections(int from, int to, poly bound, slimgb_alg *c)
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
static BOOLEAN pair_better(sorted_pair_node *a, sorted_pair_node *b, slimgb_alg *c=NULL)
static poly p_Init_Special(const ring r)
#define ENLARGE_ALIGN(pointer, type)
static void sort_region_down(red_object *los, int l, int u, slimgb_alg *)
int slim_nsize(number n, ring r)
static wlen_type pSLength(poly p, int l)
static int multi_reduction_clear_zeroes(red_object *los, int losl, int l, int u)
static int pTotaldegree_full(poly p)
static BOOLEAN lies_in_last_dp_block(poly p, slimgb_alg *c)
wlen_type pELength(poly p, slimgb_alg *c, ring)
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
wlen_type kEBucketLength(kBucket *b, poly lm, slimgb_alg *ca)
static int posInPairs(sorted_pair_node **p, int pn, sorted_pair_node *qe, slimgb_alg *c, int an=0)
static const int delay_factor
int kFindDivisibleByInS_easy(kStrategy strat, const red_object &obj)
static int poly_crit(const void *ap1, const void *ap2)
static int simple_posInS(kStrategy strat, poly p, int len, wlen_type wlen)
static wlen_type quality_of_pos_in_strat_S(int pos, slimgb_alg *c)
static void c_S_element_changed_hook(int pos, slimgb_alg *c)
sorted_pair_node * top_pair(slimgb_alg *c)
static void replace_pair(int &i, int &j, slimgb_alg *c)
static void multi_reduction_find(red_object *los, int, slimgb_alg *c, int startf, find_erg &erg)
static void line_of_extended_prod(int fixpos, slimgb_alg *c)
static BOOLEAN trivial_syzygie(int pos1, int pos2, poly bound, slimgb_alg *c)
static int iq_crit(const void *ap, const void *bp)
static poly redNF2(poly h, slimgb_alg *c, int &len, number &m, int n=0)
static void simplify_poly(poly p, ring r)
static void multi_reduction(red_object *los, int &losl, slimgb_alg *c)
static void add_later(poly p, const char *prot, slimgb_alg *c)
static poly pOne_Special(const ring r=currRing)
static poly redTailShort(poly h, kStrategy strat)
static void cleanS(kStrategy strat, slimgb_alg *c)
static BOOLEAN ascending(int *i, int top)
static wlen_type quality_of_pos_in_strat_S_mult_high(int pos, poly high, slimgb_alg *c)
static void multi_reduce_step(find_erg &erg, red_object *r, slimgb_alg *c)
static wlen_type do_pELength(poly p, slimgb_alg *c, int dlm=-1)
ideal do_t_rep_gb(ring, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
static wlen_type pQuality(poly p, slimgb_alg *c, int l=-1)
static void move_backward_in_S(int old_pos, int new_pos, kStrategy strat)
void free_sorted_pair_node(sorted_pair_node *s, const ring r)
BOOLEAN lenS_correct(kStrategy strat)
void init_with_mac_poly(tgb_sparse_matrix *mat, int row, mac_poly m)
int terms_sort_crit(const void *a, const void *b)
static void canonicalize_region(red_object *los, int l, int u, slimgb_alg *)
static BOOLEAN polynomial_root(poly h, ring r)
poly free_row_to_poly(tgb_sparse_matrix *mat, int row, poly *monoms, int monom_index)
static int bucket_guess(kBucket *bucket)
wlen_type kSBucketLength(kBucket *b, poly lm=NULL)
TODO CoefBuckets bercksichtigen.
static void super_clean_top_of_pair_list(slimgb_alg *c)
static void multi_reduction_lls_trick(red_object *los, int, slimgb_alg *c, find_erg &erg)
static int red_object_better_gen(const void *ap, const void *bp)
static void length_one_crit(slimgb_alg *c, int pos, int len)
static BOOLEAN has_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *state)
static BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m)
static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg *c)
static const int bundle_size_noro
static BOOLEAN state_is(calc_state state, const int &i, const int &j, slimgb_alg *c)
static BOOLEAN elength_is_normal_length(poly p, slimgb_alg *c)
void simplest_gauss_modp(number_type *a, int nrows, int ncols)
int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set)
poly row_to_poly(number_type *row, poly *terms, int tn, ring r)
wlen_type expected_length
void write_poly_to_row(number_type *row, poly h, poly *terms, int tn, ring r)
void noro_step(poly *p, int &pn, slimgb_alg *c)