source: git/Singular/tgb.h @ 5c5638

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