60 #ifndef RTIMER_BENCHMARKING
61 # define RTIMER_BENCHMARKING 0
104 inline void Add( poly
p,
const int l )
135 const poly nxt =
pNext(
s);
160 return ((
int)(
long)(
atGet(rootRingHdl, attribute,
INT_CMD, (
void*)def)));
163 #if (defined(HAVE_QSORT_R) && (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9))
164 static int cmp_c_ds(
void *
R,
const void *p1,
const void *p2){
165 #elif (defined(HAVE_QSORT_R) && (defined _GNU_SOURCE || defined __GNU__ || defined __linux__))
166 static int cmp_c_ds(
const void *p1,
const void *p2,
void *
R){
174 const ring r = (
const ring)
R;
178 const poly a = *(
const poly*)p1;
179 const poly
b = *(
const poly*)p2;
212 for (
int v =
rVar(r);
v > 0;
v--)
277 memcpy(np->exp,
p->exp, r->ExpL_Size*
sizeof(
long));
288 poly
leadmonom(
const poly
p,
const ring r,
const bool bSetZeroComp)
333 newid->m[
i] =
p_Tail( id->m[
i], r );
344 const int sizeNew =
IDELEMS(
id);
346 #if ( (defined(HAVE_QSORT_R)) && (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9) )
347 #define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, r, cmp)
348 #elif ( (defined(HAVE_QSORT_R)) && (defined _GNU_SOURCE || defined __GNU__ || defined __linux__))
349 #define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, cmp, r)
351 #define qsort_my(m, s, ss, r, cmp) qsort(m, s, ss, cmp)
380 for( TCache::iterator it =
m_cache.begin(); it !=
m_cache.end(); it++ )
384 for(TP2PCache::iterator vit =
T.begin(); vit !=
T.end(); vit++ )
417 CReducersHash::const_iterator itr =
m_hash.find(
comp);
419 if ( itr ==
m_hash.end() )
424 const bool bIdealCase = (
comp == 0);
425 const bool bSyzCheck = syzChecker.
IsNonempty();
430 const int N =
rVar(r);
433 for(TReducers::const_iterator vit =
v.begin(); (vit !=
v.end()) && coprime; ++vit )
437 const poly
p = (*vit)->lt();
442 for(
int var =
N; var > 0; --var )
449 if( bSyzCheck && coprime )
465 return coprime? 3: 0;
481 unsigned long pp[4] = {0,0,0,0};
483 for(
int p =
IDELEMS(idTails) - 1;
p >= 0; --
p )
484 for( poly* tt = &(idTails->m[
p]); (*tt) !=
NULL; )
503 Print(
"(PP/ST: {c: %lu, C: %lu, P: %lu} + %lu)",
pp[1],
pp[2],
pp[3],
pp[0]);
535 Print(
"SchreyerSyzygyComputation Stats: (PP/ST: {c: %lu, C: %lu, P: %lu} + %lu, LOT: %lu, LCM: %lu, ST:%lu, LK: %lu {*: %lu})\n",
561 const ideal newid =
idInit(1, 0); newid->m[0] =
NULL;
578 const poly
p =
id->m[
j];
582 for (
int i =
j - 1;
i >= 0;
i--)
584 const poly
pp =
id->m[
i];
594 for (
int v =
rVar(r);
v > 0;
v--)
649 const ideal newid =
idInit(1, 1); newid->m[0] =
NULL;
667 const poly
p =
id->m[
j];
671 for (
int i =
j - 1;
i >= 0;
i--)
673 const poly
pp =
id->m[
i];
687 for (
int v =
rVar(r);
v > 0;
v--)
717 number
g =
n_Lcm( lc1, lc2, r->cf );
842 Print(
"\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::ComputeLeadingSyzygyTerms: t: %d, r: %d\n", r, t, r);
852 Print(
"\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::ComputeLeadingSyzygyTerms: dt: %d, dr: %d\n",
getRTimer(), t, r);
886 Print(
"\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SetUpTailTerms(): t: %d, r: %d\n", r, t, r);
896 Print(
"\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SetUpTailTerms(): dt: %d, dr: %d\n",
getRTimer(), t, r);
906 Print(
"\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SyzygyLift: t: %d, r: %d\n", r, t, r);
911 for(
int k =
size - 1;
k >= 0; --
k )
964 Print(
"\n%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SyzygyLift: dt: %d, dr: %d\n",
getRTimer(), t, r);
1025 const int rr =
p_GetComp(syz_lead, r) - 1;
1157 TCache::iterator top_itr =
m_cache.find(tail);
1159 if ( top_itr !=
m_cache.end() )
1161 assume( top_itr->first == tail );
1165 TP2PCache::iterator itr =
T.find(multiplier);
1167 if( itr !=
T.end() )
1171 if( itr->second ==
NULL )
1174 poly
p =
p_Copy(itr->second, r);
1187 Print(
"\"recale\": \"%s\", ",
s);
1212 T.insert( TP2PCache::value_type(
myp_Head(multiplier, (
p==
NULL), r),
p) );
1228 T.insert( TP2PCache::value_type(
myp_Head(multiplier, (
p==
NULL), r),
p) );
1230 m_cache.insert( TCache::value_type(tail,
T) );
1389 poly product =
pp_Mult_mm(multiplier, term4reduction, r);
1428 PrintS(
"\", \"children\": [");
1443 OPT__DEBUG(
atGetInt(rootRingHdl,
"DEBUG", 0) ),
1444 OPT__LEAD2SYZ(
atGetInt(rootRingHdl,
"LEAD2SYZ", 0) ),
1445 OPT__TAILREDSYZ(
atGetInt(rootRingHdl,
"TAILREDSYZ", 1) ),
1446 OPT__HYBRIDNF(
atGetInt(rootRingHdl,
"HYBRIDNF", 0) ),
1447 OPT__IGNORETAILS(
atGetInt(rootRingHdl,
"IGNORETAILS", 0) ),
1448 OPT__SYZNUMBER(
atGetInt(rootRingHdl,
"SYZNUMBER", 0) ),
1449 OPT__TREEOUTPUT(
atGetInt(rootRingHdl,
"TREEOUTPUT", 0) ),
1450 OPT__SYZCHECK(
atGetInt(rootRingHdl,
"SYZCHECK", 0) ),
1452 OPT__NOCACHING(
atGetInt(rootRingHdl,
"NOCACHING", 0) ),
1453 m_rBaseRing( rootRingHdl->data.uring )
1472 for( CReducersHash::const_iterator it =
m_hash.begin(); it !=
m_hash.end(); it++ )
1475 for(TReducers::const_iterator vit =
v.begin(); vit !=
v.end(); vit++ )
1496 const poly a = L->m[
k];
1507 m_L(const_cast<ideal>(L)),
1518 int i=r->VarL_Size - 1;
1519 unsigned long divmask = r->divmask;
1520 unsigned long la, lb;
1522 if (r->VarL_LowIndex >= 0)
1524 i += r->VarL_LowIndex;
1528 lb =
b->exp[
i] + c->exp[
i];
1530 (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
1537 while (
i>=r->VarL_LowIndex);
1543 la = a->exp[r->VarL_Offset[
i]];
1544 lb =
b->exp[r->VarL_Offset[
i]] + c->exp[r->VarL_Offset[
i]];
1546 (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
1565 return ( L->m[
label()] ==
lt() );
1607 if (
sev() & not_sev)
1625 CReducerFinder::CReducersHash::const_iterator
m_itr;
1673 return *(*m_current);
1733 CReducerFinder::CReducersHash::const_iterator
m_itr;
1787 return *(*m_current);
1844 if (syzterm !=
NULL)
1875 if (syzterm !=
NULL && (
k == c))
1935 if (syzterm !=
NULL)
1956 if (syzterm !=
NULL && (
k == c))
2079 for(
int k =
l - 1;
k >= 0;
k-- )
2083 for (
unsigned int j =
m_N;
j > 0;
j--)
2102 for (
unsigned int j =
m_N;
j > 0;
j--)
void * atGet(idhdl root, const char *name, int t, void *defaultReturnValue)
const CanonicalForm CFMap CFMap & N
const unsigned long m_not_sev
const CLeadingTerm & Current() const
CReducerFinder::CReducersHash::const_iterator m_itr
CDivisorEnumerator2(const CReducerFinder &self, const poly m, const poly t)
CReducerFinder::TReducers::const_iterator m_finish
const CReducerFinder & m_reds
CReducerFinder::TReducers::const_iterator m_current
CReducerFinder::TReducers::const_iterator m_finish
const unsigned long m_not_sev
CDivisorEnumerator(const CReducerFinder &self, const poly product)
const CReducerFinder & m_reds
const CLeadingTerm & Current() const
CReducerFinder::CReducersHash::const_iterator m_itr
CReducerFinder::TReducers::const_iterator m_current
const unsigned int m_N
number of ring variables
bool Check(const poly m) const
CLCM(const ideal &L, const SchreyerSyzygyComputationFlags &flags)
bool DivisibilityCheck(const poly multiplier, const poly t, const unsigned long not_sev, const ring r) const
as DivisibilityCheck(multiplier * t, ...) for monomial 'm' and a module term 't'
bool CheckLT(const ideal &L) const
unsigned int label() const
unsigned long sev() const
CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags &flags)
goes over all leading terms
poly FindReducer(const poly multiplier, const poly monom, const poly syzterm, const CReducerFinder &checker) const
std::vector< const CLeadingTerm * > TReducers
void Initialize(const ideal L)
int PreProcessTerm(const poly t, CReducerFinder &syzChecker) const
is the term to be "preprocessed" as lower order term or lead to only reducible syzygies....
bool IsDivisible(const poly q) const
void putBucket(const Bucket &bt, const bool replace=false)
static Bucket _CreateBucket(const ring r)
inital allocation for new buckets
static void _DestroyBucket(Bucket &bt)
we only expect empty buckets to be left at the end for destructor bt will be set to NULL
void Add(poly p)
adds p to the internal bucket destroys p
void Add(poly p, const int l)
adds p to the internal bucket destroys p, l == length(p)
SBucketFactory::Bucket Bucket
SBucketWrapper(const ring r, SBucketFactory &factory)
SBucketFactory & m_factory
const CLCM m_lcm
Bitmask for variables occuring in leading terms.
poly ComputeImage(poly multiplier, const int tail) const
low level computation...
void CleanUp()
Clean up all the accumulated data.
const ideal m_idLeads
input leading terms
kBucket_pt m_spoly_bucket
for S-Polynomial reductions
void SetUpTailTerms()
Convert the given ideal of tails into the internal representation (with reducers!) Preprocess m_idTai...
ideal Compute1LeadingSyzygyTerms()
just leading terms
poly TraverseNF(const poly syz_lead, const poly syz_2=NULL) const
unsigned long m_stat[9]
Statistics: 0..3: as in SetUpTailTerms()::PreProcessTerm() // TODO!!?? 4: number of terms discarded d...
ideal m_syzTails
output (syzygy) tails
void ComputeSyzygy()
The main driver function: computes.
void PrintStats() const
print statistics about the used heuristics
poly TraverseTail(poly multiplier, const int tail) const
High level caching function!!!
const ideal m_idTails
input tails
ideal Compute2LeadingSyzygyTerms()
leading + second terms
void ComputeLeadingSyzygyTerms(bool bComputeSecondTerms=true)
Computes Syz(leads) or only LEAD of it. The result is stored into m_syzLeads.
poly SchreyerSyzygyNF(const poly syz_lead, poly syz_2=NULL) const
Main HybridNF == 1: poly reduce + LOT + LCM?
const CReducerFinder m_div
Divisor finder.
ideal m_syzLeads
output (syzygy) leading terms (+2nd terms?)
SBucketFactory m_sum_bucket_factory
used for simple summing up
poly ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const
TODO: save shortcut (syz: |-.->) LM(m) * "t" -> ? ???
ideal m_LS
leading syzygy terms used for reducing syzygy tails
CReducerFinder m_checker
for checking tail-terms and makeing them irreducible (wrt m_LS!)
Coefficient rings, fields and other domains suitable for Singular polynomials.
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_Copy(number n, const coeffs r)
return a copy of 'n'
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_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
static FORCE_INLINE number n_Lcm(number a, number b, const coeffs r)
in Z: return the lcm of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ,...
static FORCE_INLINE void n_Write(number n, const coeffs r, const BOOLEAN bShortOut=TRUE)
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff 'a' and 'b' represent the same number; they may have different representations.
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
const CanonicalForm int s
const Variable & v
< [in] a sqrfree bivariate poly
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
void kBucketDestroy(kBucket_pt *bucket_pt)
poly kBucketExtractLm(kBucket_pt bucket)
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
void kBucket_Plus_mm_Mult_pp(kBucket_pt bucket, poly m, poly p, int l)
Bpoly == Bpoly + m*p; where m is a monom Does not destroy p and m assume (l <= 0 || pLength(p) == l)
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
#define p_SetCoeff0(p, n, r)
#define p_LmCheckPolyRing1(p, r)
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
#define p_SetRingOfLm(p, r)
#define omTypeAllocBin(type, addr, bin)
#define SI_RESTORE_OPT1(A)
BOOLEAN p_DebugLmDivisibleByNoComp(poly a, poly b, ring r)
static BOOLEAN p_ExpVectorEqual(poly p1, poly p2, const ring r1, const ring r2)
unsigned long p_GetShortExpVector(const poly p, const ring r)
static void p_ExpVectorSum(poly pr, poly p1, poly p2, const ring r)
static poly p_Add_q(poly p, poly q, const ring r)
static void p_LmDelete(poly p, const ring r)
static poly p_LmInit(poly p, const ring r)
#define p_LmEqual(p1, p2, r)
static poly pp_Mult_mm(poly p, poly m, const ring r)
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
static void p_Setm(poly p, const 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 BOOLEAN p_LmIsConstant(const poly p, const ring r)
static poly p_New(const ring, omBin bin)
static BOOLEAN p_LmShortDivisibleByNoComp(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
static poly p_Mult_nn(poly p, number n, const ring r)
static void p_Delete(poly *p, const ring r)
static unsigned pLength(poly a)
static poly pp_Mult_qq(poly p, poly q, const ring r)
static poly p_Mult_mm(poly p, poly m, const ring r)
static void p_LmFree(poly p, ring)
static poly p_Init(const ring r, omBin bin)
static poly p_LmDeleteAndNext(poly p, const ring r)
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)
void StringSetS(const char *st)
void PrintS(const char *s)
static BOOLEAN rField_is_Ring(const ring r)
static short rVar(const ring r)
#define rVar(r) (r->N)
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
void sBucketDestroy(sBucket_pt *bucket)
sBucket_pt sBucketCreate(const ring r)
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
int status int void size_t count int const void size_t count const char int flags
ideal idInit(int idsize, int rank)
initialise an ideal / module
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void id_DelDiv(ideal id, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*L...
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define FROM_NAMESPACE(a, s)
Computation attribute storage.
SchreyerSyzygyComputationFlags(idhdl rootRingHdl)
const int OPT__HYBRIDNF
Use the usual NF's S-poly reduction while dropping lower order terms 2 means - smart selection!
const ring m_rBaseRing
global base ring
const int OPT__TREEOUTPUT
output lifting tree
const int OPT__SYZCHECK
CheckSyzygyProperty: TODO.
const int OPT__NOCACHING
no caching/stores/lookups
int OPT__SYZNUMBER
Syzygy level (within a resolution)
const bool OPT__PROT
TEST_OPT_PROT.
const int OPT__TAILREDSYZ
Reduce syzygy tails wrt the leading syzygy terms.
const int OPT__IGNORETAILS
ignore tails and compute the pure Schreyer frame