My Project  UNKNOWN_GIT_VERSION
Data Structures | Macros | Functions
kbuckets.h File Reference
#include "polys/monomials/ring.h"
#include "polys/templates/p_Procs.h"

Go to the source code of this file.

Data Structures

class  kBucket
 

Macros

#define MAX_BUCKET   14
 Bucket definition (should be no one elses business, though) More...
 

Functions

kBucket_pt kBucketCreate (const ring r)
 Creation/Destruction of buckets. More...
 
void kBucketDestroy (kBucket_pt *bucket)
 
void kBucketDeleteAndDestroy (kBucket_pt *bucket)
 
void kBucketInit (kBucket_pt bucket, poly p, int length)
 
void kBucketClear (kBucket_pt bucket, poly *p, int *length)
 
poly kBucketClear (kBucket_pt bucket)
 
int kBucketCanonicalize (kBucket_pt bucket)
 Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bucket into which it is canonicalized. More...
 
void kBucketNormalize (kBucket_pt bucket)
 apply n_Normalize to all coefficients More...
 
poly kBucketExtractLm (kBucket_pt bucket)
 
void kBucketSetLm (kBucket_pt bucket, poly lm)
 
void kBucketAdjust (kBucket_pt bucket, int i)
 Bucket number i from bucket is out of length sync, resync. More...
 
number kBucketPolyRed (kBucket_pt bucket, poly p, int l, poly spNoether)
 
void kBucketTakeOutComp (kBucket_pt bucket, long comp, poly *p, int *l)
 
void kBucket_Mult_n (kBucket_pt bucket, number n)
 Multiply Bucket by number ,i.e. Bpoly == n*Bpoly. More...
 
poly kBucket_ExtractLarger (kBucket_pt bucket, poly q, poly append)
 Extract all monomials of bucket which are larger than q Append those to append, and return last monomial of append. More...
 
void kBucket_Add_q (kBucket_pt bucket, poly q, int *lq)
 Add to Bucket a poly ,i.e. Bpoly == Bpoly + q. More...
 
poly kBucket_ExtractLarger_Add_q (kBucket_pt bucket, poly append, poly q, int *lq)
 
void kBucket_Minus_m_Mult_p (kBucket_pt bucket, poly m, poly p, int *l, poly spNother=NULL)
 Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m (TODO: rename into kBucket_Minus_mm_Mult_pp!?) assume (*l <= 0 || pLength(p) == *l) More...
 
void kBucket_Plus_mm_Mult_pp (kBucket_pt bucket, poly m, poly p, int l)
 Bpoly == Bpoly + m*p; where m is a monom Does not destroy p and m assume (l <= 0 || pLength(p) == l) More...
 
void kBucketShallowCopyDelete (kBucket_pt bucket, ring new_tailRing, omBin new_tailBin, pShallowCopyDeleteProc p_shallow_copy_delete)
 For changing the ring of the Bpoly to new_tailBin. More...
 
BOOLEAN kbTest (kBucket_pt bucket)
 Tests. More...
 
