Loading...
Searching...
No Matches
syz4.cc File Reference
`#include "kernel/GBEngine/syz.h"`
`#include "coeffs/numbers.h"`
`#include "kernel/polys.h"`
`#include "kernel/ideals.h"`
`#include <vector>`
`#include <map>`

Go to the source code of this file.

## Data Structures

struct | lt_struct
struct | cache_compare

## Macros

#define | insert_first_term(r, p, q, R)

## Typedefs

typedef std::map< poly, poly, cache_compare > | cache_term
typedef poly | syzHeadFunction(ideal, int, int)
typedef ideal | syzM_i_Function(ideal, int, syzHeadFunction)

## Functions

static void | update_variables (std::vector< bool > &variables, const ideal L)
static bool | check_variables (const std::vector< bool > &variables, const poly m)
static void | initialize_hash (lt_struct **C, const ideal L)
static poly | find_reducer (const poly multiplier, const poly t, const lt_struct *const *const hash_previous_module)
static poly | traverse_tail (const poly multiplier, const int comp, const ideal previous_module, const std::vector< bool > &variables, const lt_struct *const *const hash_previous_module)
static poly | compute_image (const poly multiplier, const int comp, const ideal previous_module, const std::vector< bool > &variables, const lt_struct *const *const hash_previous_module, const bool use_cache)
static poly | reduce_term (const poly multiplier, const poly term, const ideal previous_module, const std::vector< bool > &variables, const lt_struct *const *const hash_previous_module, const bool use_cache)
static void | initialize_cache (const int size)
static void | delete_cache (const int size)
static void | insert_into_cache_term (cache_term *T, const poly multiplier, const poly p)
static poly | get_from_cache_term (const cache_term::const_iterator itr, const poly multiplier)
static poly | lift_ext_LT (const poly a, const ideal previous_module, const std::vector< bool > &variables, const lt_struct *const *const hash_previous_module, const bool use_cache)
static poly | syzHeadFrame (const ideal G, const int i, const int j)
static poly | syzHeadExtFrame (const ideal G, const int i, const int j)
static ideal | syzM_i_unsorted (const ideal G, const int i, syzHeadFunction *syzHead)
static ideal | syzM_i_sorted (const ideal G, const int i, syzHeadFunction *syzHead)
static ideal | idConcat (const ideal *M, const int size, const int rank)
static int | compare_comp (const poly p_a, const poly p_b)
static int | compare_deg (const poly p_a, const poly p_b)
static int | compare_lex (const poly p_a, const poly p_b)
static int | compare_Mi (const void *a, const void *b)
static ideal | computeFrame (const ideal G, syzM_i_Function syzM_i, syzHeadFunction *syzHead)
static void | computeLiftings (const resolvente res, const int index, const std::vector< bool > &variables, const bool use_cache)
static bool | contains_unused_variable (const poly m, const std::vector< bool > &variables)
static void | delete_variables (resolvente res, const int index, const std::vector< bool > &variables)
static void | delete_tails (resolvente res, const int index)
static int | computeResolution_iteration (resolvente res, const int max_index, syzHeadFunction *syzHead, const bool do_lifting, const bool single_module, const bool use_cache, const bool use_tensor_trick, std::vector< bool > &variables)
static int | computeResolution (resolvente res, const int max_index, syzHeadFunction *syzHead, const bool do_lifting, const bool single_module, const bool use_cache, const bool use_tensor_trick)
static void | set_options (syzHeadFunction **syzHead_ptr, bool *do_lifting_ptr, bool *single_module_ptr, const char *method)
static void | insert_ext_induced_LTs (const resolvente res, const int length, const bool single_module)
syStrategy | syFrank (const ideal arg, const int length, const char *method, const bool use_cache, const bool use_tensor_trick)

## Variables

STATIC_VAR cache_term * | Cache

## Data Structure Documentation

## lt_struct

struct lt_struct

Definition at line 74 of file syz4.cc.

Data Fields
unsigned long | comp |
poly | lt |
unsigned long | sev |

## Macro Definition Documentation

## insert_first_term

#define insert_first_term | ( |  | r,
|  |  | p,
|  |  | q,
|  |  | R )

Value:
do \
{ \
p = r; \
q = p->next; \
if (q != NULL && p_LmCmp(p, q, R) != 1) { \
while (q->next != NULL && p_LmCmp(p, q->next, R) == -1) { \
pIter(q); \
} \
r = p->next; \
p->next = q->next; \
q->next = p; \
} \
} \
while (0)
p
int p
Definition cfModGcd.cc:4086
NULL
#define NULL
Definition omList.c:12
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1601
R
#define R
Definition sirandom.c:27

Definition at line 738 of file syz4.cc.

