source: git/kernel/tgb_internal.h @ b055de9

spielwiese
Last change on this file since b055de9 was b055de9, checked in by Michael Brickenstein <bricken@…>, 19 years ago
*bricken: gauss externalized git-svn-id: file:///usr/local/Singular/svn/trunk@8101 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 7.1 KB
Line 
1#ifndef TGB_INTERNAL_H
2#define TGB_INTERNAL_H
3
4#include "mod2.h"
5#include <omalloc.h>
6#include "p_polys.h"
7
8#include "ideals.h"
9#include "ring.h"
10#include "febase.h"
11#include "structs.h"
12#include "polys.h"
13#include "stdlib.h"
14
15
16#include "kutil.h"
17#include "kInline.cc"
18#include "kstd1.h"
19#include "kbuckets.h"
20
21
22
23
24//#define TGB_DEBUG
25#define FULLREDUCTIONS
26#define HANS_IDEA
27//#define HALFREDUCTIONS
28//#define HEAD_BIN
29//#define HOMOGENEOUS_EXAMPLE
30#define REDTAIL_S
31#define PAR_N 100
32#define PAR_N_F4 5000
33#define AC_NEW_MIN 2
34#define AC_FLATTEN 1
35
36//#define FIND_DETERMINISTIC
37//#define REDTAIL_PROT
38//#define QUICK_SPOLY_TEST
39struct sorted_pair_node{
40  //criterium, which is stable 0. small lcm 1. small i 2. small j
41  int i;
42  int j;
43  int deg;
44  int expected_length;
45  poly lcm_of_lm;
46};
47
48
49//static ideal debug_Ideal;
50/**
51    reduction_accumulators are objects which are shared by several sums
52 **/
53
54class reduction_accumulator{
55 
56 public:
57  /// (1/multiplied)*bucket=reduced original data
58  number multiplied;
59  ///the polynomial data
60  kBucket_pt bucket;
61  /// the short exponent vector
62  unsigned long sev;
63  /// the reference counter
64  int counter;
65  /// decrease the reference counter, at 0 it deletes the object
66  void decrease_counter(){ 
67    if((--counter)==0)
68      {
69        delete this; //self destruction
70      }
71  }
72  int last_reduction_id;
73  reduction_accumulator(poly p, int p_len, poly high_to);
74  ~reduction_accumulator(){
75    nDelete(&multiplied);
76    kBucketDeleteAndDestroy(&bucket);
77  } 
78
79 
80};
81struct poly_list_node{
82  poly p;
83  poly_list_node* next;
84};
85struct formal_sum_descriptor{
86  number c_my;
87  number c_ac;
88  reduction_accumulator* ac;
89};
90struct int_pair_node{
91  int_pair_node* next;
92  int a;
93  int b;
94};
95struct monom_poly{
96  poly m;
97  poly f;
98};
99struct mp_array_list{
100  monom_poly* mp;
101  int size;
102  mp_array_list* next;
103};
104
105class mac_poly_r{
106public:
107  number coef;
108  mac_poly_r* next;
109  int exp;
110  mac_poly_r():next(NULL){}
111};
112//mac_polys exp are smaller iff they are greater by monomial ordering
113//corresponding to solving linear equations notation
114
115typedef mac_poly_r* mac_poly;
116
117struct poly_array_list{
118  poly* p;
119  int size;
120  poly_array_list* next;
121};
122struct calc_dat
123{
124  int* rep;
125  char** states;
126  ideal S;
127  ring r;
128  int* lengths;
129  long* short_Exps;
130  kStrategy strat;
131  int* T_deg;
132  int* T_deg_full;
133  poly tmp_lm;
134  poly* tmp_pair_lm;
135  sorted_pair_node** tmp_spn;
136  poly* expandS;
137  poly* gcd_of_terms;
138  int_pair_node* soon_free;
139  sorted_pair_node** apairs;
140  BOOLEAN* modifiedS;
141  poly_list_node* to_destroy;
142  //for F4
143  mp_array_list* F;
144  poly_array_list* F_minus;
145
146  //end for F4
147#ifdef HEAD_BIN
148  struct omBin_s*   HeadBin;
149#endif
150  unsigned int reduction_steps;
151  int n;
152  int normal_forms;
153  int current_degree;
154  int Rcounter;
155  int last_index;
156  int max_pairs;
157  int pair_top;
158  int easy_product_crit;
159  int extended_product_crit;
160  int average_length;
161  BOOLEAN is_char0;
162  BOOLEAN is_homog;
163  BOOLEAN F4_mode;
164};
165class red_object{
166 public:
167  kBucket_pt bucket;
168  poly p;
169  formal_sum_descriptor* sum;
170  unsigned long sev;
171  void flatten();
172  void validate();
173  void adjust_coefs(number c_r, number c_ac_r);
174  int guess_quality(calc_dat* c);
175  int clear_to_poly();
176  void canonicalize();
177};
178
179
180enum calc_state
181  {
182    UNCALCULATED,
183    HASTREP,
184    UNIMPORTANT,
185    SOONTREP
186  };
187
188static int add_to_reductors(calc_dat* c, poly h, int len);
189static int bucket_guess(kBucket* bucket);
190static poly redNFTail (poly h,const int sl,kStrategy strat, int len);
191static poly redNF2 (poly h,calc_dat* c , int &len, number&  m,int n=0);
192static void free_sorted_pair_node(sorted_pair_node* s, ring r);
193static void shorten_tails(calc_dat* c, poly monom);
194static void replace_pair(int & i, int & j, calc_dat* c);
195static sorted_pair_node** add_to_basis(poly h, int i, int j,calc_dat* c, int* ip=NULL);
196static void do_this_spoly_stuff(int i,int j,calc_dat* c);
197//ideal t_rep_gb(ring r,ideal arg_I);
198static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, calc_dat* state);
199static int* make_connections(int from, poly bound, calc_dat* c);
200static int* make_connections(int from, int to, poly bound, calc_dat* c);
201static void now_t_rep(const int & arg_i, const int & arg_j, calc_dat* c);
202static void soon_t_rep(const int & arg_i, const int & arg_j, calc_dat* c);
203static int pLcmDeg(poly a, poly b);
204static int simple_posInS (kStrategy strat, poly p,int len);
205static BOOLEAN find_next_pair(calc_dat* c, BOOLEAN go_higher=TRUE);
206
207static sorted_pair_node* pop_pair(calc_dat* c);
208static BOOLEAN no_pairs(calc_dat* c);
209static void clean_top_of_pair_list(calc_dat* c);
210static void super_clean_top_of_pair_list(calc_dat* c);
211static BOOLEAN state_is(calc_state state, const int & i, const int & j, calc_dat* c);
212static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, calc_dat* c);
213static int pair_better_gen(const void* ap,const void* bp);
214static poly redTailShort(poly h, kStrategy strat);
215static poly gcd_of_terms(poly p, ring r);
216static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, calc_dat* c);
217static poly kBucketGcd(kBucket* b, ring r);
218static void multi_reduction(red_object* los, int & losl, calc_dat* c);
219static sorted_pair_node* quick_pop_pair(calc_dat* c);
220static sorted_pair_node* top_pair(calc_dat* c);
221//static int quality(poly p, int len, calc_dat* c);
222/**
223   makes on each red_object in a region a single_step
224 **/
225class reduction_step{
226 public:
227  /// we assume hat all occuring red_objects have same lm, and all
228  /// occ. lm's in r[l...u] are the same, only reductor does not occur
229  virtual void reduce(red_object* r, int l, int u);
230  //int reduction_id;
231  virtual ~reduction_step();
232  calc_dat* c;
233  int reduction_id;
234};
235class simple_reducer:public reduction_step{
236 public:
237  poly p;
238  kBucket_pt fill_back;
239  int p_len;
240  simple_reducer(poly p, int p_len, calc_dat* c =NULL){
241    this->p=p;
242    assume(p_len==pLength(p));
243    this->p_len=p_len;
244    this->c=c;
245  }
246  virtual void pre_reduce(red_object* r, int l, int u);
247  virtual void reduce(red_object* r, int l, int u);
248  ~simple_reducer();
249
250  virtual void target_is_a_sum_reduce(red_object & ro);
251  virtual void target_is_no_sum_reduce(red_object & ro);
252};
253class join_simple_reducer:public simple_reducer{
254 public:
255  join_simple_reducer(poly p, int p_len, poly high_to):simple_reducer(p,p_len){
256    ac=new reduction_accumulator( p, p_len, high_to);
257   
258   
259  }
260    ~join_simple_reducer();
261   void pre_reduce(red_object* r, int l, int u);
262  void target_is_no_sum_reduce(red_object & ro);
263  reduction_accumulator* ac;
264};
265//class sum_canceling_reducer:public reduction_step {
266//  void reduce(red_object* r, int l, int u);
267//};
268struct find_erg{
269  poly expand;
270  int expand_length;
271  int to_reduce_u;
272  int to_reduce_l;
273  int reduce_by;//index of reductor
274  BOOLEAN fromS;//else from los
275
276};
277
278static void multi_reduce_step(find_erg & erg, red_object* r, calc_dat* c);
279static void finalize_reduction_step(reduction_step* r);
280
281
282
283
284
285
286
287
288mac_poly mac_p_add_ff_qq(mac_poly a, number f,mac_poly b);
289
290void mac_mult_cons(mac_poly p,number c);
291int mac_length(mac_poly p);
292
293//contrary to delete on the mac_poly_r, the coefficients are also destroyed here
294void mac_destroy(mac_poly p);
295
296
297
298#endif
Note: See TracBrowser for help on using the repository browser.