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 "coeffs/numbers.h"
11 #include "kernel/polys.h"
12 #include "kernel/ideals.h"
13 
14 #include <vector>
15 #include <map>
16 
17 /*
18  * set variables[i] to false if the i-th variable does not appear among the
19  * leading terms of L
20  */
21 static void update_variables(std::vector<bool> &variables, const ideal L)
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 }
44 
45 /*
46  * If the previous step in the resolution is reduced, then this check can be
47  * used to determine lower order terms.
48  */
49 static inline bool check_variables(const std::vector<bool> &variables,
50  const poly m)
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 }
68 
69 /*
70  * For each step in the resolution, the following data is saved for each of the
71  * induced leading terms: the leading term itself, its short exponent vector,
72  * and its position in the ideal/module.
73  */
74 typedef struct {
75  poly lt;
76  unsigned long sev;
77  unsigned long comp;
78 } lt_struct;
79 
80 static void initialize_hash(lt_struct **C, const ideal L)
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 }
111 
112 /*
113  * compute a new term in the resolution, that is, compute
114  * ( t * multiplier / f ) where f is an induced leading term from the previous
115  * module, or return NULL if no such f dividing t * multiplier exists, that is,
116  * if multiplier is a lower order term
117  */
118 static poly find_reducer(const poly multiplier, const poly t,
119  const lt_struct *const *const hash_previous_module)
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);
144  n_InpMult(n, p_GetCoeff(t, r), r);
145  p_SetCoeff0(q, n_InpNeg(n, r), r);
146  return q;
147  }
148  p_LmFree(q, r);
149  return NULL;
150 }
151 
152 static poly traverse_tail(const poly multiplier, const int comp,
153  const ideal previous_module, const std::vector<bool> &variables,
154  const lt_struct *const *const hash_previous_module);
155 
156 static poly compute_image(const poly multiplier, const int comp,
157  const ideal previous_module, const std::vector<bool> &variables,
158  const lt_struct *const *const hash_previous_module,
159  const bool use_cache);
160 
161 /*
162  * recursively call traverse_tail() for each new term found by find_reducer()
163  */
164 static poly reduce_term(const poly multiplier, const poly term,
165  const ideal previous_module, const std::vector<bool> &variables,
166  const lt_struct *const *const hash_previous_module,
167  const bool use_cache)
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 }
187 
188 /*
189  * iterating over tail, call reduce_term(multiplier, p, ...) for each term p in
190  * tail and sum up the results
191  */
192 static poly compute_image(const poly multiplier, const int comp,
193  const ideal previous_module, const std::vector<bool> &variables,
194  const lt_struct *const *const hash_previous_module,
195  const bool use_cache)
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 }
215 
217 {
218  inline bool operator() (const poly& l, const poly& r) const
219  {
220  return (p_LmCmp(l, r, currRing) == -1);
221  /* For expensive orderings, consider:
222  * return (memcmp(l->exp, r->exp,
223  * (currRing->CmpL_Size)*sizeof(unsigned long)) < 0);
224  */
225  }
226 };
227 
228 typedef std::map<poly, poly, cache_compare> cache_term;
229 
231 
232 static void initialize_cache(const int size)
233 {
234  Cache = new cache_term[size];
235 }
236 
237 static void delete_cache(const int size)
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 }
252 
253 static void insert_into_cache_term(cache_term *T, const poly multiplier,
254  const poly p)
255 {
256  const ring r = currRing;
257  T->insert(cache_term::value_type(p_Head(multiplier, r), p_Copy(p, r)));
258 }
259 
260 static poly get_from_cache_term(const cache_term::const_iterator itr,
261  const poly multiplier)
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)))
270  {
271  number n = n_Div(pGetCoeff(multiplier), pGetCoeff(itr->first), r);
272  p = p_Mult_nn(p, n, r);
273  n_Delete(&n, r);
274  }
275  return p;
276 }
277 
278 static poly traverse_tail(const poly multiplier, const int comp,
279  const ideal previous_module, const std::vector<bool> &variables,
280  const lt_struct *const *const hash_previous_module)
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 }
293 
294 /*
295  * lift the extended induced leading term a to a syzygy
296  */
297 static poly lift_ext_LT(const poly a, const ideal previous_module,
298  const std::vector<bool> &variables,
299  const lt_struct *const *const hash_previous_module,
300  const bool use_cache)
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 }
318 
319 /*****************************************************************************/
320 
321 /*
322  * copied from id_DelDiv(), but without testing and without HAVE_RINGS;
323  * delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, that is,
324  * delete id[i], if LT(i) == coeff*mon*LT(j)
325  */
326 static void id_DelDiv_no_test(ideal id)
327 {
328  const ring r = currRing;
329  int i, j;
330  int k = id->ncols-1;
331  for (i = k; i >= 0; i--)
332  {
333  for (j = k; j > i; j--)
334  {
335  if (id->m[j] != NULL)
336  {
337  if (p_DivisibleBy(id->m[i], id->m[j], r))
338  {
339  p_Delete(&id->m[j], r);
340  }
341  else if (p_DivisibleBy(id->m[j], id->m[i], r))
342  {
343  p_Delete(&id->m[i], r);
344  break;
345  }
346  }
347  }
348  }
349 }
350 
351 typedef poly syzHeadFunction(ideal, int, int);
352 
353 /*
354  * compute the induced leading term corresponding to the index pair (i, j)
355  */
356 static poly syzHeadFrame(const ideal G, const int i, const int j)
357 {
358  const ring r = currRing;
359  const poly f_i = G->m[i];
360  const poly f_j = G->m[j];
361  poly head = p_Init(r);
362  pSetCoeff0(head, n_Init(1, r->cf));
363  long exp_i, exp_j, lcm;
364  for (int k = (int)r->N; k > 0; k--)
365  {
366  exp_i = p_GetExp(f_i, k, r);
367  exp_j = p_GetExp(f_j, k, r);
368  lcm = si_max(exp_i, exp_j);
369  p_SetExp(head, k, lcm-exp_i, r);
370  }
371  p_SetComp(head, i+1, r);
372  p_Setm(head, r);
373  return head;
374 }
375 
376 /*
377  * compute the _extended_ induced leading term corresponding to the index pair
378  * (i, j), that is, the first two terms w.r.t. the induced order
379  */
380 static poly syzHeadExtFrame(const ideal G, const int i, const int j)
381 {
382  const ring r = currRing;
383  const poly f_i = G->m[i];
384  const poly f_j = G->m[j];
385  poly head = p_Init(r);
386  pSetCoeff0(head, n_Init(1, r->cf));
387  poly head_ext = p_Init(r);
388  pSetCoeff0(head_ext, n_InpNeg(n_Div(pGetCoeff(f_i), pGetCoeff(f_j), r->cf),
389  r->cf));
390  long exp_i, exp_j, lcm;
391  for (int k = (int)r->N; k > 0; k--)
392  {
393  exp_i = p_GetExp(f_i, k, r);
394  exp_j = p_GetExp(f_j, k, r);
395  lcm = si_max(exp_i, exp_j);
396  p_SetExp(head, k, lcm-exp_i, r);
397  p_SetExp(head_ext, k, lcm-exp_j, r);
398  }
399  p_SetComp(head, i+1, r);
400  p_Setm(head, r);
401  p_SetComp(head_ext, j+1, r);
402  p_Setm(head_ext, r);
403  head->next = head_ext;
404  return head;
405 }
406 
407 typedef ideal syzM_i_Function(ideal, int, syzHeadFunction);
408 
409 /*
410  * compute the monomial ideal M_i, see reference;
411  * in the first step, we cannot assume that all leading terms which lie in the
412  * component are adjacent to each other
413  */
414 static ideal syzM_i_unsorted(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 ncols = 0;
421  for (int j = i-1; j >= 0; j--)
422  {
423  if (__p_GetComp(G->m[j], r) == comp) ncols++;
424  }
425  if (ncols > 0)
426  {
427  M_i = idInit(ncols, G->ncols);
428  int k = ncols-1;
429  for (int j = i-1; j >= 0; j--)
430  {
431  if (__p_GetComp(G->m[j], r) == comp)
432  {
433  M_i->m[k] = syzHead(G, i, j);
434  k--;
435  }
436  }
437  id_DelDiv_no_test(M_i);
438  idSkipZeroes(M_i);
439  }
440  return M_i;
441 }
442 
443 /*
444  * compute the monomial ideal M_i, see reference;
445  * from step two on, we can assume that all leading terms which lie in the same
446  * component are adjacent to each other
447  */
448 static ideal syzM_i_sorted(const ideal G, const int i,
449  syzHeadFunction *syzHead)
450 {
451  const ring r = currRing;
452  ideal M_i = NULL;
453  unsigned long comp = __p_GetComp(G->m[i], r);
454  int index = i-1;
455  while (__p_GetComp(G->m[index], r) == comp) index--;
456  index++;
457  int ncols = i-index;
458  if (ncols > 0)
459  {
460  M_i = idInit(ncols, G->ncols);
461  for (int j = ncols-1; j >= 0; j--)
462  {
463  M_i->m[j] = syzHead(G, i, j+index);
464  }
465  id_DelDiv_no_test(M_i);
466  idSkipZeroes(M_i);
467  }
468  return M_i;
469 }
470 
471 /*
472  * concatenate the ideals in M[]
473  */
474 static ideal idConcat(const ideal *M, const int size, const int rank)
475 {
476  int ncols = 0;
477  for (int i = size-1; i >= 0; i--)
478  {
479  if (M[i] != NULL)
480  {
481  ncols += M[i]->ncols;
482  }
483  }
484  if (ncols == 0) return idInit(1, rank);
485  ideal result = idInit(ncols, rank);
486  int k = ncols-1;
487  for (int i = size-1; i >= 0; i--)
488  {
489  if (M[i] != NULL)
490  {
491  for (int j = M[i]->ncols-1; j >= 0; j--)
492  {
493  result->m[k] = M[i]->m[j];
494  k--;
495  }
496  }
497  }
498  return result;
499 }
500 
501 static int compare_comp(const poly p_a, const poly p_b)
502 {
503  const ring r = currRing;
504  long comp_a = __p_GetComp(p_a, r);
505  long comp_b = __p_GetComp(p_b, r);
506  return (comp_a > comp_b) - (comp_a < comp_b);
507 }
508 
509 static int compare_deg(const poly p_a, const poly p_b)
510 {
511  const ring r = currRing;
512  long deg_a = p_Deg(p_a, r);
513  long deg_b = p_Deg(p_b, r);
514  return (deg_a > deg_b) - (deg_a < deg_b);
515 }
516 
517 static int compare_lex(const poly p_a, const poly p_b)
518 {
519  int cmp;
520  const ring r = currRing;
521  int exp_a[r->N+1];
522  int exp_b[r->N+1];
523  p_GetExpV(p_a, exp_a, r);
524  p_GetExpV(p_b, exp_b, r);
525  for (int i = r->N; i > 0; i--)
526  {
527  cmp = (exp_a[i] > exp_b[i]) - (exp_a[i] < exp_b[i]);
528  if (cmp != 0)
529  {
530  return cmp;
531  }
532  }
533  return 0;
534 }
535 
536 static int compare_Mi(const void* a, const void *b)
537 {
538  poly p_a = *((poly *)a);
539  poly p_b = *((poly *)b);
540  int cmp;
541  if ((cmp = compare_comp(p_a, p_b))
542  || (cmp = compare_deg(p_a, p_b))
543  || (cmp = compare_lex(p_a, p_b)))
544  {
545  return cmp;
546  }
547  return 0;
548 }
549 
550 /*
551  * compute the frame, that is, the induced leading terms for the next step in
552  * the resolution
553  */
554 static ideal computeFrame(const ideal G, syzM_i_Function syzM_i,
555  syzHeadFunction *syzHead)
556 {
557  ideal *M = (ideal *)omalloc((G->ncols-1)*sizeof(ideal));
558  for (int i = G->ncols-2; i >= 0; i--)
559  {
560  M[i] = syzM_i(G, i+1, syzHead);
561  }
562  ideal frame = idConcat(M, G->ncols-1, G->ncols);
563  for (int i = G->ncols-2; i >= 0; i--)
564  {
565  if (M[i] != NULL)
566  {
567  omFreeSize(M[i]->m, M[i]->ncols*sizeof(poly));
569  }
570  }
571  omfree(M);
572  qsort(frame->m, frame->ncols, sizeof(poly), compare_Mi);
573  return frame;
574 }
575 
576 /*
577  * lift each (extended) induced leading term to a syzygy
578  */
579 static void computeLiftings(const resolvente res, const int index,
580  const std::vector<bool> &variables, const bool use_cache)
581 {
582  if (use_cache)
583  {
584  initialize_cache(res[index-1]->ncols);
585  }
586  lt_struct **hash_previous_module
587  = (lt_struct **)omAlloc((res[index-1]->rank+1)*sizeof(lt_struct *));
588  initialize_hash(hash_previous_module, res[index-1]);
589  for (int j = res[index]->ncols-1; j >= 0; j--)
590  {
591  res[index]->m[j]->next->next = lift_ext_LT(res[index]->m[j],
592  res[index-1], variables, hash_previous_module, use_cache);
593  }
594  for (int i = 0; i <= res[index-1]->rank; i++)
595  {
596  omfree(hash_previous_module[i]);
597  }
598  omFree(hash_previous_module);
599  if (use_cache)
600  {
601  delete_cache(res[index-1]->ncols);
602  }
603 }
604 
605 /*
606  * check if the monomial m contains any of the variables set to false
607  */
608 static inline bool contains_unused_variable(const poly m,
609  const std::vector<bool> &variables)
610 {
611  const ring R = currRing;
612  for (int j = R->N; j > 0; j--)
613  {
614  if (!variables[j-1] && p_GetExp(m, j, R) > 0)
615  {
616  return true;
617  }
618  }
619  return false;
620 }
621 
622 /*
623  * delete any term in res[index] which contains any of the variables set to
624  * false
625  */
626 static void delete_variables(resolvente res, const int index,
627  const std::vector<bool> &variables)
628 {
629  for (int i = 0; i < res[index]->ncols; i++)
630  {
631  poly p_iter = res[index]->m[i]->next;
632  if (p_iter != NULL)
633  {
634  while (p_iter->next != NULL)
635  {
636  if (contains_unused_variable(p_iter->next, variables))
637  {
638  pLmDelete(&p_iter->next);
639  } else {
640  pIter(p_iter);
641  }
642  }
643  }
644  }
645 }
646 
647 static void delete_tails(resolvente res, const int index)
648 {
649  const ring r = currRing;
650  for (int i = 0; i < res[index]->ncols; i++)
651  {
652  if (res[index]->m[i] != NULL)
653  {
654  p_Delete(&(res[index]->m[i]->next), r);
655  }
656  }
657 }
658 
659 /*
660  * for each step in the resolution, compute the corresponding module until
661  * either index == max_index is reached or res[index] is the zero module
662  */
663 static int computeResolution_iteration(resolvente res, const int max_index,
664  syzHeadFunction *syzHead, const bool do_lifting,
665  const bool single_module, const bool use_cache,
666  const bool use_tensor_trick, std::vector<bool> &variables)
667 {
668  int index = 1;
669  while (!idIs0(res[index]))
670  {
671  if (do_lifting)
672  {
673  computeLiftings(res, index, variables, use_cache);
674  if (single_module)
675  {
676  delete_tails(res, index-1);
677  }
678  // we don't know if the input is a reduced SB:
679  if (index == 1)
680  {
681  variables[currRing->N] = false;
682  }
683  update_variables(variables, res[index]);
684  if (use_tensor_trick)
685  {
686  delete_variables(res, index, variables);
687  }
688  }
689  if (index >= max_index) { break; }
690  index++;
691  res[index] = computeFrame(res[index-1], syzM_i_sorted, syzHead);
692  }
693  return index;
694 }
695 
696 /*
697  * compute the frame of the first syzygy module and set variables, then call
698  * computeResolution_iteration() for the remaining steps
699  */
700 static int computeResolution(resolvente res, const int max_index,
701  syzHeadFunction *syzHead, const bool do_lifting,
702  const bool single_module, const bool use_cache,
703  const bool use_tensor_trick)
704 {
705  if (idIs0(res[0]))
706  {
707  return 1;
708  }
709  std::vector<bool> variables;
710  variables.resize(currRing->N+1, true);
711  if (do_lifting)
712  {
713  update_variables(variables, res[0]);
714  if (use_tensor_trick)
715  {
716  delete_variables(res, 0, variables);
717  }
718  }
719  int index = 0;
720  if (max_index > 0)
721  {
722  res[1] = computeFrame(res[0], syzM_i_unsorted, syzHead);
723  index = computeResolution_iteration(res, max_index, syzHead,
724  do_lifting, single_module, use_cache, use_tensor_trick,
725  variables);
726  }
727  variables.clear();
728  return index+1;
729 }
730 
731 static void set_options(syzHeadFunction **syzHead_ptr, bool *do_lifting_ptr,
732  bool *single_module_ptr, const char *method)
733 {
734  if (strcmp(method, "complete") == 0)
735  { // default
736  *syzHead_ptr = syzHeadExtFrame;
737  *do_lifting_ptr = true;
738  *single_module_ptr = false;
739  }
740  else if (strcmp(method, "frame") == 0)
741  {
742  *syzHead_ptr = syzHeadFrame;
743  *do_lifting_ptr = false;
744  *single_module_ptr = false;
745  }
746  else if (strcmp(method, "extended frame") == 0)
747  {
748  *syzHead_ptr = syzHeadExtFrame;
749  *do_lifting_ptr = false;
750  *single_module_ptr = false;
751  }
752  else if (strcmp(method, "single module") == 0)
753  {
754  *syzHead_ptr = syzHeadExtFrame;
755  *do_lifting_ptr = true;
756  *single_module_ptr = true;
757  }
758  else { // "linear strand" (not yet implemented)
759  *syzHead_ptr = syzHeadExtFrame;
760  *do_lifting_ptr = true;
761  *single_module_ptr = false;
762  }
763 }
764 
765 /*
766  * insert the first term of r at the right place
767  */
768 #define insert_first_term(r, p, q, R) \
769 do \
770 { \
771  p = r; \
772  q = p->next; \
773  if (q != NULL && p_LmCmp(p, q, R) != 1) { \
774  while (q->next != NULL && p_LmCmp(p, q->next, R) == -1) { \
775  pIter(q); \
776  } \
777  r = p->next; \
778  p->next = q->next; \
779  q->next = p; \
780  } \
781 } \
782 while (0)
783 
784 /*
785  * For each poly in the resolution, insert the first two terms at their right
786  * places. If single_module is true, then only consider the last module.
787  */
788 static void insert_ext_induced_LTs(const resolvente res, const int length,
789  const bool single_module)
790 {
791  const ring R = currRing;
792  poly p, q;
793  int index = (single_module ? length-1 : 1);
794  while (index < length && !idIs0(res[index]))
795  {
796  for (int j = res[index]->ncols-1; j >= 0; j--)
797  {
798  insert_first_term(res[index]->m[j]->next, p, q, R);
799  insert_first_term(res[index]->m[j], p, q, R);
800  }
801  index++;
802  }
803 }
804 
805 /*
806  * Compute the Schreyer resolution of arg, see reference at the beginning of
807  * this file.
808  *
809  * If use_cache == true (default), the result of compute_image() is cached for
810  * _every_ term in the current step of the resolution. This corresponds to the
811  * subtree attached to the node which represents this term, see reference.
812  *
813  * If use_tensor_trick == true, the current module is modfied after each
814  * lifting step in the resolution: any term which contains a variable which
815  * does not appear among the (induced) leading terms is deleted. Note that the
816  * resulting object is not necessarily a complex anymore. However, constant
817  * entries remain exactly the same. This option does not apply for
818  * method == "frame" and method "extended frame".
819  *
820  * These two options are used in PrymGreen.jl; do not delete!
821  */
822 syStrategy syFrank(const ideal arg, const int length, const char *method,
823  const bool use_cache, const bool use_tensor_trick)
824 {
826  resolvente res = (resolvente)omAlloc0((length+1)*sizeof(ideal));
827  if (strcmp(method, "frame") != 0)
828  {
829  res[0] = id_Copy(arg, currRing);
830  }
831  else
832  {
833  res[0] = id_Head(arg, currRing);
834  }
835  syzHeadFunction *syzHead;
836  bool do_lifting;
837  bool single_module;
838  set_options(&syzHead, &do_lifting, &single_module, method);
839  int new_length = computeResolution(res, length-1, syzHead, do_lifting,
840  single_module, use_cache, use_tensor_trick);
841  if (new_length < length)
842  {
843  res = (resolvente)omReallocSize(res, (length+1)*sizeof(ideal),
844  (new_length+1)*sizeof(ideal));
845  }
846  if (strcmp(method, "frame") != 0)
847  {
848  insert_ext_induced_LTs(res, new_length, single_module);
849  }
850  result->fullres = res;
851  result->length = new_length;
852  result->list_length = new_length;
853  return result;
854 }
855 
int status int void size_t count
Definition: si_signals.h:59
int length
Definition: syz.h:60
static void update_variables(std::vector< bool > &variables, const ideal L)
Definition: syz4.cc:21
#define __p_GetComp(p, r)
Definition: monomials.h:63
static void delete_tails(resolvente res, const int index)
Definition: syz4.cc:647
static int variables
#define p_MemSum_LengthGeneral(r, s1, s2, length)
Definition: p_MemAdd.h:86
const CanonicalForm int s
Definition: facAbsFact.cc:55
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
int j
Definition: facHensel.cc:105
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
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
Definition: int_poly.h:33
#define LIKELY(X)
Definition: auxiliary.h:417
static ideal idConcat(const ideal *M, const int size, const int rank)
Definition: syz4.cc:474
Compatiblity layer for legacy polynomial operations (over currRing)
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of &#39;a&#39; and &#39;b&#39;; replacement of &#39;a&#39; by the product a*b
Definition: coeffs.h:641
ideal id_Copy(ideal h1, const ring r)
copy an ideal
omBin sip_sideal_bin
Definition: simpleideals.cc:27
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:246
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:663
ideal syzM_i_Function(ideal, int, syzHeadFunction)
Definition: syz4.cc:407
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
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1455
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
BOOLEAN p_New(leftv res, leftv args)
Definition: cohomo.cc:4952
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:203
int k
Definition: cfEzgcd.cc:92
static poly syzHeadExtFrame(const ideal G, const int i, const int j)
Definition: syz4.cc:380
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 bool check_variables(const std::vector< bool > &variables, const poly m)
Definition: syz4.cc:49
static TreeM * G
Definition: janet.cc:31
#define omAlloc(size)
Definition: omAllocDecl.h:210
ideal p_b(ideal h, poly a)
Definition: cohomo.cc:1691
#define UNLIKELY(X)
Definition: auxiliary.h:418
static void p_LmFree(poly p, ring)
Definition: p_polys.h:682
static ideal syzM_i_unsorted(const ideal G, const int i, syzHeadFunction *syzHead)
Definition: syz4.cc:414
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:811
syStrategy syFrank(const ideal arg, const int length, const char *method, const bool use_cache, const bool use_tensor_trick)
Definition: syz4.cc:822
static void insert_into_cache_term(cache_term *T, const poly multiplier, const poly p)
Definition: syz4.cc:253
static void initialize_cache(const int size)
Definition: syz4.cc:232
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition: Cache.h:68
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
static int compare_Mi(const void *a, const void *b)
Definition: syz4.cc:536
poly lt
Definition: syz4.cc:75
unsigned long comp
Definition: syz4.cc:77
#define pIter(p)
Definition: monomials.h:37
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:1689
#define omReallocSize(addr, o_size, size)
Definition: omAllocDecl.h:220
#define M
Definition: sirandom.c:24
CanonicalForm b
Definition: cfModGcd.cc:4044
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:824
static void delete_cache(const int size)
Definition: syz4.cc:237
static poly syzHeadFrame(const ideal G, const int i, const int j)
Definition: syz4.cc:356
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:577
CanonicalForm res
Definition: facAbsFact.cc:64
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:468
#define omFree(addr)
Definition: omAllocDecl.h:261
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:103
static void insert_ext_induced_LTs(const resolvente res, const int length, const bool single_module)
Definition: syz4.cc:788
static ideal syzM_i_sorted(const ideal G, const int i, syzHeadFunction *syzHead)
Definition: syz4.cc:448
static bool contains_unused_variable(const poly m, const std::vector< bool > &variables)
Definition: syz4.cc:608
ideal p_a(ideal h)
Definition: cohomo.cc:1574
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:96
#define omfree(addr)
Definition: omAllocDecl.h:237
static void p_MemAdd_NegWeightAdjust(poly p, const ring r)
Definition: p_polys.h:1227
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1828
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1496
int m
Definition: cfEzgcd.cc:121
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
static int si_max(const int a, const int b)
Definition: auxiliary.h:138
int i
Definition: cfEzgcd.cc:125
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:913
static void computeLiftings(const resolvente res, const int index, const std::vector< bool > &variables, const bool use_cache)
Definition: syz4.cc:579
poly syzHeadFunction(ideal, int, int)
Definition: syz4.cc:351
static unsigned pLength(poly a)
Definition: p_polys.h:191
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
resolvente fullres
Definition: syz.h:57
static cache_term * Cache
Definition: syz4.cc:230
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
static void delete_variables(resolvente res, const int index, const std::vector< bool > &variables)
Definition: syz4.cc:626
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:856
static int compare_lex(const poly p_a, const poly p_b)
Definition: syz4.cc:517
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4687
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1409
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:487
static void id_DelDiv_no_test(ideal id)
Definition: syz4.cc:326
static poly find_reducer(const poly multiplier, const poly t, const lt_struct *const *const hash_previous_module)
Definition: syz4.cc:118
#define omalloc(size)
Definition: omAllocDecl.h:228
#define NULL
Definition: omList.c:12
CanonicalForm head(const CanonicalForm &f)
#define omalloc0(size)
Definition: omAllocDecl.h:229
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
static void initialize_hash(lt_struct **C, const ideal L)
Definition: syz4.cc:80
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:615
#define insert_first_term(r, p, q, R)
Definition: syz4.cc:768
#define R
Definition: sirandom.c:26
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
int int ncols
Definition: cf_linsys.cc:32
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
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:700
static int compare_comp(const poly p_a, const poly p_b)
Definition: syz4.cc:501
static ideal computeFrame(const ideal G, syzM_i_Function syzM_i, syzHeadFunction *syzHead)
Definition: syz4.cc:554
std::map< poly, poly, cache_compare > cache_term
Definition: syz4.cc:228
#define pNext(p)
Definition: monomials.h:36
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff &#39;a&#39; and &#39;b&#39; represent the same number; they may have different representations.
Definition: coeffs.h:460
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
static int compare_deg(const poly p_a, const poly p_b)
Definition: syz4.cc:509
short list_length
Definition: syz.h:62
#define pSetCoeff0(p, n)
Definition: monomials.h:59
#define p_GetCoeff(p, r)
Definition: monomials.h:50
ideal * resolvente
Definition: ideals.h:18
static poly get_from_cache_term(const cache_term::const_iterator itr, const poly multiplier)
Definition: syz4.cc:260
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:60
unsigned long sev
Definition: syz4.cc:76
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:455
static void set_options(syzHeadFunction **syzHead_ptr, bool *do_lifting_ptr, bool *single_module_ptr, const char *method)
Definition: syz4.cc:731
int p
Definition: cfModGcd.cc:4019
static jList * T
Definition: janet.cc:30
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:891
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
bool operator()(const poly &l, const poly &r) const
Definition: syz4.cc:218
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1255
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:275
#define omAlloc0(size)
Definition: omAllocDecl.h:211
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:93
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
ssyStrategy * syStrategy
Definition: syz.h:35
ListNode * next
Definition: janet.h:31