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