poly kBucketGetLm (kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
 
poly kBucketGetLm (kBucket_pt bucket)
 
poly kBucketExtractLmOfBucket (kBucket_pt bucket, int i)
 
void kBucketSimpleContent (kBucket_pt bucket)
 
BOOLEAN kBucketIsCleared (kBucket_pt bucket)
 
int ksCheckCoeff (number *a, number *b, const coeffs r)
 

Data Structure Documentation

◆ kBucket

class kBucket

Definition at line 178 of file kbuckets.h.

Data Fields
ring bucket_ring
int l
poly p

Macro Definition Documentation

◆ MAX_BUCKET

#define MAX_BUCKET   14

Bucket definition (should be no one elses business, though)

Definition at line 175 of file kbuckets.h.

Function Documentation

◆ kbTest()

BOOLEAN kbTest ( kBucket_pt  bucket)

Tests.

Definition at line 194 of file kbuckets.cc.

195 {
196  return TRUE;
197 }

◆ kBucket_Add_q()

void kBucket_Add_q ( kBucket_pt  bucket,
poly  q,
int *  l 
)

Add to Bucket a poly ,i.e. Bpoly == Bpoly + q.

Add to Bucket a poly ,i.e. Bpoly == Bpoly + q.

Definition at line 651 of file kbuckets.cc.

652 {
653  if (q == NULL) return;
654  assume(*l <= 0 || pLength(q) == *l);
655 
656  int i, l1;
657  ring r = bucket->bucket_ring;
658 
659  if (*l <= 0)
660  {
661  l1 = pLength(q);
662  *l = l1;
663  }
664  else
665  l1 = *l;
666 
667  kBucketMergeLm(bucket);
668  kbTest(bucket);
669  i = pLogLength(l1);
670 
671  while (bucket->buckets[i] != NULL)
672  {
673  //MULTIPLY_BUCKET(bucket,i);
674  #ifdef USE_COEF_BUCKETS
675  if (bucket->coef[i]!=NULL)
676  {
677  q = p_Plus_mm_Mult_qq(q, bucket->coef[i], bucket->buckets[i],
678  l1, bucket->buckets_length[i], r);
679  p_Delete(&bucket->coef[i],r);
680  p_Delete(&bucket->buckets[i],r);
681  }
682  else
683  q = p_Add_q(q, bucket->buckets[i],
684  l1, bucket->buckets_length[i], r);
685  #else
686  q = p_Add_q(q, bucket->buckets[i],
687  l1, bucket->buckets_length[i], r);
688  #endif
689  bucket->buckets[i] = NULL;
690  bucket->buckets_length[i] = 0;
691  i = pLogLength(l1);
692  assume(i<= MAX_BUCKET);
693  assume(bucket->buckets_used<= MAX_BUCKET);
694  }
695 
696  kbTest(bucket);
697  bucket->buckets[i] = q;
698  bucket->buckets_length[i]=l1;
699  if (i >= bucket->buckets_used)
700  bucket->buckets_used = i;
701  else
702  kBucketAdjustBucketsUsed(bucket);
703  kbTest(bucket);
704 }

◆ kBucket_ExtractLarger()

poly kBucket_ExtractLarger ( kBucket_pt  bucket,
poly  q,
poly  append 
)

Extract all monomials of bucket which are larger than q Append those to append, and return last monomial of append.

Definition at line 1001 of file kbuckets.cc.

1002 {
1003  if (q == NULL) return append;
1004  poly lm;
1005  loop
1006  {
1007  lm = kBucketGetLm(bucket);
1008  if (lm == NULL) return append;
1009  if (p_LmCmp(lm, q, bucket->bucket_ring) == 1)
1010  {
1011  lm = kBucketExtractLm(bucket);
1012  pNext(append) = lm;
1013  pIter(append);
1014  }
1015  else
1016  {
1017  return append;
1018  }
1019  }
1020 }

◆ kBucket_ExtractLarger_Add_q()

poly kBucket_ExtractLarger_Add_q ( kBucket_pt  bucket,
poly  append,
poly  q,
int *  lq 
)
inline

Definition at line 122 of file kbuckets.h.

123 {
124  append = kBucket_ExtractLarger(bucket, q, append);
125  kBucket_Add_q(bucket, q, lq);
126  return append;
127 }

◆ kBucket_Minus_m_Mult_p()

void kBucket_Minus_m_Mult_p ( kBucket_pt  bucket,
poly  m,
poly  p,
int *  l,
poly  spNoether 
)

Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m (TODO: rename into kBucket_Minus_mm_Mult_pp!?) assume (*l <= 0 || pLength(p) == *l)

Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m (TODO: rename into kBucket_Minus_mm_Mult_pp!?) assume (*l <= 0 || pLength(p) == *l)

Definition at line 713 of file kbuckets.cc.

715 {
716  assume(*l <= 0 || pLength(p) == *l);
717  int i, l1;
718  poly p1 = p;
719  ring r = bucket->bucket_ring;
720 
721  if (*l <= 0)
722  {
723  l1 = pLength(p1);
724  *l = l1;
725  }
726  else
727  l1 = *l;
728 
729  if (m == NULL || p == NULL) return;
730 
731 #ifndef HAVE_PSEUDO_BUCKETS
732  kBucketMergeLm(bucket);
733  kbTest(bucket);
734  i = pLogLength(l1);
735 
736 #if defined(HAVE_PLURAL)
737  if ((rField_is_Ring(r) && !(rField_is_Domain(r)))
738  ||(rIsPluralRing(r)))
739  {
740  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
741  p1=pp_Mult_mm(p,m,r);
742  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
743  l1=pLength(p1);
744  i = pLogLength(l1);
745  }
746  else
747 #endif
748  {
749  if ((i <= bucket->buckets_used) && (bucket->buckets[i] != NULL))
750  {
751  assume(pLength(bucket->buckets[i])==(unsigned)bucket->buckets_length[i]);
752 //#ifdef USE_COEF_BUCKETS
753 // if(bucket->coef[i]!=NULL)
754 // {
755 // poly mult=p_Mult_mm(bucket->coef[i],m,r);
756 // bucket->coef[i]=NULL;
757 // p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], mult, p1,
758 // bucket->buckets_length[i], l1,
759 // spNoether, r);
760 // }
761 // else
762 //#endif
763  MULTIPLY_BUCKET(bucket,i);
764  p1 = p_Minus_mm_Mult_qq(bucket->buckets[i], m, p1,
765  bucket->buckets_length[i], l1,
766  spNoether, r);
767  l1 = bucket->buckets_length[i];
768  bucket->buckets[i] = NULL;
769  bucket->buckets_length[i] = 0;
770  i = pLogLength(l1);
771  }
772  else
773  {
774  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
775  if (spNoether != NULL)
776  {
777  l1 = -1;
778  p1 = r->p_Procs->pp_Mult_mm_Noether(p1, m, spNoether, l1, r);
779  i = pLogLength(l1);
780  }
781  else
782  {
783  p1 = r->p_Procs->pp_Mult_mm(p1, m, r);
784  }
785  pSetCoeff0(m, n_InpNeg(pGetCoeff(m),r->cf));
786  }
787  }
788 
789  while (bucket->buckets[i] != NULL)
790  {
791  //kbTest(bucket);
792  MULTIPLY_BUCKET(bucket,i);
793  p1 = p_Add_q(p1, bucket->buckets[i],
794  l1, bucket->buckets_length[i], r);
795  bucket->buckets[i] = NULL;
796  bucket->buckets_length[i] = 0;
797  i = pLogLength(l1);
798  }
799 
800  bucket->buckets[i] = p1;
801  bucket->buckets_length[i]=l1;
802  if (i >= bucket->buckets_used)
803  bucket->buckets_used = i;
804  else
805  kBucketAdjustBucketsUsed(bucket);
806 #else // HAVE_PSEUDO_BUCKETS
807  bucket->p = p_Minus_mm_Mult_qq(bucket->p, m, p,
808  bucket->l, l1,
809  spNoether, r);
810 #endif
811 }

◆ kBucket_Mult_n()

void kBucket_Mult_n ( kBucket_pt  bucket,
number  n 
)

Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.

Definition at line 595 of file kbuckets.cc.

596 {
597 #ifndef HAVE_PSEUDO_BUCKETS
598  kbTest(bucket);
599  ring r=bucket->bucket_ring;
600  int i;
601 
602  for (i=0; i<= bucket->buckets_used; i++)
603  {
604  if (bucket->buckets[i] != NULL)
605  {
606 #ifdef USE_COEF_BUCKETS
607  if (i<coef_start)
608  bucket->buckets[i] = __p_Mult_nn(bucket->buckets[i], n, r);
609  /* Frank Seelisch on March 11, 2010:
610  This looks a bit strange: The following "if" is indented
611  like the previous line of code. But coded as it is,
612  it should actually be two spaces less indented.
613  Question: Should the following "if" also only be
614  performed when "(i<coef_start)" is true?
615  For the time being, I leave it as it is. */
616  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
617  {
618  bucket->buckets_length[i] = pLength(bucket->buckets[i]);
619  kBucketAdjust(bucket, i);
620  }
621  else
622  if (bucket->coef[i]!=NULL)
623  {
624  bucket->coef[i] = __p_Mult_nn(bucket->coef[i],n,r);
625  }
626  else
627  {
628  bucket->coef[i] = p_NSet(n_Copy(n,r),r);
629  }
630 #else
631  bucket->buckets[i] = __p_Mult_nn(bucket->buckets[i], n, r);
632  if (rField_is_Ring(r) && !(rField_is_Domain(r)))
633  {
634  bucket->buckets_length[i] = pLength(bucket->buckets[i]);
635  kBucketAdjust(bucket, i);
636  }
637 #endif
638  }
639  }
640  kbTest(bucket);
641 #else
642  bucket->p = __p_Mult_nn(bucket->p, n, bucket->bucket_ring);
643 #endif
644 }

◆ kBucket_Plus_mm_Mult_pp()

void kBucket_Plus_mm_Mult_pp ( kBucket_pt  bucket,
poly  m,
poly  p,
int  l 
)

Bpoly == Bpoly + m*p; where m is a monom Does not destroy p and m assume (l <= 0 || pLength(p) == l)

Definition at line 818 of file kbuckets.cc.

819 {
820  assume((!rIsPluralRing(bucket->bucket_ring))||p_IsConstant(m, bucket->bucket_ring));
821  assume(l <= 0 || pLength(p) == (unsigned)l);
822  int i, l1;
823  poly p1 = p;
824  ring r = bucket->bucket_ring;
825 
826  if (m == NULL || p == NULL) return;
827 
828  if (l <= 0)
829  {
830  l1 = pLength(p1);
831  l = l1;
832  }
833  else
834  l1 = l;
835 
836  kBucketMergeLm(bucket);
837  kbTest(bucket);
838  i = pLogLength(l1);
839  #ifdef USE_COEF_BUCKETS
840  number n=n_Init(1,r->cf);
841  #endif
842  if (i <= bucket->buckets_used && bucket->buckets[i] != NULL)
843  {
844  //if (FALSE){
845  #ifdef USE_COEF_BUCKETS
846  if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
847  {
848  number orig_coef=p_GetCoeff(bucket->coef[i],r);
849  //we take ownership:
850  p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
851  number add_coef=n_Copy(p_GetCoeff(m,r),r);
852  number gcd=n_Gcd(add_coef, orig_coef,r);
853 
854  if (!(n_IsOne(gcd,r)))
855  {
856  number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
857  number add_coef2=n_ExactDiv(add_coef, gcd,r);
858  n_Delete(&orig_coef,r);
859  n_Delete(&add_coef,r);
860  orig_coef=orig_coef2;
861  add_coef=add_coef2;
862 
863  //p_Mult_nn(bucket->buckets[i], orig_coef,r);
864  n_Delete(&n,r);
865  n=gcd;
866  }
867 
868  //assume(n_IsOne(n,r));
869  number backup=p_GetCoeff(m,r);
870 
871  p_SetCoeff0(m,add_coef,r);
872  bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
873 
874  n_Delete(&orig_coef,r);
875  p_Delete(&bucket->coef[i],r);
876 
877  p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
878  bucket->buckets_length[i], l1, r);
879  l1=bucket->buckets_length[i];
880  bucket->buckets[i]=NULL;
881  bucket->buckets_length[i] = 0;
882  i = pLogLength(l1);
883  assume(l1==pLength(p1));
884 
885  p_SetCoeff(m,backup,r); //deletes add_coef
886  }
887  else
888  #endif
889  {
890  MULTIPLY_BUCKET(bucket,i);
891  p1 = p_Plus_mm_Mult_qq(bucket->buckets[i], m, p1,
892  bucket->buckets_length[i], l1, r);
893  l1 = bucket->buckets_length[i];
894  bucket->buckets[i] = NULL;
895  bucket->buckets_length[i] = 0;
896  i = pLogLength(l1);
897  }
898  }
899  else
900  {
901  #ifdef USE_COEF_BUCKETS
902  number swap_n=p_GetCoeff(m,r);
903 
904  assume(n_IsOne(n,r));
905  p_SetCoeff0(m,n,r);
906  n=swap_n;
907  //p_SetCoeff0(n, swap_n, r);
908  //p_GetCoeff0(n, swap_n,r);
909  #endif
910  p1 = r->p_Procs->pp_Mult_mm(p1, m, r);
911  #ifdef USE_COEF_BUCKETS
912  //m may not be changed
913  p_SetCoeff(m,n_Copy(n,r),r);
914  #endif
915  }
916 
917  while ((bucket->buckets[i] != NULL) && (p1!=NULL))
918  {
919  assume(i!=0);
920  #ifdef USE_COEF_BUCKETS
921  if ((bucket->coef[i]!=NULL) &&(i>=coef_start))
922  {
923  number orig_coef=p_GetCoeff(bucket->coef[i],r);
924  //we take ownership:
925  p_SetCoeff0(bucket->coef[i],n_Init(0,r),r);
926  number add_coef=n_Copy(n,r);
927  number gcd=n_Gcd(add_coef, orig_coef,r);
928 
929  if (!(n_IsOne(gcd,r)))
930  {
931  number orig_coef2=n_ExactDiv(orig_coef,gcd,r);
932  number add_coef2=n_ExactDiv(add_coef, gcd,r);
933  n_Delete(&orig_coef,r);
934  n_Delete(&n,r);
935  n_Delete(&add_coef,r);
936  orig_coef=orig_coef2;
937  add_coef=add_coef2;
938  //p_Mult_nn(bucket->buckets[i], orig_coef,r);
939  n=gcd;
940  }
941  //assume(n_IsOne(n,r));
942  bucket->buckets[i]=__p_Mult_nn(bucket->buckets[i],orig_coef,r);
943  p1=__p_Mult_nn(p1,add_coef,r);
944 
945  p1 = p_Add_q(p1, bucket->buckets[i],r);
946  l1=pLength(p1);
947 
948  bucket->buckets[i]=NULL;
949  n_Delete(&orig_coef,r);
950  p_Delete(&bucket->coef[i],r);
951  //l1=bucket->buckets_length[i];
952  assume(l1==pLength(p1));
953  }
954  else
955  #endif
956  {
957  //don't do that, pull out gcd
958  #ifdef USE_COEF_BUCKETS
959  if(!(n_IsOne(n,r)))
960  {
961  p1=__p_Mult_nn(p1, n, r);
962  n_Delete(&n,r);
963  n=n_Init(1,r);
964  }
965  #endif
966  MULTIPLY_BUCKET(bucket,i);
967  p1 = p_Add_q(p1, bucket->buckets[i],
968  l1, bucket->buckets_length[i], r);
969  bucket->buckets[i] = NULL;
970  bucket->buckets_length[i] = 0;
971  }
972  i = pLogLength(l1);
973  }
974 
975  bucket->buckets[i] = p1;
976 #ifdef USE_COEF_BUCKETS
977  assume(bucket->coef[i]==NULL);
978 
979  if (!(n_IsOne(n,r)))
980  {
981  bucket->coef[i]=p_NSet(n,r);
982  }
983  else
984  {
985  bucket->coef[i]=NULL;
986  n_Delete(&n,r);
987  }
988 
989  if (p1==NULL)
990  p_Delete(&bucket->coef[i],r);
991 #endif
992  bucket->buckets_length[i]=l1;
993  if (i > bucket->buckets_used)
994  bucket->buckets_used = i;
995  else
996  kBucketAdjustBucketsUsed(bucket);
997 
998  kbTest(bucket);
999 }

