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