#define insert_first_term(r, p, q, R) \
do \
{ \
p = r; \
q = p->next; \
if (q != NULL && p_LmCmp(p, q, R) != 1) { \
while (q->next != NULL && p_LmCmp(p, q->next, R) == -1) { \
pIter(q); \
} \
r = p->next; \
p->next = q->next; \
q->next = p; \
} \
} \
while (0)

## Typedef Documentation

## cache_term

typedef std::map<poly, poly, cache_compare> cache_term

Definition at line 228 of file syz4.cc.

## syzHeadFunction

typedef poly syzHeadFunction(ideal, int, int)

Definition at line 321 of file syz4.cc.

## syzM_i_Function

typedef ideal syzM_i_Function(ideal, int, syzHeadFunction)

Definition at line 377 of file syz4.cc.

## Function Documentation

## check_variables()

bool check_variables | ( | const std::vector< bool > & | variables,
|  | const poly | m )

inline static

Definition at line 49 of file syz4.cc.

{
const ring R = currRing;
// variables[R->N] is true iff index == 1, that is, for the first step in
// the resolution
if (UNLIKELY(variables[R->N]))
{
return true;
}
for (int j = R->N; j > 0; j--)
{
if (UNLIKELY(variables[j-1] && p_GetExp(m, j, R) > 0))
{
return true;
}
}
return false;
}
UNLIKELY
#define UNLIKELY(X)
Definition auxiliary.h:405
m
int m
Definition cfEzgcd.cc:128
j
int j
Definition facHensel.cc:110
variables
STATIC_VAR int variables
Definition interpolation.cc:87
p_GetExp
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition p_polys.h:471
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13

## compare_comp()

int compare_comp | ( | const poly | p_a,
|  | const poly | p_b )

static

Definition at line 471 of file syz4.cc.

{
const ring r = currRing;
long comp_a = __p_GetComp(p_a, r);
long comp_b = __p_GetComp(p_b, r);
return (comp_a > comp_b) - (comp_a < comp_b);
}
p_a
static ideal p_a(ideal h)
Definition cohomo.cc:1351
p_b
static ideal p_b(ideal h, poly a)
Definition cohomo.cc:1445
__p_GetComp
#define __p_GetComp(p, r)
Definition monomials.h:63

## compare_deg()

int compare_deg | ( | const poly | p_a,
|  | const poly | p_b )

static

Definition at line 479 of file syz4.cc.

{
const ring r = currRing;
long deg_a = p_Deg(p_a, r);
long deg_b = p_Deg(p_b, r);
return (deg_a > deg_b) - (deg_a < deg_b);
}
p_Deg
long p_Deg(poly a, const ring r)
Definition p_polys.cc:586

## compare_lex()

int compare_lex | ( | const poly | p_a,
|  | const poly | p_b )

static

Definition at line 487 of file syz4.cc.

{
int cmp;
const ring r = currRing;
int exp_a[r->N+1];
int exp_b[r->N+1];
p_GetExpV(p_a, exp_a, r);
p_GetExpV(p_b, exp_b, r);
for (int i = r->N; i > 0; i--)
{
cmp = (exp_a[i] > exp_b[i]) - (exp_a[i] < exp_b[i]);
if (cmp != 0)
{
return cmp;
}
}
return 0;
}
i
int i
Definition cfEzgcd.cc:132
p_GetExpV
static void p_GetExpV(poly p, int *ev, const ring r)
Definition p_polys.h:1541

## compare_Mi()

int compare_Mi | ( | const void * | a,
|  | const void * | b )

static

Definition at line 506 of file syz4.cc.

{
poly p_a = *((poly *)a);
poly p_b = *((poly *)b);
int cmp;
if ((cmp = compare_comp(p_a, p_b))
|| (cmp = compare_deg(p_a, p_b))
|| (cmp = compare_lex(p_a, p_b)))
{
return cmp;
}
return 0;
}
b
CanonicalForm b
Definition cfModGcd.cc:4111
compare_deg
static int compare_deg(const poly p_a, const poly p_b)
Definition syz4.cc:479
compare_comp
static int compare_comp(const poly p_a, const poly p_b)
Definition syz4.cc:471
compare_lex
static int compare_lex(const poly p_a, const poly p_b)
Definition syz4.cc:487

## compute_image()

poly compute_image | ( | const poly | multiplier,
|  | const int | comp,
|  | const ideal | previous_module,
|  | const std::vector< bool > & | variables,
|  | const lt_struct *const *const | hash_previous_module,
|  | const bool | use_cache )

static

Definition at line 192 of file syz4.cc.

