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