38 int dn, iv, rad0,
b, c,
x;
51 while(pure[var[iv]]) iv--;
52 hStepR(rad, Nrad, var, iv, &rad0);
60 hDimSolve(pn, Npure + 1, rn, rad0, var, iv);
63 hElimR(rn, &rad0,
b, c, var, iv);
64 hPure(rn,
b, &c, var, iv, pn, &
x);
71 hDimSolve(pure, Npure, rad, Nrad, var, iv);
165 for(
unsigned ii=0;ii<(unsigned)
IDELEMS(vv);ii++)
174 for(
unsigned jj = 0;jj<(unsigned)
IDELEMS(vc)-1;jj++)
210 int dn, iv, rad0,
b, c,
x;
247 while(pure[var[iv]]) iv--;
248 hStepR(rad, Nrad, var, iv, &rad0);
257 hIndSolve(pn, Npure + 1, rn, rad0, var, iv);
261 hElimR(rn, &rad0,
b, c, var, iv);
262 hPure(rn,
b, &c, var, iv, pn, &
x);
269 hIndSolve(pure, Npure, rad, Nrad, var, iv);
376 for (iv=(
currRing->N); iv!=0 ; iv--)
378 (*Set)[iv-1] = (pure[iv]==0);
387 int dn, iv, rad0,
b, c,
x;
400 for (iv = Nvar; iv!=0; iv--)
436 while(pure[var[iv]]) iv--;
437 hStepR(rad, Nrad, var, iv, &rad0);
444 hIndMult(pn, Npure + 1, rn, rad0, var, iv);
448 hElimR(rn, &rad0,
b, c, var, iv);
449 hPure(rn,
b, &c, var, iv, pn, &
x);
452 hIndMult(pn, Npure +
x, rn, rad0, var, iv);
456 hIndMult(pure, Npure, rad, Nrad, var, iv);
469 while (sm->nx !=
NULL)
475 if (((*Set)[iv-1] == 0) && (pure[iv] == 0))
496 while (sm->nx !=
NULL)
502 if ((pure[iv] == 1) && ((*Set)[iv-1] == 1))
558 (*Set)[iv-1] = (pure[iv]==0);
567 int dn, iv, rad0,
b, c,
x;
580 for (iv = Nvar; iv; iv--)
595 while(pure[var[iv]]) iv--;
596 hStepR(rad, Nrad, var, iv, &rad0);
607 hElimR(rn, &rad0,
b, c, var, iv);
608 hPure(rn,
b, &c, var, iv, pn, &
x);
623 int iv = Nvar -1, a, a0, a1,
b,
i;
633 for (
i = Nvar;
i;
i--)
640 hStepS(sn, Nstc, var, Nvar, &a, &
x);
644 return (
long)pure[var[Nvar]] *
hZeroMult(pn, sn, a, var, iv);
647 t *= pure[var[Nvar]];
648 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
660 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
669 hStepS(sn, Nstc, var, Nvar, &a, &
x);
670 hElimS(sn, &
b, a0, a, var, iv);
672 hPure(sn, a0, &a1, var, iv, pn, &
i);
678 sum += (long)(
x - x0) *
hZeroMult(pn, sn,
b, var, iv);
683 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
690 sum += (long)(pure[var[Nvar]] - x0) *
hZeroMult(pn, sn,
b, var, iv);
693 t *= (pure[var[Nvar]]-x0);
695 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
718 if ((i0 > 2) && (
i > 10))
729 int dn, iv, rad0,
b, c,
x;
742 for (iv = Nvar; iv; iv--)
778 while(pure[var[iv]]) iv--;
779 hStepR(rad, Nrad, var, iv, &rad0);
786 hDimMult(pn, Npure + 1, rn, rad0, var, iv);
790 hElimR(rn, &rad0,
b, c, var, iv);
791 hPure(rn,
b, &c, var, iv, pn, &
x);
794 hDimMult(pn, Npure +
x, rn, rad0, var, iv);
798 hDimMult(pure, Npure, rad, Nrad, var, iv);
918 Print(
"// dimension (proj.) = %d\n// degree (proj.) = %d\n", di-1,
mu);
920 Print(
"// dimension (affine) = 0\n// degree (affine) = %d\n",
mu);
923 Print(
"// dimension (local) = %d\n// multiplicity = %d\n", di,
mu);
941 if ((
l == 1) &&(
mu == 0))
999 memset(
hpur0, 0, ((r->N) + 1) *
sizeof(
int));
1012 if (mc <= 0 ||
hMu < 0)
1042 int Nstc,
varset var,
int Nvar,poly hEdge)
1044 int iv = Nvar -1,
k = var[Nvar], a, a0, a1,
b,
i;
1056 for (
i = Nvar;
i>0;
i--)
1064 hStepS(sn, Nstc, var, Nvar, &a, &
x);
1081 hStepS(sn, Nstc, var, Nvar, &a, &
x);
1082 hElimS(sn, &
b, a0, a, var, iv);
1084 hPure(sn, a0, &a1, var, iv, pn, &
i);
1126 printf(
"\nThis is HC:\n");
1127 for(
int ii=0;ii<=
idElem(S);ii++)
1187 int x,
y=stc[0][Nvar];
1199 int x,
y=stc[0][Nvar];
1212 int i,
j, Istc = Nstc;
1215 for (
i=Nstc-1;
i>=0;
i--)
1220 if(stc[
i][
j] != 0)
break;
1234 for (
i=Nstc-1;
i>=0;
i--)
1236 if (stc[
i] && (stc[
i][Nvar] >=
y))
1266 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1279 scAll(Nvar-1, deg-d);
1289 scAll(Nvar-1, deg-ideg);
1291 }
while (ideg >= 0);
1296 int Ivar, Istc,
i,
j;
1302 for (
i=Nstc-1;
i>=0;
i--)
1304 for (
j=Nvar;
j;
j--){
if(stc[
i][
j])
break; }
1307 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1313 for (
i=Nstc-1;
i>=0;
i--)
if(deg >= stc[
i][1])
return;
1328 if (deg <
x) ideg = deg;
1338 x =
scMax(Nstc, sn, Nvar);
1345 if (ideg < 0)
return;
1347 for (
i=Nstc-1;
i>=0;
i--)
1349 if (ideg < sn[
i][Nvar])
1377 int Ivar, Istc,
i,
j;
1383 ideg =
scMin(Nstc, stc, 1);
1399 x =
scMax(Nstc, sn, Nvar);
1406 if (ideg < 0)
return;
1408 for (
i=Nstc-1;
i>=0;
i--)
1410 if (ideg < sn[
i][Nvar])
1489 if (mv!=
NULL) deg_ei -= (*mv)[
i-1];
1490 if ((deg < 0) || (deg_ei>=0))
1610static 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)
1614 if (cache[
v] != -2)
return cache;
1620 for (
int w = 0;
w <
G->cols();
w++)
1632 cycles =
si_max(cycles, cache[
w]);
1636 int pathIndexOfW = -1;
1637 for (
int i = path.size() - 1;
i >= 0;
i--) {
1638 if (cyclic[path[
i]] == 1) {
1642 cyclic[path[
i]] =
TRUE;
1654 assume(pathIndexOfW != -1);
1655 for (
int i = path.size() - 1;
i >= pathIndexOfW;
i--) {
1656 cache =
countCycles(
G, path[
i], path, visited, cyclic, cache);
1657 if (cache[path[
i]] == -1)
1662 cycles =
si_max(cycles, cache[path[
i]] + 1);
1678 std::vector<int> path;
1679 std::vector<BOOLEAN> visited;
1680 std::vector<BOOLEAN> cyclic;
1681 std::vector<int> cache;
1682 visited.resize(n,
FALSE);
1683 cyclic.resize(n,
FALSE);
1684 cache.resize(n, -2);
1688 for (
int v = 0;
v < n;
v++)
1693 cycles =
si_max(cycles, cache[
v]);
1709 numberOfNormalWords = 0;
1715 numberOfNormalWords = 1;
1723 int numberOfNewNormalWords = 0;
1725 for (
int j = nVars - 1;
j >= 0;
j--)
1727 for (
int i =
last;
i >= 0;
i--)
1731 if (words->m[
i] !=
NULL)
1749 numberOfNewNormalWords++;
1757 numberOfNormalWords += numberOfNewNormalWords;
1773 ideal words =
idInit(maxElems);
1774 int last, numberOfNormalWords;
1791 for (
int i = 0;
i < upToLength;
i++)
1793 ideal words =
idInit(maxElems);
1794 int last, numberOfNormalWords;
1797 return numberOfNormalWords;
1809 WerrorS(
"Ufnarovski graph not implemented for l <= 0");
1816 int n =
IDELEMS(standardWords);
1818 for (
int i = 0;
i < n;
i++)
1820 for (
int j = 0;
j < n;
j++)
1822 poly
v = standardWords->m[
i];
1823 poly
w = standardWords->m[
j];
1826 bool overlap =
true;
1827 for (
int k = 1;
k <= (
l - 1) * lV;
k++)
1867 WerrorS(
"GK-Dim not implemented for rings");
1873 if (_G->m[
i] !=
NULL)
1877 WerrorS(
"GK-Dim not implemented for modules");
1882 WerrorS(
"GK-Dim not implemented for bi-modules");
1897 int ncGenCount =
currRing->LPncGenCount;
1898 if (lV - ncGenCount == 0)
1903 if (lV - ncGenCount == 1)
1908 if (lV - ncGenCount >= 2)
1924 WerrorS(
"GK-Dim not defined for 0-ring");
1934 int ncGenCount =
currRing->LPncGenCount;
1940 if (
IDELEMS(
G) == lV - ncGenCount - 1)
1945 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
1952 ideal standardWords;
1974 int rows =
M->rows();
1975 int cols =
M->cols();
1977 std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
1979 for (
int i = 0;
i < rows;
i++)
1981 for (
int j = 0;
j < cols;
j++)
1990static void vvPrint(
const std::vector<std::vector<int> >& mat)
1992 for (
int i = 0;
i < mat.size();
i++)
1994 for (
int j = 0;
j < mat[
i].size();
j++)
2002static void vvTest(
const std::vector<std::vector<int> >& mat)
2006 int cols = mat[0].size();
2007 for (
int i = 1;
i < mat.size();
i++)
2009 if (cols != mat[
i].
size())
2010 WerrorS(
"number of cols in matrix inconsistent");
2017 mat.erase(mat.begin() + row);
2022 for (
int i = 0;
i < mat.size();
i++)
2024 mat[
i].erase(mat[
i].begin() + col);
2030 for (
int i = 0;
i < mat[row].size();
i++)
2032 if (mat[row][
i] != 0)
2040 for (
int i = 0;
i < mat.size();
i++)
2042 if (mat[
i][col] != 0)
2050 for (
int i = 0;
i < mat.size();
i++)
2058static std::vector<std::vector<int> >
vvMult(
const std::vector<std::vector<int> >& a,
const std::vector<std::vector<int> >&
b)
2062 int ca = a.size() > 0 ? a[0].size() : 0;
2063 int cb =
b.size() > 0 ?
b[0].size() : 0;
2067 WerrorS(
"matrix dimensions do not match");
2068 return std::vector<std::vector<int> >();
2071 std::vector<std::vector<int> >
res(ra, std::vector<int>(cb));
2072 for (
int i = 0;
i < ra;
i++)
2074 for (
int j = 0;
j < cb;
j++)
2077 for (
int k = 0;
k < ca;
k++)
2078 sum += a[
i][
k] *
b[
k][
j];
2089 std::vector<int> path;
2090 std::vector<BOOLEAN> visited;
2091 std::vector<BOOLEAN> cyclic;
2092 std::vector<int> cache;
2093 visited.resize(n,
FALSE);
2094 cyclic.resize(n,
FALSE);
2095 cache.resize(n, -2);
2097 for (
int v = 0;
v < n;
v++)
2115 WerrorS(
"K-Dim not implemented for rings");
2121 if (_G->m[
i] !=
NULL)
2125 WerrorS(
"K-Dim not implemented for modules");
2130 WerrorS(
"K-Dim not implemented for bi-modules");
2149 int ncGenCount =
currRing->LPncGenCount;
2150 if (lV - ncGenCount == 0)
2155 if (lV - ncGenCount == 1)
2160 if (lV - ncGenCount >= 2)
2176 WerrorS(
"K-Dim not defined for 0-ring");
2182 Print(
"max deg: %ld\n", maxDeg);
2188 PrintS(
"Computing normal words normally...\n");
2192 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
2198 int ncGenCount =
currRing->LPncGenCount;
2202 return numberOfNormalWords;
2204 if (
IDELEMS(
G) == lV - ncGenCount - 1)
2209 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
2217 PrintS(
"Computing Ufnarovski graph...\n");
2219 ideal standardWords;
2234 Print(
"Ufnarovski graph is %dx%d.\n", UG->
rows(), UG->
cols());
2237 PrintS(
"Checking whether Ufnarovski graph is acyclic...\n");
2245 std::vector<std::vector<int> > vvUG =
iv2vv(UG);
2246 for (
int i = 0;
i < vvUG.size();
i++)
2256 Print(
"Simplified Ufnarovski graph to %dx%d.\n", (
int)vvUG.size(), (
int)vvUG.size());
2261 PrintS(
"Computing normal words via Ufnarovski graph...\n");
2262 std::vector<std::vector<int> > UGpower = vvUG;
2267 PrintS(
"Start count graph entries.\n");
2268 for (
int i = 0;
i < UGpower.size();
i++)
2270 for (
int j = 0;
j < UGpower[
i].size();
j++)
2272 numberOfNormalWords += UGpower[
i][
j];
2278 PrintS(
"Done count graph entries.\n");
2279 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
2283 PrintS(
"Start mat mult.\n");
2284 UGpower =
vvMult(UGpower, vvUG);
2286 PrintS(
"Done mat mult.\n");
2292 return numberOfNormalWords;
static int si_max(const int a, const int b)
static int si_min(const int a, const int b)
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.
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:...
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
const Variable & v
< [in] a sqrfree bivariate poly
void WerrorS(const char *s)
static long hZeroMult(scmon pure, scfmon stc, int Nstc, varset var, int Nvar)
static ideal lp_computeNormalWords(int length, ideal M)
void scComputeHC(ideal S, ideal Q, int ak, poly &hEdge)
static void hHedgeStep(scmon pure, scfmon stc, int Nstc, varset var, int Nvar, poly hEdge)
static void hDimMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
ideal scKBase(int deg, ideal s, ideal Q, intvec *mv)
int scDimIntRing(ideal vid, ideal Q)
scDimInt for ring-coefficients
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)
long scMult0Int(ideal S, ideal Q)
void hIndMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
static std::vector< std::vector< int > > vvMult(const std::vector< std::vector< int > > &a, const std::vector< std::vector< int > > &b)
static int scMin(int i, scfmon stc, int Nvar)
intvec * scIndIntvec(ideal S, ideal Q)
static void vvDeleteRow(std::vector< std::vector< int > > &mat, int row)
static indset hCheck2(indset sm, scmon pure)
static BOOLEAN hCheck1(indset sm, scmon pure)
static int graphGrowth(const intvec *G)
static BOOLEAN vvIsColumnZero(const std::vector< std::vector< int > > &mat, int col)
static void hDegree(ideal S, ideal Q)
static void vvDeleteColumn(std::vector< std::vector< int > > &mat, int col)
static BOOLEAN hNotZero(scfmon rad, int Nrad, varset var, int Nvar)
int lp_kDim(const ideal _G)
static void hHedge(poly hEdge)
static void hIndSolve(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
intvec * lp_ufnarovskiGraph(ideal G, ideal &standardWords)
static int scRestrict(int &Nstc, scfmon stc, int Nvar)
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 scAllKbase(int Nvar, int ideg, int deg)
static void scAll(int Nvar, int deg)
int scMultInt(ideal S, ideal Q)
static void scDegKbase(scfmon stc, int Nstc, int Nvar, int deg)
static void hCheckIndep(scmon pure)
void scPrintDegree(int co, int mu)
static int lp_countNormalWords(int upToLength, ideal M)
static BOOLEAN isAcyclic(const intvec *G)
static int scMax(int i, scfmon stc, int Nvar)
static ideal scIdKbase(poly q, const int rank)
static void hIndep(scmon pure)
static void scInKbase(scfmon stc, int Nstc, int Nvar)
static void hProject(scmon pure, varset sel)
void scDegree(ideal S, intvec *modulweight, ideal Q)
static BOOLEAN vvIsZero(const std::vector< std::vector< int > > &mat)
int scDimInt(ideal S, ideal Q)
ideal dimension
static BOOLEAN vvIsRowZero(const std::vector< std::vector< int > > &mat, int row)
static void _lp_computeNormalWords(ideal words, int &numberOfNormalWords, int length, ideal M, int minDeg, int &last)
void hDimSolve(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
void hIndAllMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
intvec * hSecondSeries(intvec *hseries1)
intvec * hFirstSeries(ideal A, intvec *module_w, ideal Q, intvec *wdegree)
void hDegreeSeries(intvec *s1, intvec *s2, int *co, int *mu)
void hComp(scfmon exist, int Nexist, int ak, scfmon stc, int *Nstc)
void hLex2S(scfmon rad, int e1, int a2, int e2, varset var, int Nvar, scfmon w)
void hKill(monf xmem, int Nvar)
void hElimS(scfmon stc, int *e1, int a2, int e2, varset var, int Nvar)
void hLexS(scfmon stc, int Nstc, varset var, int Nvar)
void hDelete(scfmon ev, int ev_length)
scfmon hGetmem(int lm, scfmon old, monp monmem)
void hPure(scfmon stc, int a, int *Nstc, varset var, int Nvar, scmon pure, int *Npure)
void hSupp(scfmon stc, int Nstc, varset var, int *Nvar)
void hLexR(scfmon rad, int Nrad, varset var, int Nvar)
void hStepR(scfmon rad, int Nrad, varset var, int Nvar, int *a)
void hLex2R(scfmon rad, int e1, int a2, int e2, varset var, int Nvar, scfmon w)
void hStepS(scfmon stc, int Nstc, varset var, int Nvar, int *a, int *x)
void hStaircase(scfmon stc, int *Nstc, varset var, int Nvar)
void hElimR(scfmon rad, int *e1, int a2, int e2, varset var, int Nvar)
void hOrdSupp(scfmon stc, int Nstc, varset var, int Nvar)
scfmon hInit(ideal S, ideal Q, int *Nexist)
void hRadical(scfmon rad, int *Nrad, int Nvar)
#define idDelete(H)
delete an ideal
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 id_Copy(ideal h1, const ring r)
copy an ideal
#define idPosConstant(I)
index of generator with leading term in ground ring (if any); otherwise -1
static BOOLEAN length(leftv result, leftv arg)
intvec * ivCopy(const intvec *o)
#define IMATELEM(M, I, J)
static matrix mu(matrix A, const ring R)
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
#define omFreeSize(addr, size)
#define omFreeBin(addr, bin)
#define omGetSpecBin(size)
static int index(p_Length length, p_Ord ord)
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
static int pLength(poly a)
static void p_Delete(poly *p, const ring r)
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Compatibility layer for legacy polynomial operations (over currRing)
static long pTotaldegree(poly p)
#define pGetComp(p)
Component.
#define pIsConstantComp(p)
return true if p is either NULL, or if all exponents of p are 0, Comp of p might be !...
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
#define pGetExp(p, i)
Exponent.
#define pInit()
allocates a new monomial and initializes everything to 0
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
#define pCopy(p)
return a copy of the poly
void PrintS(const char *s)
static BOOLEAN rField_is_Z(const ring r)
#define rField_is_Ring(R)
BOOLEAN p_LPDivisibleBy(poly a, poly b, const ring r)
poly p_LPVarAt(poly p, int pos, const ring r)
ideal idInit(int idsize, int rank)
initialise an ideal / module
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.
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static int idElem(const ideal F)
number of non-zero polys in F