{
const poly tail = previous_module->m[comp]->next;
if (UNLIKELY(tail == NULL) || !check_variables(variables, multiplier))
{
return NULL;
}
sBucket_pt sum = sBucketCreate(currRing);
for (poly p = tail; p != NULL; p = pNext(p))
{
const poly rt = reduce_term(multiplier, p, previous_module, variables,
hash_previous_module, use_cache);
sBucket_Add_p(sum, rt, pLength(rt));
}
poly s;
int l;
sBucketClearAdd(sum, &s, &l);
sBucketDestroy(&sum);
return s;
}
l
int l
Definition cfEzgcd.cc:100
s
const CanonicalForm int s
Definition facAbsFact.cc:51
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition facSparseHensel.h:25
pNext
#define pNext(p)
Definition monomials.h:36
pLength
static int pLength(poly a)
Definition p_polys.h:190
sBucket_Add_p
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition sbuckets.cc:203
sBucketDestroy
void sBucketDestroy(sBucket_pt *bucket)
Definition sbuckets.cc:103
sBucketCreate
sBucket_pt sBucketCreate(const ring r)
Definition sbuckets.cc:96
sBucketClearAdd
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition sbuckets.cc:275
sBucket_pt
sBucket * sBucket_pt
Definition sbuckets.h:16
check_variables
static bool check_variables(const std::vector< bool > &variables, const poly m)
Definition syz4.cc:49
reduce_term
static poly reduce_term(const poly multiplier, const poly term, const ideal previous_module, const std::vector< bool > &variables, const lt_struct *const *const hash_previous_module, const bool use_cache)
Definition syz4.cc:164

## computeFrame()

ideal computeFrame | ( | const ideal | G,
|  | syzM_i_Function | syzM_i,
|  | syzHeadFunction * | syzHead )

static

Definition at line 524 of file syz4.cc.

{
ideal *M = (ideal *)omalloc((G->ncols-1)*sizeof(ideal));
for (int i = G->ncols-2; i >= 0; i--)
{
M[i] = syzM_i(G, i+1, syzHead);
}
ideal frame = idConcat(M, G->ncols-1, G->ncols);
for (int i = G->ncols-2; i >= 0; i--)
{
if (M[i] != NULL)
{
omFreeSize(M[i]->m, M[i]->ncols*sizeof(poly));
omFreeBin(M[i], sip_sideal_bin);
}
}
omfree(M);
qsort(frame->m, frame->ncols, sizeof(poly), compare_Mi);
return frame;
}
ncols
int int ncols
Definition cf_linsys.cc:32
G
STATIC_VAR TreeM * G
Definition janet.cc:31
omfree
#define omfree(addr)
Definition omAllocDecl.h:237
omFreeSize
#define omFreeSize(addr, size)
Definition omAllocDecl.h:260
omalloc
#define omalloc(size)
Definition omAllocDecl.h:228
omFreeBin
#define omFreeBin(addr, bin)
Definition omAllocDecl.h:259
sip_sideal_bin
VAR omBin sip_sideal_bin
Definition simpleideals.cc:27
M
#define M
Definition sirandom.c:25
idConcat
static ideal idConcat(const ideal *M, const int size, const int rank)
Definition syz4.cc:444
compare_Mi
static int compare_Mi(const void *a, const void *b)
Definition syz4.cc:506

## computeLiftings()

void computeLiftings | ( | const resolvente | res,
|  | const int | index,
|  | const std::vector< bool > & | variables,
|  | const bool | use_cache )

static

Definition at line 549 of file syz4.cc.

{
if (use_cache)
{
initialize_cache(res[index-1]->ncols);
}
lt_struct **hash_previous_module
= (lt_struct **)omAlloc((res[index-1]->rank+1)*sizeof(lt_struct *));
initialize_hash(hash_previous_module, res[index-1]);
for (int j = res[index]->ncols-1; j >= 0; j--)
{
res[index]->m[j]->next->next = lift_ext_LT(res[index]->m[j],
res[index-1], variables, hash_previous_module, use_cache);
}
for (int i = 0; i <= res[index-1]->rank; i++)
{
omfree(hash_previous_module[i]);
}
omFree(hash_previous_module);
if (use_cache)
{
delete_cache(res[index-1]->ncols);
}
}
res
CanonicalForm res
Definition facAbsFact.cc:60
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592
lift_ext_LT
static poly lift_ext_LT(const poly a, const ideal previous_module, const std::vector< bool > &variables, const lt_struct *const *const hash_previous_module, const bool use_cache)
Definition syz4.cc:297
initialize_hash
static void initialize_hash(lt_struct **C, const ideal L)
Definition syz4.cc:80
initialize_cache
static void initialize_cache(const int size)
Definition syz4.cc:232
delete_cache
static void delete_cache(const int size)
Definition syz4.cc:237
lt_struct
Definition syz4.cc:74

## computeResolution()

int computeResolution | ( | resolvente | res,
|  | const int | max_index,
|  | syzHeadFunction * | syzHead,
|  | const bool | do_lifting,
|  | const bool | single_module,
|  | const bool | use_cache,
|  | const bool | use_tensor_trick )