◆ kBucketAdjust()

void kBucketAdjust ( kBucket_pt  bucket,
int  i 
)

Bucket number i from bucket is out of length sync, resync.

Definition at line 562 of file kbuckets.cc.

562  {
563 
564  MULTIPLY_BUCKET(bucket,i);
565 
566  int l1 = bucket->buckets_length[i];
567  poly p1 = bucket->buckets[i];
568  bucket->buckets[i] = NULL;
569  bucket->buckets_length[i] = 0;
570  i = pLogLength(l1);
571 
572  while (bucket->buckets[i] != NULL)
573  {
574  //kbTest(bucket);
575  MULTIPLY_BUCKET(bucket,i);
576  p1 = p_Add_q(p1, bucket->buckets[i],
577  l1, bucket->buckets_length[i], bucket->bucket_ring);
578  bucket->buckets[i] = NULL;
579  bucket->buckets_length[i] = 0;
580  i = pLogLength(l1);
581  }
582 
583  bucket->buckets[i] = p1;
584  bucket->buckets_length[i]=l1;
585  if (i >= bucket->buckets_used)
586  bucket->buckets_used = i;
587  else
588  kBucketAdjustBucketsUsed(bucket);
589 }

◆ kBucketCanonicalize()

int kBucketCanonicalize ( kBucket_pt  bucket)

Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bucket into which it is canonicalized.

