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