My Project
Loading...
Searching...
No Matches
Data Structures | Macros | Typedefs | Functions | Variables
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_comparecache_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_termCache
 

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)
int p
Definition: cfModGcd.cc:4078
#define NULL
Definition: omList.c:12
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1578
#define R
Definition: sirandom.c:27

Definition at line 738 of file syz4.cc.

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()

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

Definition at line 49 of file syz4.cc.

51{
52 const ring R = currRing;
53 // variables[R->N] is true iff index == 1, that is, for the first step in
54 // the resolution
55 if (UNLIKELY(variables[R->N]))
56 {
57 return true;
58 }
59 for (int j = R->N; j > 0; j--)
60 {
61 if (UNLIKELY(variables[j-1] && p_GetExp(m, j, R) > 0))
62 {
63 return true;
64 }
65 }
66 return false;
67}
#define UNLIKELY(X)
Definition: auxiliary.h:404
int m
Definition: cfEzgcd.cc:128
int j
Definition: facHensel.cc:110
STATIC_VAR int variables
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:467
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13

◆ compare_comp()

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

Definition at line 471 of file syz4.cc.

472{
473 const ring r = currRing;
474 long comp_a = __p_GetComp(p_a, r);
475 long comp_b = __p_GetComp(p_b, r);
476 return (comp_a > comp_b) - (comp_a < comp_b);
477}
static ideal p_a(ideal h)
Definition: cohomo.cc:1335
static ideal p_b(ideal h, poly a)
Definition: cohomo.cc:1427
#define __p_GetComp(p, r)
Definition: monomials.h:63

◆ compare_deg()

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

Definition at line 479 of file syz4.cc.

480{
481 const ring r = currRing;
482 long deg_a = p_Deg(p_a, r);
483 long deg_b = p_Deg(p_b, r);
484 return (deg_a > deg_b) - (deg_a < deg_b);
485}
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:587

◆ compare_lex()

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

Definition at line 487 of file syz4.cc.

488{
489 int cmp;
490 const ring r = currRing;
491 int exp_a[r->N+1];
492 int exp_b[r->N+1];
493 p_GetExpV(p_a, exp_a, r);
494 p_GetExpV(p_b, exp_b, r);
495 for (int i = r->N; i > 0; i--)
496 {
497 cmp = (exp_a[i] > exp_b[i]) - (exp_a[i] < exp_b[i]);
498 if (cmp != 0)
499 {
500 return cmp;
501 }
502 }
503 return 0;
504}
int i
Definition: cfEzgcd.cc:132
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1518

◆ compare_Mi()

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

Definition at line 506 of file syz4.cc.

507{
508 poly p_a = *((poly *)a);
509 poly p_b = *((poly *)b);
510 int cmp;
511 if ((cmp = compare_comp(p_a, p_b))
512 || (cmp = compare_deg(p_a, p_b))
513 || (cmp = compare_lex(p_a, p_b)))
514 {
515 return cmp;
516 }
517 return 0;
518}
CanonicalForm b
Definition: cfModGcd.cc:4103
static int compare_deg(const poly p_a, const poly p_b)
Definition: syz4.cc:479
static int compare_comp(const poly p_a, const poly p_b)
Definition: syz4.cc:471
static int compare_lex(const poly p_a, const poly p_b)
Definition: syz4.cc:487

◆ 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 
)
static

Definition at line 192 of file syz4.cc.

196{
197 const poly tail = previous_module->m[comp]->next;
198 if (UNLIKELY(tail == NULL) || !check_variables(variables, multiplier))
199 {
200 return NULL;
201 }
203 for (poly p = tail; p != NULL; p = pNext(p))
204 {
205 const poly rt = reduce_term(multiplier, p, previous_module, variables,
206 hash_previous_module, use_cache);
207 sBucket_Add_p(sum, rt, pLength(rt));
208 }
209 poly s;
210 int l;
211 sBucketClearAdd(sum, &s, &l);
212 sBucketDestroy(&sum);
213 return s;
214}
int l
Definition: cfEzgcd.cc:100
const CanonicalForm int s
Definition: facAbsFact.cc:51
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
#define pNext(p)
Definition: monomials.h:36
static int pLength(poly a)
Definition: p_polys.h:188
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:203
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:103
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:96
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:275
static bool check_variables(const std::vector< bool > &variables, const poly m)
Definition: syz4.cc:49
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()