◆ kBucketClear() [1/2]

poly kBucketClear ( kBucket_pt  bucket)
inline

Definition at line 42 of file kbuckets.h.

43 {
44  int dummy;
45  poly p;
46  kBucketClear(bucket, &p, &dummy);
47  return p;
48 }

◆ kBucketClear() [2/2]

void kBucketClear ( kBucket_pt  bucket,
poly *  p,
int *  length 
)

Definition at line 518 of file kbuckets.cc.

519 {
520  assume(pLength(bucket->p) == bucket->l);
521  *p = bucket->p;
522  *length = bucket->l;
523  bucket->p = NULL;
524  bucket->l = 0;
525 }

◆ kBucketCreate()

kBucket_pt kBucketCreate ( const ring  r)

Creation/Destruction of buckets.

Definition at line 206 of file kbuckets.cc.

207 {
208  assume(bucket_ring != NULL);
210  bucket->bucket_ring = bucket_ring;
211  return bucket;
212 }

◆ kBucketDeleteAndDestroy()

void kBucketDeleteAndDestroy ( kBucket_pt bucket)

Definition at line 220 of file kbuckets.cc.

221 {
222  kBucket_pt bucket = *bucket_pt;
223  kbTest(bucket);
224  int i;
225  for (i=0; i<= bucket->buckets_used; i++)
226  {
227  p_Delete(&(bucket->buckets[i]), bucket->bucket_ring);
228 #ifdef USE_COEF_BUCKETS
229  p_Delete(&(bucket->coef[i]), bucket->bucket_ring);
230 #endif
231  }
232  omFreeBin(bucket, kBucket_bin);
233  *bucket_pt = NULL;
234 }

