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
213 void introduceDelayedPairs(poly* pa,
int s);
215 void cleanDegs(
int lower,
int upper);
217 #ifdef USE_STDVECBOOL 218 vector<vector<bool> > states;
223 vector<dynamic_bitset<> > states;
244 #ifdef TGB_RESORT_PAIRS 282 #ifdef TGB_RESORT_PAIRS 290 return p->exp[deg_pos];
314 void adjust_coefs(number c_r, number c_ac_r);
366 this->reducer_deg=pp_reducer_deg;
371 virtual void pre_reduce(
red_object* r,
int l,
int u);
401 if ((len>setL[length])
402 || ((len==setL[length]) && (
pLmCmp(
set[length],p)== -1)))
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) 443 if (branch>=branches_len)
447 branches_len=branch+1;
448 branches_len=
si_max(branches_len,3);
451 for(i=0;i<branches_len;i++)
458 int branches_len_old=branches_len;
459 branches_len=branch+1;
462 for(i=branches_len_old;i<branches_len;i++)
469 branches[branch]=node;
474 if (branch<branches_len)
return branches[branch];
480 for(i=0;i<branches_len;i++)
488 if ((branch<branches_len)&&(branches[branch]))
489 return branches[branch];
525 idx_array=(
int*)
omAlloc(n*
sizeof(
int));
526 coef_array=(number_type*)
omAlloc(n*
sizeof(number_type));
532 coef_array=(number_type*)
omAlloc(n*
sizeof(number_type));
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;
602 static const int backLinkCode=-222;
612 ressources.push_back(term);
613 nIrreducibleMonomials++;
614 return treeInsertBackLink(term);
623 ressources.push_back(nf);
625 return treeInsert(term,nf,len);
631 #ifdef NORO_SPARSE_ROWS_PRE 637 return treeInsert(term,srow);
645 ressources.push_back(t);
648 nIrreducibleMonomials++;
656 #ifdef NORO_RED_ARRAY_RESERVER 658 recursionPolyBuffer=(poly*)
omAlloc(1000000*
sizeof(poly));
660 nIrreducibleMonomials=0;
661 nReducibleMonomials=0;
664 tempBuffer=
omAlloc(tempBufferSize);
668 if (tempBufferSize<size)
670 tempBufferSize=2*
size;
672 tempBuffer=
omAlloc(tempBufferSize);
675 #ifdef NORO_RED_ARRAY_RESERVER 678 poly*
res=recursionPolyBuffer+reserved;
689 int s=ressources.size();
696 #ifdef NORO_RED_ARRAY_RESERVER 697 omfree(recursionPolyBuffer);
710 nReducibleMonomials++;
719 #ifdef NORO_SPARSE_ROWS_PRE 723 nReducibleMonomials++;
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;
840 for(
i=0;
i<cache->nIrreducibleMonomials;
i++){
841 if (!(0==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];
922 int bpos_bound=bound-
j;
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];
970 int bpos_bound=bound-
j;
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);
1182 bool operator<(const CoefIdx<number_type>& other)
const 1184 return (idx<other.idx);
1192 assume(coef_array[j]!=0);
1195 ci.
idx=idx_array[
j];
1205 if (coef_array[j]!=0)
1207 assume(coef_array[j]!=0);
1222 if (coef_array[j]!=0)
1224 assume(coef_array[j]!=0);
1226 ci.
coef=coef_array[
j];
1240 if (coef_array[j]!=0)
1242 assume(coef_array[j]!=0);
1256 assume(coef_array[j]!=0);
1258 ci.
coef=coef_array[
j];
1259 ci.
idx=idx_array[
j];
1269 assume(coef_array[j]!=0);
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;
1366 assume(pairs[0].coef!=0);
1367 for(i=1;i<together;i++)
1369 if (pairs[i].idx!=pairs[act].idx)
1371 if (pairs[act].coef!=0)
1375 pairs[
act]=pairs[
i];
1383 if (pairs[act].coef==0)
1387 int sparse_row_len=act+1;
1389 if (sparse_row_len==0) {
return NULL;}
1394 for(i=0;i<sparse_row_len;i++)
1396 idx_array[
i]=pairs[
i].
idx;
1397 coef_array[
i]=pairs[
i].
coef;
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){
1465 poly* ptr_to_h=(poly*) bsearch(&h,terms,tn,
sizeof(poly),
terms_sort_crit);
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);
1524 updateStartIndex(i,-1);
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)
1597 updateStartIndex(other_row,start);
1604 number_type* row_array=
rows[row];
1608 for(i=lower_bound+1;i<
ncols;i++)
1610 if (!(row_array[i]==0))
1626 for(i=r;i<
nrows;i++)
1657 number_type* row_array=rows[row];
1658 for(i=startIndices[row];i<
ncols;i++)
1670 this->ncols=p.ncols;
1671 this->nrows=p.nrows;
1672 lastReducibleIndices=(
int*)
omalloc(nrows*
sizeof(
int));
1674 while(nonZeroUntil<nrows)
1676 if (startIndices[nonZeroUntil]<ncols)
1683 Print(
"rank:%i\n",nonZeroUntil);
1686 for(i=0;i<=nonZeroUntil;i++)
1688 assume(startIndices[i]<ncols);
1690 assume(startIndices[i]>=i);
1691 updateLastReducibleIndex(i,nonZeroUntil+1);
1696 number_type* row_array=rows[r];
1697 if (upper_bound>nonZeroUntil) upper_bound=nonZeroUntil+1;
1699 const number_type zero=0;
1700 for(i=upper_bound-1;i>r;i--)
1702 int start=startIndices[
i];
1704 if (!(row_array[start]==zero))
1706 lastReducibleIndices[r]=start;
1710 lastReducibleIndices[r]=-1;
1714 int start=startIndices[r];
1717 number_type* row_array=rows[r];
1729 for(other_row=r-1;other_row>=0;other_row--)
1731 assume(lastReducibleIndices[other_row]<=start);
1732 if (lastReducibleIndices[other_row]==start)
1734 number_type* other_row_array=rows[other_row];
1735 number coef=
npNeg((number)(
long) other_row_array[start],
currRing->cf);
1738 assume(start>startIndices[other_row]);
1739 for(i=start;i<=lastIndex;i++)
1741 if (row_array[i]!=zero)
1747 updateLastReducibleIndex(other_row,r);
1753 omfree(lastReducibleIndices);
1758 for(i=nonZeroUntil;i>0;i--)
1760 backwardSubstitute(i);
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;
1847 number_type* row=number_array+n*
j;
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;
1916 collectIrreducibleMonomials(level+1,node->
branches[i],
res);
1954 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 simplest_gauss_modp(number_type *a, int nrows, int ncols)
sorted_pair_node ** apairs
void add_dense(number_type *const temp_array, int, const number_type *row, int len)
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
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)
void add_coef_times_sparse(number_type *const temp_array, int, SparseRow< number_type > *row, number coef)
NoroCacheNode * getBranch(int branch)
int_pair_node * soon_free
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
void add_coef_times_dense(number_type *const temp_array, int, const number_type *row, int len, number coef)
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 poly p_Copy(poly p, const ring r)
returns a copy of p
int slim_nsize(number n, ring r)
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
DataNoroCacheNode< number_type > * treeInsertBackLink(poly term)
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
void add_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
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)
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)
bool operator<(const PolySimple &other) const
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)
static unsigned pLength(poly a)
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, SparseRow< number_type > *row)
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)
#define omrealloc(addr, size)
DataNoroCacheNode< number_type > * treeInsert(poly term, SparseRow< number_type > *srow)
PolySimple(const PolySimple &a)
DataNoroCacheNode< number_type > * node
static BOOLEAN length(leftv result, leftv arg)
void now_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *c)
void sub_dense(number_type *const temp_array, int, const number_type *row, int len)
BOOLEAN eliminationProblem
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
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 free_sorted_pair_node(sorted_pair_node *s, const ring r)
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;
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