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;
74 #define npInvers npInversM
75 #define npIsOne npIsOne
76 #define npIsZero npIsZeroM
81 #error Please do NOT call internal functions directly!
170 #ifndef NORO_NON_POLY
171 class NoroPlaceHolder
221 #ifdef USE_STDVECBOOL
222 vector<vector<bool> >
states;
227 vector<dynamic_bitset<> >
states;
248 #ifdef TGB_RESORT_PAIRS
286 #ifdef TGB_RESORT_PAIRS
370 this->reducer_deg=pp_reducer_deg;
414 || ((len==setL[an]) && (
pLmCmp(set[an],
p) == 1)))
return an;
419 || ((len==setL[
i]) && (
pLmCmp(set[
i],
p) == 1))) en=
i;
427 #define slim_prec_cast(a) (unsigned int) (unsigned long) (a)
428 #define F4mat_to_number_type(a) (number_type) slim_prec_cast(a)
537 memcpy(
coef_array,source,n*
sizeof(number_type));
552 #ifdef NORO_SPARSE_ROWS_PRE
565 #ifdef NORO_SPARSE_ROWS_PRE
594 #ifndef NORO_NON_POLY
595 void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
602 #ifdef NORO_RED_ARRAY_RESERVER
604 poly* recursionPolyBuffer;
635 #ifdef NORO_SPARSE_ROWS_PRE
660 #ifdef NORO_RED_ARRAY_RESERVER
662 recursionPolyBuffer=(poly*)
omAlloc(1000000*
sizeof(poly));
679 #ifdef NORO_RED_ARRAY_RESERVER
682 poly*
res=recursionPolyBuffer+reserved;
700 #ifdef NORO_RED_ARRAY_RESERVER
701 omfree(recursionPolyBuffer);
723 #ifdef NORO_SPARSE_ROWS_PRE
795 srow=noro_red_to_non_poly_t<number_type>(
res,len,cache,c);
796 ref=cache->
insert(t,srow);
800 res_holder.
coef=coef_bak;
806 number one=
npInit(1, c->
r->cf);
811 res_holder.
coef=coef_bak;
842 number_type* it_coef=
res->coef_array;
843 int* it_idx=
res->idx_array;
845 for(
i=0;
i<cache->nIrreducibleMonomials;
i++)
847 if (!(0==temp_array[
i]))
850 res->idx_array[pos]=
i;
851 res->coef_array[pos]=temp_array[
i];
855 if (non_zeros==0)
break;
862 const int multiple=
sizeof(
int64)/
sizeof(number_type);
863 if (temp_size==0) end=start;
867 int temp_size_rounded=temp_size+(multiple-(temp_size%multiple));
868 assume(temp_size_rounded>=temp_size);
869 assume(temp_size_rounded%multiple==0);
870 assume(temp_size_rounded<temp_size+multiple);
871 number_type* nt_end=temp_array+temp_size_rounded;
872 end=(
int64*)((
void*)nt_end);
880 const int temp_index=((number_type*)((
void*) it))-temp_array;
881 const int bound=temp_index+multiple;
883 for(small_i=temp_index;small_i<
bound;small_i++)
885 if((c=temp_array[small_i])!=0)
889 (*(it_idx++))=small_i;
913 number_type*
const coef_array=row->
coef_array;
915 const int len=row->
len;
920 for(
j=0;
j<len;
j=
j+256)
927 buffer[bpos++]=coef_array[
i];
930 for(
i=0;
i<bpos_bound;
i++)
934 for(
i=0;
i<bpos_bound;
i++)
936 buffer[
i]=buffer[
i]%prime;
941 int idx=idx_array[
i];
954 int ,
const number_type* row,
int len,number coef)
957 int temp_size,
const number_type* row,
int len,number coef)
961 const number_type*
const coef_array=row;
968 for(
j=0;
j<len;
j=
j+256)
975 buffer[bpos++]=coef_array[
i];
978 for(
i=0;
i<bpos_bound;
i++)
982 for(
i=0;
i<bpos_bound;
i++)
984 buffer[
i]=buffer[
i]%prime;
1001 template <
class number_type>
void add_dense(number_type*
const temp_array,
1002 int ,
const number_type* row,
int len)
1004 template <
class number_type>
void add_dense(number_type*
const temp_array,
1005 int temp_size,
const number_type* row,
int len)
1027 template <
class number_type>
void sub_dense(number_type*
const temp_array,
1028 int ,
const number_type* row,
int len)
1030 template <
class number_type>
void sub_dense(number_type*
const temp_array,
1031 int temp_size,
const number_type* row,
int len)
1062 number_type*
const coef_array=row->
coef_array;
1064 const int len=row->
len;
1067 int idx=idx_array[
j];
1082 number_type*
const coef_array=row->
coef_array;
1084 const int len=row->
len;
1087 int idx=idx_array[
j];
1099 number_type* temp_array=(number_type*) cache->
tempBuffer;
1101 memset(temp_array,0,temp_size_bytes);
1112 number coef=red.
coef;
1115 if (!((coef==(number)1L)||(coef==minus_one)))
1121 if (coef==(number)1L)
1133 if (!((coef==(number)1L)||(coef==minus_one)))
1139 if (coef==(number)1L)
1169 assume(((temp_array[
i]!=0)==0)|| (((temp_array[
i]!=0)==1)));
1170 non_zeros+=(temp_array[
i]!=0);
1203 ci.
idx=idx_array[
j];
1213 if (coef_array[
j]!=0)
1230 if (coef_array[
j]!=0)
1234 ci.
coef=coef_array[
j];
1248 if (coef_array[
j]!=0)
1266 ci.
coef=coef_array[
j];
1267 ci.
idx=idx_array[
j];
1280 ci.
idx=idx_array[
j];
1291 if ((red.
ref) &&( red.
ref->row))
1293 together+=red.
ref->row->len;
1302 if (together==0)
return 0;
1312 if ((red.
ref) &&( red.
ref->row))
1315 int* idx_array=red.
ref->row->idx_array;
1316 number_type* coef_array=red.
ref->row->coef_array;
1317 int rlen=red.
ref->row->len;
1318 number coef=red.
coef;
1321 if ((coef!=one)&&(coef!=minus_one))
1340 if ((coef!=one)&&(coef!=minus_one))
1362 ci.
idx=red.
ref->term_index;
1375 for(
i=1;
i<together;
i++)
1395 int sparse_row_len=
act+1;
1397 if (sparse_row_len==0) {
return NULL;}
1400 number_type* coef_array=
res->coef_array;
1401 int* idx_array=
res->idx_array;
1402 for(
i=0;
i<sparse_row_len;
i++)
1423 double max_density=0.0;
1431 if ((red.
ref) && (red.
ref->row))
1433 double act_density=(double) red.
ref->row->len;
1435 max_density=
std::max(act_density,max_density);
1444 if (max_density<0.3) dense=
false;
1469 template <
class number_type >
void write_poly_to_row(number_type* row, poly
h, poly*terms,
int tn, ring r)
1478 int pos=ptr_to_h-terms;
1484 template <
class number_type > poly
row_to_poly(number_type* row, poly* terms,
int tn, ring r)
1489 for(
j=tn-1;
j>=0;
j--)
1491 if (!(zero==(row[
j])))
1506 const number_type zero=0;
1507 for(lastIndex=
ncols-1;lastIndex>=0;lastIndex--)
1509 if (!(row[lastIndex]==zero))
1532 rows=(number_type**)
omalloc((
size_t)nnrows*
sizeof(number_type*));
1535 for(
i=0;
i<nnrows;
i++)
1537 rows[
i]=array+((long)
i*(
long)nncols);
1559 number_type* row_array=
rows[row];
1568 number_type* row_array=
rows[r];
1571 number_type coef=row_array[start];
1580 for (other_row=r+1;other_row<
nrows;other_row++)
1586 number_type* other_row_array=
rows[other_row];
1587 number coef2=
npNeg((number)(
long) other_row_array[start],
currRing->cf);
1588 if (coef2==minus_one)
1590 for(
i=start;
i<=lastIndex;
i++)
1592 if (row_array[
i]!=zero)
1602 for(
i=start;
i<=lastIndex;
i++)
1604 if (row_array[
i]!=zero)
1618 number_type* row_array=
rows[row];
1624 if (!(row_array[
i]==0))
1671 number_type* row_array=
rows[row];
1682 this->startIndices=
p.startIndices;
1684 this->ncols=
p.ncols;
1685 this->nrows=
p.nrows;
1710 number_type* row_array=
rows[r];
1713 const number_type zero=0;
1714 for(
i=upper_bound-1;
i>r;
i--)
1718 if (!(row_array[start]==zero))
1731 number_type* row_array=
rows[r];
1743 for(other_row=r-1;other_row>=0;other_row--)
1748 number_type* other_row_array=
rows[other_row];
1749 number coef=
npNeg((number)(
long) other_row_array[start],
currRing->cf);
1753 for(
i=start;
i<=lastIndex;
i++)
1755 if (row_array[
i]!=zero)
1807 Print(
"Input rows %d\n",pn);
1819 srows[non_zeros]=noro_red_to_non_poly_t<number_type>(
h,h_len,&cache,c);
1820 if (srows[non_zeros]!=
NULL) non_zeros++;
1822 std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
1826 int n=irr_nodes.size();
1830 Print(
"Irred Mon:%d\n",n);
1839 term_nodes[
j].
t=irr_nodes[
j]->value_poly;
1841 term_nodes[
j].
node=irr_nodes[
j];
1845 poly* terms=(poly*)
omalloc(n*
sizeof(poly));
1850 old_to_new_indices[term_nodes[
j].
node->term_index]=
j;
1851 term_nodes[
j].node->term_index=
j;
1852 terms[
j]=term_nodes[
j].t;
1874 number_type*
const coef_array=srow->
coef_array;
1875 const int len=srow->
len;
1880 int idx=old_to_new_indices[idx_array[
i]];
1912 #ifdef NORO_NON_POLY
1914 omfree(old_to_new_indices);
1923 for(
i=0;
i<root.branches_len;
i++)
1925 collectIrreducibleMonomials(1,root.branches[
i],
res);
1931 if (node==
NULL)
return;
1982 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)