My Project  debian-1:4.1.1-p2+ds-4
syz4.cc
Go to the documentation of this file.
1 /***************************************
2  * Computer Algebra System SINGULAR *
3  ***************************************/
4 /*
5  * ABSTRACT: resolutions
6  * reference: https://arxiv.org/abs/1502.01654
7  */
8 
9 #include <kernel/GBEngine/syz.h>
10 #include <omalloc/omalloc.h>
11 #include <coeffs/numbers.h>
12 #include <kernel/polys.h>
13 #include <kernel/ideals.h>
14 
15 #include <vector>
16 #include <map>
17 
18 /*
19  * set variables[i] to false if the i-th variable does not appear among the
20  * leading terms of L
21  */
22 static void update_variables(std::vector<bool> &variables, const ideal L)
23 {
24  const ring R = currRing;
25  const int l = L->ncols-1;
26  int k;
27  for (int j = R->N; j > 0; j--) {
28  if (variables[j-1]) {
29  for (k = l; k >= 0; k--) {
30  if (p_GetExp(L->m[k], j, R) > 0) {
31  break;
32  }
33  }
34  if (k < 0) { // no break
35  variables[j-1] = false;
36  }
37  }
38  }
39 }
40 
41 /*
42  * If the previous step in the resolution is reduced, then this check can be
43  * used to determine lower order terms.
44  */
45 static inline bool check_variables(const std::vector<bool> &variables,
46  const poly m)
47 {
48  const ring R = currRing;
49  // variables[R->N] is true iff index == 1, that is, for the first step in
50  // the resolution
51  if (unlikely(variables[R->N])) {
52  return true;
53  }
54  for (int j = R->N; j > 0; j--) {
55  if (unlikely(variables[j-1] && p_GetExp(m, j, R) > 0)) {
56  return true;
57  }
58  }
59  return false;
60 }
61 
62 /*
63  * For each step in the resolution, the following data is saved for each of the
64  * induced leading terms: the leading term itself, its short exponent vector,
65  * and its position in the ideal/module.
66  */
67 typedef struct {
68  poly lt;
69  unsigned long sev;
70  unsigned long comp;
71 } lt_struct;
72 
73 static void initialize_hash(lt_struct **C, const ideal L)
74 {
75  const ring R = currRing;
76  const unsigned long n_elems = L->ncols;
77  unsigned int *count
78  = (unsigned int *)omAlloc0((L->rank+1)*sizeof(unsigned int));
79  unsigned long k = 0;
80  while (k < n_elems) {
81  count[__p_GetComp(L->m[k], R)]++;
82  k++;
83  }
84  for (int i = 0; i <= L->rank; i++) {
85  // do ++count[i] and use C[i][0].comp to save count[i]
86  C[i] = (lt_struct *)omalloc0((++count[i])*sizeof(lt_struct));
87  C[i][0].comp = count[i];
88  }
89  k = n_elems;
90  // the order of the elements in each C[i] matters if check_variables() is
91  // to be used
92  while (k > 0) {
93  const poly a = L->m[k-1];
94  const unsigned long comp = __p_GetComp(a, R);
95  C[comp][--count[comp]]
96  = (lt_struct){a, p_GetShortExpVector(a, R), k};
97  k--;
98  }
99  omFree(count);
100 }
101 
102 /*
103  * compute a new term in the resolution, that is, compute
104  * ( t * multiplier / f ) where f is an induced leading term from the previous
105  * module, or return NULL if no such f dividing t * multiplier exists, that is,
106  * if multiplier is a lower order term
107  */
108 static poly find_reducer(const poly multiplier, const poly t,
109  const lt_struct *const *const hash_previous_module)
110 {
111  const ring r = currRing;
112  const lt_struct *v = hash_previous_module[__p_GetComp(t, r)];
113  unsigned long count = v[0].comp;
114  if (unlikely(count == 1)) {
115  return NULL;
116  }
117  const poly q = p_New(r);
118  pNext(q) = NULL;
119  p_MemSum_LengthGeneral(q->exp, multiplier->exp, t->exp, r->ExpL_Size);
120  const unsigned long q_not_sev = ~p_GetShortExpVector(q, r);
121  for(unsigned long i = 1; i < count; i++) {
122  if (likely(v[i].sev & q_not_sev)
123  || unlikely(!(_p_LmDivisibleByNoComp(v[i].lt, q, r)))) {
124  continue;
125  }
127  p_ExpVectorDiff(q, q, v[i].lt, r);
128  p_SetComp(q, v[i].comp, r);
129  p_Setm(q, r);
130  number n = n_Div(p_GetCoeff(multiplier, r), p_GetCoeff(v[i].lt, r), r);
131  n_InpMult(n, p_GetCoeff(t, r), r);
132  p_SetCoeff0(q, n_InpNeg(n, r), r);
133  return q;
134  }
135  p_LmFree(q, r);
136  return NULL;
137 }
138 
139 static poly traverse_tail(const poly multiplier, const int comp,
140  const ideal previous_module, const std::vector<bool> &variables,
141  const lt_struct *const *const hash_previous_module);
142 
143 static poly compute_image(const poly multiplier, const int comp,
144  const ideal previous_module, const std::vector<bool> &variables,
145  const lt_struct *const *const hash_previous_module,
146  const bool use_cache);
147 
148 /*
149  * recursively call traverse_tail() for each new term found by find_reducer()
150  */
151 static poly reduce_term(const poly multiplier, const poly term,
152  const ideal previous_module, const std::vector<bool> &variables,
153  const lt_struct *const *const hash_previous_module,
154  const bool use_cache)
155 {
156  poly s = find_reducer(multiplier, term, hash_previous_module);
157  if (s == NULL) {
158  return NULL;
159  }
160  const ring r = currRing;
161  const int c = __p_GetComp(s, r) - 1;
162  poly t;
163  if (use_cache) {
164  t = traverse_tail(s, c, previous_module, variables,
165  hash_previous_module);
166  } else {
167  t = compute_image(s, c, previous_module, variables,
168  hash_previous_module, false);
169  }
170  return p_Add_q(s, t, r);
171 }
172 
173 /*
174  * iterating over tail, call reduce_term(multiplier, p, ...) for each term p in
175  * tail and sum up the results
176  */
177 static poly compute_image(const poly multiplier, const int comp,
178  const ideal previous_module, const std::vector<bool> &variables,
179  const lt_struct *const *const hash_previous_module,
180  const bool use_cache)
181 {
182  const poly tail = previous_module->m[comp]->next;
183  if (unlikely(tail == NULL) || !check_variables(variables, multiplier)) {
184  return NULL;
185  }
187  for (poly p = tail; p != NULL; p = pNext(p)) {
188  const poly rt = reduce_term(multiplier, p, previous_module, variables,
189  hash_previous_module, use_cache);
190  sBucket_Add_p(sum, rt, pLength(rt));
191  }
192  poly s;
193  int l;
194  sBucketClearAdd(sum, &s, &l);
195  sBucketDestroy(&sum);
196  return s;
197 }
198 
199 struct cache_compare
200 {
201  inline bool operator() (const poly& l, const poly& r) const
202  {
203  return (p_LmCmp(l, r, currRing) == -1);
204  /* For expensive orderings, consider:
205  * return (memcmp(l->exp, r->exp,
206  * (currRing->CmpL_Size)*sizeof(unsigned long)) < 0);
207  */
208  }
209 };
210 
211 typedef std::map<poly, poly, cache_compare> cache_term;
212 
213 static cache_term *Cache;
214 
215 static void initialize_cache(const int size)
216 {
217  Cache = new cache_term[size];
218 }
219 
220 static void delete_cache(const int size)
221 {
222  const ring r = currRing;
223  for (int i = 0; i < size; i++) {
224  cache_term *T = &(Cache[i]);
225  for (cache_term::iterator itr = T->begin(); itr != T->end(); ++itr) {
226  p_Delete(&(itr->second), r);
227  p_Delete(const_cast<poly*>(&(itr->first)), r);
228  }
229  T->clear();
230  }
231  delete[](Cache);
232 }
233 
234 static void insert_into_cache_term(cache_term *T, const poly multiplier,
235  const poly p)
236 {
237  const ring r = currRing;
238  T->insert(cache_term::value_type(p_Head(multiplier, r), p_Copy(p, r)));
239 }
240 
241 static poly get_from_cache_term(const cache_term::const_iterator itr,
242  const poly multiplier)
243 {
244  if (likely(itr->second == NULL)) {
245  return NULL;
246  }
247  const ring r = currRing;
248  poly p = p_Copy(itr->second, r);
249  if (likely(!n_Equal(pGetCoeff(multiplier), pGetCoeff(itr->first), r))) {
250  number n = n_Div(pGetCoeff(multiplier), pGetCoeff(itr->first), r);
251  p = p_Mult_nn(p, n, r);
252  n_Delete(&n, r);
253  }
254  return p;
255 }
256 
257 static poly traverse_tail(const poly multiplier, const int comp,
258  const ideal previous_module, const std::vector<bool> &variables,
259  const lt_struct *const *const hash_previous_module)
260 {
261  cache_term *T = &(Cache[comp]);
262  cache_term::const_iterator itr = T->find(multiplier);
263  if (likely(itr != T->end())) {
264  return get_from_cache_term(itr, multiplier);
265  }
266  poly p = compute_image(multiplier, comp, previous_module, variables,
267  hash_previous_module, true);
268  insert_into_cache_term(T, multiplier, p);
269  return p;
270 }
271 
272 /*
273  * lift the extended induced leading term a to a syzygy
274  */
275 static poly lift_ext_LT(const poly a, const ideal previous_module,
276  const std::vector<bool> &variables,
277  const lt_struct *const *const hash_previous_module,
278  const bool use_cache)
279 {
280  const ring R = currRing;
281  // the leading term does not need to be cached
282  poly t1 = compute_image(a, __p_GetComp(a, R)-1, previous_module, variables,
283  hash_previous_module, use_cache);
284  poly t2;
285  if (use_cache) {
286  t2 = traverse_tail(a->next, __p_GetComp(a->next, R)-1,
287  previous_module, variables, hash_previous_module);
288  } else {
289  t2 = compute_image(a->next, __p_GetComp(a->next, R)-1,
290  previous_module, variables, hash_previous_module, false);
291  }
292  t1 = p_Add_q(t1, t2, R);
293  return t1;
294 }
295 
296 /*****************************************************************************/
297 
298 /*
299  * copied from id_DelDiv(), but without testing and without HAVE_RINGS;
300  * delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, that is,
301  * delete id[i], if LT(i) == coeff*mon*LT(j)
302  */
303 static void id_DelDiv_no_test(ideal id)
304 {
305  const ring r = currRing;
306  int i, j;
307  int k = id->ncols-1;
308  for (i = k; i >= 0; i--) {
309  for (j = k; j > i; j--) {
310  if (id->m[j] != NULL) {
311  if (p_DivisibleBy(id->m[i], id->m[j], r)) {
312  p_Delete(&id->m[j], r);
313  }
314  else if (p_DivisibleBy(id->m[j], id->m[i], r)) {
315  p_Delete(&id->m[i], r);
316  break;
317  }
318  }
319  }
320  }
321 }
322 
323 typedef poly syzHeadFunction(ideal, int, int);
324 
325 /*
326  * compute the induced leading term corresponding to the index pair (i, j)
327  */
328 static poly syzHeadFrame(const ideal G, const int i, const int j)
329 {
330  const ring r = currRing;
331  const poly f_i = G->m[i];
332  const poly f_j = G->m[j];
333  poly head = p_Init(r);
334  pSetCoeff0(head, n_Init(1, r->cf));
335  long exp_i, exp_j, lcm;
336  for (int k = (int)r->N; k > 0; k--) {
337  exp_i = p_GetExp(f_i, k, r);
338  exp_j = p_GetExp(f_j, k, r);
339  lcm = si_max(exp_i, exp_j);
340  p_SetExp(head, k, lcm-exp_i, r);
341  }
342  p_SetComp(head, i+1, r);
343  p_Setm(head, r);
344  return head;
345 }
346 
347 /*
348  * compute the _extended_ induced leading term corresponding to the index pair
349  * (i, j), that is, the first two terms w.r.t. the induced order
350  */
351 static poly syzHeadExtFrame(const ideal G, const int i, const int j)
352 {
353  const ring r = currRing;
354  const poly f_i = G->m[i];
355  const poly f_j = G->m[j];
356  poly head = p_Init(r);
357  pSetCoeff0(head, n_Init(1, r->cf));
358  poly head_ext = p_Init(r);
359  pSetCoeff0(head_ext, n_InpNeg(n_Div(pGetCoeff(f_i), pGetCoeff(f_j), r->cf),
360  r->cf));
361  long exp_i, exp_j, lcm;
362  for (int k = (int)r->N; k > 0; k--) {
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 }
376 
377 typedef ideal syzM_i_Function(ideal, int, syzHeadFunction);
378 
379 /*
380  * compute the monomial ideal M_i, see reference;
381  * in the first step, we cannot assume that all leading terms which lie in the
382  * component are adjacent to each other
383  */
384 static ideal syzM_i_unsorted(const ideal G, const int i,
385  syzHeadFunction *syzHead)
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  if (__p_GetComp(G->m[j], r) == comp) ncols++;
393  }
394  if (ncols > 0) {
395  M_i = idInit(ncols, G->ncols);
396  int k = ncols-1;
397  for (int j = i-1; j >= 0; j--) {
398  if (__p_GetComp(G->m[j], r) == comp) {
399  M_i->m[k] = syzHead(G, i, j);
400  k--;
401  }
402  }
403  id_DelDiv_no_test(M_i);
404  idSkipZeroes(M_i);
405  }
406  return M_i;
407 }
408 
409 /*
410  * compute the monomial ideal M_i, see reference;
411  * from step two on, we can assume that all leading terms which lie in the same
412  * component are adjacent to each other
413  */
414 static ideal syzM_i_sorted(const ideal G, const int i,
415  syzHeadFunction *syzHead)
416 {
417  const ring r = currRing;
418  ideal M_i = NULL;
419  unsigned long comp = __p_GetComp(G->m[i], r);
420  int index = i-1;
421  while (__p_GetComp(G->m[index], r) == comp) index--;
422  index++;
423  int ncols = i-index;
424  if (ncols > 0) {
425  M_i = idInit(ncols, G->ncols);
426  for (int j = ncols-1; j >= 0; j--) {
427  M_i->m[j] = syzHead(G, i, j+index);
428  }
429  id_DelDiv_no_test(M_i);
430  idSkipZeroes(M_i);
431  }
432  return M_i;
433 }
434 
435 /*
436  * concatenate the ideals in M[]
437  */
438 static ideal idConcat(const ideal *M, const int size, const int rank)
439 {
440  int ncols = 0;
441  for (int i = size-1; i >= 0; i--) {
442  if (M[i] != NULL) {
443  ncols += M[i]->ncols;
444  }
445  }
446  if (ncols == 0) return idInit(1, rank);
447  ideal result = idInit(ncols, rank);
448  int k = ncols-1;
449  for (int i = size-1; i >= 0; i--) {
450  if (M[i] != NULL) {
451  for (int j = M[i]->ncols-1; j >= 0; j--) {
452  result->m[k] = M[i]->m[j];
453  k--;
454  }
455  }
456  }
457  return result;
458 }
459 
460 static int compare_comp(const poly p_a, const poly p_b)
461 {
462  const ring r = currRing;
463  long comp_a = __p_GetComp(p_a, r);
464  long comp_b = __p_GetComp(p_b, r);
465  return (comp_a > comp_b) - (comp_a < comp_b);
466 }
467 
468 static int compare_deg(const poly p_a, const poly p_b)
469 {
470  const ring r = currRing;
471  long deg_a = p_Deg(p_a, r);
472  long deg_b = p_Deg(p_b, r);
473  return (deg_a > deg_b) - (deg_a < deg_b);
474 }
475 
476 static int compare_lex(const poly p_a, const poly p_b)
477 {
478  int cmp;
479  const ring r = currRing;
480  int exp_a[r->N+1];
481  int exp_b[r->N+1];
482  p_GetExpV(p_a, exp_a, r);
483  p_GetExpV(p_b, exp_b, r);
484  for (int i = r->N; i > 0; i--) {
485  cmp = (exp_a[i] > exp_b[i]) - (exp_a[i] < exp_b[i]);
486  if (cmp != 0) {
487  return cmp;
488  }
489  }
490  return 0;
491 }
492 
493 static int compare_Mi(const void* a, const void *b)
494 {
495  poly p_a = *((poly *)a);
496  poly p_b = *((poly *)b);
497  int cmp;
498  if ((cmp = compare_comp(p_a, p_b))
499  || (cmp = compare_deg(p_a, p_b))
500  || (cmp = compare_lex(p_a, p_b))) {
501  return cmp;
502  }
503  return 0;
504 }
505 
506 /*
507  * compute the frame, that is, the induced leading terms for the next step in
508  * the resolution
509  */
510 static ideal computeFrame(const ideal G, syzM_i_Function syzM_i,
511  syzHeadFunction *syzHead)
512 {
513  ideal *M = (ideal *)omalloc((G->ncols-1)*sizeof(ideal));
514  for (int i = G->ncols-2; i >= 0; i--) {
515  M[i] = syzM_i(G, i+1, syzHead);
516  }
517  ideal frame = idConcat(M, G->ncols-1, G->ncols);
518  for (int i = G->ncols-2; i >= 0; i--) {
519  if (M[i] != NULL) {
520  omFreeSize(M[i]->m, M[i]->ncols*sizeof(poly));
522  }
523  }
524  omfree(M);
525  qsort(frame->m, frame->ncols, sizeof(poly), compare_Mi);
526  return frame;
527 }
528 
529 /*
530  * lift each (extended) induced leading term to a syzygy
531  */
532 static void computeLiftings(const resolvente res, const int index,
533  const std::vector<bool> &variables, const bool use_cache)
534 {
535  if (use_cache) {
537  }
538  lt_struct **hash_previous_module
539  = (lt_struct **)omAlloc((res[index-1]->rank+1)*sizeof(lt_struct *));
540  initialize_hash(hash_previous_module, res[index-1]);
541  for (int j = res[index]->ncols-1; j >= 0; j--) {
542  res[index]->m[j]->next->next = lift_ext_LT(res[index]->m[j],
543  res[index-1], variables, hash_previous_module, use_cache);
544  }
545  for (int i = 0; i <= res[index-1]->rank; i++) {
546  omfree(hash_previous_module[i]);
547  }
548  omFree(hash_previous_module);
549  if (use_cache) {
551  }
552 }
553 
554 /*
555  * check if the monomial m contains any of the variables set to false
556  */
557 static inline bool contains_unused_variable(const poly m,
558  const std::vector<bool> &variables)
559 {
560  const ring R = currRing;
561  for (int j = R->N; j > 0; j--) {
562  if (!variables[j-1] && p_GetExp(m, j, R) > 0) {
563  return true;
564  }
565  }
566  return false;
567 }
568 
569 /*
570  * delete any term in res[index] which contains any of the variables set to
571  * false
572  */
573 static void delete_variables(resolvente res, const int index,
574  const std::vector<bool> &variables)
575 {
576  for (int i = 0; i < res[index]->ncols; i++) {
577  poly p_iter = res[index]->m[i]->next;
578  if (p_iter != NULL) {
579  while (p_iter->next != NULL) {
580  if (contains_unused_variable(p_iter->next, variables)) {
581  pLmDelete(&p_iter->next);
582  } else {
583  pIter(p_iter);
584  }
585  }
586  }
587  }
588 }
589 
590 static void delete_tails(resolvente res, const int index)
591 {
592  const ring r = currRing;
593  for (int i = 0; i < res[index]->ncols; i++) {
594  if (res[index]->m[i] != NULL) {
595  p_Delete(&(res[index]->m[i]->next), r);
596  }
597  }
598 }
599 
600 /*
601  * for each step in the resolution, compute the corresponding module until
602  * either index == max_index is reached or res[index] is the zero module
603  */
604 static int computeResolution_iteration(resolvente res, const int max_index,
605  syzHeadFunction *syzHead, const bool do_lifting,
606  const bool single_module, const bool use_cache,
607  const bool use_tensor_trick, std::vector<bool> &variables)
608 {
609  int index = 1;
610  while (!idIs0(res[index])) {
611  if (do_lifting) {
612  computeLiftings(res, index, variables, use_cache);
613  if (single_module) {
614  delete_tails(res, index-1);
615  }
616  // we don't know if the input is a reduced SB:
617  if (index == 1) {
618  variables[currRing->N] = false;
619  }
621  if (use_tensor_trick) {
623  }
624  }
625  if (index >= max_index) { break; }
626  index++;
627  res[index] = computeFrame(res[index-1], syzM_i_sorted, syzHead);
628  }
629  return index;
630 }
631 
632 /*
633  * compute the frame of the first syzygy module and set variables, then call
634  * computeResolution_iteration() for the remaining steps
635  */
636 static int computeResolution(resolvente res, const int max_index,
637  syzHeadFunction *syzHead, const bool do_lifting,
638  const bool single_module, const bool use_cache,
639  const bool use_tensor_trick)
640 {
641  if (idIs0(res[0])) {
642  return 1;
643  }
644  std::vector<bool> variables;
645  variables.resize(currRing->N+1, true);
646  if (do_lifting) {
648  if (use_tensor_trick) {
650  }
651  }
652  int index = 0;
653  if (max_index > 0) {
654  res[1] = computeFrame(res[0], syzM_i_unsorted, syzHead);
655  index = computeResolution_iteration(res, max_index, syzHead,
656  do_lifting, single_module, use_cache, use_tensor_trick,
657  variables);
658  }
659  variables.clear();
660  return index+1;
661 }
662 
663 static void set_options(syzHeadFunction **syzHead_ptr, bool *do_lifting_ptr,
664  bool *single_module_ptr, const char *method)
665 {
666  if (strcmp(method, "complete") == 0) { // default
667  *syzHead_ptr = syzHeadExtFrame;
668  *do_lifting_ptr = true;
669  *single_module_ptr = false;
670  }
671  else if (strcmp(method, "frame") == 0) {
672  *syzHead_ptr = syzHeadFrame;
673  *do_lifting_ptr = false;
674  *single_module_ptr = false;
675  }
676  else if (strcmp(method, "extended frame") == 0) {
677  *syzHead_ptr = syzHeadExtFrame;
678  *do_lifting_ptr = false;
679  *single_module_ptr = false;
680  }
681  else if (strcmp(method, "single module") == 0) {
682  *syzHead_ptr = syzHeadExtFrame;
683  *do_lifting_ptr = true;
684  *single_module_ptr = true;
685  }
686  else { // "linear strand" (not yet implemented)
687  *syzHead_ptr = syzHeadExtFrame;
688  *do_lifting_ptr = true;
689  *single_module_ptr = false;
690  }
691 }
692 
693 /*
694  * insert the first term of r at the right place
695  */
696 #define insert_first_term(r, p, q, R) \
697 do \
698 { \
699  p = r; \
700  q = p->next; \
701  if (q != NULL && p_LmCmp(p, q, R) != 1) { \
702  while (q->next != NULL && p_LmCmp(p, q->next, R) == -1) { \
703  pIter(q); \
704  } \
705  r = p->next; \
706  p->next = q->next; \
707  q->next = p; \
708  } \
709 } \
710 while (0)
711 
712 /*
713  * For each poly in the resolution, insert the first two terms at their right
714  * places. If single_module is true, then only consider the last module.
715  */
716 static void insert_ext_induced_LTs(const resolvente res, const int length,
717  const bool single_module)
718 {
719  const ring R = currRing;
720  poly p, q;
721  int index = (single_module ? length-1 : 1);
722  while (index < length && !idIs0(res[index])) {
723  for (int j = res[index]->ncols-1; j >= 0; j--) {
724  insert_first_term(res[index]->m[j]->next, p, q, R);
725  insert_first_term(res[index]->m[j], p, q, R);
726  }
727  index++;
728  }
729 }
730 
731 /*
732  * Compute the Schreyer resolution of arg, see reference at the beginning of
733  * this file.
734  *
735  * If use_cache == true (default), the result of compute_image() is cached for
736  * _every_ term in the current step of the resolution. This corresponds to the
737  * subtree attached to the node which represents this term, see reference.
738  *
739  * If use_tensor_trick == true, the current module is modfied after each
740  * lifting step in the resolution: any term which contains a variable which
741  * does not appear among the (induced) leading terms is deleted. Note that the
742  * resulting object is not necessarily a complex anymore. However, constant
743  * entries remain exactly the same. This option does not apply for
744  * method == "frame" and method "extended frame".
745  *
746  * These two options are used in PrymGreen.jl; do not delete!
747  */
748 syStrategy syFrank(const ideal arg, const int length, const char *method,
749  const bool use_cache, const bool use_tensor_trick)
750 {
752  resolvente res = (resolvente)omAlloc0((length+1)*sizeof(ideal));
753  if (strcmp(method, "frame") != 0) {
754  res[0] = id_Copy(arg, currRing);
755  } else {
756  res[0] = id_Head(arg, currRing);
757  }
758  syzHeadFunction *syzHead;
759  bool do_lifting;
760  bool single_module;
761  set_options(&syzHead, &do_lifting, &single_module, method);
762  int new_length = computeResolution(res, length-1, syzHead, do_lifting,
763  single_module, use_cache, use_tensor_trick);
764  if (new_length < length) {
765  res = (resolvente)omReallocSize(res, (length+1)*sizeof(ideal),
766  (new_length+1)*sizeof(ideal));
767  }
768  if (strcmp(method, "frame") != 0) {
769  insert_ext_induced_LTs(res, new_length, single_module);
770  }
771  result->fullres = res;
772  result->length = new_length;
773  result->list_length = new_length;
774  return result;
775 }
776 
sip_sideal_bin
omBin sip_sideal_bin
Definition: simpleideals.cc:28
omalloc.h
delete_variables
static void delete_variables(resolvente res, const int index, const std::vector< bool > &variables)
Definition: syz4.cc:572
ncols
int int ncols
Definition: cf_linsys.cc:32
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:54
_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:1664
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:457
p_MemSum_LengthGeneral
#define p_MemSum_LengthGeneral(r, s1, s2, length)
Definition: p_MemAdd.h:83
j
int j
Definition: facHensel.cc:105
idConcat
static ideal idConcat(const ideal *M, const int size, const int rank)
Definition: syz4.cc:437
omFree
#define omFree(addr)
Definition: omAllocDecl.h:259
syzM_i_unsorted
static ideal syzM_i_unsorted(const ideal G, const int i, syzHeadFunction *syzHead)
Definition: syz4.cc:383
syFrank
syStrategy syFrank(const ideal arg, const int length, const char *method, const bool use_cache, const bool use_tensor_trick)
Definition: syz4.cc:747
insert_into_cache_term
static void insert_into_cache_term(cache_term *T, const poly multiplier, const poly p)
Definition: syz4.cc:233
p_SetCoeff0
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:64
k
int k
Definition: cfEzgcd.cc:92
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:603
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:176
p_ExpVectorDiff
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1402
syzM_i_Function
ideal syzM_i_Function(ideal, int, syzHeadFunction)
Definition: syz4.cc:376
result
return result
Definition: facAbsBiFact.cc:76
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:641
insert_first_term
#define insert_first_term(r, p, q, R)
Definition: syz4.cc:695
syStrategy
ssyStrategy * syStrategy
Definition: syz.h:34
p_Head
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:810
syzM_i_sorted
static ideal syzM_i_sorted(const ideal G, const int i, syzHeadFunction *syzHead)
Definition: syz4.cc:413
polys.h
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
initialize_hash
static void initialize_hash(lt_struct **C, const ideal L)
Definition: syz4.cc:72
__p_GetComp
#define __p_GetComp(p, r)
Definition: monomials.h:67
p_MemAdd_NegWeightAdjust
static void p_MemAdd_NegWeightAdjust(poly p, const ring r)
Definition: p_polys.h:1221
contains_unused_variable
static bool contains_unused_variable(const poly m, const std::vector< bool > &variables)
Definition: syz4.cc:556
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
set_options
static void set_options(syzHeadFunction **syzHead_ptr, bool *do_lifting_ptr, bool *single_module_ptr, const char *method)
Definition: syz4.cc:662
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:274
idIs0
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
Definition: simpleideals.cc:767
b
CanonicalForm b
Definition: cfModGcd.cc:4044
get_from_cache_term
static poly get_from_cache_term(const cache_term::const_iterator itr, const poly multiplier)
Definition: syz4.cc:240
term
Definition: int_poly.h:33
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:476
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:183
next
ListNode * next
Definition: janet.h:31
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:797
currRing
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
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:256
delete_tails
static void delete_tails(resolvente res, const int index)
Definition: syz4.cc:589
i
int i
Definition: cfEzgcd.cc:125
likely
#define likely(X)
Definition: auxiliary.h:416
res
CanonicalForm res
Definition: facAbsFact.cc:64
insert_ext_induced_LTs
static void insert_ext_induced_LTs(const resolvente res, const int length, const bool single_module)
Definition: syz4.cc:715
check_variables
static bool check_variables(const std::vector< bool > &variables, const poly m)
Definition: syz4.cc:44
M
#define M
Definition: sirandom.c:24
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:635
compare_comp
static int compare_comp(const poly p_a, const poly p_b)
Definition: syz4.cc:459
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:258
sBucket_Add_p
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:204
find_reducer
static poly find_reducer(const poly multiplier, const poly t, const lt_struct *const *const hash_previous_module)
Definition: syz4.cc:107
T
static jList * T
Definition: janet.cc:31
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition: simpleideals.cc:171
sBucketCreate
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:97
cache_compare::operator()
bool operator()(const poly &l, const poly &r) const
Definition: syz4.cc:200
resolvente
ideal * resolvente
Definition: ideals.h:17
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
p_New
static poly p_New(const ring, omBin bin)
Definition: p_polys.h:651
update_variables
static void update_variables(std::vector< bool > &variables, const ideal L)
Definition: syz4.cc:21
pIter
#define pIter(p)
Definition: monomials.h:41
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
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:538
p_DivisibleBy
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1803
p_GetExpV
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1448
p_Init
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1249
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1488
cache_compare
Definition: syz4.cc:198
syzHeadExtFrame
static poly syzHeadExtFrame(const ideal G, const int i, const int j)
Definition: syz4.cc:350
computeFrame
static ideal computeFrame(const ideal G, syzM_i_Function syzM_i, syzHeadFunction *syzHead)
Definition: syz4.cc:509
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:557
lt_struct::comp
unsigned long comp
Definition: syz4.cc:69
syzHeadFrame
static poly syzHeadFrame(const ideal G, const int i, const int j)
Definition: syz4.cc:327
sBucket
Definition: sbuckets.cc:31
p_LmFree
static void p_LmFree(poly p, ring)
Definition: p_polys.h:670
lt_struct
Definition: syz4.cc:66
p_Deg
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:578
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:842
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
computeLiftings
static void computeLiftings(const resolvente res, const int index, const std::vector< bool > &variables, const bool use_cache)
Definition: syz4.cc:531
si_max
static int si_max(const int a, const int b)
Definition: auxiliary.h:138
cache_term
std::map< poly, poly, cache_compare > cache_term
Definition: syz4.cc:210
omalloc
#define omalloc(size)
Definition: omAllocDecl.h:226
initialize_cache
static void initialize_cache(const int size)
Definition: syz4.cc:214
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:36
pSetCoeff0
#define pSetCoeff0(p, n)
Definition: monomials.h:63
compare_lex
static int compare_lex(const poly p_a, const poly p_b)
Definition: syz4.cc:475
m
int m
Definition: cfEzgcd.cc:121
id_DelDiv_no_test
static void id_DelDiv_no_test(ideal id)
Definition: syz4.cc:302
syz.h
NULL
#define NULL
Definition: omList.c:9
pLmDelete
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:74
variables
static int variables
Definition: interpolation.cc:87
ideals.h
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:238
l
int l
Definition: cfEzgcd.cc:93
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
sBucketClearAdd
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:275
R
#define R
Definition: sirandom.c:26
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:224
compare_Mi
static int compare_Mi(const void *a, const void *b)
Definition: syz4.cc:492
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
compare_deg
static int compare_deg(const poly p_a, const poly p_b)
Definition: syz4.cc:467
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:460
p
int p
Definition: cfModGcd.cc:4019
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
count
int status int void size_t count
Definition: si_signals.h:58
head
CanonicalForm head(const CanonicalForm &f)
Definition: canonicalform.h:353
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:615
syzHeadFunction
poly syzHeadFunction(ideal, int, int)
Definition: syz4.cc:322
unlikely
#define unlikely(X)
Definition: auxiliary.h:417
Cache
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition: Cache.h:68
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: facSparseHensel.h:25
id_Copy
ideal id_Copy(ideal h1, const ring r)
copy an ideal
Definition: simpleideals.cc:403
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:48
sBucketDestroy
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:104
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:257
p_GetShortExpVector
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4660
G
static TreeM * G
Definition: janet.cc:32
delete_cache
static void delete_cache(const int size)
Definition: syz4.cc:219
id_Head
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
Definition: simpleideals.cc:1110
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:585
numbers.h
Cache
static cache_term * Cache
Definition: syz4.cc:212
pNext
#define pNext(p)
Definition: monomials.h:40
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:209
omalloc0
#define omalloc0(size)
Definition: omAllocDecl.h:227
p_Mult_nn
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:899
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:150
ssyStrategy
Definition: syz.h:36
omReallocSize
#define omReallocSize(addr, o_size, size)
Definition: omAllocDecl.h:218
omfree
#define omfree(addr)
Definition: omAllocDecl.h:235