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
217 void introduceDelayedPairs(poly*
pa,
int s);
219 void cleanDegs(
int lower,
int upper);
221 #ifdef USE_STDVECBOOL 222 vector<vector<bool> > states;
227 vector<dynamic_bitset<> > states;
248 #ifdef TGB_RESORT_PAIRS 286 #ifdef TGB_RESORT_PAIRS 294 return p->exp[deg_pos];
318 void adjust_coefs(number c_r, number c_ac_r);
370 this->reducer_deg=pp_reducer_deg;
375 virtual void pre_reduce(
red_object* r,
int l,
int u);
405 if ((len>setL[length])
406 || ((len==setL[length]) && (
pLmCmp(
set[length],p)== -1)))
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) 447 if (branch>=branches_len)
451 branches_len=branch+1;
452 branches_len=
si_max(branches_len,3);
455 for(i=0;i<branches_len;i++)
462 int branches_len_old=branches_len;
463 branches_len=branch+1;
466 for(i=branches_len_old;i<branches_len;i++)
473 branches[branch]=node;
478 if (branch<branches_len)
return branches[branch];
484 for(i=0;i<branches_len;i++)
492 if ((branch<branches_len)&&(branches[branch]))
493 return branches[branch];
529 idx_array=(
int*)
omAlloc(n*
sizeof(
int));
530 coef_array=(number_type*)
omAlloc(n*
sizeof(number_type));
536 coef_array=(number_type*)
omAlloc(n*
sizeof(number_type));
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;
606 static const int backLinkCode=-222;
616 ressources.push_back(term);
617 nIrreducibleMonomials++;
618 return treeInsertBackLink(term);
627 ressources.push_back(nf);
629 return treeInsert(term,nf,len);
635 #ifdef NORO_SPARSE_ROWS_PRE 641 return treeInsert(term,srow);
649 ressources.push_back(t);
652 nIrreducibleMonomials++;
660 #ifdef NORO_RED_ARRAY_RESERVER 662 recursionPolyBuffer=(poly*)
omAlloc(1000000*
sizeof(poly));
664 nIrreducibleMonomials=0;
665 nReducibleMonomials=0;
668 tempBuffer=
omAlloc(tempBufferSize);
672 if (tempBufferSize<size)
674 tempBufferSize=2*
size;
676 tempBuffer=
omAlloc(tempBufferSize);
679 #ifdef NORO_RED_ARRAY_RESERVER 682 poly*
res=recursionPolyBuffer+reserved;
693 int s=ressources.size();
700 #ifdef NORO_RED_ARRAY_RESERVER 701 omfree(recursionPolyBuffer);
714 nReducibleMonomials++;
723 #ifdef NORO_SPARSE_ROWS_PRE 727 nReducibleMonomials++;
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;
845 for(
i=0;
i<cache->nIrreducibleMonomials;
i++)
847 if (!(0==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];
929 int bpos_bound=bound-
j;
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];
977 int bpos_bound=bound-
j;
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);
1190 bool operator<(const CoefIdx<number_type>& other)
const 1192 return (idx<other.idx);
1200 assume(coef_array[j]!=0);
1203 ci.
idx=idx_array[
j];
1213 if (coef_array[j]!=0)
1215 assume(coef_array[j]!=0);
1230 if (coef_array[j]!=0)
1232 assume(coef_array[j]!=0);
1234 ci.
coef=coef_array[
j];
1248 if (coef_array[j]!=0)
1250 assume(coef_array[j]!=0);
1264 assume(coef_array[j]!=0);
1266 ci.
coef=coef_array[
j];
1267 ci.
idx=idx_array[
j];
1277 assume(coef_array[j]!=0);
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;
1374 assume(pairs[0].coef!=0);
1375 for(i=1;i<together;i++)
1377 if (pairs[i].idx!=pairs[act].idx)
1379 if (pairs[act].coef!=0)
1383 pairs[
act]=pairs[
i];
1391 if (pairs[act].coef==0)
1395 int sparse_row_len=act+1;
1397 if (sparse_row_len==0) {
return NULL;}
1402 for(i=0;i<sparse_row_len;i++)
1404 idx_array[
i]=pairs[
i].
idx;
1405 coef_array[
i]=pairs[
i].
coef;
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)
1476 poly* ptr_to_h=(poly*) bsearch(&h,terms,tn,
sizeof(poly),
terms_sort_crit);
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);
1538 updateStartIndex(i,-1);
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)
1611 updateStartIndex(other_row,start);
1618 number_type* row_array=
rows[row];
1622 for(i=lower_bound+1;i<
ncols;i++)
1624 if (!(row_array[i]==0))
1640 for(i=r;i<
nrows;i++)
1671 number_type* row_array=rows[row];
1672 for(i=startIndices[row];i<
ncols;i++)
1684 this->ncols=p.ncols;
1685 this->nrows=p.nrows;
1686 lastReducibleIndices=(
int*)
omalloc(nrows*
sizeof(
int));
1688 while(nonZeroUntil<nrows)
1690 if (startIndices[nonZeroUntil]<ncols)
1697 Print(
"rank:%i\n",nonZeroUntil);
1700 for(i=0;i<=nonZeroUntil;i++)
1702 assume(startIndices[i]<ncols);
1704 assume(startIndices[i]>=i);
1705 updateLastReducibleIndex(i,nonZeroUntil+1);
1710 number_type* row_array=rows[r];
1711 if (upper_bound>nonZeroUntil) upper_bound=nonZeroUntil+1;
1713 const number_type zero=0;
1714 for(i=upper_bound-1;i>r;i--)
1716 int start=startIndices[
i];
1718 if (!(row_array[start]==zero))
1720 lastReducibleIndices[r]=start;
1724 lastReducibleIndices[r]=-1;
1728 int start=startIndices[r];
1731 number_type* row_array=rows[r];
1743 for(other_row=r-1;other_row>=0;other_row--)
1745 assume(lastReducibleIndices[other_row]<=start);
1746 if (lastReducibleIndices[other_row]==start)
1748 number_type* other_row_array=rows[other_row];
1749 number coef=
npNeg((number)(
long) other_row_array[start],
currRing->cf);
1752 assume(start>startIndices[other_row]);
1753 for(i=start;i<=lastIndex;i++)
1755 if (row_array[i]!=zero)
1761 updateLastReducibleIndex(other_row,r);
1767 omfree(lastReducibleIndices);
1772 for(i=nonZeroUntil;i>0;i--)
1774 backwardSubstitute(i);
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;
1863 number_type* row=number_array+((long)n)*(long)j;
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]];
1902 poly
h=
row_to_poly(number_array+((
long)j)*((
long)n),terms,n,c->
r);
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;
1937 collectIrreducibleMonomials(level+1,node->
branches[i],
res);
1982 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)
BOOLEAN pa(leftv res, leftv args)
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