static ideal computeFrame ( const ideal  G,
syzM_i_Function  syzM_i,
syzHeadFunction syzHead 
)
static

Definition at line 524 of file syz4.cc.

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

◆ computeLiftings()

static 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.

551{
552 if (use_cache)
553 {
555 }
556 lt_struct **hash_previous_module
557 = (lt_struct **)omAlloc((res[index-1]->rank+1)*sizeof(lt_struct *));
558 initialize_hash(hash_previous_module, res[index-1]);
559 for (int j = res[index]->ncols-1; j >= 0; j--)
560 {
561 res[index]->m[j]->next->next = lift_ext_LT(res[index]->m[j],
562 res[index-1], variables, hash_previous_module, use_cache);
563 }
564 for (int i = 0; i <= res[index-1]->rank; i++)
565 {
566 omfree(hash_previous_module[i]);
567 }
568 omFree(hash_previous_module);
569 if (use_cache)
570 {
572 }
573}
CanonicalForm res
Definition: facAbsFact.cc:60
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
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
static void initialize_hash(lt_struct **C, const ideal L)
Definition: syz4.cc:80
static void initialize_cache(const int size)
Definition: syz4.cc:232
static void delete_cache(const int size)
Definition: syz4.cc:237

◆ 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 
)
static

Definition at line 670 of file syz4.cc.

674{
675 if (idIs0(res[0]))
676 {
677 return 1;
678 }
679 std::vector<bool> variables;
680 variables.resize(currRing->N+1, true);
681 if (do_lifting)
682 {
684 if (use_tensor_trick)
685 {
687 }
688 }
689 int index = 0;
690 if (max_index > 0)
691 {
692 res[1] = computeFrame(res[0], syzM_i_unsorted, syzHead);
693 index = computeResolution_iteration(res, max_index, syzHead,
694 do_lifting, single_module, use_cache, use_tensor_trick,
695 variables);
696 }
697 variables.clear();
698 return index+1;
699}
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static void update_variables(std::vector< bool > &variables, const ideal L)
Definition: syz4.cc:21
static ideal computeFrame(const ideal G, syzM_i_Function syzM_i, syzHeadFunction *syzHead)
Definition: syz4.cc:524
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
static ideal syzM_i_unsorted(const ideal G, const int i, syzHeadFunction *syzHead)
Definition: syz4.cc:384
static void delete_variables(resolvente res, const int index, const std::vector< bool > &variables)
Definition: syz4.cc:596

◆ 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 
)
static

Definition at line 633 of file syz4.cc.

637{
638 int index = 1;
639 while (!idIs0(res[index]))
640 {
641 if (do_lifting)
642 {
643 computeLiftings(res, index, variables, use_cache);
644 if (single_module)
645 {
647 }
648 // we don't know if the input is a reduced SB:
649 if (index == 1)
650 {
651 variables[currRing->N] = false;
652 }
654 if (use_tensor_trick)
655 {
657 }
658 }
659 if (index >= max_index) { break; }
660 index++;
661 res[index] = computeFrame(res[index-1], syzM_i_sorted, syzHead);
662 }
663 return index;
664}
static ideal syzM_i_sorted(const ideal G, const int i, syzHeadFunction *syzHead)
Definition: syz4.cc:418
static void computeLiftings(const resolvente res, const int index, const std::vector< bool > &variables, const bool use_cache)
Definition: syz4.cc:549
static void delete_tails(resolvente res, const int index)
Definition: syz4.cc:617

◆ contains_unused_variable()

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

Definition at line 578 of file syz4.cc.

580{
581 const ring R = currRing;
582 for (int j = R->N; j > 0; j--)
583 {
584 if (!variables[j-1] && p_GetExp(m, j, R) > 0)
585 {
586 return true;
587 }
588 }
589 return false;
590}

◆ delete_cache()

static void delete_cache ( const int  size)
static

Definition at line 237 of file syz4.cc.

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

