source: git/kernel/tgb_internal.h @ cb1f9b

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