static

Definition at line 670 of file syz4.cc.

{
if (idIs0(res[0]))
{
return 1;
}
std::vector<bool> variables;
variables.resize(currRing->N+1, true);
if (do_lifting)
{
update_variables(variables, res[0]);
if (use_tensor_trick)
{
delete_variables(res, 0, variables);
}
}
int index = 0;
if (max_index > 0)
{
res[1] = computeFrame(res[0], syzM_i_unsorted, syzHead);
index = computeResolution_iteration(res, max_index, syzHead,
do_lifting, single_module, use_cache, use_tensor_trick,
variables);
}
variables.clear();
return index+1;
}
idIs0
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
Definition simpleideals.cc:960
update_variables
static void update_variables(std::vector< bool > &variables, const ideal L)
Definition syz4.cc:21
computeFrame
static ideal computeFrame(const ideal G, syzM_i_Function syzM_i, syzHeadFunction *syzHead)
Definition syz4.cc:524
computeResolution_iteration
static int computeResolution_iteration(resolvente res, const int max_index, syzHeadFunction *syzHead, const bool do_lifting, const bool single_module, const bool use_cache, const bool use_tensor_trick, std::vector< bool > &variables)
Definition syz4.cc:633
syzM_i_unsorted
static ideal syzM_i_unsorted(const ideal G, const int i, syzHeadFunction *syzHead)
Definition syz4.cc:384
delete_variables
static void delete_variables(resolvente res, const int index, const std::vector< bool > &variables)
Definition syz4.cc:596

## computeResolution_iteration()

int computeResolution_iteration | ( | resolvente | res,
|  | const int | max_index,
|  | syzHeadFunction * | syzHead,
|  | const bool | do_lifting,
|  | const bool | single_module,
|  | const bool | use_cache,
|  | const bool | use_tensor_trick,
|  | std::vector< bool > & | variables )

static

Definition at line 633 of file syz4.cc.

{
int index = 1;
while (!idIs0(res[index]))
{
if (do_lifting)
{
computeLiftings(res, index, variables, use_cache);
if (single_module)
{
delete_tails(res, index-1);
}
// we don't know if the input is a reduced SB:
if (index == 1)
{
variables[currRing->N] = false;
}
update_variables(variables, res[index]);
if (use_tensor_trick)
{
delete_variables(res, index, variables);
}
}
if (index >= max_index) { break; }
index++;
res[index] = computeFrame(res[index-1], syzM_i_sorted, syzHead);
}
return index;
}
syzM_i_sorted
static ideal syzM_i_sorted(const ideal G, const int i, syzHeadFunction *syzHead)
Definition syz4.cc:418
computeLiftings
static void computeLiftings(const resolvente res, const int index, const std::vector< bool > &variables, const bool use_cache)
Definition syz4.cc:549
delete_tails
static void delete_tails(resolvente res, const int index)
Definition syz4.cc:617

## contains_unused_variable()

bool contains_unused_variable | ( | const poly | m,
|  | const std::vector< bool > & | variables )

inline static

Definition at line 578 of file syz4.cc.

{
const ring R = currRing;
for (int j = R->N; j > 0; j--)
{
if (!variables[j-1] && p_GetExp(m, j, R) > 0)
{
return true;
}
}
return false;
}

## delete_cache()

void delete_cache | ( | const int | size | ) |

static

Definition at line 237 of file syz4.cc.

{
const ring r = currRing;
for (int i = 0; i < size; i++)
{
cache_term *T = &(Cache[i]);
for (cache_term::iterator itr = T->begin(); itr != T->end(); ++itr)
{
p_Delete(&(itr->second), r);
p_Delete(const_cast<poly*>(&(itr->first)), r);
}
T->clear();
}
delete[](Cache);
}
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
Cache
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition Cache.h:69
T
STATIC_VAR jList * T
Definition janet.cc:30
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
cache_term
std::map< poly, poly, cache_compare > cache_term
Definition syz4.cc:228

## delete_tails()

void delete_tails | ( | resolvente | res,
|  | const int | index )

static

Definition at line 617 of file syz4.cc.

{
const ring r = currRing;
for (int i = 0; i < res[index]->ncols; i++)
{
if (res[index]->m[i] != NULL)
{
p_Delete(&(res[index]->m[i]->next), r);
}
}
}
next
ListNode * next
Definition janet.h:31

## delete_variables()

void delete_variables | ( | resolvente | res,
|  | const int | index,
|  | const std::vector< bool > & | variables )

static

Definition at line 596 of file syz4.cc.