◆ kBucketDestroy()

void kBucketDestroy ( kBucket_pt bucket)

Definition at line 213 of file kbuckets.cc.

214 {
215  omFreeBin(*bucket_pt, kBucket_bin);
216  *bucket_pt = NULL;
217 }

◆ kBucketExtractLm()

poly kBucketExtractLm ( kBucket_pt  bucket)
inline

Definition at line 231 of file kbuckets.h.

232 {
233  poly lm = kBucketGetLm(bucket);
234  #ifdef HAVE_COEF_BUCKETS
235  assume(bucket->coef[0]==NULL);
236  #endif
237  bucket->buckets[0] = NULL;
238  bucket->buckets_length[0] = 0;
239 
240  return lm;
241 }

◆ kBucketExtractLmOfBucket()

poly kBucketExtractLmOfBucket ( kBucket_pt  bucket,
int  i 
)

Definition at line 1349 of file kbuckets.cc.

1350 {
1351  assume(bucket->buckets[i]!=NULL);
1352 
1353  poly p=bucket->buckets[i];
1354  bucket->buckets_length[i]--;
1355 #ifdef USE_COEF_BUCKETS
1356  ring r=bucket->bucket_ring;
1357  if (bucket->coef[i]!=NULL)
1358  {
1359  poly next=pNext(p);
1360  if (next==NULL)
1361  {
1362  MULTIPLY_BUCKET(bucket,i);
1363  p=bucket->buckets[i];
1364  bucket->buckets[i]=NULL;
1365  return p;
1366  }
1367  else
1368  {
1369  bucket->buckets[i]=next;
1370  number c=p_GetCoeff(bucket->coef[i],r);
1371  pNext(p)=NULL;
1372  p=__p_Mult_nn(p,c,r);
1373  assume(p!=NULL);
1374  return p;
1375  }
1376  }
1377  else
1378 #endif
1379  {
1380  bucket->buckets[i]=pNext(bucket->buckets[i]);
1381  pNext(p)=NULL;
1382  assume(p!=NULL);
1383  return p;
1384  }
1385 }

◆ kBucketGetLm() [1/2]

poly kBucketGetLm ( kBucket_pt  bucket)
inline

Definition at line 226 of file kbuckets.h.

227 {
228  return kBucketGetLm(bucket, bucket->bucket_ring->p_Procs->p_kBucketSetLm); // TODO: needs ring :(
229 }

◆ kBucketGetLm() [2/2]

poly kBucketGetLm ( kBucket_pt  bucket,
p_kBucketSetLm_Proc_Ptr  _p_kBucketSetLm 
)
inline

Definition at line 208 of file kbuckets.h.

209 {
210 #ifdef HAVE_COEF_BUCKETS
211  assume(bucket->coef[0]==NULL);
212 #endif
213 
214  poly& lead = bucket->buckets[0];
215 
216  if (lead == NULL)
217  _p_kBucketSetLm(bucket);
218 
219 #ifdef HAVE_COEF_BUCKETS
220  assume(bucket->coef[0]==NULL);
221 #endif
222 
223  return lead;
224 }

◆ kBucketInit()

void kBucketInit ( kBucket_pt  bucket,
poly  p,
int  length 
)

Definition at line 490 of file kbuckets.cc.

491 {
492  int i;
493 
494  assume(bucket != NULL);
495  assume(length <= 0 || length == pLength(lm));
496 
497  bucket->p = lm;
498  if (length <= 0) bucket->l = pLength(lm);
499  else bucket->l = length;
500 
501 }

◆ kBucketIsCleared()

BOOLEAN kBucketIsCleared ( kBucket_pt  bucket)

◆ kBucketNormalize()

void kBucketNormalize ( kBucket_pt  bucket)

