Changeset 1102dd in git

Timestamp:

Feb 2, 2018, 1:50:34 PM (6 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '4a9821a93ffdc22a6696668bd4f6b8c9de3e6c5f')

Children:

7f0617292f0c36c3841f1264376b57d9b114c5f2

Parents:

eb4ae817a42927ba2ac7a0273e69d1d14a2958099b67d65cca6ba85b6bbd058c2032a7592d15660f

git-author:

Hans Schoenemann <hannes@mathematik.uni-kl.de>2018-02-02 13:50:34+01:00

git-committer:

GitHub <noreply@github.com>2018-02-02 13:50:34+01:00

Message:

Merge pull request #849 from steenpass/fres

update fres()

Files:

• Singular/iparith.cc (modified) (1 diff)
• doc/reference.doc (modified) (previous)
• kernel/GBEngine/syz.h (modified) (1 diff)
• kernel/GBEngine/syz4.cc (modified) (17 diffs)
• libpolys/coeffs/ffields.cc (modified) (2 diffs)

Singular/iparith.cc

@@ -2222 +2222 @@
     if (strcmp(method, "complete") != 0
             && strcmp(method, "frame") != 0
-            && strcmp(method, "extended frame") != 0) {
+            && strcmp(method, "extended frame") != 0
+            && strcmp(method, "single module") != 0) {
         WerrorS("wrong optional argument for fres");
     }

kernel/GBEngine/syz.h

@@ -99 +99 @@
 syStrategy syKosz(ideal arg,int * length);
 
-syStrategy syFrank(const ideal arg, const int length, const char *method);
+// use_cache and use_tensor_trick are needed in PrymGreen.jl; do not delete!
+syStrategy syFrank(const ideal arg, const int length, const char *method,
+        const bool use_cache = true, const bool use_tensor_trick = false);
 
 void syKillComputation(syStrategy syzstr, ring r=currRing);

kernel/GBEngine/syz4.cc

@@ -15 +15 @@
 #include <vector>
 #include <map>
-
-/*
- * If set to true, the result of compute_image() is cached for _every_ term in
- * the current step of the resolution. This corresponds to the subtree attached
- * to the node which represents this term, see reference.
- */
-#define CACHE 1
 
 /*
@@ -50 +43 @@
  * used to determine lower order terms.
  */
-static inline bool check_variables(const std::vector<bool> variables,
+static inline bool check_variables(const std::vector<bool> &variables,
         const poly m)
 {
@@ -144 +137 @@
 }
 
-#if CACHE
 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);
-#else
+
 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);
-#define traverse_tail compute_image
-#endif   // CACHE
+        const lt_struct *const *const hash_previous_module,
+        const bool use_cache);
 
 /*
@@ -160 +151 @@
 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 lt_struct *const *const hash_previous_module,
+        const bool use_cache)
 {
     poly s = find_reducer(multiplier, term, hash_previous_module);
@@ -168 +160 @@
     const ring r = currRing;
     const int c = __p_GetComp(s, r) - 1;
-    const poly t = traverse_tail(s, c, previous_module, variables,
-            hash_previous_module);
+    poly t;
+    if (use_cache) {
+        t = traverse_tail(s, c, previous_module, variables,
+                hash_previous_module);
+    } else {
+        t = compute_image(s, c, previous_module, variables,
+                hash_previous_module, false);
+    }
     return p_Add_q(s, t, r);
 }
@@ -179 +177 @@
 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 lt_struct *const *const hash_previous_module,
+        const bool use_cache)
 {
     const poly tail = previous_module->m[comp]->next;
@@ -188 +187 @@
     for (poly p = tail; p != NULL; p = pNext(p)) {
         const poly rt = reduce_term(multiplier, p, previous_module, variables,
-                hash_previous_module);
+                hash_previous_module, use_cache);
         sBucket_Add_p(sum, rt, pLength(rt));
     }
@@ -198 +197 @@
 }
 
-#if CACHE
 struct cache_compare
 {
@@ -267 +265 @@
     }
     poly p = compute_image(multiplier, comp, previous_module, variables,
-            hash_previous_module);
+            hash_previous_module, true);
     insert_into_cache_term(T, multiplier, p);
     return p;
 }
-#endif   // CACHE
 
 /*
@@ -278 +275 @@
 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 lt_struct *const *const hash_previous_module,
+        const bool use_cache)
 {
     const ring R = currRing;
     // the leading term does not need to be cached
     poly t1 = compute_image(a, __p_GetComp(a, R)-1, previous_module, variables,
-            hash_previous_module);
-    poly t2 = traverse_tail(a->next, __p_GetComp(a->next, R)-1,
-            previous_module, variables, hash_previous_module);
+            hash_previous_module, use_cache);
+    poly t2;
+    if (use_cache) {
+        t2 = traverse_tail(a->next, __p_GetComp(a->next, R)-1,
+                previous_module, variables, hash_previous_module);
+    } else {
+        t2 = compute_image(a->next, __p_GetComp(a->next, R)-1,
+                previous_module, variables, hash_previous_module, false);
+    }
     t1 = p_Add_q(t1, t2, R);
     return t1;
@@ -527 +531 @@
  */
 static void computeLiftings(const resolvente res, const int index,
-        std::vector<bool> &variables)
-{
-    update_variables(variables, res[index-1]);
-    if (index == 2) {   // we don't know if the input is a reduced SB
-        variables[currRing->N] = false;
-    }
-#if CACHE
-    initialize_cache(res[index-1]->ncols);
-#endif   // CACHE
+        const std::vector<bool> &variables, const bool use_cache)
+{
+    if (use_cache) {
+        initialize_cache(res[index-1]->ncols);
+    }
     lt_struct **hash_previous_module
         = (lt_struct **)omAlloc((res[index-1]->rank+1)*sizeof(lt_struct *));
@@ -541 +541 @@
     for (int j = res[index]->ncols-1; j >= 0; j--) {
         res[index]->m[j]->next->next = lift_ext_LT(res[index]->m[j],
-                res[index-1], variables, hash_previous_module);
+                res[index-1], variables, hash_previous_module, use_cache);
     }
     for (int i = 0; i <= res[index-1]->rank; i++) {
@@ -547 +547 @@
     }
     omFree(hash_previous_module);