{
for (int i = 0; i < res[index]->ncols; i++)
{
poly p_iter = res[index]->m[i]->next;
if (p_iter != NULL)
{
while (p_iter->next != NULL)
{
if (contains_unused_variable(p_iter->next, variables))
{
pLmDelete(&p_iter->next);
} else {
pIter(p_iter);
}
}
}
}
}
pIter
#define pIter(p)
Definition monomials.h:37
pLmDelete
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition polys.h:77
contains_unused_variable
static bool contains_unused_variable(const poly m, const std::vector< bool > &variables)
Definition syz4.cc:578

## find_reducer()

poly find_reducer | ( | const poly | multiplier,
|  | const poly | t,
|  | const lt_struct *const *const | hash_previous_module )

static

Definition at line 118 of file syz4.cc.

{
const ring r = currRing;
const lt_struct *v = hash_previous_module[__p_GetComp(t, r)];
unsigned long count = v[0].comp;
if (UNLIKELY(count == 1))
{
return NULL;
}
const poly q = p_New(r);
pNext(q) = NULL;
p_MemSum_LengthGeneral(q->exp, multiplier->exp, t->exp, r->ExpL_Size);
const unsigned long q_not_sev = ~p_GetShortExpVector(q, r);
for(unsigned long i = 1; i < count; i++)
{
if (LIKELY(v[i].sev & q_not_sev)
|| UNLIKELY(!(_p_LmDivisibleByNoComp(v[i].lt, q, r))))
{
continue;
}
p_MemAdd_NegWeightAdjust(q, r);
p_ExpVectorDiff(q, q, v[i].lt, r);
p_SetComp(q, v[i].comp, r);
p_Setm(q, r);
number n = n_Div(p_GetCoeff(multiplier, r), p_GetCoeff(v[i].lt, r), r->cf);
n_InpMult(n, p_GetCoeff(t, r), r->cf);
p_SetCoeff0(q, n_InpNeg(n, r->cf), r);
return q;
}
p_LmFree(q, r);
return NULL;
}
LIKELY
#define LIKELY(X)
Definition auxiliary.h:404
n_InpNeg
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)
Definition coeffs.h:560
n_Div
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...
Definition coeffs.h:618
n_InpMult
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of 'a' and 'b'; replacement of 'a' by the product a*b
Definition coeffs.h:644
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
p_SetCoeff0
#define p_SetCoeff0(p, n, r)
Definition monomials.h:60
p_GetCoeff
#define p_GetCoeff(p, r)
Definition monomials.h:50
p_MemSum_LengthGeneral
#define p_MemSum_LengthGeneral(r, s1, s2, length)
Definition p_MemAdd.h:86
p_GetShortExpVector
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition p_polys.cc:4934
p_MemAdd_NegWeightAdjust
static void p_MemAdd_NegWeightAdjust(poly p, const ring r)
Definition p_polys.h:1313
p_ExpVectorDiff
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition p_polys.h:1495
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition p_polys.h:249
p_Setm
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
p_New
static poly p_New(const ring, omBin bin)
Definition p_polys.h:666
_p_LmDivisibleByNoComp
static BOOLEAN _p_LmDivisibleByNoComp(poly a, poly b, const ring r)
return: FALSE, if there exists i, such that a->exp[i] > b->exp[i] TRUE, otherwise (1) Consider long v...
Definition p_polys.h:1786
p_LmFree
static void p_LmFree(poly p, ring)
Definition p_polys.h:685
count
int status int void size_t count
Definition si_signals.h:69

## get_from_cache_term()

poly get_from_cache_term | ( | const cache_term::const_iterator | itr,
|  | const poly | multiplier )

static

Definition at line 260 of file syz4.cc.

{
if (LIKELY(itr->second == NULL))
{
return NULL;
}
const ring r = currRing;
poly p = p_Copy(itr->second, r);
if (LIKELY(!n_Equal(pGetCoeff(multiplier), pGetCoeff(itr->first), r->cf)))
{
number n = n_Div(pGetCoeff(multiplier), pGetCoeff(itr->first), r->cf);
p = p_Mult_nn(p, n, r);
n_Delete(&n, r->cf);
}
return p;
}
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
n_Equal
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.
Definition coeffs.h:466
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition monomials.h:44
p_Mult_nn
static poly p_Mult_nn(poly p, number n, const ring r)
Definition p_polys.h:960
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:848

## idConcat()

ideal idConcat | ( | const ideal * | M,
|  | const int | size,
|  | const int | rank )

static

Definition at line 444 of file syz4.cc.

{
int ncols = 0;
for (int i = size-1; i >= 0; i--)
{
if (M[i] != NULL)
{
ncols += M[i]->ncols;
}
}
if (ncols == 0) return idInit(1, rank);
ideal result = idInit(ncols, rank);
int k = ncols-1;
for (int i = size-1; i >= 0; i--)
{
if (M[i] != NULL)
{
for (int j = M[i]->ncols-1; j >= 0; j--)
{
result->m[k] = M[i]->m[j];
k--;
}
}
}
return result;
}
k
int k
Definition cfEzgcd.cc:99
result
return result
Definition facAbsBiFact.cc:76
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35

