source: git/kernel/tgb_internal.h @ 5925be

spielwiese
Last change on this file since 5925be was 542228, checked in by Michael Brickenstein <bricken@…>, 18 years ago
*bricken: again HAVE_BOOST git-svn-id: file:///usr/local/Singular/svn/trunk@9293 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.44 2006-07-07 10:17:04 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    virtual ~slimgb_alg();
104#ifndef HAVE_BOOST
105#ifdef USE_STDVECBOOL
106  vector<vector<bool> > states;
107#else
108  char** states;
109#endif
110#else
111  vector<dynamic_bitset<> > states;
112#endif
113  ideal add_later;
114  ideal S;
115  ring r;
116  int* lengths;
117  wlen_type* weighted_lengths;
118  long* short_Exps;
119  kStrategy strat;
120  int* T_deg;
121  int* T_deg_full;
122  poly tmp_lm;
123  poly* tmp_pair_lm;
124  sorted_pair_node** tmp_spn;
125  poly* expandS;
126  poly* gcd_of_terms;
127  int_pair_node* soon_free;
128  sorted_pair_node** apairs;
129  #if 0
130  BOOLEAN* modifiedS;
131  #endif
132  #ifdef TGB_RESORT_PAIRS
133  bool* replaced;
134  #endif
135  poly_list_node* to_destroy;
136  //for F4
137  mp_array_list* F;
138  poly_array_list* F_minus;
139
140  //end for F4
141#ifdef HEAD_BIN
142  struct omBin_s*   HeadBin;
143#endif
144  unsigned int reduction_steps;
145  int n;
146  //! array_lengths should be greater equal n;
147  int syz_comp;
148  int array_lengths; 
149  int normal_forms;
150  int current_degree;
151  int Rcounter;
152  int last_index;
153  int max_pairs;
154  int pair_top;
155  int easy_product_crit;
156  int extended_product_crit;
157  int average_length;
158  int lastDpBlockStart;
159  BOOLEAN isDifficultField;
160  BOOLEAN completed;
161  BOOLEAN is_homog;
162 
163  BOOLEAN eliminationProblem;
164  BOOLEAN F4_mode;
165  BOOLEAN nc;
166  #ifdef TGB_RESORT_PAIRS
167  BOOLEAN used_b;
168  #endif
169};
170class red_object{
171 public:
172  kBucket_pt bucket;
173  poly p;
174  unsigned long sev;
175  void flatten();
176  void validate();
177  wlen_type initial_quality;
178  void adjust_coefs(number c_r, number c_ac_r);
179  wlen_type guess_quality(slimgb_alg* c);
180  int clear_to_poly();
181  void canonicalize();
182};
183
184
185enum calc_state
186  {
187    UNCALCULATED,
188    HASTREP//,
189    //UNIMPORTANT,
190    //SOONTREP
191  };
192static BOOLEAN pair_cmp(sorted_pair_node* a,sorted_pair_node* b);
193template <class len_type, class set_type>  int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set);
194static int add_to_reductors(slimgb_alg* c, poly h, int len, BOOLEAN simplified=FALSE);
195static int bucket_guess(kBucket* bucket);
196static poly redNFTail (poly h,const int sl,kStrategy strat, int len);
197static poly redNF2 (poly h,slimgb_alg* c , int &len, number&  m,int n=0);
198void free_sorted_pair_node(sorted_pair_node* s, ring r);
199static void shorten_tails(slimgb_alg* c, poly monom);
200static void replace_pair(int & i, int & j, slimgb_alg* c);
201//static sorted_pair_node** add_to_basis(poly h, int i, int j,slimgb_alg* c, int* ip=NULL);
202static void do_this_spoly_stuff(int i,int j,slimgb_alg* c);
203//ideal t_rep_gb(ring r,ideal arg_I);
204static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state);
205static int* make_connections(int from, poly bound, slimgb_alg* c);
206static int* make_connections(int from, int to, poly bound, slimgb_alg* c);
207void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c);
208static void soon_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c);
209static int pLcmDeg(poly a, poly b);
210static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen);
211static BOOLEAN find_next_pair(slimgb_alg* c, BOOLEAN go_higher=TRUE);
212
213static sorted_pair_node* pop_pair(slimgb_alg* c);
214static BOOLEAN no_pairs(slimgb_alg* c);
215void clean_top_of_pair_list(slimgb_alg* c);
216static void super_clean_top_of_pair_list(slimgb_alg* c);
217static BOOLEAN state_is(calc_state state, const int & i, const int & j, slimgb_alg* c);
218static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c=NULL);
219static int tgb_pair_better_gen(const void* ap,const void* bp);
220static poly redTailShort(poly h, kStrategy strat);
221static poly gcd_of_terms(poly p, ring r);
222static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c);
223static poly kBucketGcd(kBucket* b, ring r);
224static void multi_reduction(red_object* los, int & losl, slimgb_alg* c);
225int slim_nsize(number n, ring r);
226sorted_pair_node* quick_pop_pair(slimgb_alg* c);
227sorted_pair_node* top_pair(slimgb_alg* c);
228sorted_pair_node** add_to_basis_ideal_quotient(poly h, slimgb_alg* c, int* ip);//, BOOLEAN new_pairs=TRUE);
229sorted_pair_node**  spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c);
230int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj);
231int tgb_pair_better_gen2(const void* ap,const void* bp);
232int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev);
233//static int quality(poly p, int len, slimgb_alg* c);
234/**
235   makes on each red_object in a region a single_step
236 **/
237class reduction_step{
238 public:
239  /// we assume hat all occuring red_objects have same lm, and all
240  /// occ. lm's in r[l...u] are the same, only reductor does not occur
241  virtual void reduce(red_object* r, int l, int u);
242  //int reduction_id;
243  virtual ~reduction_step();
244  slimgb_alg* c;
245  int reduction_id;
246};
247class simple_reducer:public reduction_step{
248 public:
249  poly p;
250  kBucket_pt fill_back;
251  int p_len;
252  simple_reducer(poly p, int p_len, slimgb_alg* c =NULL){
253    this->p=p;
254    assume(p_len==pLength(p));
255    this->p_len=p_len;
256    this->c=c;
257  }
258  virtual void pre_reduce(red_object* r, int l, int u);
259  virtual void reduce(red_object* r, int l, int u);
260  ~simple_reducer();
261
262
263  virtual void do_reduce(red_object & ro);
264};
265
266//class sum_canceling_reducer:public reduction_step {
267//  void reduce(red_object* r, int l, int u);
268//};
269struct find_erg{
270  poly expand;
271  int expand_length;
272  int to_reduce_u;
273  int to_reduce_l;
274  int reduce_by;//index of reductor
275  BOOLEAN fromS;//else from los
276
277};
278
279static void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c);
280static void finalize_reduction_step(reduction_step* r);
281
282template <class len_type, class set_type>  int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set){
283  //Print("POSHELER:%d",sizeof(wlen_type));
284  int length=strat->sl;
285  int i;
286  int an = 0;
287  int en= length;
288
289  if ((len>setL[length])
290      || ((len==setL[length]) && (pLmCmp(set[length],p)== -1)))
291    return length+1;
292
293  loop
294  {
295    if (an >= en-1)
296    {
297      if ((len<setL[an])
298          || ((len==setL[an]) && (pLmCmp(set[an],p) == 1))) return an;
299      return en;
300    }
301    i=(an+en) / 2;
302    if ((len<setL[i])
303        || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i;
304    //else if ((len>setL[i])
305    //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i;
306    else an=i;
307  }
308
309}
310
311
312static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c);
313wlen_type pELength(poly p, ring r);
314
315#endif
Note: See TracBrowser for help on using the repository browser.