-#if CACHE
-    delete_cache(res[index-1]->ncols);
-#endif   // CACHE
+    if (use_cache) {
+        delete_cache(res[index-1]->ncols);
+    }
+}
+
+/*
+ * check if the monomial m contains any of the variables set to false
+ */
+static inline bool contains_unused_variable(const poly m,
+    const std::vector<bool> &variables)
+{
+    const ring R = currRing;
+    for (int j = R->N; j > 0; j--) {
+        if (!variables[j-1] && p_GetExp(m, j, R) > 0) {
+            return true;
+        }
+    }
+    return false;
+}
+
+/*
+ * delete any term in res[index] which contains any of the variables set to
+ * false
+ */
+static void delete_variables(resolvente res, const int index,
+    const std::vector<bool> &variables)
+{
+    for (int i = 0; i < res[index]->ncols; i++) {
+        poly p_iter = res[index]->m[i]->next;
+        if (p_iter != NULL) {
+            while (p_iter->next != NULL) {
+                if (contains_unused_variable(p_iter->next, variables)) {
+                    pLmDelete(&p_iter->next);
+                } else {
+                    pIter(p_iter);
+                }
+            }
+        }
+    }
+}
+
+static void delete_tails(resolvente res, const int index)
+{
+    const ring r = currRing;
+    for (int i = 0; i < res[index]->ncols; i++) {
+        if (res[index]->m[i] != NULL) {
+            p_Delete(&(res[index]->m[i]->next), r);
+        }
+    }
 }
 
@@ -556 +602 @@
  * either index == max_index is reached or res[index] is the zero module
  */
+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)
+{
+    int index = 1;
+    while (!idIs0(res[index])) {
+        if (do_lifting) {
+            computeLiftings(res, index, variables, use_cache);
+            if (single_module) {
+                delete_tails(res, index-1);
+            }
+            // we don't know if the input is a reduced SB:
+            if (index == 1) {
+                variables[currRing->N] = false;
+            }
+            update_variables(variables, res[index]);
+            if (use_tensor_trick) {
+                delete_variables(res, index, variables);
+            }
+        }
+        if (index >= max_index) { break; }
+        index++;
+        res[index] = computeFrame(res[index-1], syzM_i_sorted, syzHead);
+    }
+    return index;
+}
+
+/*
+ * compute the frame of the first syzygy module and set variables, then call
+ * computeResolution_iteration() for the remaining steps
+ */
 static int computeResolution(resolvente res, const int max_index,
-        syzHeadFunction *syzHead, const bool do_lifting)
-{
+        syzHeadFunction *syzHead, const bool do_lifting,
+        const bool single_module, const bool use_cache,
+        const bool use_tensor_trick)
+{
+    if (idIs0(res[0])) {
+        return 1;
+    }
+    std::vector<bool> variables;
+    variables.resize(currRing->N+1, true);
+    if (do_lifting) {
+        update_variables(variables, res[0]);
+        if (use_tensor_trick) {
+            delete_variables(res, 0, variables);
+        }
+    }
     int index = 0;
-    if (!idIs0(res[0]) && 0 < max_index) {
-        index++;
+    if (max_index > 0) {
         res[1] = computeFrame(res[0], syzM_i_unsorted, syzHead);
-        std::vector<bool> variables;
-        variables.resize(currRing->N+1, true);
-        while (!idIs0(res[index])) {
-            if (do_lifting) {
-                computeLiftings(res, index, variables);
-            }
-            if (index >= max_index) { break; }
-            index++;
-            res[index] = computeFrame(res[index-1], syzM_i_sorted, syzHead);
-        }
-        variables.clear();
-    }
+        index = computeResolution_iteration(res, max_index, syzHead,
+                do_lifting, single_module, use_cache, use_tensor_trick,
+                variables);
+    }
+    variables.clear();
     return index+1;
 }
 
 static void set_options(syzHeadFunction **syzHead_ptr, bool *do_lifting_ptr,
-        const char *method)
+        bool *single_module_ptr, const char *method)
 {
     if (strcmp(method, "complete") == 0) {   // default
         *syzHead_ptr = syzHeadExtFrame;
         *do_lifting_ptr = true;
+        *single_module_ptr = false;
     }
     else if (strcmp(method, "frame") == 0) {
         *syzHead_ptr = syzHeadFrame;
         *do_lifting_ptr = false;
+        *single_module_ptr = false;
     }
     else if (strcmp(method, "extended frame") == 0) {
         *syzHead_ptr = syzHeadExtFrame;
         *do_lifting_ptr = false;
+        *single_module_ptr = false;
+    }
+    else if (strcmp(method, "single module") == 0) {
+        *syzHead_ptr = syzHeadExtFrame;
+        *do_lifting_ptr = true;
+        *single_module_ptr = true;
     }
     else {   // "linear strand" (not yet implemented)
         *syzHead_ptr = syzHeadExtFrame;
         *do_lifting_ptr = true;
+        *single_module_ptr = false;
     }
 }
