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>
45using boost::dynamic_bitset;
46using std::vector;
47#endif
48#ifdef USE_STDVECBOOL
49#include <vector>
50using std::vector;
51#endif
52#include <stdlib.h>
53
54#include "misc/options.h"
55
56#include "coeffs/modulop.h"
57
60#include "polys/kbuckets.h"
61
62#include "kernel/ideals.h"
63#include "kernel/polys.h"
64
68
69#include "coeffs/modulop_inl.h" // npInit, npMult
70
72{
73public:
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};
109template<class number_type> class DataNoroCacheNode;
110/*class MonRedRes{
111public:
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};*/
132template <class number_type> class MonRedResNP
133{
134public:
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
149 int i;
150 int j;
151 int deg;
152
153
154};
155#ifdef NORO_CACHE
156#ifndef NORO_NON_POLY
157class NoroPlaceHolder
158{
159public:
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
216 ideal S;
217 ring r;
222 int* T_deg;
224 poly tmp_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;
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 };
318template <class len_type, class set_type> int pos_helper(kStrategy strat, poly p, len_type len, set_type setL, polyset set);
319void free_sorted_pair_node(sorted_pair_node* s, const ring r);
320ideal do_t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode,int deg_pos);
321void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c);
322
324int slim_nsize(number n, ring r);
327sorted_pair_node** add_to_basis_ideal_quotient(poly h, slimgb_alg* c, int* ip);//, BOOLEAN new_pairs=TRUE);
329int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj);
330int tgb_pair_better_gen2(const void* ap,const void* bp);
331int 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);
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//};
373{
374 poly expand;
378 int reduce_by;//index of reductor
379 BOOLEAN fromS;//else from los
380
381};
382
383template <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)
415typedef unsigned short tgb_uint16;
416typedef unsigned char tgb_uint8;
417typedef unsigned int tgb_uint32;
419{
420public:
423
424
426 {
428 branches_len=0;
429
430 }
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 }
468 {
469 int i;
470 for(i=0;i<branches_len;i++)
471 {
472 delete branches[i];
473 }
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};
487public:
488 number* array;
489 int begin;
490 int end;
492 {
493 array=NULL;
494 }
496 {
497 omfree(array);
498 }
499};
500template <class number_type> class SparseRow
501{
502public:
504 number_type* coef_array;
505 int len;
507 {
508 len=0;
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;
522 coef_array=(number_type*) omAlloc(n*sizeof(number_type));
523 memcpy(coef_array,source,n*sizeof(number_type));
524 }
526 {
529 }
530};
531
532template <class number_type> class DataNoroCacheNode:public NoroCacheNode
533{
534public:
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;
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};
569template <class number_type> class TermNoroDataNode
570{
571public:
573 poly t;
574};
575
576template <class number_type> class NoroCache
577{
578public:
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);
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 {
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 {
684 }
686#ifdef NORO_RED_ARRAY_RESERVER
687 omfree(recursionPolyBuffer);
688#endif
690 }
691
696protected:
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};
743template<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/*
805poly 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
823template<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));
828number_type* it_coef=res->coef_array;
829int* it_idx=res->idx_array;
830#if 0
831for(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
846int64* start=(int64*) ((void*)temp_array);
847int64* end;
848const int multiple=sizeof(int64)/sizeof(number_type);
849if (temp_size==0) end=start;
850
851else
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}
860int64* it=start;
861while(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
888return res;
889}
890#ifdef SING_NDEBUG
891template <class number_type> void add_coef_times_sparse(number_type* const temp_array,
892int /*temp_size*/,SparseRow<number_type>* row, number coef)
893#else
894template <class number_type> void add_coef_times_sparse(number_type* const temp_array,
895int 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
939template <class number_type> void add_coef_times_dense(number_type* const temp_array,
940int /*temp_size*/,const number_type* row, int len,number coef)
941#else
942template <class number_type> void add_coef_times_dense(number_type* const temp_array,
943int 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
987template <class number_type> void add_dense(number_type* const temp_array,
988int /*temp_size*/,const number_type* row, int len)
989#else
990template <class number_type> void add_dense(number_type* const temp_array,
991int 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
1013template <class number_type> void sub_dense(number_type* const temp_array,
1014int /*temp_size*/,const number_type* row, int len)
1015#else
1016template <class number_type> void sub_dense(number_type* const temp_array,
1017int 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
1039template <class number_type> void add_sparse(number_type* const temp_array,int /*temp_size*/,SparseRow<number_type>* row)
1040#else
1041template <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
1059template <class number_type> void sub_sparse(number_type* const temp_array,int /*temp_size*/,SparseRow<number_type>* row)
1060#else
1061template <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}
1169template<class number_type> class CoefIdx
1170{
1171public:
1172 number_type coef;
1173 int idx;
1174 bool operator<(const CoefIdx<number_type>& other) const
1175 {
1176 return (idx<other.idx);
1177 }
1178};
1179template<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}
1191template<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}
1208template<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
1226template<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}
1243template<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
1256template<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 {
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;}
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}
1396template<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
1445int 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
1452template <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}
1467template <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}
1486template <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}
1499template <class number_type> int term_nodes_sort_crit(const void* a, const void* b)
1500{
1502}
1503
1504template <class number_type>class ModPMatrixBackSubstProxyOnArray;
1505template <class number_type > class ModPMatrixProxyOnArray
1506{
1507public:
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}
1644void 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}
1657int getStartIndex(int row)
1658{
1659 return startIndices[row];
1660}
1661BOOLEAN 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}
1683protected:
1684 number_type** rows;
1686};
1687template <class number_type > class ModPMatrixBackSubstProxyOnArray
1688{
1690 number_type** rows;
1695public:
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)));
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 }
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};
1841template <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()
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);
1864template <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
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}
2028template<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 * getBranch(int branch)
Definition: tgb_internal.h:462
NoroCacheNode * getOrInsertBranch(int branch)
Definition: tgb_internal.h:476
NoroCacheNode * setNode(int branch, NoroCacheNode *node)
Definition: tgb_internal.h:431
virtual ~NoroCacheNode()
Definition: tgb_internal.h:467
int nIrreducibleMonomials
Definition: tgb_internal.h:692
DataNoroCacheNode< number_type > * treeInsert(poly term, poly nf, int len)
Definition: tgb_internal.h:697
DataNoroCacheNode< number_type > * treeInsert(poly term, SparseRow< number_type > *srow)
Definition: tgb_internal.h:710
poly temp_term
Definition: tgb_internal.h:579
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)
DataNoroCacheNode< number_type > * insertAndTransferOwnerShip(poly t, ring)
Definition: tgb_internal.h:633
std::vector< PolySimple > poly_vec
Definition: tgb_internal.h:736
number * buffer
Definition: tgb_internal.h:741
DataNoroCacheNode< number_type > * treeInsertBackLink(poly term)
Definition: tgb_internal.h:723
DataNoroCacheNode< number_type > * insert(poly term, SparseRow< number_type > *srow)
Definition: tgb_internal.h:622
DataNoroCacheNode< number_type > * insert(poly term, poly nf, int len)
Definition: tgb_internal.h:593
void collectIrreducibleMonomials(std::vector< DataNoroCacheNode< number_type > * > &res)
size_t tempBufferSize
Definition: tgb_internal.h:695
poly_vec ressources
Definition: tgb_internal.h:737
int nReducibleMonomials
Definition: tgb_internal.h:693
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
#define p_GetCoeff(p, r)
Definition: monomials.h:50
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
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:75
int_pair_node * next
Definition: tgb_internal.h:176
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
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)
MonRedResNP< number_type > noro_red_mon_to_non_poly(poly t, NoroCache< number_type > *cache, slimgb_alg *c)
Definition: tgb_internal.h:744
sorted_pair_node ** spn_merge(sorted_pair_node **p, int pn, sorted_pair_node **q, int qn, slimgb_alg *c)
Definition: tgb.cc:716
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)
SparseRow< number_type > * noro_red_to_non_poly_dense(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
SparseRow< number_type > * noro_red_to_non_poly_sparse(MonRedResNP< number_type > *mon, int len, NoroCache< number_type > *cache)
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
sorted_pair_node ** add_to_basis_ideal_quotient(poly h, slimgb_alg *c, int *ip)
Definition: tgb.cc:1389
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
sorted_pair_node * quick_pop_pair(slimgb_alg *c)
Definition: tgb.cc:3914
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 * top_pair(slimgb_alg *c)
Definition: tgb.cc:3890
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
SparseRow< number_type > * convert_to_sparse_row(number_type *temp_array, int temp_size, int non_zeros)
Definition: tgb_internal.h:823
void add_sparse(number_type *const temp_array, int, SparseRow< number_type > *row)
DataNoroCacheNode< number_type > * node
Definition: tgb_internal.h:572
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)
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