 |
My Project
UNKNOWN_GIT_VERSION
|
Go to the documentation of this file.
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 )
DataNoroCacheNode< number_type > * treeInsert(poly term, poly nf, int len)
unsigned short tgb_uint16
void sub_dense(number_type *const temp_array, int, const number_type *row, int len)
SparseRow< number_type > * noro_red_to_non_poly_t(poly p, int &len, NoroCache< number_type > *cache, slimgb_alg *c)
unsigned long pTotaldegree(poly p)
void ensureTempBufferSize(size_t size)
void multiplyRow(int row, number_type coef)
unsigned int reduction_steps
void adjust_coefs(number c_r, number c_ac_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:
NoroCacheNode * setNode(int branch, NoroCacheNode *node)
void introduceDelayedPairs(poly *pa, int s)
void add_coef_times_sparse(number_type *const temp_array, int, SparseRow< number_type > *row, number coef)
int nIrreducibleMonomials
DataNoroCacheNode< number_type > * treeInsert(poly term, SparseRow< number_type > *srow)
#define F4mat_to_number_type(a)
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
sorted_pair_node ** apairs
PolySimple(const PolySimple &a)
static number npMultM(number a, number b, const coeffs r)
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
DataNoroCacheNode< number_type > * ref
void free_sorted_pair_node(sorted_pair_node *s, const ring r)
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
sorted_pair_node ** tmp_spn
void backwardSubstitute(int r)
virtual void do_reduce(red_object &ro)
int modP_lastIndexRow(number_type *row, int ncols)
int terms_sort_crit(const void *a, const void *b)
static poly p_LmInit(poly p, const ring r)
std::vector< PolySimple > poly_vec
int term_nodes_sort_crit(const void *a, const void *b)
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)
Compatiblity layer for legacy polynomial operations (over currRing)
BOOLEAN use_noro_last_block
wlen_type * weighted_lengths
void noro_step(poly *p, int &pn, slimgb_alg *c)
static BOOLEAN length(leftv result, leftv arg)
bool operator==(const PolySimple &other)
poly lookup(poly term, BOOLEAN &succ, int &len)
int pTotaldegree_full(poly p)
bool operator<(const CoefIdx< number_type > &other) const
PolySimple & operator=(const PolySimple &p2)
int tgb_pair_better_gen2(const void *ap, const void *bp)
sorted_pair_node * top_pair(slimgb_alg *c)
static poly pp_Mult_mm(poly p, poly m, const ring r)
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
void multiplyRow(int row, number_type coef)
void write_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
poly row_to_poly(number_type *row, poly *terms, int tn, ring r)
int_pair_node * soon_free
static const int backLinkCode
void write_poly_to_row(number_type *row, poly h, poly *terms, int tn, ring r)
void cleanDegs(int lower, int upper)
simple_reducer(poly pp, int pp_len, int pp_reducer_deg, slimgb_alg *pp_c=NULL)
int * lastReducibleIndices
SparseRow< number_type > * convert_to_sparse_row(number_type *temp_array, int temp_size, int non_zeros)
static unsigned pLength(poly a)
void write_minus_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
void simplest_gauss_modp(number_type *a, int nrows, int ncols)
MonRedResNP< number_type > noro_red_mon_to_non_poly(poly t, NoroCache< number_type > *cache, slimgb_alg *c)
static poly p_Copy(poly p, const ring r)
returns a copy of p
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
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 number npAddM(number a, number b, const coeffs r)
static number npSubM(number a, number b, const coeffs r)
DataNoroCacheNode(SparseRow< number_type > *row)
SparseRow< number_type > * noro_red_to_non_poly_dense(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
void backwardSubstitute()
SparseRow< number_type > * noro_red_to_non_poly_sparse(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
static number npNegM(number a, const coeffs r)
virtual ~reduction_step()
void sub_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
DataNoroCacheNode< number_type > * insert(poly term, SparseRow< number_type > *srow)
slimgb_alg(ideal I, int syz_comp, BOOLEAN F4, int deg_pos)
DataNoroCacheNode< number_type > * getCacheReference(poly term)
#define omrealloc(addr, size)
static int max(int a, int b)
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set)
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
int extended_product_crit
DataNoroCacheNode< number_type > * node
void add_coef_times_dense(number_type *const temp_array, int, const number_type *row, int len, number coef)
static int p_LmCmp(poly p, poly q, const ring r)
NoroCacheNode * getOrInsertBranch(int branch)
int slim_nsize(number n, ring r)
void now_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *c)
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)
void sort(CFArray &A, int l=0)
quick sort A
void reduceOtherRowsForward(int r)
void add_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
int kFindDivisibleByInS_easy(kStrategy strat, const red_object &obj)
void updateStartIndex(int row, int lower_bound)
static void p_Delete(poly *p, const ring r)
static int min(int a, int b)
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)
wlen_type initial_quality
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,...
makes on each red_object in a region a single_step
wlen_type guess_quality(slimgb_alg *c)
static int si_max(const int a, const int b)
static CanonicalForm bound(const CFMatrix &M)
NoroCacheNode * getBranch(int branch)
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,...
void updateLastReducibleIndex(int r, int upper_bound)
static number p_SetCoeff(poly p, number n, ring r)
wlen_type pELength(poly p, ring r)
void collectIrreducibleMonomials(std::vector< DataNoroCacheNode< number_type > * > &res)
ideal do_t_rep_gb(ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
DataNoroCacheNode< number_type > * treeInsertBackLink(poly term)
void permRows(int i, int j)
~ModPMatrixProxyOnArray()
ModPMatrixProxyOnArray(number_type *array, int nnrows, int nncols)
static void p_Setm(poly p, const ring r)
bool operator<(const PolySimple &other) const
BOOLEAN eliminationProblem
static long p_Totaldegree(poly p, const ring r)
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
const CanonicalForm int s
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
int syz_comp
array_lengths should be greater equal n;
SparseRow< number_type > * row
poly_array_list * F_minus
wlen_type expected_length
unsigned long p_GetShortExpVector(const poly p, const ring r)
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)
void clean_top_of_pair_list(slimgb_alg *c)
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 add_dense(number_type *const temp_array, int, const number_type *row, int len)
DataNoroCacheNode(poly p, int len)
BOOLEAN findPivot(int &r, int &c)
int getStartIndex(int row)
virtual void pre_reduce(red_object *r, int l, int u)
NoroCacheNode ** branches
poly_list_node * to_destroy