apply n_Normalize to all coefficients

◆ kBucketPolyRed()

number kBucketPolyRed ( kBucket_pt  bucket,
poly  p,
int  l,
poly  spNoether 
)

Definition at line 1076 of file kbuckets.cc.

1079 {
1080  ring r=bucket->bucket_ring;
1081  assume((!rIsPluralRing(r))||p_LmEqual(p1,kBucketGetLm(bucket), r));
1082  assume(p1 != NULL &&
1083  p_DivisibleBy(p1, kBucketGetLm(bucket), r));
1084  assume(pLength(p1) == (unsigned) l1);
1085 
1086  poly a1 = pNext(p1), lm = kBucketExtractLm(bucket);
1087  BOOLEAN reset_vec=FALSE;
1088  number rn;
1089 
1090  /* we shall reduce bucket=bn*lm+... by p1=an*t+a1 where t=lm(p1)
1091  and an,bn shall be defined further down only if lc(p1)!=1
1092  we already know: an|bn and t|lm */
1093  if(a1==NULL)
1094  {
1095  p_LmDelete(&lm, r);
1096  return n_Init(1,r->cf);
1097  }
1098 
1099  if (! n_IsOne(pGetCoeff(p1),r->cf))
1100  {
1101  number an = pGetCoeff(p1), bn = pGetCoeff(lm);
1102 //StringSetS("##### an = "); nWrite(an); PrintS(StringEndS("\n")); // NOTE/TODO: use StringAppendS("\n"); omFree(s);
1103 //StringSetS("##### bn = "); nWrite(bn); PrintS(StringEndS("\n")); // NOTE/TODO: use StringAppendS("\n"); omFree(s);
1104  /* ksCheckCoeff: divide out gcd from an and bn: */
1105  int ct = ksCheckCoeff(&an, &bn,r->cf);
1106  /* the previous command returns ct=0 or ct=2 iff an!=1
1107  note: an is now 1 or -1 */
1108 
1109  /* setup factor for p1 which cancels leading terms */
1110  p_SetCoeff(lm, bn, r);
1111  if ((ct == 0) || (ct == 2))
1112  {
1113  /* next line used to be here before but is WRONG:
1114  kBucket_Mult_n(bucket, an);
1115  its use would result in a wrong sign for the tail of bucket
1116  in the reduction */
1117 
1118  /* correct factor for cancelation by changing sign if an=-1 */
1119  if (rField_is_Ring(r))
1120  lm = __p_Mult_nn(lm, an, r);
1121  else
1122  kBucket_Mult_n(bucket, an);
1123  }
1124  rn = an;
1125  }
1126  else
1127  {
1128  rn = n_Init(1,r->cf);
1129  }
1130 
1131  if (p_GetComp(p1, r) != p_GetComp(lm, r))
1132  {
1133  p_SetCompP(a1, p_GetComp(lm, r), r);
1134  reset_vec = TRUE;
1135  p_SetComp(lm, p_GetComp(p1, r), r);
1136  p_Setm(lm, r);
1137  }
1138 
1139  p_ExpVectorSub(lm, p1, r);
1140  l1--;
1141 
1142  assume((unsigned)l1==pLength(a1));
1143 #if 0
1144  BOOLEAN backuped=FALSE;
1145  number coef;
1146  //@Viktor, don't ignore coefficients on monomials
1147  if(l1==1) {
1148 
1149  //if (rField_is_Q(r)) {
1150  //avoid this for function fields, as gcds are expensive at the moment
1151 
1152 
1153  coef=p_GetCoeff(a1,r);
1154  lm=p_Mult_nn(lm, coef, r);
1155  p_SetCoeff0(a1, n_Init(1,r), r);
1156  backuped=TRUE;
1157  //WARNING: not thread_safe
1158  //deletes coef as side effect
1159  //}
1160  }
1161 #endif
1162 
1163  kBucket_Minus_m_Mult_p(bucket, lm, a1, &l1, spNoether);
1164 
1165 #if 0
1166  if (backuped)
1167  p_SetCoeff0(a1,coef,r);
1168 #endif
1169 
1170  p_LmDelete(&lm, r);
1171  if (reset_vec) p_SetCompP(a1, 0, r);
1172  kbTest(bucket);
1173  return rn;
1174 }

◆ kBucketSetLm()

void kBucketSetLm ( kBucket_pt  bucket,
poly  lm 
)

◆ kBucketShallowCopyDelete()

void kBucketShallowCopyDelete ( kBucket_pt  bucket,
ring  new_tailRing,
omBin  new_tailBin,
pShallowCopyDeleteProc  p_shallow_copy_delete 
)

For changing the ring of the Bpoly to new_tailBin.

Definition at line 532 of file kbuckets.cc.

535 {
536 #ifndef HAVE_PSEUDO_BUCKETS
537  int i;
538 
539  kBucketCanonicalize(bucket);
540  for (i=0; i<= bucket->buckets_used; i++)
541  if (bucket->buckets[i] != NULL)
542  {
543  MULTIPLY_BUCKET(bucket,i);
544  bucket->buckets[i] = p_shallow_copy_delete(bucket->buckets[i],
545  bucket->bucket_ring,
546  new_tailRing,
547  new_tailBin);
548  }
549 #else
550  bucket->p = p_shallow_copy_delete(p,
551  bucket_ring,
552  new_tailRing,
553  new_tailBin);
554 #endif
555  bucket->bucket_ring = new_tailRing;
556 }

