30#define NORO_SPARSE_ROWS_PRE 1
31#define NORO_NON_POLY 1
38#ifdef HAVE_BOOST_DYNAMIC_BITSET_HPP
45using boost::dynamic_bitset;
208 vector<vector<bool> >
states;
213 vector<dynamic_bitset<> >
states;
234 #ifdef TGB_RESORT_PAIRS
272 #ifdef TGB_RESORT_PAIRS
356 this->reducer_deg=pp_reducer_deg;
400 || ((len==setL[an]) && (
pLmCmp(set[an],
p) == 1)))
return an;
405 || ((len==setL[
i]) && (
pLmCmp(set[
i],
p) == 1))) en=
i;
413#define slim_prec_cast(a) (unsigned int) (unsigned long) (a)
414#define F4mat_to_number_type(a) (number_type) slim_prec_cast(a)
523 memcpy(
coef_array,source,n*
sizeof(number_type));
538 #ifdef NORO_SPARSE_ROWS_PRE
551 #ifdef NORO_SPARSE_ROWS_PRE
581 void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
588#ifdef NORO_RED_ARRAY_RESERVER
590 poly* recursionPolyBuffer;
621 #ifdef NORO_SPARSE_ROWS_PRE
646#ifdef NORO_RED_ARRAY_RESERVER
648 recursionPolyBuffer=(poly*)
omAlloc(1000000*
sizeof(poly));
665#ifdef NORO_RED_ARRAY_RESERVER
668 poly*
res=recursionPolyBuffer+reserved;
686#ifdef NORO_RED_ARRAY_RESERVER
687 omfree(recursionPolyBuffer);
709 #ifdef NORO_SPARSE_ROWS_PRE
781 srow=noro_red_to_non_poly_t<number_type>(
res,len,cache,c);
782 ref=cache->
insert(t,srow);
786 res_holder.
coef=coef_bak;
792 number one=
npInit(1, c->
r->cf);
797 res_holder.
coef=coef_bak;
828number_type* it_coef=
res->coef_array;
829int* it_idx=
res->idx_array;
831for(
i=0;
i<cache->nIrreducibleMonomials;
i++)
833 if (!(0==temp_array[
i]))
836 res->idx_array[pos]=
i;
837 res->coef_array[pos]=temp_array[
i];
841 if (non_zeros==0)
break;
848const int multiple=
sizeof(
int64)/
sizeof(number_type);
849if (temp_size==0) end=start;
853 int temp_size_rounded=temp_size+(multiple-(temp_size%multiple));
854 assume(temp_size_rounded>=temp_size);
855 assume(temp_size_rounded%multiple==0);
856 assume(temp_size_rounded<temp_size+multiple);
857 number_type* nt_end=temp_array+temp_size_rounded;
858 end=(
int64*)((
void*)nt_end);
866 const int temp_index=((number_type*)((
void*) it))-temp_array;
867 const int bound=temp_index+multiple;
869 for(small_i=temp_index;small_i<
bound;small_i++)
871 if((c=temp_array[small_i])!=0)
875 (*(it_idx++))=small_i;
899 number_type*
const coef_array=row->
coef_array;
901 const int len=row->
len;
906 for(
j=0;
j<len;
j=
j+256)
913 buffer[bpos++]=coef_array[
i];
916 for(
i=0;
i<bpos_bound;
i++)
920 for(
i=0;
i<bpos_bound;
i++)
922 buffer[
i]=buffer[
i]%prime;
927 int idx=idx_array[
i];
940int ,
const number_type* row,
int len,number coef)
943int temp_size,
const number_type* row,
int len,number coef)
947 const number_type*
const coef_array=row;
954 for(
j=0;
j<len;
j=
j+256)
961 buffer[bpos++]=coef_array[
i];
964 for(
i=0;
i<bpos_bound;
i++)
968 for(
i=0;
i<bpos_bound;
i++)
970 buffer[
i]=buffer[
i]%prime;
987template <
class number_type>
void add_dense(number_type*
const temp_array,
988int ,
const number_type* row,
int len)
990template <
class number_type>
void add_dense(number_type*
const temp_array,
991int temp_size,
const number_type* row,
int len)
1013template <
class number_type>
void sub_dense(number_type*
const temp_array,
1014int ,
const number_type* row,
int len)
1016template <
class number_type>
void sub_dense(number_type*
const temp_array,
1017int temp_size,
const number_type* row,
int len)
1046 number_type*
const coef_array=row->
coef_array;
1048 const int len=row->
len;
1051 int idx=idx_array[
j];
1066 number_type*
const coef_array=row->
coef_array;
1068 const int len=row->
len;
1071 int idx=idx_array[
j];
1083 number_type* temp_array=(number_type*) cache->
tempBuffer;
1085 memset(temp_array,0,temp_size_bytes);
1096 number coef=red.
coef;
1099 if (!((coef==(number)1L)||(coef==minus_one)))
1105 if (coef==(number)1L)
1117 if (!((coef==(number)1L)||(coef==minus_one)))
1123 if (coef==(number)1L)
1153 assume(((temp_array[
i]!=0)==0)|| (((temp_array[
i]!=0)==1)));
1154 non_zeros+=(temp_array[
i]!=0);
1187 ci.
idx=idx_array[
j];
1197 if (coef_array[
j]!=0)
1214 if (coef_array[
j]!=0)
1218 ci.
coef=coef_array[
j];
1232 if (coef_array[
j]!=0)
1250 ci.
coef=coef_array[
j];
1251 ci.
idx=idx_array[
j];
1264 ci.
idx=idx_array[
j];
1275 if ((red.
ref) &&( red.
ref->row))
1277 together+=red.
ref->row->len;
1286 if (together==0)
return 0;
1296 if ((red.
ref) &&( red.
ref->row))
1299 int* idx_array=red.
ref->row->idx_array;
1300 number_type* coef_array=red.
ref->row->coef_array;
1301 int rlen=red.
ref->row->len;
1302 number coef=red.
coef;
1305 if ((coef!=one)&&(coef!=minus_one))
1324 if ((coef!=one)&&(coef!=minus_one))
1346 ci.
idx=red.
ref->term_index;
1359 for(
i=1;
i<together;
i++)
1379 int sparse_row_len=
act+1;
1381 if (sparse_row_len==0) {
return NULL;}
1384 number_type* coef_array=
res->coef_array;
1385 int* idx_array=
res->idx_array;
1386 for(
i=0;
i<sparse_row_len;
i++)
1407 double max_density=0.0;
1415 if ((red.
ref) && (red.
ref->row))
1417 double act_density=(double) red.
ref->row->len;
1419 max_density=
std::max(act_density,max_density);
1428 if (max_density<0.3) dense=
false;
1461 int pos=ptr_to_h-terms;
1467template <
class number_type > poly
row_to_poly(number_type* row, poly* terms,
int tn, ring r)
1472 for(
j=tn-1;
j>=0;
j--)
1474 if (!(zero==(row[
j])))
1489 const number_type zero=0;
1490 for(lastIndex=
ncols-1;lastIndex>=0;lastIndex--)
1492 if (!(row[lastIndex]==zero))
1515 rows=(number_type**)
omalloc((
size_t)nnrows*
sizeof(number_type*));
1518 for(
i=0;
i<nnrows;
i++)
1520 rows[
i]=array+((long)
i*(
long)nncols);
1542 number_type* row_array=
rows[row];
1561 number_type* row_array=
rows[r];
1564 number_type coef=row_array[start];
1575 for (other_row=r+1;other_row<
nrows;other_row++)
1581 number_type* other_row_array=
rows[other_row];
1582 number coef2=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1583 if (coef2==minus_one)
1585 for(
i=start;
i<=lastIndex;
i++)
1587 if (row_array[
i]!=zero)
1595 for(
i=start;
i<=lastIndex;
i++)
1597 if (row_array[
i]!=zero)
1610 for (other_row=r+1;other_row<
nrows;other_row++)
1616 number_type* other_row_array=
rows[other_row];
1617 number coef2=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1618 if (coef2==minus_one)
1620 for(
i=start;
i<=lastIndex;
i++)
1622 if (row_array[
i]!=zero)
1630 for(
i=start;
i<=lastIndex;
i++)
1632 if (row_array[
i]!=zero)
1646 number_type* row_array=
rows[row];
1652 if (!(row_array[
i]==0))
1699 number_type* row_array=
rows[row];
1720 this->startIndices=
p.startIndices;
1722 this->ncols=
p.ncols;
1723 this->nrows=
p.nrows;
1748 number_type* row_array=
rows[r];
1751 const number_type zero=0;
1752 for(
i=upper_bound-1;
i>r;
i--)
1756 if (!(row_array[start]==zero))
1769 number_type* row_array=
rows[r];
1783 for(other_row=r-1;other_row>=0;other_row--)
1788 number_type* other_row_array=
rows[other_row];
1789 number coef=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1793 for(
i=start;
i<=lastIndex;
i++)
1795 if (row_array[
i]!=zero)
1806 for(other_row=r-1;other_row>=0;other_row--)
1811 number_type* other_row_array=
rows[other_row];
1812 number coef=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1816 for(
i=start;
i<=lastIndex;
i++)
1818 if (row_array[
i]!=zero)
1870 Print(
"Input rows %d\n",pn);
1882 srows[non_zeros]=noro_red_to_non_poly_t<number_type>(
h,h_len,&cache,c);
1883 if (srows[non_zeros]!=
NULL) non_zeros++;
1885 std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
1889 int n=irr_nodes.size();
1893 Print(
"Irred Mon:%d\n",n);
1902 term_nodes[
j].
t=irr_nodes[
j]->value_poly;
1904 term_nodes[
j].
node=irr_nodes[
j];
1908 poly* terms=(poly*)
omalloc(n*
sizeof(poly));
1913 old_to_new_indices[term_nodes[
j].
node->term_index]=
j;
1914 term_nodes[
j].node->term_index=
j;
1915 terms[
j]=term_nodes[
j].t;
1937 number_type*
const coef_array=srow->
coef_array;
1938 const int len=srow->
len;
1943 int idx=old_to_new_indices[idx_array[
i]];
1975 #ifdef NORO_NON_POLY
1977 omfree(old_to_new_indices);
1986 for(
i=0;
i<root.branches_len;
i++)
1988 collectIrreducibleMonomials(1,root.branches[
i],
res);
1994 if (node==
NULL)
return;
2045 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 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)
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 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)
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_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
BOOLEAN pa(leftv res, leftv args)
const CanonicalForm int s
void sort(CFArray &A, int l=0)
quick sort A
static int min(int a, int b)
static int max(int a, int b)
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 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 unsigned pLength(poly a)
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 ...
Compatiblity 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)