15 #define FULLREDUCTIONS
30 #define NORO_SPARSE_ROWS_PRE 1
31 #define NORO_NON_POLY 1
38 #ifdef HAVE_BOOST_DYNAMIC_BITSET_HPP
45 using boost::dynamic_bitset;
73 #define npNeg n_InpNeg
74 #define npInvers n_Invers
76 #define npIsOne n_IsOne
77 #define npIsZero n_IsZero
80 #error Please do NOT call internal functions directly!
166 #ifndef NORO_NON_POLY
167 class NoroPlaceHolder
217 #ifdef USE_STDVECBOOL
218 vector<vector<bool> >
states;
223 vector<dynamic_bitset<> >
states;
244 #ifdef TGB_RESORT_PAIRS
282 #ifdef TGB_RESORT_PAIRS
366 this->reducer_deg=pp_reducer_deg;
410 || ((len==setL[an]) && (
pLmCmp(set[an],
p) == 1)))
return an;
415 || ((len==setL[
i]) && (
pLmCmp(set[
i],
p) == 1))) en=
i;
423 #define slim_prec_cast(a) (unsigned int) (unsigned long) (a)
424 #define F4mat_to_number_type(a) (number_type) slim_prec_cast(a)
533 memcpy(
coef_array,source,n*
sizeof(number_type));
548 #ifdef NORO_SPARSE_ROWS_PRE
561 #ifdef NORO_SPARSE_ROWS_PRE
590 #ifndef NORO_NON_POLY
591 void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
598 #ifdef NORO_RED_ARRAY_RESERVER
600 poly* recursionPolyBuffer;
631 #ifdef NORO_SPARSE_ROWS_PRE
656 #ifdef NORO_RED_ARRAY_RESERVER
658 recursionPolyBuffer=(poly*)
omAlloc(1000000*
sizeof(poly));
675 #ifdef NORO_RED_ARRAY_RESERVER
678 poly*
res=recursionPolyBuffer+reserved;
696 #ifdef NORO_RED_ARRAY_RESERVER
697 omfree(recursionPolyBuffer);
719 #ifdef NORO_SPARSE_ROWS_PRE
791 srow=noro_red_to_non_poly_t<number_type>(
res,len,cache,c);
792 ref=cache->
insert(t,srow);
796 res_holder.
coef=coef_bak;
802 number one=
npInit(1, c->
r->cf);
807 res_holder.
coef=coef_bak;
837 number_type* it_coef=
res->coef_array;
838 int* it_idx=
res->idx_array;
840 for(
i=0;
i<cache->nIrreducibleMonomials;
i++){
841 if (!(0==temp_array[
i])){
843 res->idx_array[pos]=
i;
844 res->coef_array[pos]=temp_array[
i];
848 if (non_zeros==0)
break;
855 const int multiple=
sizeof(
int64)/
sizeof(number_type);
856 if (temp_size==0) end=start;
860 int temp_size_rounded=temp_size+(multiple-(temp_size%multiple));
861 assume(temp_size_rounded>=temp_size);
862 assume(temp_size_rounded%multiple==0);
863 assume(temp_size_rounded<temp_size+multiple);
864 number_type* nt_end=temp_array+temp_size_rounded;
865 end=(
int64*)((
void*)nt_end);
873 const int temp_index=((number_type*)((
void*) it))-temp_array;
874 const int bound=temp_index+multiple;
876 for(small_i=temp_index;small_i<
bound;small_i++)
878 if((c=temp_array[small_i])!=0)
882 (*(it_idx++))=small_i;
906 number_type*
const coef_array=row->
coef_array;
908 const int len=row->
len;
913 for(
j=0;
j<len;
j=
j+256)
920 buffer[bpos++]=coef_array[
i];
923 for(
i=0;
i<bpos_bound;
i++)
927 for(
i=0;
i<bpos_bound;
i++)
929 buffer[
i]=buffer[
i]%prime;
934 int idx=idx_array[
i];
947 int ,
const number_type* row,
int len,number coef)
950 int temp_size,
const number_type* row,
int len,number coef)
954 const number_type*
const coef_array=row;
961 for(
j=0;
j<len;
j=
j+256)
968 buffer[bpos++]=coef_array[
i];
971 for(
i=0;
i<bpos_bound;
i++)
975 for(
i=0;
i<bpos_bound;
i++)
977 buffer[
i]=buffer[
i]%prime;
994 template <
class number_type>
void add_dense(number_type*
const temp_array,
995 int ,
const number_type* row,
int len)
997 template <
class number_type>
void add_dense(number_type*
const temp_array,
998 int temp_size,
const number_type* row,
int len)
1020 template <
class number_type>
void sub_dense(number_type*
const temp_array,
1021 int ,
const number_type* row,
int len)
1023 template <
class number_type>
void sub_dense(number_type*
const temp_array,
1024 int temp_size,
const number_type* row,
int len)
1055 number_type*
const coef_array=row->
coef_array;
1057 const int len=row->
len;
1060 int idx=idx_array[
j];
1075 number_type*
const coef_array=row->
coef_array;
1077 const int len=row->
len;
1080 int idx=idx_array[
j];
1092 number_type* temp_array=(number_type*) cache->
tempBuffer;
1094 memset(temp_array,0,temp_size_bytes);
1105 number coef=red.
coef;
1108 if (!((coef==(number)1L)||(coef==minus_one)))
1114 if (coef==(number)1L)
1126 if (!((coef==(number)1L)||(coef==minus_one)))
1132 if (coef==(number)1L)
1161 assume(((temp_array[
i]!=0)==0)|| (((temp_array[
i]!=0)==1)));
1162 non_zeros+=(temp_array[
i]!=0);
1195 ci.
idx=idx_array[
j];
1205 if (coef_array[
j]!=0)
1222 if (coef_array[
j]!=0)
1226 ci.
coef=coef_array[
j];
1240 if (coef_array[
j]!=0)
1258 ci.
coef=coef_array[
j];
1259 ci.
idx=idx_array[
j];
1272 ci.
idx=idx_array[
j];
1283 if ((red.
ref) &&( red.
ref->row))
1285 together+=red.
ref->row->len;
1294 if (together==0)
return 0;
1304 if ((red.
ref) &&( red.
ref->row))
1307 int* idx_array=red.
ref->row->idx_array;
1308 number_type* coef_array=red.
ref->row->coef_array;
1309 int rlen=red.
ref->row->len;
1310 number coef=red.
coef;
1313 if ((coef!=one)&&(coef!=minus_one))
1332 if ((coef!=one)&&(coef!=minus_one))
1354 ci.
idx=red.
ref->term_index;
1367 for(
i=1;
i<together;
i++)
1387 int sparse_row_len=
act+1;
1389 if (sparse_row_len==0) {
return NULL;}
1392 number_type* coef_array=
res->coef_array;
1393 int* idx_array=
res->idx_array;
1394 for(
i=0;
i<sparse_row_len;
i++)
1414 double max_density=0.0;
1422 if ((red.
ref) && (red.
ref->row))
1424 double act_density=(double) red.
ref->row->len;
1426 max_density=
std::max(act_density,max_density);
1435 if (max_density<0.3) dense=
false;
1460 template <
class number_type >
void write_poly_to_row(number_type* row, poly
h, poly*terms,
int tn, ring r){
1467 int pos=ptr_to_h-terms;
1473 template <
class number_type > poly
row_to_poly(number_type* row, poly* terms,
int tn, ring r){
1477 for(
j=tn-1;
j>=0;
j--){
1478 if (!(zero==(row[
j]))){
1492 const number_type zero=0;
1493 for(lastIndex=
ncols-1;lastIndex>=0;lastIndex--)
1495 if (!(row[lastIndex]==zero))
1518 rows=(number_type**)
omalloc(nnrows*
sizeof(number_type*));
1521 for(
i=0;
i<nnrows;
i++)
1523 rows[
i]=array+(
i*nncols);
1545 number_type* row_array=
rows[row];
1554 number_type* row_array=
rows[r];
1557 number_type coef=row_array[start];
1566 for (other_row=r+1;other_row<
nrows;other_row++)
1572 number_type* other_row_array=
rows[other_row];
1573 number coef2=
npNeg((number)(
long) other_row_array[start],
currRing->cf);
1574 if (coef2==minus_one)
1576 for(
i=start;
i<=lastIndex;
i++)
1578 if (row_array[
i]!=zero)
1588 for(
i=start;
i<=lastIndex;
i++)
1590 if (row_array[
i]!=zero)
1604 number_type* row_array=
rows[row];
1610 if (!(row_array[
i]==0))
1657 number_type* row_array=
rows[row];
1668 this->startIndices=
p.startIndices;
1670 this->ncols=
p.ncols;
1671 this->nrows=
p.nrows;
1696 number_type* row_array=
rows[r];
1699 const number_type zero=0;
1700 for(
i=upper_bound-1;
i>r;
i--)
1704 if (!(row_array[start]==zero))
1717 number_type* row_array=
rows[r];
1729 for(other_row=r-1;other_row>=0;other_row--)
1734 number_type* other_row_array=
rows[other_row];
1735 number coef=
npNeg((number)(
long) other_row_array[start],
currRing->cf);
1739 for(
i=start;
i<=lastIndex;
i++)
1741 if (row_array[
i]!=zero)
1791 Print(
"Input rows %d\n",pn);
1803 srows[non_zeros]=noro_red_to_non_poly_t<number_type>(
h,h_len,&cache,c);
1804 if (srows[non_zeros]!=
NULL) non_zeros++;
1806 std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
1810 int n=irr_nodes.size();
1814 Print(
"Irred Mon:%d\n",n);
1823 term_nodes[
j].
t=irr_nodes[
j]->value_poly;
1825 term_nodes[
j].
node=irr_nodes[
j];
1829 poly* terms=(poly*)
omalloc(n*
sizeof(poly));
1834 old_to_new_indices[term_nodes[
j].
node->term_index]=
j;
1835 term_nodes[
j].node->term_index=
j;
1836 terms[
j]=term_nodes[
j].t;
1858 number_type*
const coef_array=srow->
coef_array;
1859 const int len=srow->
len;
1864 int idx=old_to_new_indices[idx_array[
i]];
1894 #ifdef NORO_NON_POLY
1896 omfree(old_to_new_indices);
1904 for(
i=0;
i<root.branches_len;
i++){
1905 collectIrreducibleMonomials(1,root.branches[
i],
res);
1910 if (node==
NULL)
return;
1954 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 * getOrInsertBranch(int branch)
NoroCacheNode * setNode(int branch, NoroCacheNode *node)
NoroCacheNode * getBranch(int branch)
int nIrreducibleMonomials
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
void ensureTempBufferSize(size_t size)
DataNoroCacheNode< number_type > * getCacheReference(poly term)
poly lookup(poly term, BOOLEAN &succ, int &len)
std::vector< PolySimple > poly_vec
DataNoroCacheNode< number_type > * treeInsert(poly term, poly nf, int len)
void collectIrreducibleMonomials(std::vector< DataNoroCacheNode< number_type > * > &res)
DataNoroCacheNode< number_type > * treeInsertBackLink(poly term)
DataNoroCacheNode< number_type > * treeInsert(poly term, SparseRow< number_type > *srow)
DataNoroCacheNode< number_type > * insert(poly term, SparseRow< number_type > *srow)
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
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 number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
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 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 npSubM(number a, number b, const coeffs r)
#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)
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
MonRedResNP< number_type > noro_red_mon_to_non_poly(poly t, NoroCache< number_type > *cache, slimgb_alg *c)
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)
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
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)
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)
ideal do_t_rep_gb(ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
SparseRow< number_type > * noro_red_to_non_poly_sparse(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
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 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)
int kFindDivisibleByInS_easy(kStrategy strat, const red_object &obj)
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, 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)
void write_poly_to_row(number_type *row, poly h, poly *terms, int tn, ring r)
#define F4mat_to_number_type(a)
void add_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
sorted_pair_node * top_pair(slimgb_alg *c)
DataNoroCacheNode< number_type > * node
SparseRow< number_type > * convert_to_sparse_row(number_type *temp_array, int temp_size, int non_zeros)
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
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)
SparseRow< number_type > * noro_red_to_non_poly_dense(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
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)
wlen_type pELength(poly p, ring r)
void write_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)