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;
156 #ifndef NORO_NON_POLY
157 class NoroPlaceHolder
207 #ifdef USE_STDVECBOOL
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
580 #ifndef NORO_NON_POLY
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;
828 number_type* it_coef=
res->coef_array;
829 int* it_idx=
res->idx_array;
831 for(
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;
848 const int multiple=
sizeof(
int64)/
sizeof(number_type);
849 if (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];
940 int ,
const number_type* row,
int len,number coef)
943 int 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;
987 template <
class number_type>
void add_dense(number_type*
const temp_array,
988 int ,
const number_type* row,
int len)
990 template <
class number_type>
void add_dense(number_type*
const temp_array,
991 int temp_size,
const number_type* row,
int len)
1013 template <
class number_type>
void sub_dense(number_type*
const temp_array,
1014 int ,
const number_type* row,
int len)
1016 template <
class number_type>
void sub_dense(number_type*
const temp_array,
1017 int 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;
1453 template <
class number_type >
void write_poly_to_row(number_type* row, poly
h, poly*terms,
int tn, ring r)
1462 int pos=ptr_to_h-terms;
1468 template <
class number_type > poly
row_to_poly(number_type* row, poly* terms,
int tn, ring r)
1473 for(
j=tn-1;
j>=0;
j--)
1475 if (!(zero==(row[
j])))
1490 const number_type zero=0;
1491 for(lastIndex=
ncols-1;lastIndex>=0;lastIndex--)
1493 if (!(row[lastIndex]==zero))
1516 rows=(number_type**)
omalloc((
size_t)nnrows*
sizeof(number_type*));
1519 for(
i=0;
i<nnrows;
i++)
1521 rows[
i]=array+((long)
i*(
long)nncols);
1543 number_type* row_array=
rows[row];
1562 number_type* row_array=
rows[r];
1565 number_type coef=row_array[start];
1576 for (other_row=r+1;other_row<
nrows;other_row++)
1582 number_type* other_row_array=
rows[other_row];
1583 number coef2=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1584 if (coef2==minus_one)
1586 for(
i=start;
i<=lastIndex;
i++)
1588 if (row_array[
i]!=zero)
1596 for(
i=start;
i<=lastIndex;
i++)
1598 if (row_array[
i]!=zero)
1611 for (other_row=r+1;other_row<
nrows;other_row++)
1617 number_type* other_row_array=
rows[other_row];
1618 number coef2=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1619 if (coef2==minus_one)
1621 for(
i=start;
i<=lastIndex;
i++)
1623 if (row_array[
i]!=zero)
1631 for(
i=start;
i<=lastIndex;
i++)
1633 if (row_array[
i]!=zero)
1647 number_type* row_array=
rows[row];
1653 if (!(row_array[
i]==0))
1700 number_type* row_array=
rows[row];
1721 this->startIndices=
p.startIndices;
1723 this->ncols=
p.ncols;
1724 this->nrows=
p.nrows;
1749 number_type* row_array=
rows[r];
1752 const number_type zero=0;
1753 for(
i=upper_bound-1;
i>r;
i--)
1757 if (!(row_array[start]==zero))
1770 number_type* row_array=
rows[r];
1784 for(other_row=r-1;other_row>=0;other_row--)
1789 number_type* other_row_array=
rows[other_row];
1790 number coef=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1794 for(
i=start;
i<=lastIndex;
i++)
1796 if (row_array[
i]!=zero)
1807 for(other_row=r-1;other_row>=0;other_row--)
1812 number_type* other_row_array=
rows[other_row];
1813 number coef=
npNegM((number)(
long) other_row_array[start],
currRing->cf);
1817 for(
i=start;
i<=lastIndex;
i++)
1819 if (row_array[
i]!=zero)
1871 Print(
"Input rows %d\n",pn);
1883 srows[non_zeros]=noro_red_to_non_poly_t<number_type>(
h,h_len,&cache,c);
1884 if (srows[non_zeros]!=
NULL) non_zeros++;
1886 std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
1890 int n=irr_nodes.size();
1894 Print(
"Irred Mon:%d\n",n);
1903 term_nodes[
j].
t=irr_nodes[
j]->value_poly;
1905 term_nodes[
j].
node=irr_nodes[
j];
1909 poly* terms=(poly*)
omalloc(n*
sizeof(poly));
1914 old_to_new_indices[term_nodes[
j].
node->term_index]=
j;
1915 term_nodes[
j].node->term_index=
j;
1916 terms[
j]=term_nodes[
j].t;
1938 number_type*
const coef_array=srow->
coef_array;
1939 const int len=srow->
len;
1944 int idx=old_to_new_indices[idx_array[
i]];
1976 #ifdef NORO_NON_POLY
1978 omfree(old_to_new_indices);
1987 for(
i=0;
i<root.branches_len;
i++)
1989 collectIrreducibleMonomials(1,root.branches[
i],
res);
1995 if (node==
NULL)
return;
2046 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 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)
#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
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)