29#define NORO_SPARSE_ROWS_PRE 1
30#define NORO_NON_POLY 1
37#ifdef HAVE_BOOST_DYNAMIC_BITSET_HPP
44using boost::dynamic_bitset;
207 vector<vector<bool> >
states;
212 vector<dynamic_bitset<> >
states;
233 #ifdef TGB_RESORT_PAIRS
268 #ifdef TGB_RESORT_PAIRS
352 this->reducer_deg=pp_reducer_deg;
396 || ((len==setL[an]) && (
pLmCmp(set[an],
p) == 1)))
return an;
401 || ((len==setL[
i]) && (
pLmCmp(set[
i],
p) == 1))) en=
i;
409#define slim_prec_cast(a) (unsigned int) (unsigned long) (a)
410#define F4mat_to_number_type(a) (number_type) slim_prec_cast(a)
519 memcpy(
coef_array,source,n*
sizeof(number_type));
534 #ifdef NORO_SPARSE_ROWS_PRE
547 #ifdef NORO_SPARSE_ROWS_PRE
577 void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
584#ifdef NORO_RED_ARRAY_RESERVER
586 poly* recursionPolyBuffer;
617 #ifdef NORO_SPARSE_ROWS_PRE
642#ifdef NORO_RED_ARRAY_RESERVER
644 recursionPolyBuffer=(poly*)
omAlloc(1000000*
sizeof(poly));
661#ifdef NORO_RED_ARRAY_RESERVER
664 poly*
res=recursionPolyBuffer+reserved;
682#ifdef NORO_RED_ARRAY_RESERVER
683 omfree(recursionPolyBuffer);
705 #ifdef NORO_SPARSE_ROWS_PRE
777 srow=noro_red_to_non_poly_t<number_type>(
res,len,cache,c);
778 ref=cache->
insert(t,srow);
782 res_holder.
coef=coef_bak;
788 number one=
npInit(1, c->
r->cf);
793 res_holder.
coef=coef_bak;
824number_type* it_coef=
res->coef_array;
825int* it_idx=
res->idx_array;
827for(
i=0;
i<cache->nIrreducibleMonomials;
i++)
829 if (!(0==temp_array[
i]))
832 res->idx_array[pos]=
i;
833 res->coef_array[pos]=temp_array[
i];
837 if (non_zeros==0)
break;
844const int multiple=
sizeof(
int64)/
sizeof(number_type);
845if (temp_size==0) end=start;
849 int temp_size_rounded=temp_size+(multiple-(temp_size%multiple));
850 assume(temp_size_rounded>=temp_size);
851 assume(temp_size_rounded%multiple==0);
852 assume(temp_size_rounded<temp_size+multiple);
853 number_type* nt_end=temp_array+temp_size_rounded;
854 end=(
int64*)((
void*)nt_end);
862 const int temp_index=((number_type*)((
void*) it))-temp_array;
863 const int bound=temp_index+multiple;
865 for(small_i=temp_index;small_i<
bound;small_i++)
867 if((c=temp_array[small_i])!=0)
871 (*(it_idx++))=small_i;
895 number_type*
const coef_array=row->
coef_array;
897 const int len=row->
len;
902 for(
j=0;
j<len;
j=
j+256)
904 const int bound=std::min(
j+256,len);
909 buffer[bpos++]=coef_array[
i];
912 for(
i=0;
i<bpos_bound;
i++)
916 for(
i=0;
i<bpos_bound;
i++)
918 buffer[
i]=buffer[
i]%prime;
923 int idx=idx_array[
i];
936int ,
const number_type* row,
int len,number coef)
939int temp_size,
const number_type* row,
int len,number coef)
943 const number_type*
const coef_array=row;
950 for(
j=0;
j<len;
j=
j+256)
952 const int bound=std::min(
j+256,len);
957 buffer[bpos++]=coef_array[
i];
960 for(
i=0;
i<bpos_bound;
i++)
964 for(
i=0;
i<bpos_bound;
i++)
966 buffer[
i]=buffer[
i]%prime;
983template <
class number_type>
void add_dense(number_type*
const temp_array,
984int ,
const number_type* row,
int len)
986template <
class number_type>
void add_dense(number_type*
const temp_array,
987int temp_size,
const number_type* row,
int len)
1009template <
class number_type>
void sub_dense(number_type*
const temp_array,
1010int ,
const number_type* row,
int len)
1012template <
class number_type>
void sub_dense(number_type*
const temp_array,
1013int temp_size,
const number_type* row,
int len)
1042 number_type*
const coef_array=row->
coef_array;
1044 const int len=row->
len;
1047 int idx=idx_array[
j];
1062 number_type*
const coef_array=row->
coef_array;
1064 const int len=row->
len;
1067 int idx=idx_array[
j];
1079 number_type* temp_array=(number_type*) cache->
tempBuffer;
1081 memset(temp_array,0,temp_size_bytes);
1092 number coef=red.
coef;
1095 if (!((coef==(number)1L)||(coef==minus_one)))
1101 if (coef==(number)1L)
1113 if (!((coef==(number)1L)||(coef==minus_one)))
1119 if (coef==(number)1L)
1149 assume(((temp_array[
i]!=0)==0)|| (((temp_array[
i]!=0)==1)));
1150 non_zeros+=(temp_array[
i]!=0);
1183 ci.
idx=idx_array[
j];
1193 if (coef_array[
j]!=0)
1210 if (coef_array[
j]!=0)
1214 ci.
coef=coef_array[
j];
1228 if (coef_array[
j]!=0)
1246 ci.
coef=coef_array[
j];
1247 ci.
idx=idx_array[
j];
1260 ci.
idx=idx_array[
j];
1271 if ((red.
ref) &&( red.
ref->row))
1273 together+=red.
ref->row->len;
1282 if (together==0)
return 0;
1292 if ((red.
ref) &&( red.
ref->row))
1295 int* idx_array=red.
ref->row->idx_array;
1296 number_type* coef_array=red.
ref->row->coef_array;
1297 int rlen=red.
ref->row->len;
1298 number coef=red.
coef;
1301 if ((coef!=one)&&(coef!=minus_one))
1320 if ((coef!=one)&&(coef!=minus_one))
1342 ci.
idx=red.
ref->term_index;
1355 for(
i=1;
i<together;
i++)
1375 int sparse_row_len=
act+1;
1377 if (sparse_row_len==0) {
return NULL;}
1380 number_type* coef_array=
res->coef_array;
1381 int* idx_array=
res->idx_array;
1382 for(
i=0;
i<sparse_row_len;
i++)
1403 double max_density=0.0;
1411 if ((red.
ref) && (red.
ref->row))
1413 double act_density=(double) red.
ref->row->len;
1415 max_density=std::max(act_density,max_density);
1424 if (max_density<0.3) dense=
false;
1457 int pos=ptr_to_h-terms;
1463template <
class number_type > poly
row_to_poly(number_type* row, poly* terms,
int tn, ring r)
1468 for(
j=tn-1;
j>=0;
j--)
1470 if (!(zero==(row[
j])))
1485 const number_type zero=0;
1486 for(lastIndex=
ncols-1;lastIndex>=0;lastIndex--)
1488 if (!(row[lastIndex]==zero))
1511 rows=(number_type**)
omalloc((
size_t)nnrows*
sizeof(number_type*));
1514 for(
i=0;
i<nnrows;
i++)
1516 rows[
i]=array+((long)
i*(
long)nncols);
1538 number_type* row_array=
rows[row];
1557 number_type* row_array=
rows[r];
1560 number_type coef=row_array[start];
1571 for (other_row=r+1;other_row<
nrows;other_row++)
1577 number_type* other_row_array=
rows[other_row];
1578 number coef2=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1579 if (coef2==minus_one)
1581 for(
i=start;
i<=lastIndex;
i++)
1583 if (row_array[
i]!=zero)
1591 for(
i=start;
i<=lastIndex;
i++)
1593 if (row_array[
i]!=zero)
1606 for (other_row=r+1;other_row<
nrows;other_row++)
1612 number_type* other_row_array=
rows[other_row];
1613 number coef2=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1614 if (coef2==minus_one)
1616 for(
i=start;
i<=lastIndex;
i++)
1618 if (row_array[
i]!=zero)
1626 for(
i=start;
i<=lastIndex;
i++)
1628 if (row_array[
i]!=zero)
1642 number_type* row_array=
rows[row];
1648 if (!(row_array[
i]==0))
1695 number_type* row_array=
rows[row];
1716 this->startIndices=
p.startIndices;
1718 this->ncols=
p.ncols;
1719 this->nrows=
p.nrows;
1744 number_type* row_array=
rows[r];
1747 const number_type zero=0;
1748 for(
i=upper_bound-1;
i>r;
i--)
1752 if (!(row_array[start]==zero))
1765 number_type* row_array=
rows[r];
1779 for(other_row=r-1;other_row>=0;other_row--)
1784 number_type* other_row_array=
rows[other_row];
1785 number coef=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1789 for(
i=start;
i<=lastIndex;
i++)
1791 if (row_array[
i]!=zero)
1802 for(other_row=r-1;other_row>=0;other_row--)
1807 number_type* other_row_array=
rows[other_row];
1808 number coef=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1812 for(
i=start;
i<=lastIndex;
i++)
1814 if (row_array[
i]!=zero)
1866 Print(
"Input rows %d\n",pn);
1878 srows[non_zeros]=noro_red_to_non_poly_t<number_type>(
h,h_len,&cache,c);
1879 if (srows[non_zeros]!=
NULL) non_zeros++;
1881 std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
1885 int n=irr_nodes.size();
1889 Print(
"Irred Mon:%d\n",n);
1898 term_nodes[
j].
t=irr_nodes[
j]->value_poly;
1900 term_nodes[
j].
node=irr_nodes[
j];
1904 poly* terms=(poly*)
omalloc(n*
sizeof(poly));
1909 old_to_new_indices[term_nodes[
j].
node->term_index]=
j;
1910 term_nodes[
j].node->term_index=
j;
1911 terms[
j]=term_nodes[
j].t;
1933 number_type*
const coef_array=srow->
coef_array;
1934 const int len=srow->
len;
1939 int idx=old_to_new_indices[idx_array[
i]];
1971 #ifdef NORO_NON_POLY
1973 omfree(old_to_new_indices);
1982 for(
i=0;
i<root.branches_len;
i++)
1984 collectIrreducibleMonomials(1,root.branches[
i],
res);
1990 if (node==
NULL)
return;
2041 if ( res_holder->
value_len==backLinkCode )
static int si_max(const int a, const int b)
static CanonicalForm bound(const CFMatrix &M)
bool operator<(const CoefIdx< number_type > &other) const
DataNoroCacheNode(SparseRow< number_type > *row)
DataNoroCacheNode(poly p, int len)
SparseRow< number_type > * row
void updateLastReducibleIndex(int r, int upper_bound)
void multiplyRow(int row, number_type coef)
void backwardSubstitute()
int * lastReducibleIndices
void backwardSubstitute(int r)
ModPMatrixProxyOnArray(number_type *array, int nnrows, int nncols)
int getStartIndex(int row)
BOOLEAN findPivot(int &r, int &c)
void reduceOtherRowsForward(int r)
void permRows(int i, int j)
~ModPMatrixProxyOnArray()
void multiplyRow(int row, number_type coef)
void updateStartIndex(int row, int lower_bound)
DataNoroCacheNode< number_type > * ref
NoroCacheNode ** branches
NoroCacheNode * getBranch(int branch)
NoroCacheNode * getOrInsertBranch(int branch)
NoroCacheNode * setNode(int branch, NoroCacheNode *node)
int nIrreducibleMonomials
DataNoroCacheNode< number_type > * treeInsert(poly term, poly nf, int len)
DataNoroCacheNode< number_type > * treeInsert(poly term, SparseRow< number_type > *srow)
void ensureTempBufferSize(size_t size)
DataNoroCacheNode< number_type > * getCacheReference(poly term)
poly lookup(poly term, BOOLEAN &succ, int &len)
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
std::vector< PolySimple > poly_vec
DataNoroCacheNode< number_type > * treeInsertBackLink(poly term)
DataNoroCacheNode< number_type > * insert(poly term, SparseRow< number_type > *srow)
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
void collectIrreducibleMonomials(std::vector< DataNoroCacheNode< number_type > * > &res)
static const int backLinkCode
bool operator==(const PolySimple &other)
PolySimple(const PolySimple &a)
PolySimple & operator=(const PolySimple &p2)
bool operator<(const PolySimple &other) const
wlen_type initial_quality
wlen_type guess_quality(slimgb_alg *c)
void adjust_coefs(number c_r, number c_ac_r)
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 that all occurring red_objects have same lm, and all occ. lm's in r[l......
virtual void pre_reduce(red_object *r, int l, int u)
simple_reducer(poly pp, int pp_len, int pp_reducer_deg, slimgb_alg *pp_c=NULL)
virtual void reduce(red_object *r, int l, int u)
we assume that all occurring red_objects have same lm, and all occ. lm's in r[l......
virtual void do_reduce(red_object &ro)
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
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_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
static BOOLEAN pa(leftv res, leftv args)
const CanonicalForm int s
static BOOLEAN length(leftv result, leftv arg)
static BOOLEAN npIsOne(number a, const coeffs)
static number npAddM(number a, number b, const coeffs r)
static number npMultM(number a, number b, const coeffs r)
static number npNegM(number a, const coeffs r)
static number npInversM(number c, const coeffs r)
static number npSubM(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 BOOLEAN npIsZero(number a, 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 omrealloc(addr, size)
unsigned long p_GetShortExpVector(const poly p, const ring r)
static int pLength(poly a)
static poly p_LmInit(poly p, const ring r)
static poly pp_Mult_mm(poly p, poly m, const ring r)
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 int p_LmCmp(poly p, poly q, 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 void p_Delete(poly *p, const ring r)
static poly p_Copy(poly p, const ring r)
returns a copy of p
static long p_Totaldegree(poly p, const ring r)
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Compatibility layer for legacy polynomial operations (over currRing)
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
void write_minus_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
void add_dense(number_type *const temp_array, int, const number_type *row, int len)
int tgb_pair_better_gen2(const void *ap, const void *bp)
void write_minus_coef_idx_to_buffer(CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen)
MonRedResNP< number_type > noro_red_mon_to_non_poly(poly t, NoroCache< number_type > *cache, slimgb_alg *c)
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
void now_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *c)
void clean_top_of_pair_list(slimgb_alg *c)
void simplest_gauss_modp(number_type *a, int nrows, int ncols)
SparseRow< number_type > * noro_red_to_non_poly_dense(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
SparseRow< number_type > * noro_red_to_non_poly_sparse(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
ideal do_t_rep_gb(ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
int slim_nsize(number n, ring r)
void write_coef_idx_to_buffer(CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen)
void write_poly_to_row(number_type *row, poly h, poly *terms, int tn)
void sub_dense(number_type *const temp_array, int, const number_type *row, int len)
void add_coef_times_sparse(number_type *const temp_array, int, SparseRow< number_type > *row, number coef)
int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set)
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
int kFindDivisibleByInS_easy(kStrategy strat, const red_object &obj)
sorted_pair_node * top_pair(slimgb_alg *c)
poly row_to_poly(number_type *row, poly *terms, int tn, ring r)
void sub_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
SparseRow< number_type > * noro_red_to_non_poly_t(poly p, int &len, NoroCache< number_type > *cache, slimgb_alg *c)
wlen_type expected_length
void write_coef_times_xx_idx_to_buffer(CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen, const number coef)
#define F4mat_to_number_type(a)
SparseRow< number_type > * convert_to_sparse_row(number_type *temp_array, int temp_size, int non_zeros)
void add_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
DataNoroCacheNode< number_type > * node
int modP_lastIndexRow(number_type *row, int ncols)
void add_coef_times_dense(number_type *const temp_array, int, const number_type *row, int len, number coef)
unsigned short tgb_uint16
void free_sorted_pair_node(sorted_pair_node *s, const ring r)
void noro_step(poly *p, int &pn, slimgb_alg *c)
int terms_sort_crit(const void *a, const void *b)
void write_coef_times_xx_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen, const number coef)
int term_nodes_sort_crit(const void *a, const void *b)
void write_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)