source: git/kernel/tgb_internal.h @ f4adfcb

jengelh-datetimespielwiese
Last change on this file since f4adfcb was f4adfcb, checked in by Michael Brickenstein <bricken@…>, 18 years ago
*bricken: tgb.h now smaller git-svn-id: file:///usr/local/Singular/svn/trunk@8100 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 8.5 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//#define FIND_DETERMINISTIC
36//#define REDTAIL_PROT
37//#define QUICK_SPOLY_TEST
38struct sorted_pair_node{
39  //criterium, which is stable 0. small lcm 1. small i 2. small j
40  int i;
41  int j;
42  int deg;
43  int expected_length;
44  poly lcm_of_lm;
45};
46
47
48//static ideal debug_Ideal;
49/**
50    reduction_accumulators are objects which are shared by several sums
51 **/
52
53class reduction_accumulator{
54 
55 public:
56  /// (1/multiplied)*bucket=reduced original data
57  number multiplied;
58  ///the polynomial data
59  kBucket_pt bucket;
60  /// the short exponent vector
61  unsigned long sev;
62  /// the reference counter
63  int counter;
64  /// decrease the reference counter, at 0 it deletes the object
65  void decrease_counter(){ 
66    if((--counter)==0)
67      {
68        delete this; //self destruction
69      }
70  }
71  int last_reduction_id;
72  reduction_accumulator(poly p, int p_len, poly high_to);
73  ~reduction_accumulator(){
74    nDelete(&multiplied);
75    kBucketDeleteAndDestroy(&bucket);
76  } 
77
78 
79};
80struct poly_list_node{
81  poly p;
82  poly_list_node* next;
83};
84struct formal_sum_descriptor{
85  number c_my;
86  number c_ac;
87  reduction_accumulator* ac;
88};
89struct int_pair_node{
90  int_pair_node* next;
91  int a;
92  int b;
93};
94struct monom_poly{
95  poly m;
96  poly f;
97};
98struct mp_array_list{
99  monom_poly* mp;
100  int size;
101  mp_array_list* next;
102};
103class tgb_matrix{
104 private:
105  number** n;
106  int columns;
107  int rows;
108  BOOLEAN free_numbers;
109 public:
110  tgb_matrix(int i, int j);
111  ~tgb_matrix();
112  int get_rows();
113  int get_columns();
114  void print();
115  void perm_rows(int i, int j);
116  void set(int i, int j, number n);
117  number get(int i, int j);
118  BOOLEAN is_zero_entry(int i, int j);
119  void free_row(int row, BOOLEAN free_non_zeros=TRUE);
120  int min_col_not_zero_in_row(int row);
121  int next_col_not_zero(int row,int pre);
122  BOOLEAN zero_row(int row);
123  void mult_row(int row,number factor);
124  void add_lambda_times_row(int add_to,int summand,number factor);
125  int non_zero_entries(int row);
126};
127class mac_poly_r{
128public:
129  number coef;
130  mac_poly_r* next;
131  int exp;
132  mac_poly_r():next(NULL){}
133};
134//mac_polys exp are smaller iff they are greater by monomial ordering
135//corresponding to solving linear equations notation
136
137typedef mac_poly_r* mac_poly;
138class tgb_sparse_matrix{
139 private:
140  ring r;
141  mac_poly* mp;
142  int columns;
143  int rows;
144  BOOLEAN free_numbers;
145 public:
146  void sort_rows();
147  friend poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index);
148  friend void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m);
149  tgb_sparse_matrix(int i, int j, ring rarg);
150  ~tgb_sparse_matrix();
151  int get_rows();
152  int get_columns();
153  void print();
154  void row_normalize(int row);
155  void row_content(int row);
156  //  void perm_rows(int i, int j);
157  void perm_rows(int i, int j){
158  mac_poly h;
159  h=mp[i];
160  mp[i]=mp[j];
161  mp[j]=h;
162  }
163  void set(int i, int j, number n);
164  number get(int i, int j);
165  BOOLEAN is_zero_entry(int i, int j);
166  void free_row(int row, BOOLEAN free_non_zeros=TRUE);
167  int min_col_not_zero_in_row(int row);
168  int next_col_not_zero(int row,int pre);
169  BOOLEAN zero_row(int row);
170  void mult_row(int row,number factor);
171  void add_lambda_times_row(int add_to,int summand,number factor);
172  int non_zero_entries(int row);
173};
174struct poly_array_list{
175  poly* p;
176  int size;
177  poly_array_list* next;
178};
179struct calc_dat
180{
181  int* rep;
182  char** states;
183  ideal S;
184  ring r;
185  int* lengths;
186  long* short_Exps;
187  kStrategy strat;
188  int* T_deg;
189  int* T_deg_full;
190  poly tmp_lm;
191  poly* tmp_pair_lm;
192  sorted_pair_node** tmp_spn;
193  poly* expandS;
194  poly* gcd_of_terms;
195  int_pair_node* soon_free;
196  sorted_pair_node** apairs;
197  BOOLEAN* modifiedS;
198  poly_list_node* to_destroy;
199  //for F4
200  mp_array_list* F;
201  poly_array_list* F_minus;
202
203  //end for F4
204#ifdef HEAD_BIN
205  struct omBin_s*   HeadBin;
206#endif
207  unsigned int reduction_steps;
208  int n;
209  int normal_forms;
210  int current_degree;
211  int Rcounter;
212  int last_index;
213  int max_pairs;
214  int pair_top;
215  int easy_product_crit;
216  int extended_product_crit;
217  int average_length;
218  BOOLEAN is_char0;
219  BOOLEAN is_homog;
220  BOOLEAN F4_mode;
221};
222class red_object{
223 public:
224  kBucket_pt bucket;
225  poly p;
226  formal_sum_descriptor* sum;
227  unsigned long sev;
228  void flatten();
229  void validate();
230  void adjust_coefs(number c_r, number c_ac_r);
231  int guess_quality(calc_dat* c);
232  int clear_to_poly();
233  void canonicalize();
234};
235
236
237enum calc_state
238  {
239    UNCALCULATED,
240    HASTREP,
241    UNIMPORTANT,
242    SOONTREP
243  };
244
245static int add_to_reductors(calc_dat* c, poly h, int len);
246static int bucket_guess(kBucket* bucket);
247static poly redNFTail (poly h,const int sl,kStrategy strat, int len);
248static poly redNF2 (poly h,calc_dat* c , int &len, number&  m,int n=0);
249static void free_sorted_pair_node(sorted_pair_node* s, ring r);
250static void shorten_tails(calc_dat* c, poly monom);
251static void replace_pair(int & i, int & j, calc_dat* c);
252static sorted_pair_node** add_to_basis(poly h, int i, int j,calc_dat* c, int* ip=NULL);
253static void do_this_spoly_stuff(int i,int j,calc_dat* c);
254//ideal t_rep_gb(ring r,ideal arg_I);
255static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, calc_dat* state);
256static int* make_connections(int from, poly bound, calc_dat* c);
257static int* make_connections(int from, int to, poly bound, calc_dat* c);
258static void now_t_rep(const int & arg_i, const int & arg_j, calc_dat* c);
259static void soon_t_rep(const int & arg_i, const int & arg_j, calc_dat* c);
260static int pLcmDeg(poly a, poly b);
261static int simple_posInS (kStrategy strat, poly p,int len);
262static BOOLEAN find_next_pair(calc_dat* c, BOOLEAN go_higher=TRUE);
263
264static sorted_pair_node* pop_pair(calc_dat* c);
265static BOOLEAN no_pairs(calc_dat* c);
266static void clean_top_of_pair_list(calc_dat* c);
267static void super_clean_top_of_pair_list(calc_dat* c);
268static BOOLEAN state_is(calc_state state, const int & i, const int & j, calc_dat* c);
269static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, calc_dat* c);
270static int pair_better_gen(const void* ap,const void* bp);
271static poly redTailShort(poly h, kStrategy strat);
272static poly gcd_of_terms(poly p, ring r);
273static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, calc_dat* c);
274static poly kBucketGcd(kBucket* b, ring r);
275static void multi_reduction(red_object* los, int & losl, calc_dat* c);
276static sorted_pair_node* quick_pop_pair(calc_dat* c);
277static sorted_pair_node* top_pair(calc_dat* c);
278//static int quality(poly p, int len, calc_dat* c);
279/**
280   makes on each red_object in a region a single_step
281 **/
282class reduction_step{
283 public:
284  /// we assume hat all occuring red_objects have same lm, and all
285  /// occ. lm's in r[l...u] are the same, only reductor does not occur
286  virtual void reduce(red_object* r, int l, int u);
287  //int reduction_id;
288  virtual ~reduction_step();
289  calc_dat* c;
290  int reduction_id;
291};
292class simple_reducer:public reduction_step{
293 public:
294  poly p;
295  kBucket_pt fill_back;
296  int p_len;
297  simple_reducer(poly p, int p_len, calc_dat* c =NULL){
298    this->p=p;
299    assume(p_len==pLength(p));
300    this->p_len=p_len;
301    this->c=c;
302  }
303  virtual void pre_reduce(red_object* r, int l, int u);
304  virtual void reduce(red_object* r, int l, int u);
305  ~simple_reducer();
306
307  virtual void target_is_a_sum_reduce(red_object & ro);
308  virtual void target_is_no_sum_reduce(red_object & ro);
309};
310class join_simple_reducer:public simple_reducer{
311 public:
312  join_simple_reducer(poly p, int p_len, poly high_to):simple_reducer(p,p_len){
313    ac=new reduction_accumulator( p, p_len, high_to);
314   
315   
316  }
317    ~join_simple_reducer();
318   void pre_reduce(red_object* r, int l, int u);
319  void target_is_no_sum_reduce(red_object & ro);
320  reduction_accumulator* ac;
321};
322//class sum_canceling_reducer:public reduction_step {
323//  void reduce(red_object* r, int l, int u);
324//};
325struct find_erg{
326  poly expand;
327  int expand_length;
328  int to_reduce_u;
329  int to_reduce_l;
330  int reduce_by;//index of reductor
331  BOOLEAN fromS;//else from los
332
333};
334
335static void multi_reduce_step(find_erg & erg, red_object* r, calc_dat* c);
336static void finalize_reduction_step(reduction_step* r);
337#endif
Note: See TracBrowser for help on using the repository browser.