◆ kBucketSimpleContent()

void kBucketSimpleContent ( kBucket_pt  bucket)

Definition at line 1177 of file kbuckets.cc.

1178 {
1179  if (bucket->buckets[0]==NULL) return;
1180 
1181  ring r=bucket->bucket_ring;
1182  if (rField_is_Ring(r)) return;
1183 
1184  coeffs cf=r->cf;
1185  if (cf->cfSubringGcd==ndGcd) /* trivial gcd*/ return;
1186 
1187  number nn=pGetCoeff(bucket->buckets[0]);
1188  //if ((bucket->buckets_used==0)
1189  //&&(!n_IsOne(nn,cf)))
1190  //{
1191  // if (TEST_OPT_PROT) PrintS("@");
1192  // p_SetCoeff(bucket->buckets[0],n_Init(1,cf),r);
1193  // return;
1194  //}
1195 
1196  if (n_Size(nn,cf)<2) return;
1197 
1198  //kBucketAdjustBucketsUsed(bucket);
1199  number coef=n_Copy(nn,cf);
1200  // find an initial guess of a gcd
1201  for (int i=1; i<=bucket->buckets_used;i++)
1202  {
1203  if (bucket->buckets[i]!=NULL)
1204  {
1205  number t=p_InitContent(bucket->buckets[i],r);
1206  if (n_Size(t,cf)<2)
1207  {
1208  n_Delete(&t,cf);
1209  n_Delete(&coef,cf);
1210  return;
1211  }
1212  number t2=n_SubringGcd(coef,t,cf);
1213  n_Delete(&t,cf);
1214  n_Delete(&coef,cf);
1215  coef=t2;
1216  if (n_Size(coef,cf)<2) { n_Delete(&coef,cf);return;}
1217  }
1218  }
1219  // find the gcd
1220  for (int i=0; i<=bucket->buckets_used;i++)
1221  {
1222  if (bucket->buckets[i]!=NULL)
1223  {
1224  poly p=bucket->buckets[i];
1225  while(p!=NULL)
1226  {
1227  number t=n_SubringGcd(coef,pGetCoeff(p),cf);
1228  if (n_Size(t,cf)<2)
1229  {
1230  n_Delete(&t,cf);
1231  n_Delete(&coef,cf);
1232  return;
1233  }
1234  pIter(p);
1235  }
1236  }
1237  }
1238  // divided by the gcd
1239  if (TEST_OPT_PROT) PrintS("@");
1240  for (int i=bucket->buckets_used;i>=0;i--)
1241  {
1242  if (bucket->buckets[i]!=NULL)
1243  {
1244  poly p=bucket->buckets[i];
1245  while(p!=NULL)
1246  {
1247  number d = n_ExactDiv(pGetCoeff(p),coef,cf);
1248  p_SetCoeff(p,d,r);
1249  pIter(p);
1250  }
1251  }
1252  }
1253  n_Delete(&coef,cf);
1254 }

◆ kBucketTakeOutComp()

void kBucketTakeOutComp ( kBucket_pt  bucket,
long  comp,
poly *  p,
int *  l 
)

Definition at line 1035 of file kbuckets.cc.

1038 {
1039  poly p = NULL, q;
1040  int i, lp = 0, lq;
1041 
1042 #ifndef HAVE_PSEUDO_BUCKETS
1043  kBucketMergeLm(bucket);
1044  for (i=1; i<=bucket->buckets_used; i++)
1045  {
1046  if (bucket->buckets[i] != NULL)
1047  {
1048  MULTIPLY_BUCKET(bucket,i);
1049  p_TakeOutComp(&(bucket->buckets[i]), comp, &q, &lq, bucket->bucket_ring);
1050  if (q != NULL)
1051  {
1052  assume(pLength(q) == (unsigned)lq);
1053  bucket->buckets_length[i] -= lq;
1054  assume(pLength(bucket->buckets[i]) == (unsigned)bucket->buckets_length[i]);
1055  p = p_Add_q(p, q, lp, lq, bucket->bucket_ring);
1056  }
1057  }
1058  }
1059  kBucketAdjustBucketsUsed(bucket);
1060 #else
1061  p_TakeOutComp(&(bucket->p), comp, &p, &lp,bucket->bucket_ring);
1062  (bucket->l) -= lp;
1063 #endif
1064  *r_p = p;
1065  *l = lp;
1066 
1067  kbTest(bucket);
1068 }

◆ ksCheckCoeff()

int ksCheckCoeff ( number *  a,
number *  b,
const coeffs  r 
)

Definition at line 1398 of file kbuckets.cc.

