15 #define FULLREDUCTIONS 31 #define NORO_SPARSE_ROWS_PRE 1 32 #define NORO_NON_POLY 1 39 #ifdef HAVE_BOOST_DYNAMIC_BITSET_HPP 46 using boost::dynamic_bitset;
74 #define npNeg n_InpNeg 75 #define npInvers n_Invers 77 #define npIsOne n_IsOne 78 #define npIsZero n_IsZero 81 #error Please do NOT call internal functions directly! 167 #ifndef NORO_NON_POLY 168 class NoroPlaceHolder
214 void introduceDelayedPairs(
poly* pa,
int s);
216 void cleanDegs(
int lower,
int upper);
218 #ifdef USE_STDVECBOOL 219 vector<vector<bool> > states;
224 vector<dynamic_bitset<> > states;
245 #ifdef TGB_RESORT_PAIRS 283 #ifdef TGB_RESORT_PAIRS 291 return p->exp[deg_pos];
315 void adjust_coefs(number c_r, number c_ac_r);
367 this->reducer_deg=pp_reducer_deg;
397 int length=strat->
sl;
402 if ((len>setL[length])
403 || ((len==setL[length]) && (
pLmCmp(
set[length],p)== -1)))
411 || ((len==setL[an]) && (
pLmCmp(
set[an],p) == 1)))
return an;
416 || ((len==setL[
i]) && (
pLmCmp(
set[i],p) == 1))) en=i;
424 #define slim_prec_cast(a) (unsigned int) (unsigned long) (a) 425 #define F4mat_to_number_type(a) (number_type) slim_prec_cast(a) 444 if (branch>=branches_len)
448 branches_len=branch+1;
449 branches_len=
si_max(branches_len,3);
452 for(i=0;i<branches_len;i++)
459 int branches_len_old=branches_len;
460 branches_len=branch+1;
463 for(i=branches_len_old;i<branches_len;i++)
470 branches[branch]=node;
475 if (branch<branches_len)
return branches[branch];
481 for(i=0;i<branches_len;i++)
489 if ((branch<branches_len)&&(branches[branch]))
490 return branches[branch];
526 idx_array=(
int*)
omAlloc(n*
sizeof(
int));
527 coef_array=(number_type*)
omAlloc(n*
sizeof(number_type));
533 coef_array=(number_type*)
omAlloc(n*
sizeof(number_type));
534 memcpy(coef_array,source,n*
sizeof(number_type));
549 #ifdef NORO_SPARSE_ROWS_PRE 562 #ifdef NORO_SPARSE_ROWS_PRE 591 #ifndef NORO_NON_POLY 592 void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
599 #ifdef NORO_RED_ARRAY_RESERVER 601 poly* recursionPolyBuffer;
603 static const int backLinkCode=-222;
613 ressources.push_back(term);
614 nIrreducibleMonomials++;
615 return treeInsertBackLink(term);
624 ressources.push_back(nf);
626 return treeInsert(term,nf,len);
632 #ifdef NORO_SPARSE_ROWS_PRE 638 return treeInsert(term,srow);
646 ressources.push_back(t);
649 nIrreducibleMonomials++;
657 #ifdef NORO_RED_ARRAY_RESERVER 661 nIrreducibleMonomials=0;
662 nReducibleMonomials=0;
665 tempBuffer=
omAlloc(tempBufferSize);
669 if (tempBufferSize<size)
671 tempBufferSize=2*
size;
673 tempBuffer=
omAlloc(tempBufferSize);
676 #ifdef NORO_RED_ARRAY_RESERVER 679 poly*
res=recursionPolyBuffer+reserved;
690 int s=ressources.size();
697 #ifdef NORO_RED_ARRAY_RESERVER 698 omfree(recursionPolyBuffer);
711 nReducibleMonomials++;
720 #ifdef NORO_SPARSE_ROWS_PRE 724 nReducibleMonomials++;
792 srow=noro_red_to_non_poly_t<number_type>(
res,len,cache,c);
793 ref=cache->insert(t,srow);
797 res_holder.
coef=coef_bak;
803 number one=
npInit(1, c->
r->cf);
808 res_holder.
coef=coef_bak;
834 #define LIKELY(expression) (__builtin_expect(!!(expression), 1)) 835 #define UNLIKELY(expression) (__builtin_expect(!!(expression), 0)) 837 #define LIKELY(expression) (expression) 838 #define UNLIKELY(expression) (expression) 848 for(
i=0;
i<cache->nIrreducibleMonomials;
i++){
849 if (!(0==temp_array[
i])){
856 if (non_zeros==0)
break;
863 const int multiple=
sizeof(
int64)/
sizeof(number_type);
864 if (temp_size==0) end=start;
868 int temp_size_rounded=temp_size+(multiple-(temp_size%multiple));
869 assume(temp_size_rounded>=temp_size);
870 assume(temp_size_rounded%multiple==0);
871 assume(temp_size_rounded<temp_size+multiple);
872 number_type* nt_end=temp_array+temp_size_rounded;
873 end=(
int64*)((
void*)nt_end);
881 const int temp_index=((number_type*)((
void*) it))-temp_array;
882 const int bound=temp_index+multiple;
884 for(small_i=temp_index;small_i<
bound;small_i++)
886 if((c=temp_array[small_i])!=0)
890 (*(it_idx++))=small_i;
914 number_type*
const coef_array=row->
coef_array;
916 const int len=row->
len;
921 for(j=0;j<len;j=j+256)
928 buffer[bpos++]=coef_array[
i];
930 int bpos_bound=bound-
j;
931 for(i=0;i<bpos_bound;i++)
935 for(i=0;i<bpos_bound;i++)
937 buffer[
i]=buffer[
i]%prime;
942 int idx=idx_array[
i];
953 int ,
const number_type* row,
int len,number coef)
956 int temp_size,
const number_type* row,
int len,number coef)
960 const number_type*
const coef_array=row;
967 for(j=0;j<len;j=j+256)
974 buffer[bpos++]=coef_array[
i];
976 int bpos_bound=bound-
j;
977 for(i=0;i<bpos_bound;i++)
981 for(i=0;i<bpos_bound;i++)
983 buffer[
i]=buffer[
i]%prime;
998 template <
class number_type>
void add_dense(number_type*
const temp_array,
999 int ,
const number_type* row,
int len)
1001 template <
class number_type>
void add_dense(number_type*
const temp_array,
1002 int temp_size,
const number_type* row,
int len)
1022 template <
class number_type>
void sub_dense(number_type*
const temp_array,
1023 int ,
const number_type* row,
int len)
1025 template <
class number_type>
void sub_dense(number_type*
const temp_array,
1026 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];
1073 number_type*
const coef_array=row->
coef_array;
1075 const int len=row->
len;
1078 int idx=idx_array[
j];
1088 number_type* temp_array=(number_type*) cache->
tempBuffer;
1090 memset(temp_array,0,temp_size_bytes);
1101 number coef=red.
coef;
1104 if (!((coef==(number)(
long) 1)||(coef==minus_one)))
1110 if (coef==(number)(
long) 1)
1122 if (!((coef==(number)(
long) 1)||(coef==minus_one)))
1128 if (coef==(number)(
long)1)
1157 assume(((temp_array[i]!=0)==0)|| (((temp_array[i]!=0)==1)));
1158 non_zeros+=(temp_array[
i]!=0);
1178 bool operator<(const CoefIdx<number_type>& other)
const 1180 return (idx<other.idx);
1188 assume(coef_array[j]!=0);
1191 ci.
idx=idx_array[
j];
1201 if (coef_array[j]!=0)
1203 assume(coef_array[j]!=0);
1218 if (coef_array[j]!=0)
1220 assume(coef_array[j]!=0);
1222 ci.
coef=coef_array[
j];
1236 if (coef_array[j]!=0)
1238 assume(coef_array[j]!=0);
1252 assume(coef_array[j]!=0);
1254 ci.
coef=coef_array[
j];
1255 ci.
idx=idx_array[
j];
1265 assume(coef_array[j]!=0);
1268 ci.
idx=idx_array[
j];
1279 if ((red.
ref) &&( red.
ref->row))
1281 together+=red.
ref->row->len;
1290 if (together==0)
return 0;
1300 if ((red.
ref) &&( red.
ref->row))
1303 int* idx_array=red.
ref->row->idx_array;
1304 number_type* coef_array=red.
ref->row->coef_array;
1305 int rlen=red.
ref->row->len;
1306 number coef=red.
coef;
1309 if ((coef!=one)&&(coef!=minus_one))
1328 if ((coef!=one)&&(coef!=minus_one))
1350 ci.
idx=red.
ref->term_index;
1362 assume(pairs[0].coef!=0);
1363 for(i=1;i<together;i++)
1365 if (pairs[i].idx!=pairs[act].idx)
1367 if (pairs[act].coef!=0)
1371 pairs[
act]=pairs[
i];
1379 if (pairs[act].coef==0)
1383 int sparse_row_len=act+1;
1385 if (sparse_row_len==0) {
return NULL;}
1390 for(i=0;i<sparse_row_len;i++)
1392 idx_array[
i]=pairs[
i].
idx;
1393 coef_array[
i]=pairs[
i].
coef;
1410 double max_density=0.0;
1418 if ((red.
ref) && (red.
ref->row))
1420 double act_density=(double) red.
ref->row->len;
1422 max_density=
std::max(act_density,max_density);
1431 if (max_density<0.3) dense=
false;
1460 int pos=ptr_to_h-terms;
1470 for(j=tn-1;j>=0;j--){
1471 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(nnrows*
sizeof(number_type*));
1514 for(i=0;i<nnrows;i++)
1516 rows[
i]=array+(i*nncols);
1517 updateStartIndex(i,-1);
1538 number_type* row_array=
rows[row];
1547 number_type* row_array=
rows[
r];
1550 number_type coef=row_array[start];
1559 for (other_row=r+1;other_row<
nrows;other_row++)
1565 number_type* other_row_array=
rows[other_row];
1566 number coef2=
npNeg((number)(
long) other_row_array[start],
currRing->cf);
1567 if (coef2==minus_one)
1569 for(i=start;i<=lastIndex;i++)
1571 if (row_array[i]!=zero)
1581 for(i=start;i<=lastIndex;i++)
1583 if (row_array[i]!=zero)
1590 updateStartIndex(other_row,start);
1597 number_type* row_array=
rows[row];
1601 for(i=lower_bound+1;i<
ncols;i++)
1603 if (!(row_array[i]==0))
1619 for(i=r;i<
nrows;i++)
1650 number_type* row_array=rows[row];
1651 for(i=startIndices[row];i<
ncols;i++)
1663 this->ncols=p.ncols;
1664 this->nrows=p.nrows;
1665 lastReducibleIndices=(
int*)
omalloc(nrows*
sizeof(
int));
1667 while(nonZeroUntil<nrows)
1669 if (startIndices[nonZeroUntil]<ncols)
1676 Print(
"rank:%i\n",nonZeroUntil);
1679 for(i=0;i<=nonZeroUntil;i++)
1681 assume(startIndices[i]<ncols);
1683 assume(startIndices[i]>=i);
1684 updateLastReducibleIndex(i,nonZeroUntil+1);
1689 number_type* row_array=rows[
r];
1690 if (upper_bound>nonZeroUntil) upper_bound=nonZeroUntil+1;
1692 const number_type zero=0;
1693 for(i=upper_bound-1;i>
r;i--)
1695 int start=startIndices[
i];
1697 if (!(row_array[start]==zero))
1699 lastReducibleIndices[
r]=start;
1703 lastReducibleIndices[
r]=-1;
1707 int start=startIndices[
r];
1710 number_type* row_array=rows[
r];
1722 for(other_row=r-1;other_row>=0;other_row--)
1724 assume(lastReducibleIndices[other_row]<=start);
1725 if (lastReducibleIndices[other_row]==start)
1727 number_type* other_row_array=rows[other_row];
1728 number coef=
npNeg((number)(
long) other_row_array[start],
currRing->cf);
1731 assume(start>startIndices[other_row]);
1732 for(i=start;i<=lastIndex;i++)
1734 if (row_array[i]!=zero)
1740 updateLastReducibleIndex(other_row,r);
1746 omfree(lastReducibleIndices);
1751 for(i=nonZeroUntil;i>0;i--)
1753 backwardSubstitute(i);
1784 Print(
"Input rows %d\n",pn);
1796 srows[non_zeros]=noro_red_to_non_poly_t<number_type>(
h,h_len,&cache,c);
1797 if (srows[non_zeros]!=
NULL) non_zeros++;
1799 std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
1803 int n=irr_nodes.size();
1807 Print(
"Irred Mon:%d\n",n);
1816 term_nodes[
j].
t=irr_nodes[
j]->value_poly;
1818 term_nodes[
j].
node=irr_nodes[
j];
1827 old_to_new_indices[term_nodes[
j].
node->term_index]=
j;
1828 term_nodes[
j].node->term_index=
j;
1829 terms[
j]=term_nodes[
j].t;
1835 number_type* number_array=(number_type*)
omalloc0(n*pn*
sizeof(number_type));
1840 number_type* row=number_array+n*
j;
1851 number_type*
const coef_array=srow->
coef_array;
1852 const int len=srow->
len;
1857 int idx=old_to_new_indices[idx_array[
i]];
1887 #ifdef NORO_NON_POLY 1889 omfree(old_to_new_indices);
1897 for(i=0;i<root.branches_len;i++){
1898 collectIrreducibleMonomials(1,root.branches[i],
res);
1903 if (node==
NULL)
return;
1909 collectIrreducibleMonomials(level+1,node->
branches[i],
res);
1947 if ( res_holder->
value_len==backLinkCode ){
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
void noro_step(poly *p, int &pn, slimgb_alg *c)
std::vector< PolySimple > poly_vec
DataNoroCacheNode< number_type > * insert(poly term, SparseRow< number_type > *srow)
void updateStartIndex(int row, int lower_bound)
DataNoroCacheNode< number_type > * treeInsert(poly term, poly nf, int len)
const CanonicalForm int s
unsigned int reduction_steps
unsigned long pTotaldegree(poly p)
poly lookup(poly term, BOOLEAN &succ, int &len)
NoroCacheNode * setNode(int branch, NoroCacheNode *node)
DataNoroCacheNode(poly p, int len)
static CanonicalForm bound(const CFMatrix &M)
void backwardSubstitute()
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)
static number npMultM(number a, number b, const coeffs r)
void add_sparse(number_type *const temp_array, int temp_size, SparseRow< number_type > *row)
void simplest_gauss_modp(number_type *a, int nrows, int ncols)
sorted_pair_node ** apairs
void collectIrreducibleMonomials(std::vector< DataNoroCacheNode< number_type > * > &res)
void write_minus_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
static int min(int a, int b)
~ModPMatrixProxyOnArray()
int * lastReducibleIndices
Compatiblity layer for legacy polynomial operations (over currRing)
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)
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
sorted_pair_node ** tmp_spn
wlen_type * weighted_lengths
ModPMatrixProxyOnArray(number_type *array, int nnrows, int nncols)
BOOLEAN use_noro_last_block
int pTotaldegree_full(poly p)
unsigned short tgb_uint16
bool operator<(const PolySimple &other) const
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
static poly pp_Mult_mm(poly p, poly m, const ring r)
SparseRow< number_type > * noro_red_to_non_poly_t(poly p, int &len, NoroCache< number_type > *cache, slimgb_alg *c)
static long p_Totaldegree(poly p, const ring r)
void reduceOtherRowsForward(int r)
NoroCacheNode * getBranch(int branch)
#define UNLIKELY(expression)
int_pair_node * soon_free
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
BOOLEAN findPivot(int &r, int &c)
void updateLastReducibleIndex(int r, int upper_bound)
DataNoroCacheNode(SparseRow< number_type > *row)
static number p_SetCoeff(poly p, number n, ring r)
int modP_lastIndexRow(number_type *row, int ncols)
int terms_sort_crit(const void *a, const void *b)
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set)
static int pLength(poly a)
static poly p_Copy(poly p, const ring r)
returns a copy of p
int slim_nsize(number n, ring r)
void add_coef_times_sparse(number_type *const temp_array, int temp_size, SparseRow< number_type > *row, number coef)
static number npNegM(number a, const coeffs r)
static number npSubM(number a, number b, const coeffs 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)
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
DataNoroCacheNode< number_type > * treeInsertBackLink(poly term)
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
void write_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
int tgb_pair_better_gen2(const void *ap, const void *bp)
poly row_to_poly(number_type *row, poly *terms, int tn, ring r)
void add_dense(number_type *const temp_array, int temp_size, const number_type *row, int len)
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
int kFindDivisibleByInS_easy(kStrategy strat, const red_object &obj)
static int max(int a, int b)
void ensureTempBufferSize(size_t size)
sorted_pair_node * top_pair(slimgb_alg *c)
static long pTotaldegree(poly p)
simple_reducer(poly pp, int pp_len, int pp_reducer_deg, slimgb_alg *pp_c=NULL)
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
DataNoroCacheNode< number_type > * getCacheReference(poly term)
wlen_type pELength(poly p, ring r)
void backwardSubstitute(int r)
void permRows(int i, int j)
SparseRow< number_type > * convert_to_sparse_row(number_type *temp_array, int temp_size, int non_zeros)
MonRedResNP< number_type > noro_red_mon_to_non_poly(poly t, NoroCache< number_type > *cache, slimgb_alg *c)
static number npAddM(number a, number b, const coeffs r)
void write_poly_to_row(number_type *row, poly h, poly *terms, int tn, ring r)
makes on each red_object in a region a single_step
static int p_LmCmp(poly p, poly q, const ring r)
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)
int extended_product_crit
static int si_max(const int a, const int b)
SparseRow< number_type > * noro_red_to_non_poly_dense(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
NoroCacheNode * getOrInsertBranch(int branch)
int getStartIndex(int row)
SparseRow< number_type > * noro_red_to_non_poly_sparse(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
void sub_sparse(number_type *const temp_array, int temp_size, SparseRow< number_type > *row)
void add_coef_times_dense(number_type *const temp_array, int temp_size, const number_type *row, int len, number coef)
void multiplyRow(int row, number_type coef)
static void p_Delete(poly *p, const ring r)
void multiplyRow(int row, number_type coef)
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
unsigned long p_GetShortExpVector(const poly p, const ring r)
bool operator==(const PolySimple &other)
wlen_type expected_length
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
void clean_top_of_pair_list(slimgb_alg *c)
void free_sorted_pair_node(sorted_pair_node *s, ring r)
#define omrealloc(addr, size)
DataNoroCacheNode< number_type > * treeInsert(poly term, SparseRow< number_type > *srow)
PolySimple(const PolySimple &a)
DataNoroCacheNode< number_type > * node
void now_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *c)
BOOLEAN eliminationProblem
static poly p_LmInit(poly p, const ring r)
static void p_Setm(poly p, const ring r)
NoroCacheNode ** branches
wlen_type initial_quality
void sort(CFArray &A, int l=0)
quick sort A
poly_array_list * F_minus
#define F4mat_to_number_type(a)
PolySimple & operator=(const PolySimple &p2)
int nIrreducibleMonomials
DataNoroCacheNode< number_type > * ref
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)
int syz_comp
array_lengths should be greater equal n;
void sub_dense(number_type *const temp_array, int temp_size, const number_type *row, int len)
int term_nodes_sort_crit(const void *a, const void *b)
ideal do_t_rep_gb(ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
poly_list_node * to_destroy
SparseRow< number_type > * row