## initialize_cache()

void initialize_cache | ( | const int | size | ) |

static

Definition at line 232 of file syz4.cc.

{
Cache = new cache_term[size];
}

## initialize_hash()

void initialize_hash | ( | lt_struct ** | C,
|  | const ideal | L )

static

Definition at line 80 of file syz4.cc.

{
const ring R = currRing;
const unsigned long n_elems = L->ncols;
unsigned int *count
= (unsigned int *)omAlloc0((L->rank+1)*sizeof(unsigned int));
unsigned long k = 0;
while (k < n_elems)
{
count[__p_GetComp(L->m[k], R)]++;
k++;
}
for (int i = 0; i <= L->rank; i++)
{
// do ++count[i] and use C[i][0].comp to save count[i]
C[i] = (lt_struct *)omalloc0((++count[i])*sizeof(lt_struct));
C[i][0].comp = count[i];
}
k = n_elems;
// the order of the elements in each C[i] matters if check_variables() is
// to be used
while (k > 0)
{
const poly a = L->m[k-1];
const unsigned long comp = __p_GetComp(a, R);
C[comp][--count[comp]]
= (lt_struct){a, p_GetShortExpVector(a, R), k};
k--;
}
omFree(count);
}
omalloc0
#define omalloc0(size)
Definition omAllocDecl.h:229
omAlloc0
#define omAlloc0(size)
Definition omAllocDecl.h:211
lt_struct::comp
unsigned long comp
Definition syz4.cc:77

## insert_ext_induced_LTs()

void insert_ext_induced_LTs | ( | const resolvente | res,
|  | const int | length,
|  | const bool | single_module )

static

Definition at line 758 of file syz4.cc.

{
const ring R = currRing;
poly p, q;
int index = (single_module ? length-1 : 1);
while (index < length && !idIs0(res[index]))
{
for (int j = res[index]->ncols-1; j >= 0; j--)
{
insert_first_term(res[index]->m[j]->next, p, q, R);
insert_first_term(res[index]->m[j], p, q, R);
}
index++;
}
}
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
insert_first_term
#define insert_first_term(r, p, q, R)
Definition syz4.cc:738

## insert_into_cache_term()

void insert_into_cache_term | ( | cache_term * | T,
|  | const poly | multiplier,
|  | const poly | p )

static

Definition at line 253 of file syz4.cc.

{
const ring r = currRing;
T->insert(cache_term::value_type(p_Head(multiplier, r), p_Copy(p, r)));
}
p_Head
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition p_polys.h:862

## lift_ext_LT()

poly lift_ext_LT | ( | const poly | a,
|  | const ideal | previous_module,
|  | const std::vector< bool > & | variables,
|  | const lt_struct *const *const | hash_previous_module,
|  | const bool | use_cache )

static

Definition at line 297 of file syz4.cc.

{
const ring R = currRing;
// the leading term does not need to be cached
poly t1 = compute_image(a, __p_GetComp(a, R)-1, previous_module, variables,
hash_previous_module, use_cache);
poly t2;
if (use_cache)
{
t2 = traverse_tail(a->next, __p_GetComp(a->next, R)-1,
previous_module, variables, hash_previous_module);
} else {
t2 = compute_image(a->next, __p_GetComp(a->next, R)-1,
previous_module, variables, hash_previous_module, false);
}
t1 = p_Add_q(t1, t2, R);
return t1;
}
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938
traverse_tail
static poly traverse_tail(const poly multiplier, const int comp, const ideal previous_module, const std::vector< bool > &variables, const lt_struct *const *const hash_previous_module)
Definition syz4.cc:278
compute_image
static poly compute_image(const poly multiplier, const int comp, const ideal previous_module, const std::vector< bool > &variables, const lt_struct *const *const hash_previous_module, const bool use_cache)
Definition syz4.cc:192

## reduce_term()

poly reduce_term | ( | const poly | multiplier,
|  | const poly | term,
|  | const ideal | previous_module,
|  | const std::vector< bool > & | variables,
|  | const lt_struct *const *const | hash_previous_module,
|  | const bool | use_cache )

static

Definition at line 164 of file syz4.cc.

{
poly s = find_reducer(multiplier, term, hash_previous_module);
if (s == NULL)
{
return NULL;
}
const ring r = currRing;
const int c = __p_GetComp(s, r) - 1;
poly t;
if (use_cache)
{
t = traverse_tail(s, c, previous_module, variables,
hash_previous_module);
} else {
t = compute_image(s, c, previous_module, variables,
hash_previous_module, false);
}
return p_Add_q(s, t, r);
}
term
Definition int_poly.h:33
find_reducer
static poly find_reducer(const poly multiplier, const poly t, const lt_struct *const *const hash_previous_module)
Definition syz4.cc:118