1399 {
1400  int c = 0;
1401  number an = *a, bn = *b;
1402  n_Test(an,r);
1403  n_Test(bn,r);
1404 
1405  number cn = n_SubringGcd(an, bn, r);
1406 
1407  if(n_IsOne(cn, r))
1408  {
1409  an = n_Copy(an, r);
1410  bn = n_Copy(bn, r);
1411  }
1412  else
1413  {
1414  an = n_ExactDiv(an, cn, r); n_Normalize(an,r);
1415  bn = n_ExactDiv(bn, cn, r); n_Normalize(bn,r);
1416  }
1417  n_Delete(&cn, r);
1418  if (n_IsOne(an, r))
1419  {
1420  c = 1;
1421  }
1422  if (n_IsOne(bn, r))
1423  {
1424  c += 2;
1425  }
1426  *a = an;
1427  *b = bn;
1428  return c;
1429 }
ksCheckCoeff
int ksCheckCoeff(number *a, number *b)
FALSE
#define FALSE
Definition: auxiliary.h:94
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
kBucket_ExtractLarger
poly kBucket_ExtractLarger(kBucket_pt bucket, poly q, poly append)
Extract all monomials of bucket which are larger than q Append those to append, and return last monom...
Definition: kbuckets.cc:1001
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:51
p_GetComp
#define p_GetComp(p, r)
Definition: monomials.h:65
p_SetCoeff0
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:61
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:102
n_ExactDiv
static FORCE_INLINE number n_ExactDiv(number a, number b, const coeffs r)
assume that there is a canonical subring in cf and we know that division is possible for these a and ...
Definition: coeffs.h:622
rField_is_Domain
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:478
lq
Definition: lq.h:39
kBucket_pt
kBucket * kBucket_pt
Definition: ring.h:25
p_SetCompP
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:255
MAX_BUCKET
#define MAX_BUCKET
Bucket definition (should be no one elses business, though)
Definition: kbuckets.h:175
p_Plus_mm_Mult_qq
static poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq, const ring r)
Definition: p_polys.h:1120
cf
CanonicalForm cf
Definition: cfModGcd.cc:4024
p_Minus_mm_Mult_qq
static poly p_Minus_mm_Mult_qq(poly p, const poly m, const poly q, int &lp, int lq, const poly spNoether, const ring r)
Definition: p_polys.h:1007
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
p_InitContent
number p_InitContent(poly ph, const ring r)
Definition: p_polys.cc:2549
kBucket::l
int l
Definition: kbuckets.h:183
pLogLength
static unsigned int pLogLength(unsigned int l)
Definition: kbuckets.cc:68
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:988
omAlloc0Bin
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
kBucketGetLm
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:503
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:468
loop
#define loop
Definition: structs.h:78
b
CanonicalForm b
Definition: cfModGcd.cc:4044
__p_Mult_nn
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:928
n_Normalize
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:578
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:518
p_ExpVectorSub
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition: p_polys.h:1377
p_LmEqual
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1649
rIsPluralRing
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:398
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:193
next
ListNode * next
Definition: janet.h:31
kBucket_bin
static omBin kBucket_bin
Definition: kbuckets.cc:42
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:508
TRUE
#define TRUE
Definition: auxiliary.h:98
i
int i
Definition: cfEzgcd.cc:125
PrintS
void PrintS(const char *s)
Definition: reporter.cc:284
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
kbTest
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:194
kBucket_Minus_m_Mult_p
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition: kbuckets.cc:713
rField_is_Ring
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:475
kBucket_Mult_n
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:595
ndGcd
number ndGcd(number, number, const coeffs r)
Definition: numbers.cc:162
p_LmDelete
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:712
coeffs
pIter
#define pIter(p)
Definition: monomials.h:38
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:538
p_DivisibleBy
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1830
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1498
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
kBucketGetLm
poly kBucketGetLm(kBucket_pt bucket, p_kBucketSetLm_Proc_Ptr _p_kBucketSetLm)
Definition: kbuckets.h:208
n_InpNeg
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:557
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:858
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:893
kBucket_Add_q
void kBucket_Add_q(kBucket_pt bucket, poly q, int *lq)
Add to Bucket a poly ,i.e. Bpoly == Bpoly + q.
Definition: kbuckets.cc:651
kBucket::bucket_ring
ring bucket_ring
Definition: kbuckets.h:192
kBucket::p
poly p
Definition: kbuckets.h:182
p_NSet
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1435
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:413
pSetCoeff0
#define pSetCoeff0(p, n)
Definition: monomials.h:60
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:451
n_Gcd
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ,...
Definition: coeffs.h:686
m
int m
Definition: cfEzgcd.cc:121
assume
#define assume(x)
Definition: mod2.h:390
NULL
#define NULL
Definition: omList.c:10
p_TakeOutComp
void p_TakeOutComp(poly *p, long comp, poly *q, int *lq, const ring r)
Definition: p_polys.cc:3446
kBucketAdjust
void kBucketAdjust(kBucket_pt bucket, int i)
Bucket number i from bucket is out of length sync, resync.
Definition: kbuckets.cc:562
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:248
l
int l
Definition: cfEzgcd.cc:93
n_SubringGcd
static FORCE_INLINE number n_SubringGcd(number a, number b, const coeffs r)
Definition: coeffs.h:688
kBucket
Definition: kbuckets.h:178
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:234
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
MULTIPLY_BUCKET
#define MULTIPLY_BUCKET(B, I)
Definition: kbuckets.cc:40
p
int p
Definition: cfModGcd.cc:4019
p_IsConstant
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1929
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: facSparseHensel.h:25
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:45
n_Size
static FORCE_INLINE int n_Size(number n, const coeffs r)
return a non-negative measure for the complexity of n; return 0 only when n represents zero; (used fo...
Definition: coeffs.h:570
n_Test
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
pNext
#define pNext(p)
Definition: monomials.h:37
p_Mult_nn
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:915