source: git/kernel/tgb_internal.h @ 6e08ad

jengelh-datetimespielwiese
Last change on this file since 6e08ad was 6e08ad, checked in by Michael Brickenstein <bricken@…>, 16 years ago
+ improved initialization process git-svn-id: file:///usr/local/Singular/svn/trunk@9464 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 8.0 KB
Line 
1#ifndef TGB_INTERNAL_H
2#define TGB_INTERNAL_H
3//!\file tgb_internal.h
4/****************************************
5*  Computer Algebra System SINGULAR     *
6****************************************/
7/* $Id: tgb_internal.h,v 1.45 2006-10-25 10:14:52 bricken Exp $ */
8/*
9 * ABSTRACT: tgb internal .h file
10*/
11#include <omalloc.h>
12#include "p_polys.h"
13
14#include "ideals.h"
15#include "ring.h"
16#include "febase.h"
17#include "structs.h"
18#include "polys.h"
19#include "stdlib.h"
20#ifdef HAVE_BOOST_DYNAMIC_BITSET_HPP
21#define  HAVE_BOOST 1
22#endif
23//#define HAVE_BOOST 1
24//#define USE_STDVECBOOL 1
25#ifdef HAVE_BOOST
26#include "boost/dynamic_bitset.hpp"
27#include <vector>
28using boost::dynamic_bitset;
29using std::vector;
30#endif
31#ifdef USE_STDVECBOOL
32#include <vector>
33using std::vector;
34#endif
35#include "kutil.h"
36#include "kInline.cc"
37#include "kstd1.h"
38#include "kbuckets.h"
39
40
41
42
43//#define TGB_DEBUG
44#define FULLREDUCTIONS
45#define HANS_IDEA
46//#define HALFREDUCTIONS
47//#define HEAD_BIN
48//#define HOMOGENEOUS_EXAMPLE
49#define REDTAIL_S
50#define PAR_N 100
51#define PAR_N_F4 5000
52#define AC_NEW_MIN 2
53#define AC_FLATTEN 1
54
55//#define FIND_DETERMINISTIC
56//#define REDTAIL_PROT
57//#define QUICK_SPOLY_TEST
58struct sorted_pair_node{
59  //criterium, which is stable 0. small lcm 1. small i 2. small j
60  wlen_type expected_length;
61  poly lcm_of_lm;
62  int i;
63  int j;
64  int deg;
65 
66 
67};
68
69
70//static ideal debug_Ideal;
71
72
73struct poly_list_node{
74  poly p;
75  poly_list_node* next;
76};
77
78struct int_pair_node{
79  int_pair_node* next;
80  int a;
81  int b;
82};
83struct monom_poly{
84  poly m;
85  poly f;
86};
87struct mp_array_list{
88  monom_poly* mp;
89  int size;
90  mp_array_list* next;
91};
92
93
94struct poly_array_list{
95  poly* p;
96  int size;
97  poly_array_list* next;
98};
99class slimgb_alg
100{
101  public:
102    slimgb_alg(ideal I, int syz_comp,BOOLEAN F4);
103                void introduceDelayedPairs(poly* pa,int s);
104    virtual ~slimgb_alg();
105#ifndef HAVE_BOOST
106#ifdef USE_STDVECBOOL
107  vector<vector<bool> > states;
108#else
109  char** states;
110#endif
111#else
112  vector<dynamic_bitset<> > states;
113#endif
114  ideal add_later;
115  ideal S;
116  ring r;
117  int* lengths;
118  wlen_type* weighted_lengths;
119  long* short_Exps;
120  kStrategy strat;
121  int* T_deg;
122  int* T_deg_full;
123  poly tmp_lm;
124  poly* tmp_pair_lm;
125  sorted_pair_node** tmp_spn;
126  poly* expandS;
127  poly* gcd_of_terms;
128  int_pair_node* soon_free;
129  sorted_pair_node** apairs;
130  #if 0
131  BOOLEAN* modifiedS;
132  #endif
133  #ifdef TGB_RESORT_PAIRS
134  bool* replaced;
135  #endif
136  poly_list_node* to_destroy;
137  //for F4
138  mp_array_list* F;
139  poly_array_list* F_minus;
140
141  //end for F4
142#ifdef HEAD_BIN
143  struct omBin_s*   HeadBin;
144#endif
145  unsigned int reduction_steps;
146  int n;
147  //! array_lengths should be greater equal n;
148  int syz_comp;
149  int array_lengths; 
150  int normal_forms;
151  int current_degree;
152  int Rcounter;
153  int last_index;
154  int max_pairs;
155  int pair_top;
156  int easy_product_crit;
157  int extended_product_crit;
158  int average_length;
159  int lastDpBlockStart;
160  BOOLEAN isDifficultField;
161  BOOLEAN completed;
162  BOOLEAN is_homog;
163 
164  BOOLEAN eliminationProblem;
165  BOOLEAN F4_mode;
166  BOOLEAN nc;
167  #ifdef TGB_RESORT_PAIRS
168  BOOLEAN used_b;
169  #endif
170};
171class red_object{
172 public:
173  kBucket_pt bucket;
174  poly p;
175  unsigned long sev;
176  void flatten();
177  void validate();
178  wlen_type initial_quality;
179  void adjust_coefs(number c_r, number c_ac_r);
180  wlen_type guess_quality(slimgb_alg* c);
181  int clear_to_poly();
182  void canonicalize();
183};
184
185
186enum calc_state
187  {
188    UNCALCULATED,
189    HASTREP//,
190    //UNIMPORTANT,
191    //SOONTREP
192  };
193static BOOLEAN pair_cmp(sorted_pair_node* a,sorted_pair_node* b);
194template <class len_type, class set_type>  int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set);
195static int add_to_reductors(slimgb_alg* c, poly h, int len, BOOLEAN simplified=FALSE);
196static int bucket_guess(kBucket* bucket);
197static poly redNFTail (poly h,const int sl,kStrategy strat, int len);
198static poly redNF2 (poly h,slimgb_alg* c , int &len, number&  m,int n=0);
199void free_sorted_pair_node(sorted_pair_node* s, ring r);
200static void shorten_tails(slimgb_alg* c, poly monom);
201static void replace_pair(int & i, int & j, slimgb_alg* c);
202//static sorted_pair_node** add_to_basis(poly h, int i, int j,slimgb_alg* c, int* ip=NULL);
203static void do_this_spoly_stuff(int i,int j,slimgb_alg* c);
204//ideal t_rep_gb(ring r,ideal arg_I);
205static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state);
206static int* make_connections(int from, poly bound, slimgb_alg* c);
207static int* make_connections(int from, int to, poly bound, slimgb_alg* c);
208void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c);
209static void soon_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c);
210static int pLcmDeg(poly a, poly b);
211static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen);
212static BOOLEAN find_next_pair(slimgb_alg* c, BOOLEAN go_higher=TRUE);
213
214static sorted_pair_node* pop_pair(slimgb_alg* c);
215static BOOLEAN no_pairs(slimgb_alg* c);
216void clean_top_of_pair_list(slimgb_alg* c);
217static void super_clean_top_of_pair_list(slimgb_alg* c);
218static BOOLEAN state_is(calc_state state, const int & i, const int & j, slimgb_alg* c);
219static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c=NULL);
220static int tgb_pair_better_gen(const void* ap,const void* bp);
221static poly redTailShort(poly h, kStrategy strat);
222static poly gcd_of_terms(poly p, ring r);
223static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c);
224static poly kBucketGcd(kBucket* b, ring r);
225static void multi_reduction(red_object* los, int & losl, slimgb_alg* c);
226int slim_nsize(number n, ring r);
227sorted_pair_node* quick_pop_pair(slimgb_alg* c);
228sorted_pair_node* top_pair(slimgb_alg* c);
229sorted_pair_node** add_to_basis_ideal_quotient(poly h, slimgb_alg* c, int* ip);//, BOOLEAN new_pairs=TRUE);
230sorted_pair_node**  spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c);
231int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj);
232int tgb_pair_better_gen2(const void* ap,const void* bp);
233int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev);
234//static int quality(poly p, int len, slimgb_alg* c);
235/**
236   makes on each red_object in a region a single_step
237 **/
238class reduction_step{
239 public:
240  /// we assume hat all occuring red_objects have same lm, and all
241  /// occ. lm's in r[l...u] are the same, only reductor does not occur
242  virtual void reduce(red_object* r, int l, int u);
243  //int reduction_id;
244  virtual ~reduction_step();
245  slimgb_alg* c;
246  int reduction_id;
247};
248class simple_reducer:public reduction_step{
249 public:
250  poly p;
251  kBucket_pt fill_back;
252  int p_len;
253  simple_reducer(poly p, int p_len, slimgb_alg* c =NULL){
254    this->p=p;
255    assume(p_len==pLength(p));
256    this->p_len=p_len;
257    this->c=c;
258  }
259  virtual void pre_reduce(red_object* r, int l, int u);
260  virtual void reduce(red_object* r, int l, int u);
261  ~simple_reducer();
262
263
264  virtual void do_reduce(red_object & ro);
265};
266
267//class sum_canceling_reducer:public reduction_step {
268//  void reduce(red_object* r, int l, int u);
269//};
270struct find_erg{
271  poly expand;
272  int expand_length;
273  int to_reduce_u;
274  int to_reduce_l;
275  int reduce_by;//index of reductor
276  BOOLEAN fromS;//else from los
277
278};
279
280static void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c);
281static void finalize_reduction_step(reduction_step* r);
282
283template <class len_type, class set_type>  int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set){
284  //Print("POSHELER:%d",sizeof(wlen_type));
285  int length=strat->sl;
286  int i;
287  int an = 0;
288  int en= length;
289
290  if ((len>setL[length])
291      || ((len==setL[length]) && (pLmCmp(set[length],p)== -1)))
292    return length+1;
293
294  loop
295  {
296    if (an >= en-1)
297    {
298      if ((len<setL[an])
299          || ((len==setL[an]) && (pLmCmp(set[an],p) == 1))) return an;
300      return en;
301    }
302    i=(an+en) / 2;
303    if ((len<setL[i])
304        || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i;
305    //else if ((len>setL[i])
306    //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i;
307    else an=i;
308  }
309
310}
311
312
313static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c);
314wlen_type pELength(poly p, ring r);
315
316#endif
Note: See TracBrowser for help on using the repository browser.