@@ -619 +711 @@
 
 /*
- * for each poly in the resolution, insert the first two terms at their right
- * places
- */
-static void insert_ext_induced_LTs(const resolvente res, const int length)
+ * For each poly in the resolution, insert the first two terms at their right
+ * places. If single_module is true, then only consider the last module.
+ */
+static void insert_ext_induced_LTs(const resolvente res, const int length,
+        const bool single_module)
 {
     const ring R = currRing;
     poly p, q;
-    for (int i = length-2; i > 0; i--) {
-        for (int j = res[i]->ncols-1; j >= 0; j--) {
-            insert_first_term(res[i]->m[j]->next, p, q, R);
-            insert_first_term(res[i]->m[j], p, q, R);
-        }
-    }
-}
-
-/*
- * compute the Schreyer resolution of arg, see reference at the beginning of
- * this file
- */
-syStrategy syFrank(const ideal arg, const int length, const char *method)
+    int index = (single_module ? length-1 : 1);
+    while (index < length && !idIs0(res[index])) {
+        for (int j = res[index]->ncols-1; j >= 0; j--) {
+            insert_first_term(res[index]->m[j]->next, p, q, R);
+            insert_first_term(res[index]->m[j], p, q, R);
+        }
+        index++;
+    }
+}
+
+/*
+ * Compute the Schreyer resolution of arg, see reference at the beginning of
+ * this file.
+ *
+ * If use_cache == true (default), the result of compute_image() is cached for
+ * _every_ term in the current step of the resolution. This corresponds to the
+ * subtree attached to the node which represents this term, see reference.
+ *
+ * If use_tensor_trick == true, the current module is modfied after each
+ * lifting step in the resolution: any term which contains a variable which
+ * does not appear among the (induced) leading terms is deleted. Note that the
+ * resulting object is not necessarily a complex anymore. However, constant
+ * entries remain exactly the same. This option does not apply for
+ * method == "frame" and method "extended frame".
+ *
+ * These two options are used in PrymGreen.jl; do not delete!
+ */
+syStrategy syFrank(const ideal arg, const int length, const char *method,
+        const bool use_cache, const bool use_tensor_trick)
 {
     syStrategy result = (syStrategy)omAlloc0(sizeof(ssyStrategy));
@@ -649 +758 @@
     syzHeadFunction *syzHead;
     bool do_lifting;
-    set_options(&syzHead, &do_lifting, method);
-    int new_length = computeResolution(res, length-1, syzHead, do_lifting);
+    bool single_module;
+    set_options(&syzHead, &do_lifting, &single_module, method);
+    int new_length = computeResolution(res, length-1, syzHead, do_lifting,
+            single_module, use_cache, use_tensor_trick);
     if (new_length < length) {
         res = (resolvente)omReallocSize(res, (length+1)*sizeof(ideal),
@@ -656 +767 @@
     }
     if (strcmp(method, "frame") != 0) {
-        insert_ext_induced_LTs(res, new_length);
+        insert_ext_induced_LTs(res, new_length, single_module);
     }
     result->fullres = res;

libpolys/coeffs/ffields.cc

@@ -807 +807 @@
   if (n==n_GF) {
     GFInfo* p = (GFInfo *)(parameter);
-    int c = pow (p->GFChar, p->GFDegree);
+    int c = (int)pow ((double)p->GFChar, (double)p->GFDegree);
     if ((c == r->m_nfCharQ) && (strcmp(n_ParameterNames(r)[0], p->GFPar_name) == 0))
       return TRUE;
@@ -928 +928 @@
   }
 
-  int c = pow (p->GFChar, p->GFDegree);
+  int c = (int)pow ((double)p->GFChar, (double)p->GFDegree);
 
   nfReadTable(c, r);