## set_options()

void set_options | ( | syzHeadFunction ** | syzHead_ptr,
|  | bool * | do_lifting_ptr,
|  | bool * | single_module_ptr,
|  | const char * | method )

static

Definition at line 701 of file syz4.cc.

{
if (strcmp(method, "complete") == 0)
{ // default
*syzHead_ptr = syzHeadExtFrame;
*do_lifting_ptr = true;
*single_module_ptr = false;
}
else if (strcmp(method, "frame") == 0)
{
*syzHead_ptr = syzHeadFrame;
*do_lifting_ptr = false;
*single_module_ptr = false;
}
else if (strcmp(method, "extended frame") == 0)
{
*syzHead_ptr = syzHeadExtFrame;
*do_lifting_ptr = false;
*single_module_ptr = false;
}
else if (strcmp(method, "single module") == 0)
{
*syzHead_ptr = syzHeadExtFrame;
*do_lifting_ptr = true;
*single_module_ptr = true;
}
else { // "linear strand" (not yet implemented)
*syzHead_ptr = syzHeadExtFrame;
*do_lifting_ptr = true;
*single_module_ptr = false;
}
}
syzHeadExtFrame
static poly syzHeadExtFrame(const ideal G, const int i, const int j)
Definition syz4.cc:350
syzHeadFrame
static poly syzHeadFrame(const ideal G, const int i, const int j)
Definition syz4.cc:326

## syFrank()

syStrategy syFrank | ( | const ideal | arg,
|  | const int | length,
|  | const char * | method,
|  | const bool | use_cache,
|  | const bool | use_tensor_trick )

Definition at line 792 of file syz4.cc.

{
syStrategy result = (syStrategy)omAlloc0(sizeof(ssyStrategy));
resolvente res = (resolvente)omAlloc0((length+1)*sizeof(ideal));
if (strcmp(method, "frame") != 0)
{
res[0] = id_Copy(arg, currRing);
}
else
{
res[0] = id_Head(arg, currRing);
}
syzHeadFunction *syzHead;
bool do_lifting;
bool single_module;
set_options(&syzHead, &do_lifting, &single_module, method);
int new_length = computeResolution(res, length-1, syzHead, do_lifting,
single_module, use_cache, use_tensor_trick);
if (new_length < length)
{
res = (resolvente)omReallocSize(res, (length+1)*sizeof(ideal),
(new_length+1)*sizeof(ideal));
}
if (strcmp(method, "frame") != 0)
{
insert_ext_induced_LTs(res, new_length, single_module);
}
result->fullres = res;
result->length = new_length;
result->list_length = new_length;
return result;
}
id_Copy
ideal id_Copy(ideal h1, const ring r)
copy an ideal
Definition simpleideals.cc:542
resolvente
ideal * resolvente
Definition ideals.h:18
omReallocSize
#define omReallocSize(addr, o_size, size)
Definition omAllocDecl.h:220
id_Head
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
Definition simpleideals.cc:1483
set_options
static void set_options(syzHeadFunction **syzHead_ptr, bool *do_lifting_ptr, bool *single_module_ptr, const char *method)
Definition syz4.cc:701
computeResolution
static int computeResolution(resolvente res, const int max_index, syzHeadFunction *syzHead, const bool do_lifting, const bool single_module, const bool use_cache, const bool use_tensor_trick)
Definition syz4.cc:670
insert_ext_induced_LTs
static void insert_ext_induced_LTs(const resolvente res, const int length, const bool single_module)
Definition syz4.cc:758
syzHeadFunction
poly syzHeadFunction(ideal, int, int)
Definition syz4.cc:321
syStrategy
ssyStrategy * syStrategy
Definition syz.h:36
ssyStrategy
Definition syz.h:37

## syzHeadExtFrame()

poly syzHeadExtFrame | ( | const ideal | G,
|  | const int | i,
|  | const int | j )

static

Definition at line 350 of file syz4.cc.

