My Project  UNKNOWN_GIT_VERSION
tgb_internal.h
Go to the documentation of this file.
1 #ifndef TGB_INTERNAL_H
2 #define TGB_INTERNAL_H
3 //!\file tgb_internal.h
4 /****************************************
5 * Computer Algebra System SINGULAR *
6 ****************************************/
7 /*
8  * ABSTRACT: tgb internal .h file
9 */
10 #define USE_NORO 1
11 
12 #include "omalloc/omalloc.h"
13 
14 //#define TGB_DEBUG
15 #define FULLREDUCTIONS
16 //#define HALFREDUCTIONS
17 //#define HEAD_BIN
18 //#define HOMOGENEOUS_EXAMPLE
19 #define REDTAIL_S
20 #define PAR_N 100
21 #define PAR_N_F4 5000
22 #define AC_NEW_MIN 2
23 #define AC_FLATTEN 1
24 
25 //#define FIND_DETERMINISTIC
26 //#define REDTAIL_PROT
27 //#define QUICK_SPOLY_TEST
28 #ifdef USE_NORO
29 #define NORO_CACHE 1
30 #define NORO_SPARSE_ROWS_PRE 1
31 #define NORO_NON_POLY 1
32 #include <algorithm>
33 #endif
34 #ifdef NORO_CACHE
35 //#include <map>
36 #include <vector>
37 #endif
38 #ifdef HAVE_BOOST_DYNAMIC_BITSET_HPP
39 #define HAVE_BOOST 1
40 #endif
41 //#define HAVE_BOOST 1
42 //#define USE_STDVECBOOL 1
43 #ifdef HAVE_BOOST
44 #include <vector>
45 using boost::dynamic_bitset;
46 using std::vector;
47 #endif
48 #ifdef USE_STDVECBOOL
49 #include <vector>
50 using std::vector;
51 #endif
52 #include <stdlib.h>
53 
54 #include "misc/options.h"
55 
56 #include "coeffs/modulop.h"
57 
59 #include "polys/monomials/ring.h"
60 #include "polys/kbuckets.h"
61 
62 #include "kernel/ideals.h"
63 #include "kernel/polys.h"
64 
65 #include "kernel/GBEngine/kutil.h"
67 #include "kernel/GBEngine/kstd1.h"
68 
69 
70 #if 1
71 
72 #define npInit n_Init
73 #define npNeg npNegM
74 #define npInvers npInversM
75 #define npIsOne npIsOne
76 #define npIsZero npIsZeroM
77 
78 #define npMult npMult
79 
80 #else
81 #error Please do NOT call internal functions directly!
82 #endif
83 
84 
86 {
87 public:
88  PolySimple(poly p)
89  {
90  impl=p;
91  }
93  {
94  impl=NULL;
95  }
97  {
98  //impl=p_Copy(a.impl,currRing);
99  impl=a.impl;
100  }
102  {
103  //p_Delete(&impl,currRing);
104  //impl=p_Copy(p2.impl,currRing);
105  impl=p2.impl;
106  return *this;
107  }
109  {
110  //p_Delete(&impl,currRing);
111  }
112  bool operator< (const PolySimple& other) const
113  {
114  return pLmCmp(impl,other.impl)<0;
115  }
116  bool operator==(const PolySimple& other)
117  {
118  return pLmEqual(impl,other.impl);
119  }
120  poly impl;
121 
122 };
123 template<class number_type> class DataNoroCacheNode;
124 /*class MonRedRes{
125 public:
126  poly p;
127  number coef;
128  BOOLEAN changed;
129  int len;
130  BOOLEAN onlyBorrowed;
131  bool operator<(const MonRedRes& other) const
132  {
133  int cmp=p_LmCmp(p,other.p,currRing);
134  if ((cmp<0)||((cmp==0)&&((onlyBorrowed)&&(!(other.onlyBorrowed)))))
135  {
136  return true;
137  } else return false;
138  }
139  DataNoroCacheNode* ref;
140  MonRedRes()
141  {
142  ref=NULL;
143  p=NULL;
144  }
145 };*/
146 template <class number_type> class MonRedResNP
147 {
148 public:
149  number coef;
150 
151 
154  {
155  ref=NULL;
156  }
157 };
159 {
160  //criterium, which is stable 0. small lcm 1. small i 2. small j
162  poly lcm_of_lm;
163  int i;
164  int j;
165  int deg;
166 
167 
168 };
169 #ifdef NORO_CACHE
170 #ifndef NORO_NON_POLY
171 class NoroPlaceHolder
172 {
173 public:
174  DataNoroCacheNode* ref;
175  number coef;
176 };
177 #endif
178 #endif
179 //static ideal debug_Ideal;
180 
181 
183 {
184  poly p;
186 };
187 
189 {
191  int a;
192  int b;
193 };
195 {
196  poly m;
197  poly f;
198 };
200 {
202  int size;
204 };
205 
206 
208 {
209  poly* p;
210  int size;
212 };
214 {
215  public:
216  slimgb_alg(ideal I, int syz_comp,BOOLEAN F4,int deg_pos);
217  void introduceDelayedPairs(poly* pa,int s);
218  virtual ~slimgb_alg();
219  void cleanDegs(int lower, int upper);
220 #ifndef HAVE_BOOST
221 #ifdef USE_STDVECBOOL
222  vector<vector<bool> > states;
223 #else
224  char** states;
225 #endif
226 #else
227  vector<dynamic_bitset<> > states;
228 #endif
229  ideal add_later;
230  ideal S;
231  ring r;
232  int* lengths;
234  long* short_Exps;
236  int* T_deg;
238  poly tmp_lm;
239  poly* tmp_pair_lm;
241  poly* expandS;
245  #if 0
246  BOOLEAN* modifiedS;
247  #endif
248  #ifdef TGB_RESORT_PAIRS
249  bool* replaced;
250  #endif
252  //for F4
255 
256  //end for F4
257 #ifdef HEAD_BIN
258  omBin HeadBin;
259 #endif
260  unsigned int reduction_steps;
261  int n;
262  //! array_lengths should be greater equal n;
263  int syz_comp;
267  int Rcounter;
270  int pair_top;
276  int deg_pos;
286  #ifdef TGB_RESORT_PAIRS
287  BOOLEAN used_b;
288  #endif
289  unsigned long pTotaldegree(poly p)
290  {
291  pTest(p);
292  //assume(pDeg(p,r)==::p_Totaldegree(p,r));
293  assume(((unsigned long)::p_Totaldegree(p,r))==p->exp[deg_pos]);
294  return p->exp[deg_pos];
295  //return ::pTotaldegree(p,this->r);
296  }
298  {
299  int rr=0;
300  while(p)
301  {
302  int d=this->pTotaldegree(p);
303  rr=si_max(rr,d);
304  pIter(p);
305  }
306  return rr;
307  }
308 };
310 {
311  public:
313  poly p;
314  unsigned long sev;
315  void flatten();
316  void validate();
318  void adjust_coefs(number c_r, number c_ac_r);
320  int clear_to_poly();
321  void canonicalize();
322 };
323 
324 
326  {
329  //UNIMPORTANT,
330  //SOONTREP
331  };
332 template <class len_type, class set_type> int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set);
333 void free_sorted_pair_node(sorted_pair_node* s, const ring r);
334 ideal do_t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode,int deg_pos);
335 void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c);
336 
338 int slim_nsize(number n, ring r);
341 sorted_pair_node** add_to_basis_ideal_quotient(poly h, slimgb_alg* c, int* ip);//, BOOLEAN new_pairs=TRUE);
343 int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj);
344 int tgb_pair_better_gen2(const void* ap,const void* bp);
345 int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev);
346 /**
347  makes on each red_object in a region a single_step
348  **/
350 {
351  public:
352  /// we assume hat all occuring red_objects have same lm, and all
353  /// occ. lm's in r[l...u] are the same, only reductor does not occur
354  virtual void reduce(red_object* r, int l, int u);
355  //int reduction_id;
356  virtual ~reduction_step();
359 };
361 {
362  public:
363  poly p;
365  int p_len;
367  simple_reducer(poly pp, int pp_len,int pp_reducer_deg, slimgb_alg* pp_c =NULL)
368  {
369  this->p=pp;
370  this->reducer_deg=pp_reducer_deg;
371  assume(pp_len==pLength(pp));
372  this->p_len=pp_len;
373  this->c=pp_c;
374  }
375  virtual void pre_reduce(red_object* r, int l, int u);
376  virtual void reduce(red_object* r, int l, int u);
377  ~simple_reducer();
378 
379 
380  virtual void do_reduce(red_object & ro);
381 };
382 
383 //class sum_canceling_reducer:public reduction_step {
384 // void reduce(red_object* r, int l, int u);
385 //};
386 struct find_erg
387 {
388  poly expand;
392  int reduce_by;//index of reductor
393  BOOLEAN fromS;//else from los
394 
395 };
396 
397 template <class len_type, class set_type> int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set)
398 {
399  //Print("POSHELER:%d",sizeof(wlen_type));
400  int length=strat->sl;
401  int i;
402  int an = 0;
403  int en= length;
404 
405  if ((len>setL[length])
406  || ((len==setL[length]) && (pLmCmp(set[length],p)== -1)))
407  return length+1;
408 
409  loop
410  {
411  if (an >= en-1)
412  {
413  if ((len<setL[an])
414  || ((len==setL[an]) && (pLmCmp(set[an],p) == 1))) return an;
415  return en;
416  }
417  i=(an+en) / 2;
418  if ((len<setL[i])
419  || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i;
420  //else if ((len>setL[i])
421  //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i;
422  else an=i;
423  }
424 
425 }
426 #ifdef NORO_CACHE
427 #define slim_prec_cast(a) (unsigned int) (unsigned long) (a)
428 #define F4mat_to_number_type(a) (number_type) slim_prec_cast(a)
429 typedef unsigned short tgb_uint16;
430 typedef unsigned char tgb_uint8;
431 typedef unsigned int tgb_uint32;
433 {
434 public:
437 
438 
440  {
441  branches=NULL;
442  branches_len=0;
443 
444  }
445  NoroCacheNode* setNode(int branch, NoroCacheNode* node)
446  {
447  if (branch>=branches_len)
448  {
449  if (branches==NULL)
450  {
451  branches_len=branch+1;
454  int i;
455  for(i=0;i<branches_len;i++)
456  {
457  branches[i]=NULL;
458  }
459  }
460  else
461  {
462  int branches_len_old=branches_len;
463  branches_len=branch+1;
465  int i;
466  for(i=branches_len_old;i<branches_len;i++)
467  {
468  branches[i]=NULL;
469  }
470  }
471  }
472  assume(branches[branch]==NULL);
473  branches[branch]=node;
474  return node;
475  }
477  {
478  if (branch<branches_len) return branches[branch];
479  return NULL;
480  }
481  virtual ~NoroCacheNode()
482  {
483  int i;
484  for(i=0;i<branches_len;i++)
485  {
486  delete branches[i];
487  }
488  omfree(branches);
489  }
491  {
492  if ((branch<branches_len)&&(branches[branch]))
493  return branches[branch];
494  else
495  {
496  return setNode(branch,new NoroCacheNode());
497  }
498  }
499 };
500 class DenseRow{
501 public:
502  number* array;
503  int begin;
504  int end;
506  {
507  array=NULL;
508  }
510  {
511  omfree(array);
512  }
513 };
514 template <class number_type> class SparseRow
515 {
516 public:
517  int* idx_array;
518  number_type* coef_array;
519  int len;
521  {
522  len=0;
523  idx_array=NULL;
525  }
527  {
528  len=n;
529  idx_array=(int*) omAlloc(n*sizeof(int));
530  coef_array=(number_type*) omAlloc(n*sizeof(number_type));
531  }
532  SparseRow<number_type>(int n, const number_type* source)
533  {
534  len=n;
535  idx_array=NULL;
536  coef_array=(number_type*) omAlloc(n*sizeof(number_type));
537  memcpy(coef_array,source,n*sizeof(number_type));
538  }
540  {
541  omfree(idx_array);
543  }
544 };
545 
546 template <class number_type> class DataNoroCacheNode:public NoroCacheNode
547 {
548 public:
549 
552  #ifdef NORO_SPARSE_ROWS_PRE
554  #else
555  DenseRow* row;
556  #endif
558  DataNoroCacheNode(poly p, int len)
559  {
560  value_len=len;
561  value_poly=p;
562  row=NULL;
563  term_index=-1;
564  }
565  #ifdef NORO_SPARSE_ROWS_PRE
567  {
568  if (row!=NULL)
569  value_len=row->len;
570  else
571  value_len=0;
573  this->row=row;
574  term_index=-1;
575  }
576  #endif
578  {
579  //p_Delete(&value_poly,currRing);
580  if (row) delete row;
581  }
582 };
583 template <class number_type> class TermNoroDataNode
584 {
585 public:
587  poly t;
588 };
589 
590 template <class number_type> class NoroCache
591 {
592 public:
593  poly temp_term;
594 #ifndef NORO_NON_POLY
595  void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
596  void evaluateRows();
597  void evaluateRows(int level, NoroCacheNode* node);
598 #endif
601 
602 #ifdef NORO_RED_ARRAY_RESERVER
603  int reserved;
604  poly* recursionPolyBuffer;
605 #endif
606  static const int backLinkCode=-222;
608  {
609  //assume(impl.find(p_Copy(term,currRing))==impl.end());
610  //assume(len==pLength(nf));
612  if (term==nf)
613  {
615 
616  ressources.push_back(term);
618  return treeInsertBackLink(term);
619 
620  }
621  else
622  {
623  if (nf)
624  {
625  //nf=p_Copy(nf,currRing);
626  assume(p_LmCmp(nf,term,currRing)==-1);
627  ressources.push_back(nf);
628  }
629  return treeInsert(term,nf,len);
630 
631  }
632 
633  //impl[term]=std::pair<PolySimple,int> (nf,len);
634  }
635  #ifdef NORO_SPARSE_ROWS_PRE
637  {
638  //assume(impl.find(p_Copy(term,currRing))==impl.end());
639  //assume(len==pLength(nf));
640 
641  return treeInsert(term,srow);
642 
643 
644  //impl[term]=std::pair<PolySimple,int> (nf,len);
645  }
646  #endif
648  {
649  ressources.push_back(t);
651  res->term_index=nIrreducibleMonomials;
653  return res;
654  }
655  poly lookup(poly term, BOOLEAN& succ, int & len);
658  {
659  buffer=NULL;
660 #ifdef NORO_RED_ARRAY_RESERVER
661  reserved=0;
662  recursionPolyBuffer=(poly*)omAlloc(1000000*sizeof(poly));
663 #endif
666  temp_term=pOne();
667  tempBufferSize=3000;
669  }
671  {
672  if (tempBufferSize<size)
673  {
677  }
678  }
679 #ifdef NORO_RED_ARRAY_RESERVER
680  poly* reserve(int n)
681  {
682  poly* res=recursionPolyBuffer+reserved;
683  reserved+=n;
684  return res;
685  }
686  void free(int n)
687  {
688  reserved-=n;
689  }
690 #endif
692  {
693  int s=ressources.size();
694  int i;
695  for(i=0;i<s;i++)
696  {
697  p_Delete(&ressources[i].impl,currRing);
698  }
700 #ifdef NORO_RED_ARRAY_RESERVER
701  omfree(recursionPolyBuffer);
702 #endif
704  }
705 
708  void* tempBuffer;
710 protected:
712  {
713  int i;
715  int nvars=(currRing->N);
716  NoroCacheNode* parent=&root;
717  for(i=1;i<nvars;i++)
718  {
719  parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
720  }
722  }
723  #ifdef NORO_SPARSE_ROWS_PRE
725  {
726  int i;
728  int nvars=(currRing->N);
729  NoroCacheNode* parent=&root;
730  for(i=1;i<nvars;i++)
731  {
732  parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
733  }
735  }
736  #endif
738  {
739  int i;
740  int nvars=(currRing->N);
741  NoroCacheNode* parent=&root;
742  for(i=1;i<nvars;i++)
743  {
744  parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
745  }
747  }
748 
749  //@TODO descruct nodes;
750  typedef std::vector<PolySimple> poly_vec;
752  //typedef std::map<PolySimple,std::pair<PolySimple,int> > cache_map;
753  //cache_map impl;
755  number* buffer;
756 };
757 template<class number_type> SparseRow<number_type> * noro_red_to_non_poly_t(poly p, int &len, NoroCache<number_type>* cache,slimgb_alg* c);
759 {
760  MonRedResNP<number_type> res_holder;
761 
762 
764  if (ref!=NULL)
765  {
766  res_holder.coef=p_GetCoeff(t,c->r);
767 
768  res_holder.ref=ref;
769  p_Delete(&t,c->r);
770  return res_holder;
771  }
772 
773  unsigned long sev=p_GetShortExpVector(t,currRing);
774  int i=kFindDivisibleByInS_easy(c->strat,t,sev);
775  if (i>=0)
776  {
777  number coef_bak=p_GetCoeff(t,c->r);
778 
779  p_SetCoeff(t,npInit(1,c->r->cf),c->r);
780  assume(npIsOne(p_GetCoeff(c->strat->S[i],c->r),c->r->cf));
781  number coefstrat=p_GetCoeff(c->strat->S[i],c->r);
782 
783 
784  poly exp_diff=cache->temp_term;
785  p_ExpVectorDiff(exp_diff,t,c->strat->S[i],c->r);
786  p_SetCoeff(exp_diff,npNeg(npInvers(coefstrat,c->r->cf),c->r->cf),c->r);
787  p_Setm(exp_diff,c->r);
788  assume(c->strat->S[i]!=NULL);
789 
790  poly res;
791  res=pp_Mult_mm(pNext(c->strat->S[i]),exp_diff,c->r);
792 
793  int len=c->strat->lenS[i]-1;
795  srow=noro_red_to_non_poly_t<number_type>(res,len,cache,c);
796  ref=cache->insert(t,srow);
797  p_Delete(&t,c->r);
798 
799 
800  res_holder.coef=coef_bak;
801  res_holder.ref=ref;
802  return res_holder;
803 
804  } else {
805  number coef_bak=p_GetCoeff(t,c->r);
806  number one=npInit(1, c->r->cf);
807  p_SetCoeff(t,one,c->r);
808 
809  res_holder.ref=cache->insertAndTransferOwnerShip(t,c->r);
810  assume(res_holder.ref!=NULL);
811  res_holder.coef=coef_bak;
812 
813  return res_holder;
814 
815  }
816 
817 }
818 /*
819 poly tree_add(poly* a,int begin, int end,ring r)
820 {
821  int d=end-begin;
822  switch(d)
823  {
824  case 0:
825  return NULL;
826  case 1:
827  return a[begin];
828  case 2:
829  return p_Add_q(a[begin],a[begin+1],r);
830  default:
831  int s=d/2;
832  return p_Add_q(tree_add(a,begin,begin+s,r),tree_add(a,begin+s,end,r),r);
833  }
834 }
835 */
836 
837 template<class number_type> SparseRow<number_type>* convert_to_sparse_row(number_type* temp_array,int temp_size,int non_zeros)
838 {
840 //int pos=0;
841 //Print("denseness:%f\n",((double) non_zeros/(double) temp_size));
842 number_type* it_coef=res->coef_array;
843 int* it_idx=res->idx_array;
844 #if 0
845 for(i=0;i<cache->nIrreducibleMonomials;i++)
846 {
847  if (!(0==temp_array[i]))
848  {
849 
850  res->idx_array[pos]=i;
851  res->coef_array[pos]=temp_array[i];
852 
853  pos++;
854  non_zeros--;
855  if (non_zeros==0) break;
856  }
857 
858 }
859 #else
860 int64* start=(int64*) ((void*)temp_array);
861 int64* end;
862 const int multiple=sizeof(int64)/sizeof(number_type);
863 if (temp_size==0) end=start;
864 
865 else
866 {
867  int temp_size_rounded=temp_size+(multiple-(temp_size%multiple));
868  assume(temp_size_rounded>=temp_size);
869  assume(temp_size_rounded%multiple==0);
870  assume(temp_size_rounded<temp_size+multiple);
871  number_type* nt_end=temp_array+temp_size_rounded;
872  end=(int64*)((void*)nt_end);
873 }
874 int64* it=start;
875 while(it!=end)
876 {
877  if UNLIKELY((*it)!=0)
878  {
879  int small_i;
880  const int temp_index=((number_type*)((void*) it))-temp_array;
881  const int bound=temp_index+multiple;
882  number_type c;
883  for(small_i=temp_index;small_i<bound;small_i++)
884  {
885  if((c=temp_array[small_i])!=0)
886  {
887  //res->idx_array[pos]=small_i;
888  //res->coef_array[pos]=temp_array[small_i];
889  (*(it_idx++))=small_i;
890  (*(it_coef++))=c;
891  //pos++;
892  non_zeros--;
893 
894  }
895  if UNLIKELY(non_zeros==0) break;
896  }
897 
898  }
899  ++it;
900 }
901 #endif
902 return res;
903 }
904 #ifdef SING_NDEBUG
905 template <class number_type> void add_coef_times_sparse(number_type* const temp_array,
906 int /*temp_size*/,SparseRow<number_type>* row, number coef)
907 #else
908 template <class number_type> void add_coef_times_sparse(number_type* const temp_array,
909 int temp_size,SparseRow<number_type>* row, number coef)
910 #endif
911 {
912  int j;
913  number_type* const coef_array=row->coef_array;
914  int* const idx_array=row->idx_array;
915  const int len=row->len;
916  tgb_uint32 buffer[256];
917  const tgb_uint32 prime=n_GetChar(currRing->cf);
918  const tgb_uint32 c=F4mat_to_number_type(coef);
919  assume(!(npIsZero(coef,currRing->cf)));
920  for(j=0;j<len;j=j+256)
921  {
922  const int bound=std::min(j+256,len);
923  int i;
924  int bpos=0;
925  for(i=j;i<bound;i++)
926  {
927  buffer[bpos++]=coef_array[i];
928  }
929  int bpos_bound=bound-j;
930  for(i=0;i<bpos_bound;i++)
931  {
932  buffer[i]*=c;
933  }
934  for(i=0;i<bpos_bound;i++)
935  {
936  buffer[i]=buffer[i]%prime;
937  }
938  bpos=0;
939  for(i=j;i<bound;i++)
940  {
941  int idx=idx_array[i];
942  assume(bpos<256);
943  assume(!(npIsZero((number)(long) buffer[bpos],currRing->cf)));
944  STATISTIC(n_Add); temp_array[idx]=F4mat_to_number_type(npAddM((number)(long) temp_array[idx], (number)(long) buffer[bpos++],currRing->cf));
945  #ifndef SING_NDEBUG
946  assume(idx<temp_size);
947  #endif
948  }
949 
950  }
951 }
952 #ifdef SING_NDEBUG
953 template <class number_type> void add_coef_times_dense(number_type* const temp_array,
954 int /*temp_size*/,const number_type* row, int len,number coef)
955 #else
956 template <class number_type> void add_coef_times_dense(number_type* const temp_array,
957 int temp_size,const number_type* row, int len,number coef)
958 #endif
959 {
960  int j;
961  const number_type* const coef_array=row;
962  //int* const idx_array=row->idx_array;
963  //const int len=temp_size;
964  tgb_uint32 buffer[256];
965  const tgb_uint32 prime=n_GetChar(currRing->cf);
966  const tgb_uint32 c=F4mat_to_number_type(coef);
967  assume(!(npIsZero(coef,currRing->cf)));
968  for(j=0;j<len;j=j+256)
969  {
970  const int bound=std::min(j+256,len);
971  int i;
972  int bpos=0;
973  for(i=j;i<bound;i++)
974  {
975  buffer[bpos++]=coef_array[i];
976  }
977  int bpos_bound=bound-j;
978  for(i=0;i<bpos_bound;i++)
979  {
980  buffer[i]*=c;
981  }
982  for(i=0;i<bpos_bound;i++)
983  {
984  buffer[i]=buffer[i]%prime;
985  }
986  bpos=0;
987  for(i=j;i<bound;i++)
988  {
989  //int idx=idx_array[i];
990  assume(bpos<256);
991  //assume(!(npIsZero((number) buffer[bpos])));
992  STATISTIC(n_Add); temp_array[i]=F4mat_to_number_type(npAddM((number)(long) temp_array[i], (number)(long) buffer[bpos++],currRing->cf));
993  #ifndef SING_NDEBUG
994  assume(i<temp_size);
995  #endif
996  }
997 
998  }
999 }
1000 #ifdef SING_NDEBUG
1001 template <class number_type> void add_dense(number_type* const temp_array,
1002 int /*temp_size*/,const number_type* row, int len)
1003 #else
1004 template <class number_type> void add_dense(number_type* const temp_array,
1005 int temp_size,const number_type* row, int len)
1006 #endif
1007 {
1008  //int j;
1009  //const number_type* const coef_array=row;
1010  //int* const idx_array=row->idx_array;
1011  //const int len=temp_size;
1012  //tgb_uint32 buffer[256];
1013  //const tgb_uint32 prime=npPrimeM;
1014  //const tgb_uint32 c=F4mat_to_number_type(coef);
1015 
1016  int i;
1017  for(i=0;i<len;i++)
1018  {
1019  STATISTIC(n_Add); temp_array[i]=F4mat_to_number_type(npAddM((number)(long) temp_array[i], (number)(long) row[i],currRing->cf));
1020  #ifndef SING_NDEBUG
1021  assume(i<temp_size);
1022  #endif
1023  }
1024 
1025 }
1026 #ifdef SING_NDEBUG
1027 template <class number_type> void sub_dense(number_type* const temp_array,
1028 int /*temp_size*/,const number_type* row, int len)
1029 #else
1030 template <class number_type> void sub_dense(number_type* const temp_array,
1031 int temp_size,const number_type* row, int len)
1032 #endif
1033 {
1034  //int j;
1035  //const number_type* const coef_array=row;
1036  //int* const idx_array=row->idx_array;
1037  //const int len=temp_size;
1038  //tgb_uint32 buffer[256];
1039  //const tgb_uint32 prime=npPrimeM;
1040  //const tgb_uint32 c=F4mat_to_number_type(coef);
1041 
1042  int i;
1043  for(i=0;i<len;i++)
1044  {
1045 
1046  STATISTIC(n_Sub); temp_array[i]=F4mat_to_number_type(npSubM((number)(long) temp_array[i], (number)(long) row[i],currRing->cf));
1047  #ifndef SING_NDEBUG
1048  assume(i<temp_size);
1049  #endif
1050  }
1051 
1052 }
1053 
1054 #ifdef SING_NDEBUG
1055 template <class number_type> void add_sparse(number_type* const temp_array,int /*temp_size*/,SparseRow<number_type>* row)
1056 #else
1057 template <class number_type> void add_sparse(number_type* const temp_array,int temp_size,SparseRow<number_type>* row)
1058 #endif
1059 {
1060  int j;
1061 
1062  number_type* const coef_array=row->coef_array;
1063  int* const idx_array=row->idx_array;
1064  const int len=row->len;
1065  for(j=0;j<len;j++)
1066  {
1067  int idx=idx_array[j];
1068  STATISTIC(n_Add); temp_array[idx]=F4mat_to_number_type( (number_type)(long)npAddM((number) (long)temp_array[idx],(number)(long) coef_array[j],currRing->cf));
1069  #ifndef SING_NDEBUG
1070  assume(idx<temp_size);
1071  #endif
1072  }
1073 }
1074 #ifdef SING_NDEBUG
1075 template <class number_type> void sub_sparse(number_type* const temp_array,int /*temp_size*/,SparseRow<number_type>* row)
1076 #else
1077 template <class number_type> void sub_sparse(number_type* const temp_array,int temp_size,SparseRow<number_type>* row)
1078 #endif
1079 {
1080  int j;
1081 
1082  number_type* const coef_array=row->coef_array;
1083  int* const idx_array=row->idx_array;
1084  const int len=row->len;
1085  for(j=0;j<len;j++)
1086  {
1087  int idx=idx_array[j];
1088  STATISTIC(n_Sub); temp_array[idx]=F4mat_to_number_type( (number_type)(long) npSubM((number) (long)temp_array[idx],(number)(long) coef_array[j],currRing->cf));
1089  #ifndef SING_NDEBUG
1090  assume(idx<temp_size);
1091  #endif
1092  }
1093 }
1095 {
1096  size_t temp_size_bytes=cache->nIrreducibleMonomials*sizeof(number_type)+8;//use 8bit int for testing
1097  assume(sizeof(int64)==8);
1098  cache->ensureTempBufferSize(temp_size_bytes);
1099  number_type* temp_array=(number_type*) cache->tempBuffer;//omalloc(cache->nIrreducibleMonomials*sizeof(number_type));
1100  int temp_size=cache->nIrreducibleMonomials;
1101  memset(temp_array,0,temp_size_bytes);
1102  number minus_one=npInit(-1,currRing->cf);
1103  int i;
1104  for(i=0;i<len;i++)
1105  {
1106  MonRedResNP<number_type> red=mon[i];
1107  if ( /*(*/ red.ref /*)*/ )
1108  {
1109  if (red.ref->row)
1110  {
1111  SparseRow<number_type>* row=red.ref->row;
1112  number coef=red.coef;
1113  if (row->idx_array)
1114  {
1115  if (!((coef==(number)1L)||(coef==minus_one)))
1116  {
1117  add_coef_times_sparse(temp_array,temp_size,row,coef);
1118  }
1119  else
1120  {
1121  if (coef==(number)1L)
1122  {
1123  add_sparse(temp_array,temp_size,row);
1124  }
1125  else
1126  {
1127  sub_sparse(temp_array,temp_size,row);
1128  }
1129  }
1130  }
1131  else
1132  //TODO: treat, 1,-1
1133  if (!((coef==(number)1L)||(coef==minus_one)))
1134  {
1135  add_coef_times_dense(temp_array,temp_size,row->coef_array,row->len,coef);
1136  }
1137  else
1138  {
1139  if (coef==(number)1L)
1140  add_dense(temp_array,temp_size,row->coef_array,row->len);
1141  else
1142  {
1143  assume(coef==minus_one);
1144  sub_dense(temp_array,temp_size,row->coef_array,row->len);
1145  //add_coef_times_dense(temp_array,temp_size,row->coef_array,row->len,coef);
1146  }
1147  }
1148  }
1149  else
1150  {
1151  if (red.ref->value_len==NoroCache<number_type>::backLinkCode)
1152  {
1153  STATISTIC(n_Add); temp_array[red.ref->term_index]=F4mat_to_number_type( npAddM((number)(long) temp_array[red.ref->term_index],red.coef,currRing->cf));
1154  }
1155  else
1156  {
1157  //PrintS("third case\n");
1158  }
1159  }
1160  }
1161  }
1162  int non_zeros=0;
1163  for(i=0;i<cache->nIrreducibleMonomials;i++)
1164  {
1165  //if (!(temp_array[i]==0))
1166  //{
1167  // non_zeros++;
1168  //}
1169  assume(((temp_array[i]!=0)==0)|| (((temp_array[i]!=0)==1)));
1170  non_zeros+=(temp_array[i]!=0);
1171  }
1172 
1173  if (non_zeros==0)
1174  {
1175  //omfree(mon);
1176  return NULL;
1177  }
1178  SparseRow<number_type>* res=new SparseRow<number_type>(temp_size,temp_array);//convert_to_sparse_row(temp_array,temp_size, non_zeros);
1179 
1180  //omfree(temp_array);
1181 
1182 
1183  return res;
1184 }
1185 template<class number_type> class CoefIdx
1186 {
1187 public:
1188  number_type coef;
1189  int idx;
1190  bool operator<(const CoefIdx<number_type>& other) const
1191  {
1192  return (idx<other.idx);
1193  }
1194 };
1195 template<class number_type> void write_coef_times_xx_idx_to_buffer(CoefIdx<number_type>* const pairs,int& pos,int* const idx_array, number_type* const coef_array,const int rlen, const number coef)
1196 {
1197  int j;
1198  for(j=0;j<rlen;j++)
1199  {
1200  assume(coef_array[j]!=0);
1202  STATISTIC(n_Mult); ci.coef=F4mat_to_number_type(npMultM((number)(long) coef,(number)(long) coef_array[j],currRing->cf));
1203  ci.idx=idx_array[j];
1204  pairs[pos++]=ci;
1205  }
1206 }
1207 template<class number_type> void write_coef_times_xx_idx_to_buffer_dense(CoefIdx<number_type>* const pairs,int& pos, number_type* const coef_array,const int rlen, const number coef)
1208 {
1209  int j;
1210 
1211  for(j=0;j<rlen;j++)
1212  {
1213  if (coef_array[j]!=0)
1214  {
1215  assume(coef_array[j]!=0);
1217  STATISTIC(n_Mult); ci.coef=F4mat_to_number_type(npMultM((number)(long) coef,(number)(long) coef_array[j],currRing->cf));
1218  assume(ci.coef!=0);
1219  ci.idx=j;
1220  pairs[pos++]=ci;
1221  }
1222  }
1223 }
1224 template<class number_type> void write_coef_idx_to_buffer_dense(CoefIdx<number_type>* const pairs,int& pos, number_type* const coef_array,const int rlen)
1225 {
1226  int j;
1227 
1228  for(j=0;j<rlen;j++)
1229  {
1230  if (coef_array[j]!=0)
1231  {
1232  assume(coef_array[j]!=0);
1234  ci.coef=coef_array[j];
1235  assume(ci.coef!=0);
1236  ci.idx=j;
1237  pairs[pos++]=ci;
1238  }
1239  }
1240 }
1241 
1242 template<class number_type> void write_minus_coef_idx_to_buffer_dense(CoefIdx<number_type>* const pairs,int& pos, number_type* const coef_array,const int rlen)
1243 {
1244  int j;
1245 
1246  for(j=0;j<rlen;j++)
1247  {
1248  if (coef_array[j]!=0)
1249  {
1250  assume(coef_array[j]!=0);
1252  STATISTIC(n_InpNeg); ci.coef=F4mat_to_number_type(npNegM((number)(long) coef_array[j],currRing->cf)); // FIXME: inplace negation! // TODO: check if this is not a bug!?
1253  assume(ci.coef!=0);
1254  ci.idx=j;
1255  pairs[pos++]=ci;
1256  }
1257  }
1258 }
1259 template<class number_type> void write_coef_idx_to_buffer(CoefIdx<number_type>* const pairs,int& pos,int* const idx_array, number_type* const coef_array,const int rlen)
1260 {
1261  int j;
1262  for(j=0;j<rlen;j++)
1263  {
1264  assume(coef_array[j]!=0);
1266  ci.coef=coef_array[j];
1267  ci.idx=idx_array[j];
1268  pairs[pos++]=ci;
1269  }
1270 }
1271 
1272 template<class number_type> void write_minus_coef_idx_to_buffer(CoefIdx<number_type>* const pairs,int& pos,int* const idx_array, number_type* const coef_array,const int rlen)
1273 {
1274  int j;
1275  for(j=0;j<rlen;j++)
1276  {
1277  assume(coef_array[j]!=0);
1279  STATISTIC(n_InpNeg); ci.coef=F4mat_to_number_type(npNegM((number)(unsigned long)coef_array[j],currRing->cf)); // FIXME: inplace negation! // TODO: check if this is not a bug!?
1280  ci.idx=idx_array[j];
1281  pairs[pos++]=ci;
1282  }
1283 }
1285 {
1286  int i;
1287  int together=0;
1288  for(i=0;i<len;i++)
1289  {
1290  MonRedResNP<number_type> red=mon[i];
1291  if ((red.ref) &&( red.ref->row))
1292  {
1293  together+=red.ref->row->len;
1294  }
1295  else
1296  {
1297  if ((red.ref) &&(red.ref->value_len==NoroCache<number_type>::backLinkCode))
1298  together++;
1299  }
1300  }
1301  //PrintS("here\n");
1302  if (together==0) return 0;
1303  //PrintS("there\n");
1304  cache->ensureTempBufferSize(together*sizeof(CoefIdx<number_type>));
1305  CoefIdx<number_type>* pairs=(CoefIdx<number_type>*) cache->tempBuffer; //omalloc(together*sizeof(CoefIdx<number_type>));
1306  int pos=0;
1307  const number one=npInit(1, currRing->cf);
1308  const number minus_one=npInit(-1, currRing->cf);
1309  for(i=0;i<len;i++)
1310  {
1311  MonRedResNP<number_type> red=mon[i];
1312  if ((red.ref) &&( red.ref->row))
1313  {
1314  //together+=red.ref->row->len;
1315  int* idx_array=red.ref->row->idx_array;
1316  number_type* coef_array=red.ref->row->coef_array;
1317  int rlen=red.ref->row->len;
1318  number coef=red.coef;
1319  if (idx_array)
1320  {
1321  if ((coef!=one)&&(coef!=minus_one))
1322  {
1323  write_coef_times_xx_idx_to_buffer(pairs,pos,idx_array, coef_array,rlen, coef);
1324  }
1325  else
1326  {
1327  if (coef==one)
1328  {
1329  write_coef_idx_to_buffer(pairs,pos,idx_array, coef_array,rlen);
1330  }
1331  else
1332  {
1333  assume(coef==minus_one);
1334  write_minus_coef_idx_to_buffer(pairs,pos,idx_array, coef_array,rlen);
1335  }
1336  }
1337  }
1338  else
1339  {
1340  if ((coef!=one)&&(coef!=minus_one))
1341  {
1342  write_coef_times_xx_idx_to_buffer_dense(pairs,pos,coef_array,rlen,coef);
1343  }
1344  else
1345  {
1346  if (coef==one)
1347  write_coef_idx_to_buffer_dense(pairs,pos,coef_array,rlen);
1348  else
1349  {
1350  assume(coef==minus_one);
1351  write_minus_coef_idx_to_buffer_dense(pairs,pos,coef_array,rlen);
1352  }
1353  }
1354  }
1355  }
1356  else
1357  {
1358  if ((red.ref) &&(red.ref->value_len==NoroCache<number_type>::backLinkCode))
1359  {
1361  ci.coef=F4mat_to_number_type(red.coef);
1362  ci.idx=red.ref->term_index;
1363  pairs[pos++]=ci;
1364  }
1365  }
1366  }
1367  assume(pos<=together);
1368  together=pos;
1369 
1370  std::sort(pairs,pairs+together);
1371 
1372  int act=0;
1373 
1374  assume(pairs[0].coef!=0);
1375  for(i=1;i<together;i++)
1376  {
1377  if (pairs[i].idx!=pairs[act].idx)
1378  {
1379  if (pairs[act].coef!=0)
1380  {
1381  act=act+1;
1382  }
1383  pairs[act]=pairs[i];
1384  }
1385  else
1386  {
1387  STATISTIC(n_Add); pairs[act].coef=F4mat_to_number_type(npAddM((number)(long)pairs[act].coef,(number)(long)pairs[i].coef,currRing->cf));
1388  }
1389  }
1390 
1391  if (pairs[act].coef==0)
1392  {
1393  act--;
1394  }
1395  int sparse_row_len=act+1;
1396  //Print("res len:%d",sparse_row_len);
1397  if (sparse_row_len==0) {return NULL;}
1398  SparseRow<number_type>* res=new SparseRow<number_type>(sparse_row_len);
1399  {
1400  number_type* coef_array=res->coef_array;
1401  int* idx_array=res->idx_array;
1402  for(i=0;i<sparse_row_len;i++)
1403  {
1404  idx_array[i]=pairs[i].idx;
1405  coef_array[i]=pairs[i].coef;
1406  }
1407  }
1408  //omfree(pairs);
1409 
1410  return res;
1411 }
1412 template<class number_type> SparseRow<number_type> * noro_red_to_non_poly_t(poly p, int &len, NoroCache<number_type>* cache,slimgb_alg* c)
1413 {
1414  assume(len==pLength(p));
1415  if (p==NULL)
1416  {
1417  len=0;
1418  return NULL;
1419  }
1420 
1422  int i=0;
1423  double max_density=0.0;
1424  while(p!=NULL)
1425  {
1426  poly t=p;
1427  pIter(p);
1428  pNext(t)=NULL;
1429 
1431  if ((red.ref) && (red.ref->row))
1432  {
1433  double act_density=(double) red.ref->row->len;
1434  act_density/=(double) cache->nIrreducibleMonomials;
1435  max_density=std::max(act_density,max_density);
1436  }
1437  mon[i]=red;
1438  i++;
1439  }
1440 
1441  assume(i==len);
1442  len=i;
1443  bool dense=true;
1444  if (max_density<0.3) dense=false;
1445  if (dense)
1446  {
1448  omfree(mon);
1449  return res;
1450  }
1451  else
1452  {
1454  omfree(mon);
1455  return res;
1456  }
1457  //in the loop before nIrreducibleMonomials increases, so position here is important
1458 
1459 }
1460 #endif
1461 wlen_type pELength(poly p, ring r);
1462 int terms_sort_crit(const void* a, const void* b);
1463 //void simplest_gauss_modp(number* a, int nrows,int ncols);
1464 // a: a[0,0],a[0,1]....a[nrows-1,ncols-1]
1465 // assume: field is Zp
1466 #ifdef USE_NORO
1467 
1468 
1469 template <class number_type > void write_poly_to_row(number_type* row, poly h, poly*terms, int tn, ring r)
1470 {
1471  //poly* base=row;
1472  while(h!=NULL)
1473  {
1474  //Print("h:%i\n",h);
1475  number coef=p_GetCoeff(h,r);
1476  poly* ptr_to_h=(poly*) bsearch(&h,terms,tn,sizeof(poly),terms_sort_crit);
1477  assume(ptr_to_h!=NULL);
1478  int pos=ptr_to_h-terms;
1479  row[pos]=F4mat_to_number_type(coef);
1480  //number_type_array[base+pos]=coef;
1481  pIter(h);
1482  }
1483 }
1484 template <class number_type > poly row_to_poly(number_type* row, poly* terms, int tn, ring r)
1485 {
1486  poly h=NULL;
1487  int j;
1488  number_type zero=0;//;npInit(0);
1489  for(j=tn-1;j>=0;j--)
1490  {
1491  if (!(zero==(row[j])))
1492  {
1493  poly t=terms[j];
1494  t=p_LmInit(t,r);
1495  p_SetCoeff(t,(number)(long) row[j],r);
1496  pNext(t)=h;
1497  h=t;
1498  }
1499 
1500  }
1501  return h;
1502 }
1503 template <class number_type > int modP_lastIndexRow(number_type* row,int ncols)
1504 {
1505  int lastIndex;
1506  const number_type zero=0;//npInit(0);
1507  for(lastIndex=ncols-1;lastIndex>=0;lastIndex--)
1508  {
1509  if (!(row[lastIndex]==zero))
1510  {
1511  return lastIndex;
1512  }
1513  }
1514  return -1;
1515 }
1516 template <class number_type> int term_nodes_sort_crit(const void* a, const void* b)
1517 {
1519 }
1520 
1521 template <class number_type>class ModPMatrixBackSubstProxyOnArray;
1522 template <class number_type > class ModPMatrixProxyOnArray
1523 {
1524 public:
1525  friend class ModPMatrixBackSubstProxyOnArray<number_type>;
1526 
1528  ModPMatrixProxyOnArray(number_type* array, int nnrows, int nncols)
1529  {
1530  this->ncols=nncols;
1531  this->nrows=nnrows;
1532  rows=(number_type**) omalloc((size_t)nnrows*sizeof(number_type*));
1533  startIndices=(int*)omalloc((size_t)nnrows*sizeof(int));
1534  int i;
1535  for(i=0;i<nnrows;i++)
1536  {
1537  rows[i]=array+((long)i*(long)nncols);
1538  updateStartIndex(i,-1);
1539  }
1540  }
1542  {
1543  omfree(rows);
1545  }
1546 
1547  void permRows(int i, int j)
1548  {
1549  number_type* h=rows[i];
1550  rows[i]=rows[j];
1551  rows[j]=h;
1552  int hs=startIndices[i];
1554  startIndices[j]=hs;
1555  }
1556  void multiplyRow(int row, number_type coef)
1557  {
1558  int i;
1559  number_type* row_array=rows[row];
1560  for(i=startIndices[row];i<ncols;i++)
1561  {
1562  row_array[i]=F4mat_to_number_type(npMult((number)(long) row_array[i],(number)(long) coef,currRing->cf));
1563  }
1564  }
1566  {
1567  //assume rows "under r" have bigger or equal start index
1568  number_type* row_array=rows[r];
1569  number_type zero=F4mat_to_number_type((number)0 /*npInit(0, currRing)*/);
1570  int start=startIndices[r];
1571  number_type coef=row_array[start];
1572  assume(start<ncols);
1573  int other_row;
1574  assume(!(npIsZero((number)(long) row_array[start],currRing->cf)));
1575  if (!(npIsOne((number)(long) coef,currRing->cf)))
1576  multiplyRow(r,F4mat_to_number_type(npInvers((number)(long) coef,currRing->cf)));
1577  assume(npIsOne((number)(long) row_array[start],currRing->cf));
1578  int lastIndex=modP_lastIndexRow(row_array, ncols);
1579  number minus_one=npInit(-1, currRing->cf);
1580  for (other_row=r+1;other_row<nrows;other_row++)
1581  {
1582  assume(startIndices[other_row]>=start);
1583  if (startIndices[other_row]==start)
1584  {
1585  int i;
1586  number_type* other_row_array=rows[other_row];
1587  number coef2=npNeg((number)(long) other_row_array[start],currRing->cf);
1588  if (coef2==minus_one)
1589  {
1590  for(i=start;i<=lastIndex;i++)
1591  {
1592  if (row_array[i]!=zero)
1593  { STATISTIC(n_Sub);
1594  other_row_array[i]=F4mat_to_number_type(npSubM((number)(long) other_row_array[i], (number)(long) row_array[i],currRing->cf));
1595  }
1596 
1597  }
1598  }
1599  else
1600  {
1601  //assume(FALSE);
1602  for(i=start;i<=lastIndex;i++)
1603  {
1604  if (row_array[i]!=zero)
1605  { STATISTIC(n_Add);
1606  other_row_array[i]=F4mat_to_number_type(npAddM(npMult(coef2,(number)(long) row_array[i],currRing->cf),(number)(long) other_row_array[i],currRing->cf));
1607  }
1608 
1609  }
1610  }
1611  updateStartIndex(other_row,start);
1612  assume(npIsZero((number)(long) other_row_array[start],currRing->cf));
1613  }
1614  }
1615  }
1616  void updateStartIndex(int row,int lower_bound)
1617  {
1618  number_type* row_array=rows[row];
1619  assume((lower_bound<0)||(npIsZero((number)(long) row_array[lower_bound],currRing->cf)));
1620  int i;
1621  //number_type zero=npInit(0);
1622  for(i=lower_bound+1;i<ncols;i++)
1623  {
1624  if (!(row_array[i]==0))
1625  break;
1626  }
1627  startIndices[row]=i;
1628  }
1629  int getStartIndex(int row)
1630  {
1631  return startIndices[row];
1632  }
1633  BOOLEAN findPivot(int &r, int &c)
1634  {
1635  //row>=r, col>=c
1636 
1637  while(c<ncols)
1638  {
1639  int i;
1640  for(i=r;i<nrows;i++)
1641  {
1642  assume(startIndices[i]>=c);
1643  if (startIndices[i]==c)
1644  {
1645  //r=i;
1646  if (r!=i)
1647  permRows(r,i);
1648  return TRUE;
1649  }
1650  }
1651  c++;
1652  }
1653  return FALSE;
1654  }
1655 protected:
1656  number_type** rows;
1658 };
1659 template <class number_type > class ModPMatrixBackSubstProxyOnArray
1660 {
1662  number_type** rows;
1664  int ncols;
1665  int nrows;
1667 public:
1668  void multiplyRow(int row, number_type coef)
1669  {
1670  int i;
1671  number_type* row_array=rows[row];
1672  for(i=startIndices[row];i<ncols;i++)
1673  {
1674  row_array[i]=F4mat_to_number_type(npMult((number)(long) row_array[i],(number)(long) coef,currRing->cf));
1675  }
1676  }
1678  {
1679 // (number_type* array, int nrows, int ncols, int* startIndices, number_type** rows){
1680  //we borrow some parameters ;-)
1681  //we assume, that nobody changes the order of the rows
1682  this->startIndices=p.startIndices;
1683  this->rows=p.rows;
1684  this->ncols=p.ncols;
1685  this->nrows=p.nrows;
1686  lastReducibleIndices=(int*) omalloc(nrows*sizeof(int));
1687  nonZeroUntil=0;
1688  while(nonZeroUntil<nrows)
1689  {
1691  {
1692  nonZeroUntil++;
1693  }
1694  else break;
1695  }
1696  if (TEST_OPT_PROT)
1697  Print("rank:%i\n",nonZeroUntil);
1698  nonZeroUntil--;
1699  int i;
1700  for(i=0;i<=nonZeroUntil;i++)
1701  {
1703  assume(!(npIsZero((number)(long) rows[i][startIndices[i]],currRing->cf)));
1704  assume(startIndices[i]>=i);
1706  }
1707  }
1708  void updateLastReducibleIndex(int r, int upper_bound)
1709  {
1710  number_type* row_array=rows[r];
1711  if (upper_bound>nonZeroUntil) upper_bound=nonZeroUntil+1;
1712  int i;
1713  const number_type zero=0;//npInit(0);
1714  for(i=upper_bound-1;i>r;i--)
1715  {
1716  int start=startIndices[i];
1717  assume(start<ncols);
1718  if (!(row_array[start]==zero))
1719  {
1720  lastReducibleIndices[r]=start;
1721  return;
1722  }
1723  }
1724  lastReducibleIndices[r]=-1;
1725  }
1727  {
1728  int start=startIndices[r];
1729  assume(start<ncols);
1730  number_type zero=0;//npInit(0);
1731  number_type* row_array=rows[r];
1732  assume((!(npIsZero((number)(long) row_array[start],currRing->cf))));
1733  assume(start<ncols);
1734  int other_row;
1735  if (!(npIsOne((number)(long) row_array[r],currRing->cf)))
1736  {
1737  //it should be one, but this safety is not expensive
1738  multiplyRow(r, F4mat_to_number_type(npInvers((number)(long) row_array[start],currRing->cf)));
1739  }
1740  int lastIndex=modP_lastIndexRow(row_array, ncols);
1741  assume(lastIndex<ncols);
1742  assume(lastIndex>=0);
1743  for(other_row=r-1;other_row>=0;other_row--)
1744  {
1745  assume(lastReducibleIndices[other_row]<=start);
1746  if (lastReducibleIndices[other_row]==start)
1747  {
1748  number_type* other_row_array=rows[other_row];
1749  number coef=npNeg((number)(long) other_row_array[start],currRing->cf);
1750  assume(!(npIsZero(coef,currRing->cf)));
1751  int i;
1752  assume(start>startIndices[other_row]);
1753  for(i=start;i<=lastIndex;i++)
1754  {
1755  if (row_array[i]!=zero)
1756  {
1757  STATISTIC(n_Add);
1758  other_row_array[i]=F4mat_to_number_type(npAddM(npMult(coef,(number)(long)row_array[i],currRing->cf),(number)(long)other_row_array[i],currRing->cf));
1759  }
1760  }
1761  updateLastReducibleIndex(other_row,r);
1762  }
1763  }
1764  }
1766  {
1768  }
1770  {
1771  int i;
1772  for(i=nonZeroUntil;i>0;i--)
1773  {
1775  }
1776  }
1777 };
1778 template <class number_type > void simplest_gauss_modp(number_type* a, int nrows,int ncols)
1779 {
1780  //use memmoves for changing rows
1781  //if (TEST_OPT_PROT)
1782  // PrintS("StartGauss\n");
1784 
1785  int c=0;
1786  int r=0;
1787  while(mat.findPivot(r,c))
1788  {
1789  //int pivot=find_pivot()
1790  mat.reduceOtherRowsForward(r);
1791  r++;
1792  c++;
1793  }
1795  backmat.backwardSubstitute();
1796  //backward substitutions
1797  //if (TEST_OPT_PROT)
1798  //PrintS("StopGauss\n");
1799 }
1800 //int term_nodes_sort_crit(const void* a, const void* b);
1801 template <class number_type> void noro_step(poly*p,int &pn,slimgb_alg* c)
1802 {
1803  //Print("Input rows %d\n",pn);
1804  int j;
1805  if (TEST_OPT_PROT)
1806  {
1807  Print("Input rows %d\n",pn);
1808  }
1809 
1810  NoroCache<number_type> cache;
1811 
1813  int non_zeros=0;
1814  for(j=0;j<pn;j++)
1815  {
1816  poly h=p[j];
1817  int h_len=pLength(h);
1818  //number coef;
1819  srows[non_zeros]=noro_red_to_non_poly_t<number_type>(h,h_len,&cache,c);
1820  if (srows[non_zeros]!=NULL) non_zeros++;
1821  }
1822  std::vector<DataNoroCacheNode<number_type>*> irr_nodes;
1823  cache.collectIrreducibleMonomials(irr_nodes);
1824  //now can build up terms array
1825  //Print("historic irred Mon%d\n",cache.nIrreducibleMonomials);
1826  int n=irr_nodes.size();//cache.countIrreducibleMonomials();
1827  cache.nIrreducibleMonomials=n;
1828  if (TEST_OPT_PROT)
1829  {
1830  Print("Irred Mon:%d\n",n);
1831  Print("red Mon:%d\n",cache.nReducibleMonomials);
1832  }
1834 
1835  for(j=0;j<n;j++)
1836  {
1837  assume(irr_nodes[j]!=NULL);
1838  assume(irr_nodes[j]->value_len==NoroCache<number_type>::backLinkCode);
1839  term_nodes[j].t=irr_nodes[j]->value_poly;
1840  assume(term_nodes[j].t!=NULL);
1841  term_nodes[j].node=irr_nodes[j];
1842  }
1843 
1844  qsort(term_nodes,n,sizeof(TermNoroDataNode<number_type>),term_nodes_sort_crit<number_type>);
1845  poly* terms=(poly*) omalloc(n*sizeof(poly));
1846 
1847  int* old_to_new_indices=(int*) omalloc(cache.nIrreducibleMonomials*sizeof(int));
1848  for(j=0;j<n;j++)
1849  {
1850  old_to_new_indices[term_nodes[j].node->term_index]=j;
1851  term_nodes[j].node->term_index=j;
1852  terms[j]=term_nodes[j].t;
1853  }
1854 
1855  //if (TEST_OPT_PROT)
1856  // Print("Evaluate Rows \n");
1857  pn=non_zeros;
1858  number_type* number_array=(number_type*) omalloc0(((size_t)n)*pn*sizeof(number_type));
1859 
1860  for(j=0;j<pn;j++)
1861  {
1862  int i;
1863  number_type* row=number_array+((long)n)*(long)j;
1864  /*for(i=0;i<n;i++)
1865  {
1866  row[i]=zero;
1867  }*/
1868 
1869  SparseRow<number_type>* srow=srows[j];
1870 
1871  if (srow)
1872  {
1873  int* const idx_array=srow->idx_array;
1874  number_type* const coef_array=srow->coef_array;
1875  const int len=srow->len;
1876  if (srow->idx_array)
1877  {
1878  for(i=0;i<len;i++)
1879  {
1880  int idx=old_to_new_indices[idx_array[i]];
1881  row[idx]=F4mat_to_number_type(coef_array[i]);
1882  }
1883  }
1884  else
1885  {
1886  for(i=0;i<len;i++)
1887  {
1888  row[old_to_new_indices[i]]=F4mat_to_number_type(coef_array[i]);
1889  }
1890  }
1891  delete srow;
1892  }
1893  }
1894 
1895  //static int export_n=0;
1896  //export_mat(number_array,pn,n,"mat%i.py",++export_n);
1898 
1899  int p_pos=0;
1900  for(j=0;j<pn;j++)
1901  {
1902  poly h=row_to_poly(number_array+((long)j)*((long)n),terms,n,c->r);
1903  if(h!=NULL)
1904  {
1905  p[p_pos++]=h;
1906  }
1907  }
1908  pn=p_pos;
1909  omfree(terms);
1910  omfree(term_nodes);
1912  #ifdef NORO_NON_POLY
1913  omfree(srows);
1914  omfree(old_to_new_indices);
1915  #endif
1916  //don't forget the rank
1917 
1918 }
1919 
1921 {
1922  int i;
1923  for(i=0;i<root.branches_len;i++)
1924  {
1925  collectIrreducibleMonomials(1,root.branches[i],res);
1926  }
1927 }
1929 {
1930  assume(level>=0);
1931  if (node==NULL) return;
1932  if (level<(currRing->N))
1933  {
1934  int i;
1935  for(i=0;i<node->branches_len;i++)
1936  {
1937  collectIrreducibleMonomials(level+1,node->branches[i],res);
1938  }
1939  }
1940  else
1941  {
1943  if (dn->value_len==backLinkCode)
1944  {
1945  res.push_back(dn);
1946  }
1947  }
1948 }
1949 
1951 {
1952  int i;
1953  NoroCacheNode* parent=&root;
1954  for(i=1;i<(currRing->N);i++)
1955  {
1956  parent=parent->getBranch(p_GetExp(term,i,currRing));
1957  if (!(parent))
1958  {
1959  return NULL;
1960  }
1961  }
1963  return res_holder;
1964 }
1965 template<class number_type> poly NoroCache<number_type>::lookup(poly term, BOOLEAN& succ, int & len)
1966 {
1967  int i;
1968  NoroCacheNode* parent=&root;
1969  for(i=1;i<(currRing->N);i++)
1970  {
1971  parent=parent->getBranch(p_GetExp(term,i,currRing));
1972  if (!(parent))
1973  {
1974  succ=FALSE;
1975  return NULL;
1976  }
1977  }
1979  if (res_holder)
1980  {
1981  succ=TRUE;
1982  if ( /*(*/ res_holder->value_len==backLinkCode /*)*/ )
1983  {
1984  len=1;
1985  return term;
1986  }
1987  len=res_holder->value_len;
1988  return res_holder->value_poly;
1989  } else {
1990  succ=FALSE;
1991  return NULL;
1992  }
1993 }
1994 #endif
1995 
1996 #endif
int_pair_node::b
int b
Definition: tgb_internal.h:192
nrows
int nrows
Definition: cf_linsys.cc:32
FALSE
#define FALSE
Definition: auxiliary.h:94
NoroCache::treeInsert
DataNoroCacheNode< number_type > * treeInsert(poly term, poly nf, int len)
Definition: tgb_internal.h:711
tgb_uint16
unsigned short tgb_uint16
Definition: tgb_internal.h:429
poly_list_node::next
poly_list_node * next
Definition: tgb_internal.h:185
CoefIdx
Definition: tgb_internal.h:1185
sub_dense
void sub_dense(number_type *const temp_array, int, const number_type *row, int len)
Definition: tgb_internal.h:1027
skStrategy
Definition: kutil.h:262
omalloc.h
noro_red_to_non_poly_t
SparseRow< number_type > * noro_red_to_non_poly_t(poly p, int &len, NoroCache< number_type > *cache, slimgb_alg *c)
Definition: tgb_internal.h:1412
slimgb_alg::pTotaldegree
unsigned long pTotaldegree(poly p)
Definition: tgb_internal.h:289
NoroCache::ensureTempBufferSize
void ensureTempBufferSize(size_t size)
Definition: tgb_internal.h:670
red_object::flatten
void flatten()
Definition: tgb.cc:4823
UNLIKELY
#define UNLIKELY(X)
Definition: auxiliary.h:418
ncols
int int ncols
Definition: cf_linsys.cc:32
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:51
ModPMatrixProxyOnArray::multiplyRow
void multiplyRow(int row, number_type coef)
Definition: tgb_internal.h:1556
pLmEqual
#define pLmEqual(p1, p2)
Definition: polys.h:111
TermNoroDataNode::t
poly t
Definition: tgb_internal.h:587
tgb_uint32
unsigned int tgb_uint32
Definition: tgb_internal.h:431
simple_reducer
Definition: tgb_internal.h:360
slimgb_alg::reduction_steps
unsigned int reduction_steps
Definition: tgb_internal.h:260
red_object::adjust_coefs
void adjust_coefs(number c_r, number c_ac_r)
kutil.h
red_object::clear_to_poly
int clear_to_poly()
Definition: tgb.cc:4835
sorted_pair_node::lcm_of_lm
poly lcm_of_lm
Definition: tgb_internal.h:162
p_GetExp
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:470
j
int j
Definition: facHensel.cc:105
omFree
#define omFree(addr)
Definition: omAllocDecl.h:261
NoroCacheNode::setNode
NoroCacheNode * setNode(int branch, NoroCacheNode *node)
Definition: tgb_internal.h:445
slimgb_alg::introduceDelayedPairs
void introduceDelayedPairs(poly *pa, int s)
Definition: tgb.cc:3102
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:102
add_coef_times_sparse
void add_coef_times_sparse(number_type *const temp_array, int, SparseRow< number_type > *row, number coef)
Definition: tgb_internal.h:905
NoroCache::nIrreducibleMonomials
int nIrreducibleMonomials
Definition: tgb_internal.h:706
NoroCache::treeInsert
DataNoroCacheNode< number_type > * treeInsert(poly term, SparseRow< number_type > *srow)
Definition: tgb_internal.h:724
kInline.h
NoroCache::NoroCache
NoroCache()
Definition: tgb_internal.h:657
F4mat_to_number_type
#define F4mat_to_number_type(a)
Definition: tgb_internal.h:428
p_ExpVectorDiff
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1411
slimgb_alg::apairs
sorted_pair_node ** apairs
Definition: tgb_internal.h:244
find_erg::fromS
BOOLEAN fromS
Definition: tgb_internal.h:393
sorted_pair_node::deg
int deg
Definition: tgb_internal.h:165
ModPMatrixBackSubstProxyOnArray::nrows
int nrows
Definition: tgb_internal.h:1665
PolySimple::PolySimple
PolySimple(const PolySimple &a)
Definition: tgb_internal.h:96
npMultM
static number npMultM(number a, number b, const coeffs r)
Definition: modulop.h:72
n_GetChar
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition: coeffs.h:444
NoroCacheNode
Definition: tgb_internal.h:432
simple_reducer::p
poly p
Definition: tgb_internal.h:363
polyset
poly * polyset
Definition: polys.h:254
slimgb_alg::tailReductions
BOOLEAN tailReductions
Definition: tgb_internal.h:282
find_erg::reduce_by
int reduce_by
Definition: tgb_internal.h:392
MonRedResNP::ref
DataNoroCacheNode< number_type > * ref
Definition: tgb_internal.h:152
slimgb_alg::tmp_lm
poly tmp_lm
Definition: tgb_internal.h:238
calc_state
calc_state
Definition: tgb_internal.h:325
pairs
void pairs()
DenseRow::begin
int begin
Definition: tgb_internal.h:503
number_array
number * number_array
Definition: ntupel.cc:26
free_sorted_pair_node
void free_sorted_pair_node(sorted_pair_node *s, const ring r)
Definition: tgb.cc:3916
quick_pop_pair
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
Definition: tgb.cc:3862
slimgb_alg::tmp_spn
sorted_pair_node ** tmp_spn
Definition: tgb_internal.h:240
reduction_step::c
slimgb_alg * c
Definition: tgb_internal.h:357
ModPMatrixBackSubstProxyOnArray::backwardSubstitute
void backwardSubstitute(int r)
Definition: tgb_internal.h:1726
ModPMatrixProxyOnArray::startIndices
int * startIndices
Definition: tgb_internal.h:1657
simple_reducer::do_reduce
virtual void do_reduce(red_object &ro)
Definition: tgb.cc:4847
skStrategy::S
polyset S
Definition: kutil.h:297
modP_lastIndexRow
int modP_lastIndexRow(number_type *row, int ncols)
Definition: tgb_internal.h:1503
terms_sort_crit
int terms_sort_crit(const void *a, const void *b)
Definition: tgb.cc:2030
ModPMatrixProxyOnArray::nrows
int nrows
Definition: tgb_internal.h:1527
ModPMatrixProxyOnArray
Definition: tgb_internal.h:1522
p_LmInit
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1272
skStrategy::lenS
intset lenS
Definition: kutil.h:310
sorted_pair_node::i
int i
Definition: tgb_internal.h:163
NoroCache::poly_vec
std::vector< PolySimple > poly_vec
Definition: tgb_internal.h:750
ModPMatrixBackSubstProxyOnArray
Definition: tgb_internal.h:1521
term_nodes_sort_crit
int term_nodes_sort_crit(const void *a, const void *b)
Definition: tgb_internal.h:1516
write_coef_idx_to_buffer
void write_coef_idx_to_buffer(CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen)
Definition: tgb_internal.h:1259
polys.h
slimgb_alg::use_noro_last_block
BOOLEAN use_noro_last_block
Definition: tgb_internal.h:278
slimgb_alg::weighted_lengths
wlen_type * weighted_lengths
Definition: tgb_internal.h:233
noro_step
void noro_step(poly *p, int &pn, slimgb_alg *c)
Definition: tgb_internal.h:1801
slimgb_alg::T_deg_full
int * T_deg_full
Definition: tgb_internal.h:237
int_pair_node::next
int_pair_node * next
Definition: tgb_internal.h:190
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
PolySimple::operator==
bool operator==(const PolySimple &other)
Definition: tgb_internal.h:116
NoroCache::lookup
poly lookup(poly term, BOOLEAN &succ, int &len)
Definition: tgb_internal.h:1965
slimgb_alg::pTotaldegree_full
int pTotaldegree_full(poly p)
Definition: tgb_internal.h:297
mp_array_list::mp
monom_poly * mp
Definition: tgb_internal.h:201
sorted_pair_node
Definition: tgb_internal.h:158
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
red_object::bucket
kBucket_pt bucket
Definition: tgb_internal.h:312
red_object::canonicalize
void canonicalize()
Definition: tgb.cc:871
CoefIdx::operator<
bool operator<(const CoefIdx< number_type > &other) const
Definition: tgb_internal.h:1190
UNCALCULATED
@ UNCALCULATED
Definition: tgb_internal.h:327
PolySimple::operator=
PolySimple & operator=(const PolySimple &p2)
Definition: tgb_internal.h:101
slimgb_alg::r
ring r
Definition: tgb_internal.h:231
tgb_pair_better_gen2
int tgb_pair_better_gen2(const void *ap, const void *bp)
Definition: tgb.cc:680
npInvers
#define npInvers
Definition: tgb_internal.h:74
options.h
top_pair
sorted_pair_node * top_pair(slimgb_alg *c)
Definition: tgb.cc:3838
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:988
add_to_basis_ideal_quotient
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
Definition: tgb.cc:1426
ModPMatrixBackSubstProxyOnArray::multiplyRow
void multiplyRow(int row, number_type coef)
Definition: tgb_internal.h:1668
slimgb_alg::normal_forms
int normal_forms
Definition: tgb_internal.h:265
write_coef_idx_to_buffer_dense
void write_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
Definition: tgb_internal.h:1224
row_to_poly
poly row_to_poly(number_type *row, poly *terms, int tn, ring r)
Definition: tgb_internal.h:1484
slimgb_alg::n
int n
Definition: tgb_internal.h:261
slimgb_alg::soon_free
int_pair_node * soon_free
Definition: tgb_internal.h:243
loop
#define loop
Definition: structs.h:78
NoroCache::backLinkCode
static const int backLinkCode
Definition: tgb_internal.h:606
b
CanonicalForm b
Definition: cfModGcd.cc:4044
ModPMatrixBackSubstProxyOnArray::nonZeroUntil
int nonZeroUntil
Definition: tgb_internal.h:1666
tgb_uint8
unsigned char tgb_uint8
Definition: tgb_internal.h:430
write_poly_to_row
void write_poly_to_row(number_type *row, poly h, poly *terms, int tn, ring r)
Definition: tgb_internal.h:1469
ap
Definition: ap.h:39
slimgb_alg::cleanDegs
void cleanDegs(int lower, int upper)
Definition: tgb.cc:3756
monom_poly::m
poly m
Definition: tgb_internal.h:196
find_erg::expand
poly expand
Definition: tgb_internal.h:388
nf
Definition: gnumpfl.cc:27
slimgb_alg::Rcounter
int Rcounter
Definition: tgb_internal.h:267
simple_reducer::simple_reducer
simple_reducer(poly pp, int pp_len, int pp_reducer_deg, slimgb_alg *pp_c=NULL)
Definition: tgb_internal.h:367
term
Definition: int_poly.h:33
NoroCache::buffer
number * buffer
Definition: tgb_internal.h:755
ModPMatrixBackSubstProxyOnArray::lastReducibleIndices
int * lastReducibleIndices
Definition: tgb_internal.h:1663
convert_to_sparse_row
SparseRow< number_type > * convert_to_sparse_row(number_type *temp_array, int temp_size, int non_zeros)
Definition: tgb_internal.h:837
NoroCacheNode::branches_len
int branches_len
Definition: tgb_internal.h:436
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:193
PolySimple::impl
poly impl
Definition: tgb_internal.h:120
write_minus_coef_idx_to_buffer_dense
void write_minus_coef_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen)
Definition: tgb_internal.h:1242
slimgb_alg::F4_mode
BOOLEAN F4_mode
Definition: tgb_internal.h:284
simplest_gauss_modp
void simplest_gauss_modp(number_type *a, int nrows, int ncols)
Definition: tgb_internal.h:1778
noro_red_mon_to_non_poly
MonRedResNP< number_type > noro_red_mon_to_non_poly(poly t, NoroCache< number_type > *cache, slimgb_alg *c)
Definition: tgb_internal.h:758
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:813
NoroCache::insertAndTransferOwnerShip
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
Definition: tgb_internal.h:647
currRing
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
slimgb_alg::~slimgb_alg
virtual ~slimgb_alg()
Definition: tgb.cc:3326
slimgb_alg::add_later
ideal add_later
Definition: tgb_internal.h:229
DataNoroCacheNode::term_index
int term_index
Definition: tgb_internal.h:557
n_Add
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition: coeffs.h:656
TRUE
#define TRUE
Definition: auxiliary.h:98
i
int i
Definition: cfEzgcd.cc:125
npAddM
static number npAddM(number a, number b, const coeffs r)
Definition: modulop.h:125
find_erg::expand_length
int expand_length
Definition: tgb_internal.h:389
poly_array_list::size
int size
Definition: tgb_internal.h:210
res
CanonicalForm res
Definition: facAbsFact.cc:64
act
static scmon act
Definition: hdegree.cc:1078
skStrategy::sl
int sl
Definition: kutil.h:341
poly_list_node::p
poly p
Definition: tgb_internal.h:184
ModPMatrixProxyOnArray::ncols
int ncols
Definition: tgb_internal.h:1527
NoroCache::~NoroCache
~NoroCache()
Definition: tgb_internal.h:691
PolySimple::~PolySimple
~PolySimple()
Definition: tgb_internal.h:108
npSubM
static number npSubM(number a, number b, const coeffs r)
Definition: modulop.h:135
DataNoroCacheNode::DataNoroCacheNode
DataNoroCacheNode(SparseRow< number_type > *row)
Definition: tgb_internal.h:566
noro_red_to_non_poly_dense
SparseRow< number_type > * noro_red_to_non_poly_dense(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
Definition: tgb_internal.h:1094
slimgb_alg::nc
BOOLEAN nc
Definition: tgb_internal.h:285
CoefIdx::idx
int idx
Definition: tgb_internal.h:1189
DenseRow::end
int end
Definition: tgb_internal.h:504
sorted_pair_node::j
int j
Definition: tgb_internal.h:164
ModPMatrixBackSubstProxyOnArray::backwardSubstitute
void backwardSubstitute()
Definition: tgb_internal.h:1769
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
noro_red_to_non_poly_sparse
SparseRow< number_type > * noro_red_to_non_poly_sparse(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
Definition: tgb_internal.h:1284
pTest
#define pTest(p)
Definition: polys.h:409
npNegM
static number npNegM(number a, const coeffs r)
Definition: modulop.h:175
NoroCache::tempBuffer
void * tempBuffer
Definition: tgb_internal.h:708
CoefIdx::coef
number_type coef
Definition: tgb_internal.h:1188
npMult
#define npMult
Definition: tgb_internal.h:78
reduction_step::~reduction_step
virtual ~reduction_step()
Definition: tgb.cc:4883
slimgb_alg::short_Exps
long * short_Exps
Definition: tgb_internal.h:234
sub_sparse
void sub_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
Definition: tgb_internal.h:1075
NoroCache::insert
DataNoroCacheNode< number_type > * insert(poly term, SparseRow< number_type > *srow)
Definition: tgb_internal.h:636
SparseRow
Definition: tgb_internal.h:514
slimgb_alg::T_deg
int * T_deg
Definition: tgb_internal.h:236
slimgb_alg::slimgb_alg
slimgb_alg(ideal I, int syz_comp, BOOLEAN F4, int deg_pos)
Definition: tgb.cc:3138
NoroCache::tempBufferSize
size_t tempBufferSize
Definition: tgb_internal.h:709
MonRedResNP::coef
number coef
Definition: tgb_internal.h:149
ModPMatrixBackSubstProxyOnArray::startIndices
int * startIndices
Definition: tgb_internal.h:1661
NoroCache::getCacheReference
DataNoroCacheNode< number_type > * getCacheReference(poly term)
Definition: tgb_internal.h:1950
h
static Poly * h
Definition: janet.cc:972
DenseRow::DenseRow
DenseRow()
Definition: tgb_internal.h:505
omrealloc
#define omrealloc(addr, size)
Definition: omAllocDecl.h:233
max
static int max(int a, int b)
Definition: fast_mult.cc:264
SparseRow::coef_array
number_type * coef_array
Definition: tgb_internal.h:518
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
pOne
#define pOne()
Definition: polys.h:309
DenseRow::array
number * array
Definition: tgb_internal.h:502
NoroCache::root
NoroCacheNode root
Definition: tgb_internal.h:754
DataNoroCacheNode::value_poly
poly value_poly
Definition: tgb_internal.h:551
NoroCache::insert
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
Definition: tgb_internal.h:607
pos_helper
int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set)
Definition: tgb_internal.h:397
pIter
#define pIter(p)
Definition: monomials.h:38
SparseRow::SparseRow
SparseRow()
Definition: tgb_internal.h:520
n_Mult
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:636
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:210
p_polys.h
slimgb_alg::extended_product_crit
int extended_product_crit
Definition: tgb_internal.h:272
slimgb_alg::isDifficultField
BOOLEAN isDifficultField
Definition: tgb_internal.h:279
TermNoroDataNode::node
DataNoroCacheNode< number_type > * node
Definition: tgb_internal.h:586
free
#define free
Definition: omAllocFunc.c:12
mp_array_list::size
int size
Definition: tgb_internal.h:202
DataNoroCacheNode
Definition: tgb_internal.h:123
slimgb_alg::pair_top
int pair_top
Definition: tgb_internal.h:270
add_coef_times_dense
void add_coef_times_dense(number_type *const temp_array, int, const number_type *row, int len, number coef)
Definition: tgb_internal.h:953
slimgb_alg::strat
kStrategy strat
Definition: tgb_internal.h:235
slimgb_alg::expandS
poly * expandS
Definition: tgb_internal.h:241
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1498
reduction_step::reduction_id
int reduction_id
Definition: tgb_internal.h:358
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
TermNoroDataNode
Definition: tgb_internal.h:583
NoroCacheNode::getOrInsertBranch
NoroCacheNode * getOrInsertBranch(int branch)
Definition: tgb_internal.h:490
PolySimple::PolySimple
PolySimple()
Definition: tgb_internal.h:92
slim_nsize
int slim_nsize(number n, ring r)
Definition: tgb.cc:73
poly_array_list::p
poly * p
Definition: tgb_internal.h:209
int_pair_node
Definition: tgb_internal.h:188
now_t_rep
void now_t_rep(const int &arg_i, const int &arg_j, slimgb_alg *c)
Definition: tgb.cc:3623
n_InpNeg
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:557
sort
void sort(CFArray &A, int l=0)
quick sort A
Definition: facSparseHensel.h:114
simple_reducer::~simple_reducer
~simple_reducer()
Definition: tgb.cc:4887
SparseRow::len
int len
Definition: tgb_internal.h:519
wlen_type
int64 wlen_type
Definition: kutil.h:50
ModPMatrixProxyOnArray::reduceOtherRowsForward
void reduceOtherRowsForward(int r)
Definition: tgb_internal.h:1565
slimgb_alg::F
mp_array_list * F
Definition: tgb_internal.h:253
add_sparse
void add_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
Definition: tgb_internal.h:1055
n_Sub
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition: coeffs.h:669
kFindDivisibleByInS_easy
int kFindDivisibleByInS_easy(kStrategy strat, const red_object &obj)
Definition: tgb.cc:685
STATISTIC
#define STATISTIC(f)
Definition: numstats.h:16
slimgb_alg::current_degree
int current_degree
Definition: tgb_internal.h:266
mp_array_list::next
mp_array_list * next
Definition: tgb_internal.h:203
MonRedResNP::MonRedResNP
MonRedResNP()
Definition: tgb_internal.h:153
kbuckets.h
ModPMatrixProxyOnArray::updateStartIndex
void updateStartIndex(int row, int lower_bound)
Definition: tgb_internal.h:1616
slimgb_alg::deg_pos
int deg_pos
Definition: tgb_internal.h:276
monom_poly::f
poly f
Definition: tgb_internal.h:197
slimgb_alg::lastDpBlockStart
int lastDpBlockStart
Definition: tgb_internal.h:274
npIsZero
#define npIsZero
Definition: tgb_internal.h:76
slimgb_alg::is_homog
BOOLEAN is_homog
Definition: tgb_internal.h:281
ring.h
omBin
omBin_t * omBin
Definition: omStructs.h:12
slimgb_alg::S
ideal S
Definition: tgb_internal.h:230
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:858
kstd1.h
monom_poly
Definition: tgb_internal.h:194
DataNoroCacheNode::~DataNoroCacheNode
~DataNoroCacheNode()
Definition: tgb_internal.h:577
min
static int min(int a, int b)
Definition: fast_mult.cc:268
DataNoroCacheNode::value_len
int value_len
Definition: tgb_internal.h:550
poly_array_list::next
poly_array_list * next
Definition: tgb_internal.h:211
npNeg
#define npNeg
Definition: tgb_internal.h:73
NoroCache
Definition: tgb_internal.h:590
slimgb_alg::lastCleanedDeg
int lastCleanedDeg
Definition: tgb_internal.h:275
ModPMatrixProxyOnArray::rows
number_type ** rows
Definition: tgb_internal.h:1656
write_coef_times_xx_idx_to_buffer
void write_coef_times_xx_idx_to_buffer(CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen, const number coef)
Definition: tgb_internal.h:1195
HASTREP
@ HASTREP
Definition: tgb_internal.h:328
npIsOne
#define npIsOne
Definition: tgb_internal.h:75
red_object::initial_quality
wlen_type initial_quality
Definition: tgb_internal.h:317
NoroCacheNode::~NoroCacheNode
virtual ~NoroCacheNode()
Definition: tgb_internal.h:481
SparseRow::idx_array
int * idx_array
Definition: tgb_internal.h:517
simple_reducer::reduce
virtual void reduce(red_object *r, int l, int u)
we assume hat all occuring red_objects have same lm, and all occ. lm's in r[l...u] are the same,...
Definition: tgb.cc:4859
reduction_step
makes on each red_object in a region a single_step
Definition: tgb_internal.h:349
red_object::guess_quality
wlen_type guess_quality(slimgb_alg *c)
Definition: tgb.cc:591
poly_array_list
Definition: tgb_internal.h:207
si_max
static int si_max(const int a, const int b)
Definition: auxiliary.h:138
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
NoroCacheNode::getBranch
NoroCacheNode * getBranch(int branch)
Definition: tgb_internal.h:476
ModPMatrixBackSubstProxyOnArray::rows
number_type ** rows
Definition: tgb_internal.h:1662
simple_reducer::reducer_deg
int reducer_deg
Definition: tgb_internal.h:366
mp_array_list
Definition: tgb_internal.h:199
slimgb_alg::use_noro
BOOLEAN use_noro
Definition: tgb_internal.h:277
reduction_step::reduce
virtual void reduce(red_object *r, int l, int u)
we assume hat all occuring red_objects have same lm, and all occ. lm's in r[l...u] are the same,...
Definition: tgb.cc:4843
Print
#define Print
Definition: emacs.cc:80
slimgb_alg
Definition: tgb_internal.h:213
omalloc
#define omalloc(size)
Definition: omAllocDecl.h:228
find_erg::to_reduce_l
int to_reduce_l
Definition: tgb_internal.h:391
int64
long int64
Definition: auxiliary.h:66
ModPMatrixBackSubstProxyOnArray::updateLastReducibleIndex
void updateLastReducibleIndex(int r, int upper_bound)
Definition: tgb_internal.h:1708
slimgb_alg::average_length
int average_length
Definition: tgb_internal.h:273
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:413
pELength
wlen_type pELength(poly p, ring r)
slimgb_alg::states
char ** states
Definition: tgb_internal.h:224
NoroCache::collectIrreducibleMonomials
void collectIrreducibleMonomials(std::vector< DataNoroCacheNode< number_type > * > &res)
Definition: tgb_internal.h:1920
do_t_rep_gb
ideal do_t_rep_gb(ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
Definition: tgb.cc:3568
NoroCache::treeInsertBackLink
DataNoroCacheNode< number_type > * treeInsertBackLink(poly term)
Definition: tgb_internal.h:737
slimgb_alg::tmp_pair_lm
poly * tmp_pair_lm
Definition: tgb_internal.h:239
NoroCache::nReducibleMonomials
int nReducibleMonomials
Definition: tgb_internal.h:707
assume
#define assume(x)
Definition: mod2.h:390
ModPMatrixProxyOnArray::permRows
void permRows(int i, int j)
Definition: tgb_internal.h:1547
ModPMatrixProxyOnArray::~ModPMatrixProxyOnArray
~ModPMatrixProxyOnArray()
Definition: tgb_internal.h:1541
NULL
#define NULL
Definition: omList.c:10
red_object::p
poly p
Definition: tgb_internal.h:313
red_object
Definition: tgb_internal.h:309
ideals.h
slimgb_alg::array_lengths
int array_lengths
Definition: tgb_internal.h:264
l
int l
Definition: cfEzgcd.cc:93
slimgb_alg::lengths
int * lengths
Definition: tgb_internal.h:232
PolySimple
Definition: tgb_internal.h:85
ModPMatrixProxyOnArray::ModPMatrixProxyOnArray
ModPMatrixProxyOnArray(number_type *array, int nnrows, int nncols)
Definition: tgb_internal.h:1528
kBucket
Definition: kbuckets.h:178
slimgb_alg::completed
BOOLEAN completed
Definition: tgb_internal.h:280
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:234
PolySimple::operator<
bool operator<(const PolySimple &other) const
Definition: tgb_internal.h:112
red_object::validate
void validate()
Definition: tgb.cc:4828
MonRedResNP
Definition: tgb_internal.h:146
slimgb_alg::eliminationProblem
BOOLEAN eliminationProblem
Definition: tgb_internal.h:283
p_Totaldegree
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1444
p
int p
Definition: cfModGcd.cc:4019
int_pair_node::a
int a
Definition: tgb_internal.h:191
spn_merge
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
Definition: tgb.cc:751
simple_reducer::fill_back
kBucket_pt fill_back
Definition: tgb_internal.h:364
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
pLmCmp
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
slimgb_alg::syz_comp
int syz_comp
array_lengths should be greater equal n;
Definition: tgb_internal.h:263
slimgb_alg::gcd_of_terms
poly * gcd_of_terms
Definition: tgb_internal.h:242
NoroCacheNode::NoroCacheNode
NoroCacheNode()
Definition: tgb_internal.h:439
DataNoroCacheNode::row
SparseRow< number_type > * row
Definition: tgb_internal.h:553
find_erg
Definition: tgb_internal.h:386
slimgb_alg::easy_product_crit
int easy_product_crit
Definition: tgb_internal.h:271
slimgb_alg::F_minus
poly_array_list * F_minus
Definition: tgb_internal.h:254
poly_list_node
Definition: tgb_internal.h:182
sorted_pair_node::expected_length
wlen_type expected_length
Definition: tgb_internal.h:161
NoroCache::ressources
poly_vec ressources
Definition: tgb_internal.h:751
DenseRow
Definition: tgb_internal.h:500
p_GetShortExpVector
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4679
write_coef_times_xx_idx_to_buffer_dense
void write_coef_times_xx_idx_to_buffer_dense(CoefIdx< number_type > *const pairs, int &pos, number_type *const coef_array, const int rlen, const number coef)
Definition: tgb_internal.h:1207
clean_top_of_pair_list
void clean_top_of_pair_list(slimgb_alg *c)
Definition: tgb.cc:3883
NoroCache::temp_term
poly temp_term
Definition: tgb_internal.h:593
write_minus_coef_idx_to_buffer
void write_minus_coef_idx_to_buffer(CoefIdx< number_type > *const pairs, int &pos, int *const idx_array, number_type *const coef_array, const int rlen)
Definition: tgb_internal.h:1272
add_dense
void add_dense(number_type *const temp_array, int, const number_type *row, int len)
Definition: tgb_internal.h:1001
DataNoroCacheNode::DataNoroCacheNode
DataNoroCacheNode(poly p, int len)
Definition: tgb_internal.h:558
simple_reducer::p_len
int p_len
Definition: tgb_internal.h:365
pNext
#define pNext(p)
Definition: monomials.h:37
ModPMatrixProxyOnArray::findPivot
BOOLEAN findPivot(int &r, int &c)
Definition: tgb_internal.h:1633
ModPMatrixProxyOnArray::getStartIndex
int getStartIndex(int row)
Definition: tgb_internal.h:1629
ModPMatrixBackSubstProxyOnArray::ncols
int ncols
Definition: tgb_internal.h:1664
modulop.h
omalloc0
#define omalloc0(size)
Definition: omAllocDecl.h:229
find_erg::to_reduce_u
int to_reduce_u
Definition: tgb_internal.h:390
DenseRow::~DenseRow
~DenseRow()
Definition: tgb_internal.h:509
npInit
#define npInit
Definition: tgb_internal.h:72
slimgb_alg::last_index
int last_index
Definition: tgb_internal.h:268
simple_reducer::pre_reduce
virtual void pre_reduce(red_object *r, int l, int u)
Definition: tgb.cc:5008
PolySimple::PolySimple
PolySimple(poly p)
Definition: tgb_internal.h:88
red_object::sev
unsigned long sev
Definition: tgb_internal.h:314
NoroCacheNode::branches
NoroCacheNode ** branches
Definition: tgb_internal.h:435
omfree
#define omfree(addr)
Definition: omAllocDecl.h:237
slimgb_alg::max_pairs
int max_pairs
Definition: tgb_internal.h:269
slimgb_alg::to_destroy
poly_list_node * to_destroy
Definition: tgb_internal.h:251