◆ delete_tails()

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

Definition at line 617 of file syz4.cc.

618{
619 const ring r = currRing;
620 for (int i = 0; i < res[index]->ncols; i++)
621 {
622 if (res[index]->m[i] != NULL)
623 {
624 p_Delete(&(res[index]->m[i]->next), r);
625 }
626 }
627}
ListNode * next
Definition: janet.h:31

◆ delete_variables()

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

Definition at line 596 of file syz4.cc.

598{
599 for (int i = 0; i < res[index]->ncols; i++)
600 {
601 poly p_iter = res[index]->m[i]->next;
602 if (p_iter != NULL)
603 {
604 while (p_iter->next != NULL)
605 {
606 if (contains_unused_variable(p_iter->next, variables))
607 {
608 pLmDelete(&p_iter->next);
609 } else {
610 pIter(p_iter);
611 }
612 }
613 }
614 }
615}
#define pIter(p)
Definition: monomials.h:37
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
static bool contains_unused_variable(const poly m, const std::vector< bool > &variables)
Definition: syz4.cc:578

◆ find_reducer()

static 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.

120{
121 const ring r = currRing;
122 const lt_struct *v = hash_previous_module[__p_GetComp(t, r)];
123 unsigned long count = v[0].comp;
124 if (UNLIKELY(count == 1))
125 {
126 return NULL;
127 }
128 const poly q = p_New(r);
129 pNext(q) = NULL;
130 p_MemSum_LengthGeneral(q->exp, multiplier->exp, t->exp, r->ExpL_Size);
131 const unsigned long q_not_sev = ~p_GetShortExpVector(q, r);
132 for(unsigned long i = 1; i < count; i++)
133 {
134 if (LIKELY(v[i].sev & q_not_sev)
135 || UNLIKELY(!(_p_LmDivisibleByNoComp(v[i].lt, q, r))))
136 {
137 continue;
138 }
140 p_ExpVectorDiff(q, q, v[i].lt, r);
141 p_SetComp(q, v[i].comp, r);
142 p_Setm(q, r);
143 number n = n_Div(p_GetCoeff(multiplier, r), p_GetCoeff(v[i].lt, r), r->cf);
144 n_InpMult(n, p_GetCoeff(t, r), r->cf);
145 p_SetCoeff0(q, n_InpNeg(n, r->cf), r);
146 return q;
147 }
148 p_LmFree(q, r);
149 return NULL;
150}
#define LIKELY(X)
Definition: auxiliary.h:403
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:554
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:612
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:638
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:60
#define p_GetCoeff(p, r)
Definition: monomials.h:50
#define p_MemSum_LengthGeneral(r, s1, s2, length)
Definition: p_MemAdd.h:86
static void p_MemAdd_NegWeightAdjust(poly p, const ring r)
Definition: p_polys.h:1290
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1472
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:245
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
static poly p_New(const ring, omBin bin)
Definition: p_polys.h:662
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:1763
static void p_LmFree(poly p, ring)
Definition: p_polys.h:681
int status int void size_t count
Definition: si_signals.h:59

◆ get_from_cache_term()

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

Definition at line 260 of file syz4.cc.

262{
263 if (LIKELY(itr->second == NULL))
264 {
265 return NULL;
266 }
267 const ring r = currRing;
268 poly p = p_Copy(itr->second, r);
269 if (LIKELY(!n_Equal(pGetCoeff(multiplier), pGetCoeff(itr->first), r->cf)))
270 {
271 number n = n_Div(pGetCoeff(multiplier), pGetCoeff(itr->first), r->cf);
272 p = p_Mult_nn(p, n, r);
273 n_Delete(&n, r->cf);
274 }
275 return p;
276}
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:452
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:457
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
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:956
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:844

◆ idConcat()

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

Definition at line 444 of file syz4.cc.

