1 /**************************************** 2 * Computer Algebra System SINGULAR * 3 ****************************************/ 4 /* 5 * ABSTRACT: f5gb interface 6 */ 7 #ifndef F5_HEADER 8 #define F5_HEADER 9 10 #ifdef HAVE_F5 11 #include "kernel/GBEngine/f5data.h" 12 #include "kernel/GBEngine/f5lists.h" 13 14 15 /* 16 ====================================================== 17 sort polynomials in ideal i by decreasing total degree 18 ====================================================== 19 */ 20 void qsortDegree(poly* left, poly* right); 21 22 /*! 23 * ====================================================================== 24 * builds the sum of the entries of the exponent vectors, i.e. the degree 25 * of the corresponding monomial 26 * ====================================================================== 27 */ 28 long sumVector(int* v, int k); 29 30 /** 31 ========================================================================== 32 compare monomials, i.e. divisibility tests for criterion 1 and criterion 2 33 ========================================================================== 34 */ 35 bool compareMonomials(int* m1, int** m2, int numberOfRuleOlds); 36 37 38 /* 39 ================================================== 40 computes incrementally gbs of subsets of the input 41 gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} 42 ================================================== 43 */ 44 LList* F5inc(int i, poly f_i, LList* gPrev,LList* reducers, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag, int plus ,int termination); 45 46 /* 47 ================================================================ 48 computes a list of critical pairs for the next reduction process 49 the first element is always "useful" thus the critical pair 50 computed is either "useful" or "useless" depending on the second 51 element which generates the critical pair. 52 first element in gPrev is always the newest element which must 53 build critical pairs with all other elements in gPrev 54 ================================================================ 55 */ 56 void criticalPair(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList, int plus); 57 58 59 bool checkDGB(LList* gPrev); 60 61 62 /* 63 * Arris Check if we are finished after the current degree step: 64 * Checks all remaining critical pairs, i.e. those of higher degree, 65 * by the two Buchberger criteria. 66 * return value: 0, if all remaining critical pairs are deleted by 67 * Buchberger's criteria 68 * 1, otherwise 69 */ 70 bool arrisCheck(CNode* first,LNode* firstGCurr, long arrisdeg); 71 72 /* 73 ================================================================ 74 computes a list of critical pairs for the next reduction process 75 the first element is always "useless" thus the critical pair 76 computed is "useless". 77 first element in gPrev is always the newest element which must 78 build critical pairs with all other elements in gPrev 79 ================================================================ 80 */ 81 void criticalPair2(LList* gPrev, CListOld* critPairs, LTagList* lTag, RTagList* rTag, RList* RuleOlds, PList* rejectedGBList); 82 83 /* 84 ======================================== 85 Criterion 1, i.e. Faugere's F5 Criterion 86 ======================================== 87 */ 88 inline bool criterion1(LList* gPrev, poly t, LNode* l, LTagList* lTag); 89 90 /* 91 ===================================== 92 Criterion 2, i.e. Rewritten Criterion 93 ===================================== 94 */ 95 inline bool criterion2(int idx, poly t, LNode* l, RList* RuleOlds, RTagList* rTag); 96 97 /* 98 ========================================================================================================== 99 Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleOldTested parameter 100 ========================================================================================================== 101 */ 102 inline bool criterion2(poly t, LPolyOld* l, RList* RuleOlds, RuleOld* testedRuleOld); 103 104 /* 105 * check for useful pairs in the given subset of critical pairs 106 */ 107 int computeUsefulMinDeg(CNode* first); 108 109 /* 110 ================================== 111 Computation of S-Polynomials in F5 112 ================================== 113 */ 114 inline void computeSPols(CNode* first, RTagList* rTag, RList* RuleOlds, LList* sPolyList, PList* rejectedGBList); 115 116 /* 117 ======================================================================== 118 reduction including subalgorithm topReduction() using Faugere's criteria 119 ======================================================================== 120 */ 121 inline void reduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, RList* RuleOlds, LTagList* lTag, RTagList* rTag, 122 ideal gbPrev, PList* rejectedGBList, int plus); 123 124 /* 125 ======================================================================== 126 reduction including subalgorithm topReduction() using Faugere's criteria 127 ======================================================================== 128 */ 129 inline void newReduction(LList* sPolyList, CListOld* critPairs, LList* gPrev, LList* reducers, RList* rules, LTagList* lTag, RTagList* rTag, ideal gbPrev, int termination, PList* rejectedGBList, int plus); 130 131 /*! 132 * ================================================================================ 133 * searches for reducers of temp similar to the symbolic preprocessing of F4 and 134 * divides them into a "good" and "bad" part: 135 * 136 * the "good" ones are the reducers which do not corrupt the label of temp, with 137 * these the normal form of temp is computed 138 * 139 * the "bad" ones are the reducers which corrupt the label of temp, they are tested 140 * later on for possible new RuleOlds and S-polynomials to be added to the algorithm 141 * ================================================================================ 142 */ 143 void findReducers(LNode* l, LList* sPolyList, ideal gbPrev, LList* gPrev, LList* reducers, CListOld* critPairs, RList* rules, LTagList* lTag, RTagList* rTag, int termination, PList* rejectedGBList, int plus); 144 145 /* 146 ===================================================================================== 147 top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of 148 the same index whereas the labels are taken into account 149 ===================================================================================== 150 */ 151 inline void topReduction(LNode* l, LList* sPolyList, LList* gPrev, CListOld* critPairs, RList* RuleOlds, LTagList* lTag, RTagList* rTag, ideal gbPrev, PList* rejectedGBList, int plus); 152 153 /* 154 ======================================================================================= 155 merging 2 polynomials p & q without requiring that all monomials of p & q are different 156 if there are equal monomials in p & q only one of these monomials (always that of p!) 157 is taken into account 158 ======================================================================================= 159 160 poly p_MergeEq_q(poly p, poly q, const ring r); 161 */ 162 /* 163 ===================================================================== 164 subalgorithm to find a possible reductor for the labeled polynomial l 165 ===================================================================== 166 */ 167 inline LNode* findReductor(LNode* l, LList* sPolyList, LNode* gPrevRedCheck, LList* gPrev, RList* RuleOlds, LTagList* lTag,RTagList* rTag); 168 169 /* 170 ====================================== 171 main function of our F5 implementation 172 ====================================== 173 */ 174 ideal F5main(ideal i, ring r, int opt, int plus, int termination); 175 176 #endif 177 #endif 178