source: git/kernel/tgb_internal.h @ abfc3b

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