445{
446 int ncols = 0;
447 for (int i = size-1; i >= 0; i--)
448 {
449 if (M[i] != NULL)
450 {
451 ncols += M[i]->ncols;
452 }
453 }
454 if (ncols == 0) return idInit(1, rank);
455 ideal result = idInit(ncols, rank);
456 int k = ncols-1;
457 for (int i = size-1; i >= 0; i--)
458 {
459 if (M[i] != NULL)
460 {
461 for (int j = M[i]->ncols-1; j >= 0; j--)
462 {
463 result->m[k] = M[i]->m[j];
464 k--;
465 }
466 }
467 }
468 return result;
469}
int k
Definition: cfEzgcd.cc:99
return result
Definition: facAbsBiFact.cc:75
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35

◆ initialize_cache()

static void initialize_cache ( const int  size)
static

Definition at line 232 of file syz4.cc.

233{
234 Cache = new cache_term[size];
235}

◆ initialize_hash()

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

Definition at line 80 of file syz4.cc.

81{
82 const ring R = currRing;
83 const unsigned long n_elems = L->ncols;
84 unsigned int *count
85 = (unsigned int *)omAlloc0((L->rank+1)*sizeof(unsigned int));
86 unsigned long k = 0;
87 while (k < n_elems)
88 {
89 count[__p_GetComp(L->m[k], R)]++;
90 k++;
91 }
92 for (int i = 0; i <= L->rank; i++)
93 {
94 // do ++count[i] and use C[i][0].comp to save count[i]
95 C[i] = (lt_struct *)omalloc0((++count[i])*sizeof(lt_struct));
96 C[i][0].comp = count[i];
97 }
98 k = n_elems;
99 // the order of the elements in each C[i] matters if check_variables() is
100 // to be used
101 while (k > 0)
102 {
103 const poly a = L->m[k-1];
104 const unsigned long comp = __p_GetComp(a, R);
105 C[comp][--count[comp]]
106 = (lt_struct){a, p_GetShortExpVector(a, R), k};
107 k--;
108 }
109 omFree(count);
110}
#define omalloc0(size)
Definition: omAllocDecl.h:229
#define omAlloc0(size)
Definition: omAllocDecl.h:211
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4780
unsigned long comp
Definition: syz4.cc:77

◆ insert_ext_induced_LTs()

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

Definition at line 758 of file syz4.cc.

760{
761 const ring R = currRing;
762 poly p, q;
763 int index = (single_module ? length-1 : 1);
764 while (index < length && !idIs0(res[index]))
765 {
766 for (int j = res[index]->ncols-1; j >= 0; j--)
767 {
768 insert_first_term(res[index]->m[j]->next, p, q, R);
769 insert_first_term(res[index]->m[j], p, q, R);
770 }
771 index++;
772 }
773}
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
#define insert_first_term(r, p, q, R)
Definition: syz4.cc:738

◆ insert_into_cache_term()

static void insert_into_cache_term ( cache_term T,
const poly  multiplier,
const poly  p 
)
static

Definition at line 253 of file syz4.cc.

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

◆ 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 
)
static

Definition at line 297 of file syz4.cc.

301{
302 const ring R = currRing;
303 // the leading term does not need to be cached
304 poly t1 = compute_image(a, __p_GetComp(a, R)-1, previous_module, variables,
305 hash_previous_module, use_cache);
306 poly t2;
307 if (use_cache)
308 {
309 t2 = traverse_tail(a->next, __p_GetComp(a->next, R)-1,
310 previous_module, variables, hash_previous_module);
311 } else {
312 t2 = compute_image(a->next, __p_GetComp(a->next, R)-1,
313 previous_module, variables, hash_previous_module, false);
314 }
315 t1 = p_Add_q(t1, t2, R);
316 return t1;
317}
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:934
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
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()

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

Definition at line 164 of file syz4.cc.

168{
169 poly s = find_reducer(multiplier, term, hash_previous_module);
170 if (s == NULL)
171 {
172 return NULL;
173 }
174 const ring r = currRing;
175 const int c = __p_GetComp(s, r) - 1;
176 poly t;
177 if (use_cache)
178 {
179 t = traverse_tail(s, c, previous_module, variables,
180 hash_previous_module);
181 } else {
182 t = compute_image(s, c, previous_module, variables,
183 hash_previous_module, false);
184 }
185 return p_Add_q(s, t, r);
186}
Definition: int_poly.h:33
static poly find_reducer(const poly multiplier, const poly t, const lt_struct *const *const hash_previous_module)
Definition: syz4.cc:118

