My Project
Loading...
Searching...
No Matches
Functions | Variables
hdegree.cc File Reference
#include "kernel/mod2.h"
#include "misc/intvec.h"
#include "coeffs/numbers.h"
#include "kernel/structs.h"
#include "kernel/ideals.h"
#include "kernel/polys.h"
#include "kernel/combinatorics/hutil.h"
#include "kernel/combinatorics/hilb.h"
#include "kernel/combinatorics/stairc.h"
#include "reporter/reporter.h"
#include <vector>
#include "misc/options.h"
#include "polys/shiftop.h"

Go to the source code of this file.

Functions

void hDimSolve (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
 
int scDimInt (ideal S, ideal Q)
 ideal dimension
 
int scDimIntRing (ideal vid, ideal Q)
 scDimInt for ring-coefficients
 
static void hIndSolve (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
 
intvecscIndIntvec (ideal S, ideal Q)
 
static BOOLEAN hNotZero (scfmon rad, int Nrad, varset var, int Nvar)
 
static void hIndep (scmon pure)
 
void hIndMult (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
 
static BOOLEAN hCheck1 (indset sm, scmon pure)
 
static indset hCheck2 (indset sm, scmon pure)
 
static void hCheckIndep (scmon pure)
 
void hIndAllMult (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
 
static long hZeroMult (scmon pure, scfmon stc, int Nstc, varset var, int Nvar)
 
static void hProject (scmon pure, varset sel)
 
static void hDimMult (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
 
static void hDegree (ideal S, ideal Q)
 
int scMultInt (ideal S, ideal Q)
 
void scPrintDegree (int co, int mu)
 
long scMult0Int (ideal S, ideal Q)
 
static void hHedge (poly hEdge)
 
static void hHedgeStep (scmon pure, scfmon stc, int Nstc, varset var, int Nvar, poly hEdge)
 
void scComputeHC (ideal S, ideal Q, int ak, poly &hEdge)
 
static void scElKbase ()
 
static int scMax (int i, scfmon stc, int Nvar)
 
static int scMin (int i, scfmon stc, int Nvar)
 
static int scRestrict (int &Nstc, scfmon stc, int Nvar)
 
static void scAll (int Nvar, int deg)
 
static void scAllKbase (int Nvar, int ideg, int deg)
 
static void scDegKbase (scfmon stc, int Nstc, int Nvar, int deg)
 
static void scInKbase (scfmon stc, int Nstc, int Nvar)
 
static ideal scIdKbase (poly q, const int rank)
 
ideal scKBase (int deg, ideal s, ideal Q, intvec *mv)
 
static std::vector< intcountCycles (const intvec *_G, int v, std::vector< int > path, std::vector< BOOLEAN > visited, std::vector< BOOLEAN > cyclic, std::vector< int > cache)
 
static int graphGrowth (const intvec *G)
 
static void _lp_computeNormalWords (ideal words, int &numberOfNormalWords, int length, ideal M, int minDeg, int &last)
 
static ideal lp_computeNormalWords (int length, ideal M)
 
static int lp_countNormalWords (int upToLength, ideal M)
 
intveclp_ufnarovskiGraph (ideal G, ideal &standardWords)
 
int lp_gkDim (const ideal _G)
 
static std::vector< std::vector< int > > iv2vv (intvec *M)
 
static void vvPrint (const std::vector< std::vector< int > > &mat)
 
static void vvTest (const std::vector< std::vector< int > > &mat)
 
static void vvDeleteRow (std::vector< std::vector< int > > &mat, int row)
 
static void vvDeleteColumn (std::vector< std::vector< int > > &mat, int col)
 
static BOOLEAN vvIsRowZero (const std::vector< std::vector< int > > &mat, int row)
 
static BOOLEAN vvIsColumnZero (const std::vector< std::vector< int > > &mat, int col)
 
static BOOLEAN vvIsZero (const std::vector< std::vector< int > > &mat)
 
static std::vector< std::vector< int > > vvMult (const std::vector< std::vector< int > > &a, const std::vector< std::vector< int > > &b)
 
static BOOLEAN isAcyclic (const intvec *G)
 
int lp_kDim (const ideal _G)
 

Variables

VAR int hCo
 
VAR int hMu2
 
VAR long hMu
 
VAR omBin indlist_bin = omGetSpecBin(sizeof(indlist))
 
STATIC_VAR scmon hInd
 
VAR indset ISet
 
VAR indset JSet
 
STATIC_VAR poly pWork
 
STATIC_VAR poly last
 
STATIC_VAR scmon act
 

Function Documentation

◆ _lp_computeNormalWords()

static void _lp_computeNormalWords ( ideal  words,
int numberOfNormalWords,
int  length,
ideal  M,
int  minDeg,
int last 
)
static

Definition at line 1676 of file hdegree.cc.

1677{
1678 if (length <= 0){
1679 poly one = pOne();
1680 if (p_LPDivisibleBy(M, one, currRing)) // 1 \in M => no normal words at all
1681 {
1682 pDelete(&one);
1683 last = -1;
1685 }
1686 else
1687 {
1688 words->m[0] = one;
1689 last = 0;
1691 }
1692 return;
1693 }
1694
1696
1697 int nVars = currRing->isLPring - currRing->LPncGenCount;
1698 int numberOfNewNormalWords = 0;
1699
1700 for (int j = nVars - 1; j >= 0; j--)
1701 {
1702 for (int i = last; i >= 0; i--)
1703 {
1704 int index = (j * (last + 1)) + i;
1705
1706 if (words->m[i] != NULL)
1707 {
1708 if (j > 0) {
1709 words->m[index] = pCopy(words->m[i]);
1710 }
1711
1712 int varOffset = ((length - 1) * currRing->isLPring) + 1;
1713 pSetExp(words->m[index], varOffset + j, 1);
1714 pSetm(words->m[index]);
1715 pTest(words->m[index]);
1716
1718 {
1719 pDelete(&words->m[index]);
1720 words->m[index] = NULL;
1721 }
1722 else
1723 {
1725 }
1726 }
1727 }
1728 }
1729
1730 last = nVars * last + nVars - 1;
1731
1733}
int i
Definition cfEzgcd.cc:132
int j
Definition facHensel.cc:110
STATIC_VAR poly last
Definition hdegree.cc:1148
static void _lp_computeNormalWords(ideal words, int &numberOfNormalWords, int length, ideal M, int minDeg, int &last)
Definition hdegree.cc:1676
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
#define NULL
Definition omList.c:12
static int index(p_Length length, p_Ord ord)
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
#define pTest(p)
Definition polys.h:414
#define pDelete(p_ptr)
Definition polys.h:186
#define pSetm(p)
Definition polys.h:271
#define pSetExp(p, i, v)
Definition polys.h:42
#define pCopy(p)
return a copy of the poly
Definition polys.h:185
#define pOne()
Definition polys.h:315
BOOLEAN p_LPDivisibleBy(poly a, poly b, const ring r)
Definition shiftop.cc:776
#define M
Definition sirandom.c:25

◆ countCycles()

static std::vector< int > countCycles ( const intvec _G,
int  v,
std::vector< int path,
std::vector< BOOLEAN visited,
std::vector< BOOLEAN cyclic,
std::vector< int cache 
)
static

Definition at line 1585 of file hdegree.cc.

1586{
1587 intvec* G = ivCopy(_G); // modifications must be local
1588
1589 if (cache[v] != -2) return cache; // value is already cached
1590
1591 visited[v] = TRUE;
1592 path.push_back(v);
1593
1594 int cycles = 0;
1595 for (int w = 0; w < G->cols(); w++)
1596 {
1597 if (IMATELEM(*G, v + 1, w + 1)) // edge v -> w exists in G
1598 {
1599 if (!visited[w])
1600 { // continue with w
1602 if (cache[w] == -1)
1603 {
1604 cache[v] = -1;
1605 return cache;
1606 }
1607 cycles = si_max(cycles, cache[w]);
1608 }
1609 else
1610 { // found new cycle
1611 int pathIndexOfW = -1;
1612 for (int i = path.size() - 1; i >= 0; i--) {
1613 if (cyclic[path[i]] == 1) { // found an already cyclic vertex
1614 cache[v] = -1;
1615 return cache;
1616 }
1617 cyclic[path[i]] = TRUE;
1618
1619 if (path[i] == w) { // end of the cycle
1620 assume(IMATELEM(*G, v + 1, w + 1) != 0);
1621 IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v -> w
1622 pathIndexOfW = i;
1623 break;
1624 } else {
1625 assume(IMATELEM(*G, path[i - 1] + 1, path[i] + 1) != 0);
1626 IMATELEM(*G, path[i - 1] + 1, path[i] + 1) = 0; // remove edge vi-1 -> vi
1627 }
1628 }
1629 assume(pathIndexOfW != -1); // should never happen
1630 for (int i = path.size() - 1; i >= pathIndexOfW; i--) {
1632 if (cache[path[i]] == -1)
1633 {
1634 cache[v] = -1;
1635 return cache;
1636 }
1637 cycles = si_max(cycles, cache[path[i]] + 1);
1638 }
1639 }
1640 }
1641 }
1642 cache[v] = cycles;
1643
1644 delete G;
1645 return cache;
1646}
static int si_max(const int a, const int b)
Definition auxiliary.h:124
#define TRUE
Definition auxiliary.h:100
const CanonicalForm & w
Definition facAbsFact.cc:51
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
static std::vector< int > countCycles(const intvec *_G, int v, std::vector< int > path, std::vector< BOOLEAN > visited, std::vector< BOOLEAN > cyclic, std::vector< int > cache)
Definition hdegree.cc:1585
intvec * ivCopy(const intvec *o)
Definition intvec.h:145
#define IMATELEM(M, I, J)
Definition intvec.h:85
STATIC_VAR TreeM * G
Definition janet.cc:31
#define assume(x)
Definition mod2.h:387

◆ graphGrowth()

static int graphGrowth ( const intvec G)
static

Definition at line 1649 of file hdegree.cc.

1650{
1651 // init
1652 int n = G->cols();
1653 std::vector<int> path;
1654 std::vector<BOOLEAN> visited;
1655 std::vector<BOOLEAN> cyclic;
1656 std::vector<int> cache;
1657 visited.resize(n, FALSE);
1658 cyclic.resize(n, FALSE);
1659 cache.resize(n, -2);
1660
1661 // get max number of cycles
1662 int cycles = 0;
1663 for (int v = 0; v < n; v++)
1664 {
1666 if (cache[v] == -1)
1667 return -1;
1668 cycles = si_max(cycles, cache[v]);
1669 }
1670 return cycles;
1671}
#define FALSE
Definition auxiliary.h:96

◆ hCheck1()

static BOOLEAN hCheck1 ( indset  sm,
scmon  pure 
)
static

Definition at line 465 of file hdegree.cc.

466{
467 int iv;
468 intvec *Set;
469 while (sm->nx != NULL)
470 {
471 Set = sm->set;
472 iv=(currRing->N);
473 loop
474 {
475 if (((*Set)[iv-1] == 0) && (pure[iv] == 0))
476 break;
477 iv--;
478 if (iv == 0)
479 return FALSE;
480 }
481 sm = sm->nx;
482 }
483 return TRUE;
484}
#define loop
Definition structs.h:75

◆ hCheck2()

static indset hCheck2 ( indset  sm,
scmon  pure 
)
static

Definition at line 491 of file hdegree.cc.

492{
493 int iv;
494 intvec *Set;
495 indset be, a1 = NULL;
496 while (sm->nx != NULL)
497 {
498 Set = sm->set;
499 iv=(currRing->N);
500 loop
501 {
502 if ((pure[iv] == 1) && ((*Set)[iv-1] == 1))
503 break;
504 iv--;
505 if (iv == 0)
506 {
507 if (a1 == NULL)
508 {
509 a1 = sm;
510 }
511 else
512 {
513 hMu2--;
514 be->nx = sm->nx;
515 delete Set;
517 sm = be;
518 }
519 break;
520 }
521 }
522 be = sm;
523 sm = sm->nx;
524 }
525 if (a1 != NULL)
526 {
527 return a1;
528 }
529 else
530 {
531 hMu2++;
532 sm->set = new intvec((currRing->N));
534 return sm;
535 }
536}
VAR omBin indlist_bin
Definition hdegree.cc:29
VAR int hMu2
Definition hdegree.cc:27
indlist * indset
Definition hutil.h:28
#define omAlloc0Bin(bin)
#define omFreeBin(addr, bin)

◆ hCheckIndep()

static void hCheckIndep ( scmon  pure)
static

Definition at line 543 of file hdegree.cc.

544{
545 intvec *Set;
546 indset res;
547 int iv;
548 if (hCheck1(ISet, pure))
549 {
550 if (hCheck1(JSet, pure))
551 {
552 res = hCheck2(JSet,pure);
553 if (res == NULL)
554 return;
555 Set = res->set;
556 for (iv=(currRing->N); iv; iv--)
557 {
558 (*Set)[iv-1] = (pure[iv]==0);
559 }
560 }
561 }
562}
CanonicalForm res
Definition facAbsFact.cc:60
static indset hCheck2(indset sm, scmon pure)
Definition hdegree.cc:491
static BOOLEAN hCheck1(indset sm, scmon pure)
Definition hdegree.cc:465
VAR indset ISet
Definition hdegree.cc:353
VAR indset JSet
Definition hdegree.cc:353

◆ hDegree()

static void hDegree ( ideal  S,
ideal  Q 
)
static

Definition at line 802 of file hdegree.cc.

803{
804 id_Test(S, currRing);
805 if( Q!=NULL ) id_Test(Q, currRing);
806
807 int di;
808 int mc;
809 hexist = hInit(S, Q, &hNexist);
810 if (!hNexist)
811 {
812 hCo = 0;
813 hMu = 1;
814 return;
815 }
816 //hWeight();
817 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
818 hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
819 hsel = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
820 hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
821 hpur0 = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
822 mc = hisModule;
823 hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
824 if (!mc)
825 {
826 memcpy(hrad, hexist, hNexist * sizeof(scmon));
827 hstc = hexist;
828 hNrad = hNstc = hNexist;
829 }
830 else
831 hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
832 radmem = hCreate((currRing->N) - 1);
833 stcmem = hCreate((currRing->N) - 1);
834 hCo = (currRing->N) + 1;
835 di = hCo + 1;
836 loop
837 {
838 if (mc)
839 {
840 hComp(hexist, hNexist, mc, hrad, &hNrad);
841 hNstc = hNrad;
842 memcpy(hstc, hrad, hNrad * sizeof(scmon));
843 }
844 if (hNrad)
845 {
846 hNvar = (currRing->N);
849 if (hNvar)
850 {
851 hCo = hNvar;
852 memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
853 hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
856 }
857 }
858 else
859 {
860 hNvar = 1;
861 hCo = 0;
862 }
863 if (hCo < di)
864 {
865 di = hCo;
866 hMu = 0;
867 }
868 if (hNvar && (hCo == di))
869 {
870 if (di && (di < (currRing->N)))
872 else if (!di)
873 hMu++;
874 else
875 {
877 if ((hNvar > 2) && (hNstc > 10))
879 memset(hpur0, 0, ((currRing->N) + 1) * sizeof(int));
880 hPure(hstc, 0, &hNstc, hvar, hNvar, hpur0, &hNpure);
883 }
884 }
885 mc--;
886 if (mc <= 0)
887 break;
888 }
889 hCo = di;
890 hKill(stcmem, (currRing->N) - 1);
891 hKill(radmem, (currRing->N) - 1);
892 omFreeSize((ADDRESS)hpur0, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
893 omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
894 omFreeSize((ADDRESS)hsel, ((currRing->N) + 1) * sizeof(int));
895 omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
896 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
897 omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
899 if (hisModule)
900 omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
901}
static long hZeroMult(scmon pure, scfmon stc, int Nstc, varset var, int Nvar)
Definition hdegree.cc:621
static void hDimMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:726
VAR int hCo
Definition hdegree.cc:27
VAR long hMu
Definition hdegree.cc:28
void hDimSolve(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:35
monf hCreate(int Nvar)
Definition hutil.cc:996
void hComp(scfmon exist, int Nexist, int ak, scfmon stc, int *Nstc)
Definition hutil.cc:154
VAR scfmon hstc
Definition hutil.cc:16
VAR varset hvar
Definition hutil.cc:18
void hKill(monf xmem, int Nvar)
Definition hutil.cc:1010
VAR int hNexist
Definition hutil.cc:19
void hLexS(scfmon stc, int Nstc, varset var, int Nvar)
Definition hutil.cc:506
void hDelete(scfmon ev, int ev_length)
Definition hutil.cc:140
VAR scmon hpur0
Definition hutil.cc:17
VAR monf stcmem
Definition hutil.cc:21
void hPure(scfmon stc, int a, int *Nstc, varset var, int Nvar, scmon pure, int *Npure)
Definition hutil.cc:621
VAR scfmon hwork
Definition hutil.cc:16
void hSupp(scfmon stc, int Nstc, varset var, int *Nvar)
Definition hutil.cc:174
void hLexR(scfmon rad, int Nrad, varset var, int Nvar)
Definition hutil.cc:565
VAR scmon hpure
Definition hutil.cc:17
VAR scfmon hrad
Definition hutil.cc:16
VAR int hisModule
Definition hutil.cc:20
void hStaircase(scfmon stc, int *Nstc, varset var, int Nvar)
Definition hutil.cc:313
VAR monf radmem
Definition hutil.cc:21
void hOrdSupp(scfmon stc, int Nstc, varset var, int Nvar)
Definition hutil.cc:202
VAR varset hsel
Definition hutil.cc:18
VAR int hNpure
Definition hutil.cc:19
VAR int hNrad
Definition hutil.cc:19
scfmon hInit(ideal S, ideal Q, int *Nexist)
Definition hutil.cc:31
VAR scfmon hexist
Definition hutil.cc:16
void hRadical(scfmon rad, int *Nrad, int Nvar)
Definition hutil.cc:411
VAR int hNstc
Definition hutil.cc:19
VAR int hNvar
Definition hutil.cc:19
scmon * scfmon
Definition hutil.h:15
int * varset
Definition hutil.h:16
int * scmon
Definition hutil.h:14
#define omFreeSize(addr, size)
#define omAlloc(size)
#define id_Test(A, lR)
#define Q
Definition sirandom.c:26

◆ hDimMult()

static void hDimMult ( scmon  pure,
int  Npure,
scfmon  rad,
int  Nrad,
varset  var,
int  Nvar 
)
static

Definition at line 726 of file hdegree.cc.

728{
729 int dn, iv, rad0, b, c, x;
730 scmon pn;
731 scfmon rn;
732 if (Nrad < 2)
733 {
734 dn = Npure + Nrad;
735 if (dn == hCo)
736 {
737 if (!Nrad)
739 else
740 {
741 pn = *rad;
742 for (iv = Nvar; iv; iv--)
743 {
744 x = var[iv];
745 if (pn[x])
746 {
747 pure[x] = 1;
749 pure[x] = 0;
750 }
751 }
752 }
753 }
754 return;
755 }
756 iv = Nvar;
757 dn = Npure+1;
758 if (dn >= hCo)
759 {
760 if (dn > hCo)
761 return;
762 loop
763 {
764 if(!pure[var[iv]])
765 {
766 if(hNotZero(rad, Nrad, var, iv))
767 {
768 pure[var[iv]] = 1;
770 pure[var[iv]] = 0;
771 }
772 }
773 iv--;
774 if (!iv)
775 return;
776 }
777 }
778 while(pure[var[iv]]) iv--;
779 hStepR(rad, Nrad, var, iv, &rad0);
780 iv--;
781 if (rad0 < Nrad)
782 {
783 pn = hGetpure(pure);
784 rn = hGetmem(Nrad, rad, radmem[iv]);
785 pn[var[iv + 1]] = 1;
786 hDimMult(pn, Npure + 1, rn, rad0, var, iv);
787 pn[var[iv + 1]] = 0;
788 b = rad0;
789 c = Nrad;
790 hElimR(rn, &rad0, b, c, var, iv);
791 hPure(rn, b, &c, var, iv, pn, &x);
792 hLex2R(rn, rad0, b, c, var, iv, hwork);
793 rad0 += (c - b);
794 hDimMult(pn, Npure + x, rn, rad0, var, iv);
795 }
796 else
797 {
798 hDimMult(pure, Npure, rad, Nrad, var, iv);
799 }
800}
Variable x
Definition cfModGcd.cc:4090
CanonicalForm b
Definition cfModGcd.cc:4111
static BOOLEAN hNotZero(scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:355
static void hProject(scmon pure, varset sel)
Definition hdegree.cc:703
scfmon hGetmem(int lm, scfmon old, monp monmem)
Definition hutil.cc:1023
void hStepR(scfmon rad, int Nrad, varset var, int Nvar, int *a)
Definition hutil.cc:974
void hLex2R(scfmon rad, int e1, int a2, int e2, varset var, int Nvar, scfmon w)
Definition hutil.cc:880
void hElimR(scfmon rad, int *e1, int a2, int e2, varset var, int Nvar)
Definition hutil.cc:742
scmon hGetpure(scmon p)
Definition hutil.cc:1052

◆ hDimSolve()

void hDimSolve ( scmon  pure,
int  Npure,
scfmon  rad,
int  Nrad,
varset  var,
int  Nvar 
)

Definition at line 35 of file hdegree.cc.

37{
38 int dn, iv, rad0, b, c, x;
39 scmon pn;
40 scfmon rn;
41 if (Nrad < 2)
42 {
43 dn = Npure + Nrad;
44 if (dn < hCo)
45 hCo = dn;
46 return;
47 }
48 if (Npure+1 >= hCo)
49 return;
50 iv = Nvar;
51 while(pure[var[iv]]) iv--;
52 hStepR(rad, Nrad, var, iv, &rad0);
53 if (rad0!=0)
54 {
55 iv--;
56 if (rad0 < Nrad)
57 {
58 pn = hGetpure(pure);
59 rn = hGetmem(Nrad, rad, radmem[iv]);
60 hDimSolve(pn, Npure + 1, rn, rad0, var, iv);
61 b = rad0;
62 c = Nrad;
63 hElimR(rn, &rad0, b, c, var, iv);
64 hPure(rn, b, &c, var, iv, pn, &x);
65 hLex2R(rn, rad0, b, c, var, iv, hwork);
66 rad0 += (c - b);
67 hDimSolve(pn, Npure + x, rn, rad0, var, iv);
68 }
69 else
70 {
71 hDimSolve(pure, Npure, rad, Nrad, var, iv);
72 }
73 }
74 else
75 hCo = Npure + 1;
76}

◆ hHedge()

static void hHedge ( poly  hEdge)
static

Definition at line 1005 of file hdegree.cc.

1006{
1007 pSetm(pWork);
1008 if (pLmCmp(pWork, hEdge) == currRing->OrdSgn)
1009 {
1010 for (int i = hNvar; i>0; i--)
1012 pSetm(hEdge);
1013 }
1014}
STATIC_VAR poly pWork
Definition hdegree.cc:1003
#define pGetExp(p, i)
Exponent.
Definition polys.h:41
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition polys.h:105

◆ hHedgeStep()

static void hHedgeStep ( scmon  pure,
scfmon  stc,
int  Nstc,
varset  var,
int  Nvar,
poly  hEdge 
)
static

Definition at line 1016 of file hdegree.cc.

1018{
1019 int iv = Nvar -1, k = var[Nvar], a, a0, a1, b, i;
1020 int x/*, x0*/;
1021 scmon pn;
1022 scfmon sn;
1023 if (iv==0)
1024 {
1025 pSetExp(pWork, k, pure[k]);
1026 hHedge(hEdge);
1027 return;
1028 }
1029 else if (Nstc==0)
1030 {
1031 for (i = Nvar; i>0; i--)
1032 pSetExp(pWork, var[i], pure[var[i]]);
1033 hHedge(hEdge);
1034 return;
1035 }
1036 x = a = 0;
1037 pn = hGetpure(pure);
1038 sn = hGetmem(Nstc, stc, stcmem[iv]);
1039 hStepS(sn, Nstc, var, Nvar, &a, &x);
1040 if (a == Nstc)
1041 {
1042 pSetExp(pWork, k, pure[k]);
1043 hHedgeStep(pn, sn, a, var, iv,hEdge);
1044 return;
1045 }
1046 else
1047 {
1048 pSetExp(pWork, k, x);
1049 hHedgeStep(pn, sn, a, var, iv,hEdge);
1050 }
1051 b = a;
1052 loop
1053 {
1054 a0 = a;
1055 // x0 = x;
1056 hStepS(sn, Nstc, var, Nvar, &a, &x);
1057 hElimS(sn, &b, a0, a, var, iv);
1058 a1 = a;
1059 hPure(sn, a0, &a1, var, iv, pn, &i);
1060 hLex2S(sn, b, a0, a1, var, iv, hwork);
1061 b += (a1 - a0);
1062 if (a < Nstc)
1063 {
1064 pSetExp(pWork, k, x);
1065 hHedgeStep(pn, sn, b, var, iv,hEdge);
1066 }
1067 else
1068 {
1069 pSetExp(pWork, k, pure[k]);
1070 hHedgeStep(pn, sn, b, var, iv,hEdge);
1071 return;
1072 }
1073 }
1074}
int k
Definition cfEzgcd.cc:99
static void hHedgeStep(scmon pure, scfmon stc, int Nstc, varset var, int Nvar, poly hEdge)
Definition hdegree.cc:1016
static void hHedge(poly hEdge)
Definition hdegree.cc:1005
void hLex2S(scfmon rad, int e1, int a2, int e2, varset var, int Nvar, scfmon w)
Definition hutil.cc:812
void hElimS(scfmon stc, int *e1, int a2, int e2, varset var, int Nvar)
Definition hutil.cc:672
void hStepS(scfmon stc, int Nstc, varset var, int Nvar, int *a, int *x)
Definition hutil.cc:949

◆ hIndAllMult()

void hIndAllMult ( scmon  pure,
int  Npure,
scfmon  rad,
int  Nrad,
varset  var,
int  Nvar 
)

Definition at line 564 of file hdegree.cc.

566{
567 int dn, iv, rad0, b, c, x;
568 scmon pn;
569 scfmon rn;
570 if (Nrad < 2)
571 {
572 dn = Npure + Nrad;
573 if (dn > hCo)
574 {
575 if (!Nrad)
577 else
578 {
579 pn = *rad;
580 for (iv = Nvar; iv; iv--)
581 {
582 x = var[iv];
583 if (pn[x])
584 {
585 pure[x] = 1;
587 pure[x] = 0;
588 }
589 }
590 }
591 }
592 return;
593 }
594 iv = Nvar;
595 while(pure[var[iv]]) iv--;
596 hStepR(rad, Nrad, var, iv, &rad0);
597 iv--;
598 if (rad0 < Nrad)
599 {
600 pn = hGetpure(pure);
601 rn = hGetmem(Nrad, rad, radmem[iv]);
602 pn[var[iv + 1]] = 1;
603 hIndAllMult(pn, Npure + 1, rn, rad0, var, iv);
604 pn[var[iv + 1]] = 0;
605 b = rad0;
606 c = Nrad;
607 hElimR(rn, &rad0, b, c, var, iv);
608 hPure(rn, b, &c, var, iv, pn, &x);
609 hLex2R(rn, rad0, b, c, var, iv, hwork);
610 rad0 += (c - b);
611 hIndAllMult(pn, Npure + x, rn, rad0, var, iv);
612 }
613 else
614 {
615 hIndAllMult(pure, Npure, rad, Nrad, var, iv);
616 }
617}
static void hCheckIndep(scmon pure)
Definition hdegree.cc:543
void hIndAllMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:564

◆ hIndep()

static void hIndep ( scmon  pure)
static

Definition at line 370 of file hdegree.cc.

371{
372 int iv;
373 intvec *Set;
374
375 Set = ISet->set = new intvec((currRing->N));
376 for (iv=(currRing->N); iv!=0 ; iv--)
377 {
378 (*Set)[iv-1] = (pure[iv]==0);
379 }
381 hMu++;
382}

◆ hIndMult()

void hIndMult ( scmon  pure,
int  Npure,
scfmon  rad,
int  Nrad,
varset  var,
int  Nvar 
)

Definition at line 384 of file hdegree.cc.

386{
387 int dn, iv, rad0, b, c, x;
388 scmon pn;
389 scfmon rn;
390 if (Nrad < 2)
391 {
392 dn = Npure + Nrad;
393 if (dn == hCo)
394 {
395 if (Nrad==0)
396 hIndep(pure);
397 else
398 {
399 pn = *rad;
400 for (iv = Nvar; iv!=0; iv--)
401 {
402 x = var[iv];
403 if (pn[x])
404 {
405 pure[x] = 1;
406 hIndep(pure);
407 pure[x] = 0;
408 }
409 }
410 }
411 }
412 return;
413 }
414 iv = Nvar;
415 dn = Npure+1;
416 if (dn >= hCo)
417 {
418 if (dn > hCo)
419 return;
420 loop
421 {
422 if(!pure[var[iv]])
423 {
424 if(hNotZero(rad, Nrad, var, iv))
425 {
426 pure[var[iv]] = 1;
427 hIndep(pure);
428 pure[var[iv]] = 0;
429 }
430 }
431 iv--;
432 if (!iv)
433 return;
434 }
435 }
436 while(pure[var[iv]]) iv--;
437 hStepR(rad, Nrad, var, iv, &rad0);
438 iv--;
439 if (rad0 < Nrad)
440 {
441 pn = hGetpure(pure);
442 rn = hGetmem(Nrad, rad, radmem[iv]);
443 pn[var[iv + 1]] = 1;
444 hIndMult(pn, Npure + 1, rn, rad0, var, iv);
445 pn[var[iv + 1]] = 0;
446 b = rad0;
447 c = Nrad;
448 hElimR(rn, &rad0, b, c, var, iv);
449 hPure(rn, b, &c, var, iv, pn, &x);
450 hLex2R(rn, rad0, b, c, var, iv, hwork);
451 rad0 += (c - b);
452 hIndMult(pn, Npure + x, rn, rad0, var, iv);
453 }
454 else
455 {
456 hIndMult(pure, Npure, rad, Nrad, var, iv);
457 }
458}
void hIndMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:384
static void hIndep(scmon pure)
Definition hdegree.cc:370

◆ hIndSolve()

static void hIndSolve ( scmon  pure,
int  Npure,
scfmon  rad,
int  Nrad,
varset  var,
int  Nvar 
)
static

Definition at line 207 of file hdegree.cc.

209{
210 int dn, iv, rad0, b, c, x;
211 scmon pn;
212 scfmon rn;
213 if (Nrad < 2)
214 {
215 dn = Npure + Nrad;
216 if (dn < hCo)
217 {
218 hCo = dn;
219 for (iv=(currRing->N); iv; iv--)
220 {
221 if (pure[iv])
222 hInd[iv] = 0;
223 else
224 hInd[iv] = 1;
225 }
226 if (Nrad)
227 {
228 pn = *rad;
229 iv = Nvar;
230 loop
231 {
232 x = var[iv];
233 if (pn[x])
234 {
235 hInd[x] = 0;
236 break;
237 }
238 iv--;
239 }
240 }
241 }
242 return;
243 }
244 if (Npure+1 >= hCo)
245 return;
246 iv = Nvar;
247 while(pure[var[iv]]) iv--;
248 hStepR(rad, Nrad, var, iv, &rad0);
249 if (rad0)
250 {
251 iv--;
252 if (rad0 < Nrad)
253 {
254 pn = hGetpure(pure);
255 rn = hGetmem(Nrad, rad, radmem[iv]);
256 pn[var[iv + 1]] = 1;
257 hIndSolve(pn, Npure + 1, rn, rad0, var, iv);
258 pn[var[iv + 1]] = 0;
259 b = rad0;
260 c = Nrad;
261 hElimR(rn, &rad0, b, c, var, iv);
262 hPure(rn, b, &c, var, iv, pn, &x);
263 hLex2R(rn, rad0, b, c, var, iv, hwork);
264 rad0 += (c - b);
265 hIndSolve(pn, Npure + x, rn, rad0, var, iv);
266 }
267 else
268 {
269 hIndSolve(pure, Npure, rad, Nrad, var, iv);
270 }
271 }
272 else
273 {
274 hCo = Npure + 1;
275 for (x=(currRing->N); x; x--)
276 {
277 if (pure[x])
278 hInd[x] = 0;
279 else
280 hInd[x] = 1;
281 }
282 hInd[var[iv]] = 0;
283 }
284}
STATIC_VAR scmon hInd
Definition hdegree.cc:205
static void hIndSolve(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:207

◆ hNotZero()

static BOOLEAN hNotZero ( scfmon  rad,
int  Nrad,
varset  var,
int  Nvar 
)
static

Definition at line 355 of file hdegree.cc.

356{
357 int k1, i;
358 k1 = var[Nvar];
359 i = 0;
360 loop
361 {
362 if (rad[i][k1]==0)
363 return FALSE;
364 i++;
365 if (i == Nrad)
366 return TRUE;
367 }
368}

◆ hProject()

static void hProject ( scmon  pure,
varset  sel 
)
static

Definition at line 703 of file hdegree.cc.

704{
705 int i, i0, k;
706 i0 = 0;
707 for (i = 1; i <= (currRing->N); i++)
708 {
709 if (pure[i])
710 {
711 i0++;
712 sel[i0] = i;
713 }
714 }
715 i = hNstc;
716 memcpy(hwork, hstc, i * sizeof(scmon));
717 hStaircase(hwork, &i, sel, i0);
718 if ((i0 > 2) && (i > 10))
719 hOrdSupp(hwork, i, sel, i0);
720 memset(hpur0, 0, ((currRing->N) + 1) * sizeof(int));
721 hPure(hwork, 0, &i, sel, i0, hpur0, &k);
722 hLexS(hwork, i, sel, i0);
723 hMu += hZeroMult(hpur0, hwork, i, sel, i0);
724}

◆ hZeroMult()

static long hZeroMult ( scmon  pure,
scfmon  stc,
int  Nstc,
varset  var,
int  Nvar 
)
static

Definition at line 621 of file hdegree.cc.

622{
623 int iv = Nvar -1, a, a0, a1, b, i;
624 long sum;
625 int x, x0;
626 scmon pn;
627 scfmon sn;
628 if (!iv)
629 return pure[var[1]];
630 else if (!Nstc)
631 {
632 sum = 1;
633 for (i = Nvar; i; i--)
634 sum *= pure[var[i]];
635 return sum;
636 }
637 x = a = 0;
638 pn = hGetpure(pure);
639 sn = hGetmem(Nstc, stc, stcmem[iv]);
640 hStepS(sn, Nstc, var, Nvar, &a, &x);
641 if (a == Nstc)
642 {
643 #if SIZEOF_LONG==8
644 return (long)pure[var[Nvar]] * hZeroMult(pn, sn, a, var, iv);
645 #else
646 int64 t=hZeroMult(pn, sn, a, var, iv);
647 t *= pure[var[Nvar]];
648 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
649 else if (!errorreported) WerrorS("int overflow in vdim 3");
650 return sum;
651 #endif
652 }
653 else
654 {
655 #if SIZEOF_LONG==8
656 sum = x * hZeroMult(pn, sn, a, var, iv);
657 #else
658 int64 t=hZeroMult(pn, sn, a, var, iv);
659 t *= x;
660 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
661 else if (!errorreported) WerrorS("int overflow in vdim 4");
662 #endif
663 }
664 b = a;
665 loop
666 {
667 a0 = a;
668 x0 = x;
669 hStepS(sn, Nstc, var, Nvar, &a, &x);
670 hElimS(sn, &b, a0, a, var, iv);
671 a1 = a;
672 hPure(sn, a0, &a1, var, iv, pn, &i);
673 hLex2S(sn, b, a0, a1, var, iv, hwork);
674 b += (a1 - a0);
675 if (a < Nstc)
676 {
677 #if SIZEOF_LONG==8
678 sum += (long)(x - x0) * hZeroMult(pn, sn, b, var, iv);
679 #else
680 int64 t=hZeroMult(pn, sn, b, var, iv);
681 t *= (x-x0);
682 t += sum;
683 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
684 else if (!errorreported) WerrorS("int overflow in vdim 1");
685 #endif
686 }
687 else
688 {
689 #if SIZEOF_LONG==8
690 sum += (long)(pure[var[Nvar]] - x0) * hZeroMult(pn, sn, b, var, iv);
691 #else
692 int64 t=hZeroMult(pn, sn, b, var, iv);
693 t *= (pure[var[Nvar]]-x0);
694 t += sum;
695 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
696 else if (!errorreported) WerrorS("int overflow in vdim 2");
697 #endif
698 return sum;
699 }
700 }
701}
long int64
Definition auxiliary.h:68
VAR short errorreported
Definition feFopen.cc:23
void WerrorS(const char *s)
Definition feFopen.cc:24

◆ isAcyclic()

static BOOLEAN isAcyclic ( const intvec G)
static

Definition at line 2060 of file hdegree.cc.

2061{
2062 // init
2063 int n = G->cols();
2064 std::vector<int> path;
2065 std::vector<BOOLEAN> visited;
2066 std::vector<BOOLEAN> cyclic;
2067 std::vector<int> cache;
2068 visited.resize(n, FALSE);
2069 cyclic.resize(n, FALSE);
2070 cache.resize(n, -2);
2071
2072 for (int v = 0; v < n; v++)
2073 {
2075 // check that there are 0 cycles from v
2076 if (cache[v] != 0)
2077 return FALSE;
2078 }
2079 return TRUE;
2080}

◆ iv2vv()

static std::vector< std::vector< int > > iv2vv ( intvec M)
static

Definition at line 1947 of file hdegree.cc.

1948{
1949 int rows = M->rows();
1950 int cols = M->cols();
1951
1952 std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
1953
1954 for (int i = 0; i < rows; i++)
1955 {
1956 for (int j = 0; j < cols; j++)
1957 {
1958 mat[i][j] = IMATELEM(*M, i + 1, j + 1);
1959 }
1960 }
1961
1962 return mat;
1963}

◆ lp_computeNormalWords()

static ideal lp_computeNormalWords ( int  length,
ideal  M 
)
static

Definition at line 1735 of file hdegree.cc.

1736{
1737 long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
1738 for (int i = 1; i < IDELEMS(M); i++)
1739 {
1741 }
1742
1743 int nVars = currRing->isLPring - currRing->LPncGenCount;
1744
1745 int maxElems = 1;
1746 for (int i = 0; i < length; i++) // maxElems = nVars^n
1747 maxElems *= nVars;
1752 return words;
1753}
static int si_min(const int a, const int b)
Definition auxiliary.h:125
static long pTotaldegree(poly p)
Definition polys.h:282
ideal idInit(int idsize, int rank)
initialise an ideal / module
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)

◆ lp_countNormalWords()

static int lp_countNormalWords ( int  upToLength,
ideal  M 
)
static

Definition at line 1755 of file hdegree.cc.

1756{
1757 long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
1758 for (int i = 1; i < IDELEMS(M); i++)
1759 {
1761 }
1762
1763 int nVars = currRing->isLPring - currRing->LPncGenCount;
1764
1765 int maxElems = 1;
1766 for (int i = 0; i < upToLength; i++) // maxElems = nVars^n
1767 maxElems *= nVars;
1771 idDelete(&words);
1772 return numberOfNormalWords;
1773}
#define idDelete(H)
delete an ideal
Definition ideals.h:29

◆ lp_gkDim()

int lp_gkDim ( const ideal  _G)

Definition at line 1837 of file hdegree.cc.

1838{
1840
1841 if (rField_is_Ring(currRing)) {
1842 WerrorS("GK-Dim not implemented for rings");
1843 return -2;
1844 }
1845
1846 for (int i=IDELEMS(_G)-1;i>=0; i--)
1847 {
1848 if (_G->m[i] != NULL)
1849 {
1850 if (pGetComp(_G->m[i]) != 0)
1851 {
1852 WerrorS("GK-Dim not implemented for modules");
1853 return -2;
1854 }
1855 if (pGetNCGen(_G->m[i]) != 0)
1856 {
1857 WerrorS("GK-Dim not implemented for bi-modules");
1858 return -2;
1859 }
1860 }
1861 }
1862
1863 ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
1864 idSkipZeroes(G); // remove zeros
1865 id_DelLmEquals(G, currRing); // remove duplicates
1866
1867 // check if G is the zero ideal
1868 if (IDELEMS(G) == 1 && G->m[0] == NULL)
1869 {
1870 // NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
1871 int lV = currRing->isLPring;
1872 int ncGenCount = currRing->LPncGenCount;
1873 if (lV - ncGenCount == 0)
1874 {
1875 idDelete(&G);
1876 return 0;
1877 }
1878 if (lV - ncGenCount == 1)
1879 {
1880 idDelete(&G);
1881 return 1;
1882 }
1883 if (lV - ncGenCount >= 2)
1884 {
1885 idDelete(&G);
1886 return -1;
1887 }
1888 }
1889
1890 // get the max deg
1891 long maxDeg = 0;
1892 for (int i = 0; i < IDELEMS(G); i++)
1893 {
1895
1896 // also check whether G = <1>
1897 if (pIsConstantComp(G->m[i]))
1898 {
1899 WerrorS("GK-Dim not defined for 0-ring");
1900 idDelete(&G);
1901 return -2;
1902 }
1903 }
1904
1905 // early termination if G \subset X
1906 if (maxDeg <= 1)
1907 {
1908 int lV = currRing->isLPring;
1909 int ncGenCount = currRing->LPncGenCount;
1910 if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
1911 {
1912 idDelete(&G);
1913 return 0;
1914 }
1915 if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
1916 {
1917 idDelete(&G);
1918 return 1;
1919 }
1920 if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
1921 {
1922 idDelete(&G);
1923 return -1;
1924 }
1925 }
1926
1929 if (UG == NULL)
1930 {
1931 idDelete(&G);
1932 return -2;
1933 }
1934 if (errorreported)
1935 {
1936 delete UG;
1937 idDelete(&G);
1938 return -2;
1939 }
1940 int gkDim = graphGrowth(UG);
1941 delete UG;
1942 idDelete(&G);
1943 return gkDim;
1944}
static int graphGrowth(const intvec *G)
Definition hdegree.cc:1649
intvec * lp_ufnarovskiGraph(ideal G, ideal &standardWords)
Definition hdegree.cc:1776
#define pGetComp(p)
Component.
Definition polys.h:37
#define pIsConstantComp(p)
return true if p is either NULL, or if all exponents of p are 0, Comp of p might be !...
Definition polys.h:236
#define rField_is_Ring(R)
Definition ring.h:490
#define pGetNCGen(p)
Definition shiftop.h:65
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
void id_DelLmEquals(ideal id, const ring r)
Delete id[j], if Lm(j) == Lm(i) and both LC(j), LC(i) are units and j > i.

◆ lp_kDim()

int lp_kDim ( const ideal  _G)

Definition at line 2087 of file hdegree.cc.

2088{
2089 if (rField_is_Ring(currRing)) {
2090 WerrorS("K-Dim not implemented for rings");
2091 return -2;
2092 }
2093
2094 for (int i=IDELEMS(_G)-1;i>=0; i--)
2095 {
2096 if (_G->m[i] != NULL)
2097 {
2098 if (pGetComp(_G->m[i]) != 0)
2099 {
2100 WerrorS("K-Dim not implemented for modules");
2101 return -2;
2102 }
2103 if (pGetNCGen(_G->m[i]) != 0)
2104 {
2105 WerrorS("K-Dim not implemented for bi-modules");
2106 return -2;
2107 }
2108 }
2109 }
2110
2111 ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
2112 if (TEST_OPT_PROT)
2113 Print("%d original generators\n", IDELEMS(G));
2114 idSkipZeroes(G); // remove zeros
2115 id_DelLmEquals(G, currRing); // remove duplicates
2116 if (TEST_OPT_PROT)
2117 Print("%d non-zero unique generators\n", IDELEMS(G));
2118
2119 // check if G is the zero ideal
2120 if (IDELEMS(G) == 1 && G->m[0] == NULL)
2121 {
2122 // NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
2123 int lV = currRing->isLPring;
2124 int ncGenCount = currRing->LPncGenCount;
2125 if (lV - ncGenCount == 0)
2126 {
2127 idDelete(&G);
2128 return 1;
2129 }
2130 if (lV - ncGenCount == 1)
2131 {
2132 idDelete(&G);
2133 return -1;
2134 }
2135 if (lV - ncGenCount >= 2)
2136 {
2137 idDelete(&G);
2138 return -1;
2139 }
2140 }
2141
2142 // get the max deg
2143 long maxDeg = 0;
2144 for (int i = 0; i < IDELEMS(G); i++)
2145 {
2147
2148 // also check whether G = <1>
2149 if (pIsConstantComp(G->m[i]))
2150 {
2151 WerrorS("K-Dim not defined for 0-ring"); // TODO is it minus infinity ?
2152 idDelete(&G);
2153 return -2;
2154 }
2155 }
2156 if (TEST_OPT_PROT)
2157 Print("max deg: %ld\n", maxDeg);
2158
2159
2160 // for normal words of length minDeg ... maxDeg-1
2161 // brute-force the normal words
2162 if (TEST_OPT_PROT)
2163 PrintS("Computing normal words normally...\n");
2165
2166 if (TEST_OPT_PROT)
2167 Print("%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
2168
2169 // early termination if G \subset X
2170 if (maxDeg <= 1)
2171 {
2172 int lV = currRing->isLPring;
2173 int ncGenCount = currRing->LPncGenCount;
2174 if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
2175 {
2176 idDelete(&G);
2177 return numberOfNormalWords;
2178 }
2179 if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
2180 {
2181 idDelete(&G);
2182 return -1;
2183 }
2184 if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
2185 {
2186 idDelete(&G);
2187 return -1;
2188 }
2189 }
2190
2191 if (TEST_OPT_PROT)
2192 PrintS("Computing Ufnarovski graph...\n");
2193
2196 if (UG == NULL)
2197 {
2198 idDelete(&G);
2199 return -2;
2200 }
2201 if (errorreported)
2202 {
2203 delete UG;
2204 idDelete(&G);
2205 return -2;
2206 }
2207
2208 if (TEST_OPT_PROT)
2209 Print("Ufnarovski graph is %dx%d.\n", UG->rows(), UG->cols());
2210
2211 if (TEST_OPT_PROT)
2212 PrintS("Checking whether Ufnarovski graph is acyclic...\n");
2213
2214 if (!isAcyclic(UG))
2215 {
2216 // in this case we have infinitely many normal words
2217 return -1;
2218 }
2219
2220 std::vector<std::vector<int> > vvUG = iv2vv(UG);
2221 for (int i = 0; i < vvUG.size(); i++)
2222 {
2223 if (vvIsRowZero(vvUG, i) && vvIsColumnZero(vvUG, i)) // i is isolated vertex
2224 {
2225 vvDeleteRow(vvUG, i);
2227 i--;
2228 }
2229 }
2230 if (TEST_OPT_PROT)
2231 Print("Simplified Ufnarovski graph to %dx%d.\n", (int)vvUG.size(), (int)vvUG.size());
2232
2233 // for normal words of length >= maxDeg
2234 // use Ufnarovski graph
2235 if (TEST_OPT_PROT)
2236 PrintS("Computing normal words via Ufnarovski graph...\n");
2237 std::vector<std::vector<int> > UGpower = vvUG;
2238 long nUGpower = 1;
2239 while (!vvIsZero(UGpower))
2240 {
2241 if (TEST_OPT_PROT)
2242 PrintS("Start count graph entries.\n");
2243 for (int i = 0; i < UGpower.size(); i++)
2244 {
2245 for (int j = 0; j < UGpower[i].size(); j++)
2246 {
2248 }
2249 }
2250
2251 if (TEST_OPT_PROT)
2252 {
2253 PrintS("Done count graph entries.\n");
2254 Print("%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
2255 }
2256
2257 if (TEST_OPT_PROT)
2258 PrintS("Start mat mult.\n");
2259 UGpower = vvMult(UGpower, vvUG); // TODO: avoid creation of new intvec
2260 if (TEST_OPT_PROT)
2261 PrintS("Done mat mult.\n");
2262 nUGpower++;
2263 }
2264
2265 delete UG;
2266 idDelete(&G);
2267 return numberOfNormalWords;
2268}
#define Print
Definition emacs.cc:80
static std::vector< std::vector< int > > vvMult(const std::vector< std::vector< int > > &a, const std::vector< std::vector< int > > &b)
Definition hdegree.cc:2033
static void vvDeleteRow(std::vector< std::vector< int > > &mat, int row)
Definition hdegree.cc:1990
static BOOLEAN vvIsColumnZero(const std::vector< std::vector< int > > &mat, int col)
Definition hdegree.cc:2013
static void vvDeleteColumn(std::vector< std::vector< int > > &mat, int col)
Definition hdegree.cc:1995
static std::vector< std::vector< int > > iv2vv(intvec *M)
Definition hdegree.cc:1947
static int lp_countNormalWords(int upToLength, ideal M)
Definition hdegree.cc:1755
static BOOLEAN isAcyclic(const intvec *G)
Definition hdegree.cc:2060
static BOOLEAN vvIsZero(const std::vector< std::vector< int > > &mat)
Definition hdegree.cc:2023
static BOOLEAN vvIsRowZero(const std::vector< std::vector< int > > &mat, int row)
Definition hdegree.cc:2003
#define TEST_OPT_PROT
Definition options.h:103
void PrintS(const char *s)
Definition reporter.cc:284

◆ lp_ufnarovskiGraph()

intvec * lp_ufnarovskiGraph ( ideal  G,
ideal standardWords 
)

Definition at line 1776 of file hdegree.cc.

1777{
1778 long l = 0;
1779 for (int i = 0; i < IDELEMS(G); i++)
1780 l = si_max(pTotaldegree(G->m[i]), l);
1781 l--;
1782 if (l <= 0)
1783 {
1784 WerrorS("Ufnarovski graph not implemented for l <= 0");
1785 return NULL;
1786 }
1787 int lV = currRing->isLPring;
1788
1790
1791 int n = IDELEMS(standardWords);
1792 intvec* UG = new intvec(n, n, 0);
1793 for (int i = 0; i < n; i++)
1794 {
1795 for (int j = 0; j < n; j++)
1796 {
1797 poly v = standardWords->m[i];
1798 poly w = standardWords->m[j];
1799
1800 // check whether v*x1 = x2*w (overlap)
1801 bool overlap = true;
1802 for (int k = 1; k <= (l - 1) * lV; k++)
1803 {
1804 if (pGetExp(v, k + lV) != pGetExp(w, k)) {
1805 overlap = false;
1806 break;
1807 }
1808 }
1809
1810 if (overlap)
1811 {
1812 // create the overlap
1813 poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing));
1814
1815 // check whether the overlap is normal
1816 bool normal = true;
1817 for (int k = 0; k < IDELEMS(G); k++)
1818 {
1819 if (p_LPDivisibleBy(G->m[k], p, currRing))
1820 {
1821 normal = false;
1822 break;
1823 }
1824 }
1825
1826 if (normal)
1827 {
1828 IMATELEM(*UG, i + 1, j + 1) = 1;
1829 }
1830 }
1831 }
1832 }
1833 return UG;
1834}
int l
Definition cfEzgcd.cc:100
int p
Definition cfModGcd.cc:4086
static ideal lp_computeNormalWords(int length, ideal M)
Definition hdegree.cc:1735
#define pMult(p, q)
Definition polys.h:207
poly p_LPVarAt(poly p, int pos, const ring r)
Definition shiftop.cc:845

◆ scAll()

static void scAll ( int  Nvar,
int  deg 
)
static

Definition at line 1235 of file hdegree.cc.

1236{
1237 int i;
1238 int d = deg;
1239 if (d == 0)
1240 {
1241 for (i=Nvar; i; i--) act[i] = 0;
1242 scElKbase();
1243 return;
1244 }
1245 if (Nvar == 1)
1246 {
1247 act[1] = d;
1248 scElKbase();
1249 return;
1250 }
1251 do
1252 {
1253 act[Nvar] = d;
1254 scAll(Nvar-1, deg-d);
1255 d--;
1256 } while (d >= 0);
1257}
static void scElKbase()
Definition hdegree.cc:1151
static void scAll(int Nvar, int deg)
Definition hdegree.cc:1235
STATIC_VAR scmon act
Definition hdegree.cc:1149

◆ scAllKbase()

static void scAllKbase ( int  Nvar,
int  ideg,
int  deg 
)
static

Definition at line 1259 of file hdegree.cc.

1260{
1261 do
1262 {
1263 act[Nvar] = ideg;
1264 scAll(Nvar-1, deg-ideg);
1265 ideg--;
1266 } while (ideg >= 0);
1267}

◆ scComputeHC()

void scComputeHC ( ideal  S,
ideal  Q,
int  ak,
poly &  hEdge 
)

Definition at line 1076 of file hdegree.cc.

1077{
1078 id_LmTest(S, currRing);
1079 if (Q!=NULL) id_LmTest(Q, currRing);
1080
1081 int i;
1082 int k = ak;
1083 #ifdef HAVE_RINGS
1084 if (rField_is_Ring(currRing) && (currRing->OrdSgn == -1))
1085 {
1086 //consider just monic generators (over rings with zero-divisors)
1088 for(i=0;i<=idElem(S);i++)
1089 {
1090 if((SS->m[i]!=NULL)
1091 && ((p_IsPurePower(SS->m[i],currRing)==0)
1092 ||(!n_IsUnit(pGetCoeff(SS->m[i]), currRing->cf))))
1093 {
1094 p_Delete(&SS->m[i],currRing);
1095 }
1096 }
1097 S=id_Copy(SS,currRing);
1098 idSkipZeroes(S);
1099 }
1100 #if 0
1101 printf("\nThis is HC:\n");
1102 for(int ii=0;ii<=idElem(S);ii++)
1103 {
1104 pWrite(S->m[ii]);
1105 }
1106 //getchar();
1107 #endif
1108 #endif
1109 if(idElem(S) == 0)
1110 return;
1111 hNvar = (currRing->N);
1112 hexist = hInit(S, Q, &hNexist);
1113 if (k!=0)
1115 else
1116 hNstc = hNexist;
1117 assume(hNexist > 0);
1118 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
1119 hvar = (varset)omAlloc((hNvar + 1) * sizeof(int));
1120 hpure = (scmon)omAlloc((1 + (hNvar * hNvar)) * sizeof(int));
1121 stcmem = hCreate(hNvar - 1);
1122 for (i = hNvar; i>0; i--)
1123 hvar[i] = i;
1125 if ((hNvar > 2) && (hNstc > 10))
1127 memset(hpure, 0, (hNvar + 1) * sizeof(int));
1128 hPure(hexist, 0, &hNstc, hvar, hNvar, hpure, &hNpure);
1130 if (hEdge!=NULL)
1131 pLmFree(hEdge);
1132 hEdge = pInit();
1133 pWork = pInit();
1135 pSetComp(hEdge,ak);
1136 hKill(stcmem, hNvar - 1);
1137 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
1138 omFreeSize((ADDRESS)hvar, (hNvar + 1) * sizeof(int));
1139 omFreeSize((ADDRESS)hpure, (1 + (hNvar * hNvar)) * sizeof(int));
1141 pLmFree(pWork);
1142}
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition coeffs.h:519
ideal id_Copy(ideal h1, const ring r)
copy an ideal
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
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition p_polys.cc:1229
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:901
#define pSetComp(p, v)
Definition polys.h:38
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition polys.h:70
void pWrite(poly p)
Definition polys.h:308
#define pInit()
allocates a new monomial and initializes everything to 0
Definition polys.h:61
static int idElem(const ideal F)
number of non-zero polys in F
#define id_LmTest(A, lR)

◆ scDegKbase()

static void scDegKbase ( scfmon  stc,
int  Nstc,
int  Nvar,
int  deg 
)
static

Definition at line 1269 of file hdegree.cc.

1270{
1271 int Ivar, Istc, i, j;
1272 scfmon sn;
1273 int x, ideg;
1274
1275 if (deg == 0)
1276 {
1277 for (i=Nstc-1; i>=0; i--)
1278 {
1279 for (j=Nvar;j;j--){ if(stc[i][j]) break; }
1280 if (j==0){return;}
1281 }
1282 for (i=Nvar; i; i--) act[i] = 0;
1283 scElKbase();
1284 return;
1285 }
1286 if (Nvar == 1)
1287 {
1288 for (i=Nstc-1; i>=0; i--) if(deg >= stc[i][1]) return;
1289 act[1] = deg;
1290 scElKbase();
1291 return;
1292 }
1293 Ivar = Nvar-1;
1294 sn = hGetmem(Nstc, stc, stcmem[Ivar]);
1295 x = scRestrict(Nstc, sn, Nvar);
1296 if (x <= 0)
1297 {
1298 if (x == 0) return;
1299 ideg = deg;
1300 }
1301 else
1302 {
1303 if (deg < x) ideg = deg;
1304 else ideg = x-1;
1305 if (Nstc == 0)
1306 {
1307 scAllKbase(Nvar, ideg, deg);
1308 return;
1309 }
1310 }
1311 loop
1312 {
1313 x = scMax(Nstc, sn, Nvar);
1314 while (ideg >= x)
1315 {
1316 act[Nvar] = ideg;
1317 scDegKbase(sn, Nstc, Ivar, deg-ideg);
1318 ideg--;
1319 }
1320 if (ideg < 0) return;
1321 Istc = Nstc;
1322 for (i=Nstc-1; i>=0; i--)
1323 {
1324 if (ideg < sn[i][Nvar])
1325 {
1326 Istc--;
1327 sn[i] = NULL;
1328 }
1329 }
1330 if (Istc == 0)
1331 {
1332 scAllKbase(Nvar, ideg, deg);
1333 return;
1334 }
1335 j = 0;
1336 while (sn[j]) j++;
1337 i = j+1;
1338 for (; i<Nstc; i++)
1339 {
1340 if (sn[i])
1341 {
1342 sn[j] = sn[i];
1343 j++;
1344 }
1345 }
1346 Nstc = Istc;
1347 }
1348}
static int scRestrict(int &Nstc, scfmon stc, int Nvar)
Definition hdegree.cc:1184
static void scAllKbase(int Nvar, int ideg, int deg)
Definition hdegree.cc:1259
static void scDegKbase(scfmon stc, int Nstc, int Nvar, int deg)
Definition hdegree.cc:1269
static int scMax(int i, scfmon stc, int Nvar)
Definition hdegree.cc:1160

◆ scDimInt()

int scDimInt ( ideal  S,
ideal  Q 
)

ideal dimension

Definition at line 78 of file hdegree.cc.

79{
80 id_Test(S, currRing);
81 if( Q!=NULL ) id_Test(Q, currRing);
82
83 int mc;
84 hexist = hInit(S, Q, &hNexist);
85 if (!hNexist)
86 return (currRing->N);
87 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
88 hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
89 hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
90 mc = hisModule;
91 if (!mc)
92 {
93 hrad = hexist;
94 hNrad = hNexist;
95 }
96 else
97 hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
98 radmem = hCreate((currRing->N) - 1);
99 hCo = (currRing->N) + 1;
100 loop
101 {
102 if (mc)
103 hComp(hexist, hNexist, mc, hrad, &hNrad);
104 if (hNrad)
105 {
106 hNvar = (currRing->N);
109 if (hNvar)
110 {
111 memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
112 hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
115 }
116 }
117 else
118 {
119 hCo = 0;
120 break;
121 }
122 mc--;
123 if (mc <= 0)
124 break;
125 }
126 hKill(radmem, (currRing->N) - 1);
127 omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
128 omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
129 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
131 if (hisModule)
132 omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
133 return (currRing->N) - hCo;
134}

◆ scDimIntRing()

int scDimIntRing ( ideal  vid,
ideal  Q 
)

scDimInt for ring-coefficients

Definition at line 136 of file hdegree.cc.

137{
138#ifdef HAVE_RINGS
140 {
141 int i = idPosConstant(vid);
142 if ((i != -1) && (n_IsUnit(pGetCoeff(vid->m[i]),currRing->cf)))
143 { /* ideal v contains unit; dim = -1 */
144 return(-1);
145 }
149 int d;
150 if(i == -1)
151 {
152 d = scDimInt(vv, Q);
154 d++;
155 }
156 else
157 {
158 if(n_IsUnit(pGetCoeff(vv->m[i]),currRing->cf))
159 d = -1;
160 else
161 d = scDimInt(vv, Q);
162 }
163 //Anne's Idea for std(4,2x) = 0 bug
164 int dcurr = d;
165 for(unsigned ii=0;ii<(unsigned)IDELEMS(vv);ii++)
166 {
167 if(vv->m[ii] != NULL && !n_IsUnit(pGetCoeff(vv->m[ii]),currRing->cf))
168 {
169 ideal vc = idCopy(vv);
170 poly c = pInit();
171 pSetCoeff0(c,nCopy(pGetCoeff(vv->m[ii])));
172 idInsertPoly(vc,c);
174 for(unsigned jj = 0;jj<(unsigned)IDELEMS(vc)-1;jj++)
175 {
176 if((vc->m[jj]!=NULL)
177 && (n_DivBy(pGetCoeff(vc->m[jj]),pGetCoeff(c),currRing->cf)))
178 {
179 pDelete(&vc->m[jj]);
180 }
181 }
183 i = idPosConstant(vc);
184 if (i != -1) pDelete(&vc->m[i]);
185 dcurr = scDimInt(vc, Q);
186 // the following assumes the ground rings to be either zero- or one-dimensional
187 if((i==-1) && rField_is_Z(currRing))
188 {
189 // should also be activated for other euclidean domains as groundfield
190 dcurr++;
191 }
192 idDelete(&vc);
193 }
194 if(dcurr > d)
195 d = dcurr;
196 }
197 idDelete(&vv);
198 return d;
199 }
200#endif
201 return scDimInt(vid,Q);
202}
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition coeffs.h:757
int scDimInt(ideal S, ideal Q)
ideal dimension
Definition hdegree.cc:78
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
ideal idCopy(ideal A)
Definition ideals.h:60
#define idPosConstant(I)
index of generator with leading term in ground ring (if any); otherwise -1
Definition ideals.h:37
#define pSetCoeff0(p, n)
Definition monomials.h:59
#define nCopy(n)
Definition numbers.h:15
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:514

◆ scElKbase()

static void scElKbase ( )
static

Definition at line 1151 of file hdegree.cc.

1152{
1153 poly q = pInit();
1154 pSetCoeff0(q,nInit(1));
1155 pSetExpV(q,act);
1156 pNext(q) = NULL;
1157 last = pNext(last) = q;
1158}
#define pNext(p)
Definition monomials.h:36
#define nInit(i)
Definition numbers.h:24
#define pSetExpV(p, e)
Definition polys.h:97

◆ scIdKbase()

static ideal scIdKbase ( poly  q,
const int  rank 
)
static

Definition at line 1406 of file hdegree.cc.

1407{
1408 ideal res = idInit(pLength(q), rank);
1409 polyset mm = res->m;
1410 do
1411 {
1412 *mm = q; ++mm;
1413
1414 const poly p = pNext(q);
1415 pNext(q) = NULL;
1416 q = p;
1417
1418 } while (q!=NULL);
1419
1420 id_Test(res, currRing); // WRONG RANK!!!???
1421 return res;
1422}
static int pLength(poly a)
Definition p_polys.h:190
poly * polyset
Definition polys.h:259

◆ scIndIntvec()

intvec * scIndIntvec ( ideal  S,
ideal  Q 
)

Definition at line 286 of file hdegree.cc.

287{
288 id_Test(S, currRing);
289 if( Q!=NULL ) id_Test(Q, currRing);
290
291 intvec *Set=new intvec((currRing->N));
292 int mc,i;
293 hexist = hInit(S, Q, &hNexist);
294 if (hNexist==0)
295 {
296 for(i=0; i<(currRing->N); i++)
297 (*Set)[i]=1;
298 return Set;
299 }
300 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
301 hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
302 hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
303 hInd = (scmon)omAlloc0((1 + (currRing->N)) * sizeof(int));
304 mc = hisModule;
305 if (mc==0)
306 {
307 hrad = hexist;
308 hNrad = hNexist;
309 }
310 else
311 hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
312 radmem = hCreate((currRing->N) - 1);
313 hCo = (currRing->N) + 1;
314 loop
315 {
316 if (mc!=0)
317 hComp(hexist, hNexist, mc, hrad, &hNrad);
318 if (hNrad!=0)
319 {
320 hNvar = (currRing->N);
323 if (hNvar!=0)
324 {
325 memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
326 hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
329 }
330 }
331 else
332 {
333 hCo = 0;
334 break;
335 }
336 mc--;
337 if (mc <= 0)
338 break;
339 }
340 for(i=0; i<(currRing->N); i++)
341 (*Set)[i] = hInd[i+1];
342 hKill(radmem, (currRing->N) - 1);
343 omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
344 omFreeSize((ADDRESS)hInd, (1 + (currRing->N)) * sizeof(int));
345 omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
346 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
348 if (hisModule)
349 omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
350 return Set;
351}
#define omAlloc0(size)

◆ scInKbase()

static void scInKbase ( scfmon  stc,
int  Nstc,
int  Nvar 
)
static

Definition at line 1350 of file hdegree.cc.

1351{
1352 int Ivar, Istc, i, j;
1353 scfmon sn;
1354 int x, ideg;
1355
1356 if (Nvar == 1)
1357 {
1358 ideg = scMin(Nstc, stc, 1);
1359 while (ideg > 0)
1360 {
1361 ideg--;
1362 act[1] = ideg;
1363 scElKbase();
1364 }
1365 return;
1366 }
1367 Ivar = Nvar-1;
1368 sn = hGetmem(Nstc, stc, stcmem[Ivar]);
1369 x = scRestrict(Nstc, sn, Nvar);
1370 if (x == 0) return;
1371 ideg = x-1;
1372 loop
1373 {
1374 x = scMax(Nstc, sn, Nvar);
1375 while (ideg >= x)
1376 {
1377 act[Nvar] = ideg;
1378 scInKbase(sn, Nstc, Ivar);
1379 ideg--;
1380 }
1381 if (ideg < 0) return;
1382 Istc = Nstc;
1383 for (i=Nstc-1; i>=0; i--)
1384 {
1385 if (ideg < sn[i][Nvar])
1386 {
1387 Istc--;
1388 sn[i] = NULL;
1389 }
1390 }
1391 j = 0;
1392 while (sn[j]) j++;
1393 i = j+1;
1394 for (; i<Nstc; i++)
1395 {
1396 if (sn[i])
1397 {
1398 sn[j] = sn[i];
1399 j++;
1400 }
1401 }
1402 Nstc = Istc;
1403 }
1404}
static int scMin(int i, scfmon stc, int Nvar)
Definition hdegree.cc:1172
static void scInKbase(scfmon stc, int Nstc, int Nvar)
Definition hdegree.cc:1350

◆ scKBase()

ideal scKBase ( int  deg,
ideal  s,
ideal  Q,
intvec mv 
)

Definition at line 1424 of file hdegree.cc.

1425{
1426 if( Q!=NULL) id_Test(Q, currRing);
1427
1428 int i, di;
1429 poly p;
1430
1431 if (deg < 0)
1432 {
1433 di = scDimInt(s, Q);
1434 if (di != 0)
1435 {
1436 //Werror("KBase not finite");
1437 return idInit(1,s->rank);
1438 }
1439 }
1440 stcmem = hCreate((currRing->N) - 1);
1441 hexist = hInit(s, Q, &hNexist);
1442 p = last = pInit();
1443 /*pNext(p) = NULL;*/
1444 act = (scmon)omAlloc(((currRing->N) + 1) * sizeof(int));
1445 *act = 0;
1446 if (!hNexist)
1447 {
1448 scAll((currRing->N), deg);
1449 goto ende;
1450 }
1451 if (!hisModule)
1452 {
1453 if (deg < 0) scInKbase(hexist, hNexist, (currRing->N));
1454 else scDegKbase(hexist, hNexist, (currRing->N), deg);
1455 }
1456 else
1457 {
1458 hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
1459 for (i = 1; i <= hisModule; i++)
1460 {
1461 *act = i;
1463 int deg_ei=deg;
1464 if (mv!=NULL) deg_ei -= (*mv)[i-1];
1465 if ((deg < 0) || (deg_ei>=0))
1466 {
1467 if (hNstc)
1468 {
1469 if (deg < 0) scInKbase(hstc, hNstc, (currRing->N));
1470 else scDegKbase(hstc, hNstc, (currRing->N), deg_ei);
1471 }
1472 else
1473 scAll((currRing->N), deg_ei);
1474 }
1475 }
1476 omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
1477 }
1478ende:
1480 omFreeSize((ADDRESS)act, ((currRing->N) + 1) * sizeof(int));
1481 hKill(stcmem, (currRing->N) - 1);
1482 pLmFree(&p);
1483 if (p == NULL)
1484 return idInit(1,s->rank);
1485
1486 last = p;
1487 return scIdKbase(p, s->rank);
1488}
const CanonicalForm int s
Definition facAbsFact.cc:51
static ideal scIdKbase(poly q, const int rank)
Definition hdegree.cc:1406

◆ scMax()

static int scMax ( int  i,
scfmon  stc,
int  Nvar 
)
static

Definition at line 1160 of file hdegree.cc.

1161{
1162 int x, y=stc[0][Nvar];
1163 for (; i;)
1164 {
1165 i--;
1166 x = stc[i][Nvar];
1167 if (x > y) y = x;
1168 }
1169 return y;
1170}
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53

◆ scMin()

static int scMin ( int  i,
scfmon  stc,
int  Nvar 
)
static

Definition at line 1172 of file hdegree.cc.

1173{
1174 int x, y=stc[0][Nvar];
1175 for (; i;)
1176 {
1177 i--;
1178 x = stc[i][Nvar];
1179 if (x < y) y = x;
1180 }
1181 return y;
1182}

◆ scMult0Int()

long scMult0Int ( ideal  S,
ideal  Q 
)

Definition at line 926 of file hdegree.cc.

927{
929 if (Q!=NULL) id_LmTest(Q, currRing);
930
931 int mc;
932 hexist = hInit(S, Q, &hNexist);
933 if (!hNexist)
934 {
935 hMu = -1;
936 return -1;
937 }
938 else
939 hMu = 0;
940
941 const ring r = currRing;
942
943 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
944 hvar = (varset)omAlloc(((r->N) + 1) * sizeof(int));
945 hpur0 = (scmon)omAlloc((1 + ((r->N) * (r->N))) * sizeof(int));
946 mc = hisModule;
947 if (!mc)
948 {
949 hstc = hexist;
950 hNstc = hNexist;
951 }
952 else
953 hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
954 stcmem = hCreate((r->N) - 1);
955 loop
956 {
957 if (mc)
958 {
959 hComp(hexist, hNexist, mc, hstc, &hNstc);
960 if (!hNstc)
961 {
962 hMu = -1;
963 break;
964 }
965 }
966 hNvar = (r->N);
967 for (int i = hNvar; i; i--)
968 hvar[i] = i;
971 if ((hNvar == (r->N)) && (hNstc >= (r->N)))
972 {
973 if ((hNvar > 2) && (hNstc > 10))
975 memset(hpur0, 0, ((r->N) + 1) * sizeof(int));
976 hPure(hstc, 0, &hNstc, hvar, hNvar, hpur0, &hNpure);
977 if (hNpure == hNvar)
978 {
981 }
982 else
983 hMu = -1;
984 }
985 else if (hNvar)
986 hMu = -1;
987 mc--;
988 if (mc <= 0 || hMu < 0)
989 break;
990 }
991 hKill(stcmem, (r->N) - 1);
992 omFreeSize((ADDRESS)hpur0, (1 + ((r->N) * (r->N))) * sizeof(int));
993 omFreeSize((ADDRESS)hvar, ((r->N) + 1) * sizeof(int));
994 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
996 if (hisModule)
997 omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
998 return hMu;
999}

◆ scMultInt()

int scMultInt ( ideal  S,
ideal  Q 
)

Definition at line 903 of file hdegree.cc.

904{
905 id_Test(S, currRing);
906 if( Q!=NULL ) id_Test(Q, currRing);
907
908 hDegree(S, Q);
909 return hMu;
910}
static void hDegree(ideal S, ideal Q)
Definition hdegree.cc:802

◆ scPrintDegree()

void scPrintDegree ( int  co,
int  mu 
)

Definition at line 912 of file hdegree.cc.

913{
914 int di = (currRing->N)-co;
915 if (currRing->OrdSgn == 1)
916 {
917 if (di>0)
918 Print("// dimension (proj.) = %d\n// degree (proj.) = %d\n", di-1, mu);
919 else
920 Print("// dimension (affine) = 0\n// degree (affine) = %d\n", mu);
921 }
922 else
923 Print("// dimension (local) = %d\n// multiplicity = %d\n", di, mu);
924}
static matrix mu(matrix A, const ring R)
Definition matpol.cc:2025

◆ scRestrict()

static int scRestrict ( int Nstc,
scfmon  stc,
int  Nvar 
)
static

Definition at line 1184 of file hdegree.cc.

1185{
1186 int x, y;
1187 int i, j, Istc = Nstc;
1188
1189 y = MAX_INT_VAL;
1190 for (i=Nstc-1; i>=0; i--)
1191 {
1192 j = Nvar-1;
1193 loop
1194 {
1195 if(stc[i][j] != 0) break;
1196 j--;
1197 if (j == 0)
1198 {
1199 Istc--;
1200 x = stc[i][Nvar];
1201 if (x < y) y = x;
1202 stc[i] = NULL;
1203 break;
1204 }
1205 }
1206 }
1207 if (Istc < Nstc)
1208 {
1209 for (i=Nstc-1; i>=0; i--)
1210 {
1211 if (stc[i] && (stc[i][Nvar] >= y))
1212 {
1213 Istc--;
1214 stc[i] = NULL;
1215 }
1216 }
1217 j = 0;
1218 while (stc[j]) j++;
1219 i = j+1;
1220 for(; i<Nstc; i++)
1221 {
1222 if (stc[i])
1223 {
1224 stc[j] = stc[i];
1225 j++;
1226 }
1227 }
1228 Nstc = Istc;
1229 return y;
1230 }
1231 else
1232 return -1;
1233}
const int MAX_INT_VAL
Definition mylimits.h:12

◆ vvDeleteColumn()

static void vvDeleteColumn ( std::vector< std::vector< int > > &  mat,
int  col 
)
static

Definition at line 1995 of file hdegree.cc.

1996{
1997 for (int i = 0; i < mat.size(); i++)
1998 {
1999 mat[i].erase(mat[i].begin() + col);
2000 }
2001}

◆ vvDeleteRow()

static void vvDeleteRow ( std::vector< std::vector< int > > &  mat,
int  row 
)
static

Definition at line 1990 of file hdegree.cc.

1991{
1992 mat.erase(mat.begin() + row);
1993}

◆ vvIsColumnZero()

static BOOLEAN vvIsColumnZero ( const std::vector< std::vector< int > > &  mat,
int  col 
)
static

Definition at line 2013 of file hdegree.cc.

2014{
2015 for (int i = 0; i < mat.size(); i++)
2016 {
2017 if (mat[i][col] != 0)
2018 return FALSE;
2019 }
2020 return TRUE;
2021}

◆ vvIsRowZero()

static BOOLEAN vvIsRowZero ( const std::vector< std::vector< int > > &  mat,
int  row 
)
static

Definition at line 2003 of file hdegree.cc.

2004{
2005 for (int i = 0; i < mat[row].size(); i++)
2006 {
2007 if (mat[row][i] != 0)
2008 return FALSE;
2009 }
2010 return TRUE;
2011}

◆ vvIsZero()

static BOOLEAN vvIsZero ( const std::vector< std::vector< int > > &  mat)
static

Definition at line 2023 of file hdegree.cc.

2024{
2025 for (int i = 0; i < mat.size(); i++)
2026 {
2027 if (!vvIsRowZero(mat, i))
2028 return FALSE;
2029 }
2030 return TRUE;
2031}

◆ vvMult()

static std::vector< std::vector< int > > vvMult ( const std::vector< std::vector< int > > &  a,
const std::vector< std::vector< int > > &  b 
)
static

Definition at line 2033 of file hdegree.cc.

2034{
2035 int ra = a.size();
2036 int rb = b.size();
2037 int ca = a.size() > 0 ? a[0].size() : 0;
2038 int cb = b.size() > 0 ? b[0].size() : 0;
2039
2040 if (ca != rb)
2041 {
2042 WerrorS("matrix dimensions do not match");
2043 return std::vector<std::vector<int> >();
2044 }
2045
2046 std::vector<std::vector<int> > res(ra, std::vector<int>(cb));
2047 for (int i = 0; i < ra; i++)
2048 {
2049 for (int j = 0; j < cb; j++)
2050 {
2051 int sum = 0;
2052 for (int k = 0; k < ca; k++)
2053 sum += a[i][k] * b[k][j];
2054 res[i][j] = sum;
2055 }
2056 }
2057 return res;
2058}

◆ vvPrint()

static void vvPrint ( const std::vector< std::vector< int > > &  mat)
static

Definition at line 1965 of file hdegree.cc.

1966{
1967 for (int i = 0; i < mat.size(); i++)
1968 {
1969 for (int j = 0; j < mat[i].size(); j++)
1970 {
1971 Print("%d ", mat[i][j]);
1972 }
1973 PrintLn();
1974 }
1975}
void PrintLn()
Definition reporter.cc:310

◆ vvTest()

static void vvTest ( const std::vector< std::vector< int > > &  mat)
static

Definition at line 1977 of file hdegree.cc.

1978{
1979 if (mat.size() > 0)
1980 {
1981 int cols = mat[0].size();
1982 for (int i = 1; i < mat.size(); i++)
1983 {
1984 if (cols != mat[i].size())
1985 WerrorS("number of cols in matrix inconsistent");
1986 }
1987 }
1988}
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600

Variable Documentation

◆ act

Definition at line 1149 of file hdegree.cc.

◆ hCo

VAR int hCo

Definition at line 27 of file hdegree.cc.

◆ hInd

Definition at line 205 of file hdegree.cc.

◆ hMu

VAR long hMu

Definition at line 28 of file hdegree.cc.

◆ hMu2

VAR int hMu2

Definition at line 27 of file hdegree.cc.

◆ indlist_bin

VAR omBin indlist_bin = omGetSpecBin(sizeof(indlist))

Definition at line 29 of file hdegree.cc.

◆ ISet

VAR indset ISet

Definition at line 353 of file hdegree.cc.

◆ JSet

VAR indset JSet

Definition at line 353 of file hdegree.cc.

◆ last

STATIC_VAR poly last

Definition at line 1148 of file hdegree.cc.

◆ pWork

STATIC_VAR poly pWork

Definition at line 1003 of file hdegree.cc.