{
const ring r = currRing;
const poly f_i = G->m[i];
const poly f_j = G->m[j];
poly head = p_Init(r);
pSetCoeff0(head, n_Init(1, r->cf));
poly head_ext = p_Init(r);
pSetCoeff0(head_ext, n_InpNeg(n_Div(pGetCoeff(f_i), pGetCoeff(f_j), r->cf),
r->cf));
long exp_i, exp_j, lcm;
for (int k = (int)r->N; k > 0; k--)
{
exp_i = p_GetExp(f_i, k, r);
exp_j = p_GetExp(f_j, k, r);
lcm = si_max(exp_i, exp_j);
p_SetExp(head, k, lcm-exp_i, r);
p_SetExp(head_ext, k, lcm-exp_j, r);
}
p_SetComp(head, i+1, r);
p_Setm(head, r);
p_SetComp(head_ext, j+1, r);
p_Setm(head_ext, r);
head->next = head_ext;
return head;
}
si_max
static int si_max(const int a, const int b)
Definition auxiliary.h:125
head
CanonicalForm head(const CanonicalForm &f)
Definition canonicalform.h:360
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition coeffs.h:541
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:709
pSetCoeff0
#define pSetCoeff0(p, n)
Definition monomials.h:59
p_SetExp
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
Definition p_polys.h:490
p_Init
static poly p_Init(const ring r, omBin bin)
Definition p_polys.h:1341

## syzHeadFrame()

poly syzHeadFrame | ( | const ideal | G,
|  | const int | i,
|  | const int | j )

static

Definition at line 326 of file syz4.cc.

{
const ring r = currRing;
const poly f_i = G->m[i];
const poly f_j = G->m[j];
poly head = p_Init(r);
pSetCoeff0(head, n_Init(1, r->cf));
long exp_i, exp_j, lcm;
for (int k = (int)r->N; k > 0; k--)
{
exp_i = p_GetExp(f_i, k, r);
exp_j = p_GetExp(f_j, k, r);
lcm = si_max(exp_i, exp_j);
p_SetExp(head, k, lcm-exp_i, r);
}
p_SetComp(head, i+1, r);
p_Setm(head, r);
return head;
}

## syzM_i_sorted()

ideal syzM_i_sorted | ( | const ideal | G,
|  | const int | i,
|  | syzHeadFunction * | syzHead )

static

Definition at line 418 of file syz4.cc.

{
const ring r = currRing;
ideal M_i = NULL;
unsigned long comp = __p_GetComp(G->m[i], r);
int index = i-1;
while (__p_GetComp(G->m[index], r) == comp) index--;
index++;
int ncols = i-index;
if (ncols > 0)
{
M_i = idInit(ncols, G->ncols);
for (int j = ncols-1; j >= 0; j--)
{
M_i->m[j] = syzHead(G, i, j+index);
}
id_DelDiv(M_i, currRing);
idSkipZeroes(M_i);
}
return M_i;
}
id_DelDiv
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...
Definition simpleideals.cc:463
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition simpleideals.cc:201

## syzM_i_unsorted()

ideal syzM_i_unsorted | ( | const ideal | G,
|  | const int | i,
|  | syzHeadFunction * | syzHead )

static

Definition at line 384 of file syz4.cc.

{
const ring r = currRing;
ideal M_i = NULL;
unsigned long comp = __p_GetComp(G->m[i], r);
int ncols = 0;
for (int j = i-1; j >= 0; j--)
{
if (__p_GetComp(G->m[j], r) == comp) ncols++;
}
if (ncols > 0)
{
M_i = idInit(ncols, G->ncols);
int k = ncols-1;
for (int j = i-1; j >= 0; j--)
{
if (__p_GetComp(G->m[j], r) == comp)
{
M_i->m[k] = syzHead(G, i, j);
k--;
}
}
id_DelDiv(M_i, currRing);
idSkipZeroes(M_i);
}
return M_i;
}

## traverse_tail()

poly traverse_tail | ( | const poly | multiplier,
|  | const int | comp,
|  | const ideal | previous_module,
|  | const std::vector< bool > & | variables,
|  | const lt_struct *const *const | hash_previous_module )

static

Definition at line 278 of file syz4.cc.

{
cache_term *T = &(Cache[comp]);
cache_term::const_iterator itr = T->find(multiplier);
if (LIKELY(itr != T->end()))
{
return get_from_cache_term(itr, multiplier);
}
poly p = compute_image(multiplier, comp, previous_module, variables,
hash_previous_module, true);
insert_into_cache_term(T, multiplier, p);
return p;
}
get_from_cache_term
static poly get_from_cache_term(const cache_term::const_iterator itr, const poly multiplier)
Definition syz4.cc:260
insert_into_cache_term
static void insert_into_cache_term(cache_term *T, const poly multiplier, const poly p)
Definition syz4.cc:253

## update_variables()

void update_variables | ( | std::vector< bool > & | variables,
|  | const ideal | L )

static

Definition at line 21 of file syz4.cc.

{
const ring R = currRing;
const int l = L->ncols-1;
int k;
for (int j = R->N; j > 0; j--)
{
if (variables[j-1])
{
for (k = l; k >= 0; k--)
{
if (p_GetExp(L->m[k], j, R) > 0)
{
break;
}
}
if (k < 0)
{ // no break
variables[j-1] = false;
}
}
}
}

## Variable Documentation

## Cache

STATIC_VAR cache_term* Cache

Definition at line 230 of file syz4.cc.