◆ set_options()

static 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.

703{
704 if (strcmp(method, "complete") == 0)
705 { // default
706 *syzHead_ptr = syzHeadExtFrame;
707 *do_lifting_ptr = true;
708 *single_module_ptr = false;
709 }
710 else if (strcmp(method, "frame") == 0)
711 {
712 *syzHead_ptr = syzHeadFrame;
713 *do_lifting_ptr = false;
714 *single_module_ptr = false;
715 }
716 else if (strcmp(method, "extended frame") == 0)
717 {
718 *syzHead_ptr = syzHeadExtFrame;
719 *do_lifting_ptr = false;
720 *single_module_ptr = false;
721 }
722 else if (strcmp(method, "single module") == 0)
723 {
724 *syzHead_ptr = syzHeadExtFrame;
725 *do_lifting_ptr = true;
726 *single_module_ptr = true;
727 }
728 else { // "linear strand" (not yet implemented)
729 *syzHead_ptr = syzHeadExtFrame;
730 *do_lifting_ptr = true;
731 *single_module_ptr = false;
732 }
733}
static poly syzHeadExtFrame(const ideal G, const int i, const int j)
Definition: syz4.cc:350
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.

794{
796 resolvente res = (resolvente)omAlloc0((length+1)*sizeof(ideal));
797 if (strcmp(method, "frame") != 0)
798 {
799 res[0] = id_Copy(arg, currRing);
800 }
801 else
802 {
803 res[0] = id_Head(arg, currRing);
804 }
805 syzHeadFunction *syzHead;
806 bool do_lifting;
807 bool single_module;
808 set_options(&syzHead, &do_lifting, &single_module, method);
809 int new_length = computeResolution(res, length-1, syzHead, do_lifting,
810 single_module, use_cache, use_tensor_trick);
811 if (new_length < length)
812 {
813 res = (resolvente)omReallocSize(res, (length+1)*sizeof(ideal),
814 (new_length+1)*sizeof(ideal));
815 }
816 if (strcmp(method, "frame") != 0)
817 {
818 insert_ext_induced_LTs(res, new_length, single_module);
819 }
820 result->fullres = res;
821 result->length = new_length;
822 result->list_length = new_length;
823 return result;
824}
ideal id_Copy(ideal h1, const ring r)
copy an ideal
ideal * resolvente
Definition: ideals.h:18
#define omReallocSize(addr, o_size, size)
Definition: omAllocDecl.h:220
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
static void set_options(syzHeadFunction **syzHead_ptr, bool *do_lifting_ptr, bool *single_module_ptr, const char *method)
Definition: syz4.cc:701
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
static void insert_ext_induced_LTs(const resolvente res, const int length, const bool single_module)
Definition: syz4.cc:758
poly syzHeadFunction(ideal, int, int)
Definition: syz4.cc:321
ssyStrategy * syStrategy
Definition: syz.h:36

◆ syzHeadExtFrame()

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

Definition at line 350 of file syz4.cc.

351{
352 const ring r = currRing;
353 const poly f_i = G->m[i];
354 const poly f_j = G->m[j];
355 poly head = p_Init(r);
356 pSetCoeff0(head, n_Init(1, r->cf));
357 poly head_ext = p_Init(r);
358 pSetCoeff0(head_ext, n_InpNeg(n_Div(pGetCoeff(f_i), pGetCoeff(f_j), r->cf),
359 r->cf));
360 long exp_i, exp_j, lcm;
361 for (int k = (int)r->N; k > 0; k--)
362 {
363 exp_i = p_GetExp(f_i, k, r);
364 exp_j = p_GetExp(f_j, k, r);
365 lcm = si_max(exp_i, exp_j);
366 p_SetExp(head, k, lcm-exp_i, r);
367 p_SetExp(head_ext, k, lcm-exp_j, r);
368 }
369 p_SetComp(head, i+1, r);
370 p_Setm(head, r);
371 p_SetComp(head_ext, j+1, r);
372 p_Setm(head_ext, r);
373 head->next = head_ext;
374 return head;
375}
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
CanonicalForm head(const CanonicalForm &f)
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:535
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
#define pSetCoeff0(p, n)
Definition: monomials.h:59
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:486
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1318

◆ syzHeadFrame()

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

Definition at line 326 of file syz4.cc.

327{
328 const ring r = currRing;
329 const poly f_i = G->m[i];
330 const poly f_j = G->m[j];
331 poly head = p_Init(r);
332 pSetCoeff0(head, n_Init(1, r->cf));
333 long exp_i, exp_j, lcm;
334 for (int k = (int)r->N; k > 0; k--)
335 {
336 exp_i = p_GetExp(f_i, k, r);
337 exp_j = p_GetExp(f_j, k, r);
338 lcm = si_max(exp_i, exp_j);
339 p_SetExp(head, k, lcm-exp_i, r);
340 }
341 p_SetComp(head, i+1, r);
342 p_Setm(head, r);
343 return head;
344}

◆ syzM_i_sorted()

static ideal syzM_i_sorted ( const ideal  G,
const int  i,
syzHeadFunction syzHead 
)
static

Definition at line 418 of file syz4.cc.

420{
421 const ring r = currRing;
422 ideal M_i = NULL;
423 unsigned long comp = __p_GetComp(G->m[i], r);
424 int index = i-1;
425 while (__p_GetComp(G->m[index], r) == comp) index--;
426 index++;
427 int ncols = i-index;
428 if (ncols > 0)
429 {
430 M_i = idInit(ncols, G->ncols);
431 for (int j = ncols-1; j >= 0; j--)
432 {
433 M_i->m[j] = syzHead(G, i, j+index);
434 }
435 id_DelDiv(M_i, currRing);
436 idSkipZeroes(M_i);
437 }
438 return M_i;
439}
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

◆ syzM_i_unsorted()

static ideal syzM_i_unsorted ( const ideal  G,
const int  i,
syzHeadFunction syzHead 
)
static

Definition at line 384 of file syz4.cc.

386{
387 const ring r = currRing;
388 ideal M_i = NULL;
389 unsigned long comp = __p_GetComp(G->m[i], r);
390 int ncols = 0;
391 for (int j = i-1; j >= 0; j--)
392 {
393 if (__p_GetComp(G->m[j], r) == comp) ncols++;
394 }
395 if (ncols > 0)
396 {
397 M_i = idInit(ncols, G->ncols);
398 int k = ncols-1;
399 for (int j = i-1; j >= 0; j--)
400 {
401 if (__p_GetComp(G->m[j], r) == comp)
402 {
403 M_i->m[k] = syzHead(G, i, j);
404 k--;
405 }
406 }
407 id_DelDiv(M_i, currRing);
408 idSkipZeroes(M_i);
409 }
410 return M_i;
411}

◆ 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 
)
static

Definition at line 278 of file syz4.cc.

281{
282 cache_term *T = &(Cache[comp]);
283 cache_term::const_iterator itr = T->find(multiplier);
284 if (LIKELY(itr != T->end()))
285 {
286 return get_from_cache_term(itr, multiplier);
287 }
288 poly p = compute_image(multiplier, comp, previous_module, variables,
289 hash_previous_module, true);
290 insert_into_cache_term(T, multiplier, p);
291 return p;
292}
static poly get_from_cache_term(const cache_term::const_iterator itr, const poly multiplier)
Definition: syz4.cc:260
static void insert_into_cache_term(cache_term *T, const poly multiplier, const poly p)
Definition: syz4.cc:253

◆ update_variables()

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

Definition at line 21 of file syz4.cc.

22{
23 const ring R = currRing;
24 const int l = L->ncols-1;
25 int k;
26 for (int j = R->N; j > 0; j--)
27 {
28 if (variables[j-1])
29 {
30 for (k = l; k >= 0; k--)
31 {
32 if (p_GetExp(L->m[k], j, R) > 0)
33 {
34 break;
35 }
36 }
37 if (k < 0)
38 { // no break
39 variables[j-1] = false;
40 }
41 }
42 }
43}

Variable Documentation

◆ Cache

Definition at line 230 of file syz4.cc.