37 int dn, iv, rad0,
b, c,
x;
50 while(pure[var[iv]]) iv--;
51 hStepR(rad, Nrad, var, iv, &rad0);
59 hDimSolve(pn, Npure + 1, rn, rad0, var, iv);
62 hElimR(rn, &rad0,
b, c, var, iv);
63 hPure(rn,
b, &c, var, iv, pn, &
x);
70 hDimSolve(pure, Npure, rad, Nrad, var, iv);
164 for(
unsigned ii=0;ii<(unsigned)
IDELEMS(vv);ii++)
173 for(
unsigned jj = 0;jj<(unsigned)
IDELEMS(vc)-1;jj++)
209 int dn, iv, rad0,
b, c,
x;
246 while(pure[var[iv]]) iv--;
247 hStepR(rad, Nrad, var, iv, &rad0);
256 hIndSolve(pn, Npure + 1, rn, rad0, var, iv);
260 hElimR(rn, &rad0,
b, c, var, iv);
261 hPure(rn,
b, &c, var, iv, pn, &
x);
268 hIndSolve(pure, Npure, rad, Nrad, var, iv);
375 for (iv=(
currRing->N); iv!=0 ; iv--)
389 int dn, iv, rad0,
b, c,
x;
402 for (iv = Nvar; iv!=0; iv--)
438 while(pure[var[iv]]) iv--;
439 hStepR(rad, Nrad, var, iv, &rad0);
446 hIndMult(pn, Npure + 1, rn, rad0, var, iv);
450 hElimR(rn, &rad0,
b, c, var, iv);
451 hPure(rn,
b, &c, var, iv, pn, &
x);
454 hIndMult(pn, Npure +
x, rn, rad0, var, iv);
458 hIndMult(pure, Npure, rad, Nrad, var, iv);
471 while (sm->nx !=
NULL)
477 if (((*Set)[iv-1] == 0) && (pure[iv] == 0))
498 while (sm->nx !=
NULL)
504 if ((pure[iv] == 1) && ((*Set)[iv-1] == 1))
572 int dn, iv, rad0,
b, c,
x;
585 for (iv = Nvar; iv; iv--)
600 while(pure[var[iv]]) iv--;
601 hStepR(rad, Nrad, var, iv, &rad0);
612 hElimR(rn, &rad0,
b, c, var, iv);
613 hPure(rn,
b, &c, var, iv, pn, &
x);
628 int iv = Nvar -1, sum, a, a0, a1,
b,
i;
637 for (
i = Nvar;
i;
i--)
644 hStepS(sn, Nstc, var, Nvar, &a, &
x);
646 return pure[var[Nvar]] *
hZeroMult(pn, sn, a, var, iv);
654 hStepS(sn, Nstc, var, Nvar, &a, &
x);
655 hElimS(sn, &
b, a0, a, var, iv);
657 hPure(sn, a0, &a1, var, iv, pn, &
i);
666 sum += (pure[var[Nvar]] - x0) *
hZeroMult(pn, sn,
b, var, iv);
687 if ((i0 > 2) && (
i > 10))
698 int dn, iv, rad0,
b, c,
x;
711 for (iv = Nvar; iv; iv--)
747 while(pure[var[iv]]) iv--;
748 hStepR(rad, Nrad, var, iv, &rad0);
755 hDimMult(pn, Npure + 1, rn, rad0, var, iv);
759 hElimR(rn, &rad0,
b, c, var, iv);
760 hPure(rn,
b, &c, var, iv, pn, &
x);
763 hDimMult(pn, Npure +
x, rn, rad0, var, iv);
767 hDimMult(pure, Npure, rad, Nrad, var, iv);
887 Print(
"// dimension (proj.) = %d\n// degree (proj.) = %d\n", di-1,
mu);
889 Print(
"// dimension (affine) = 0\n// degree (affine) = %d\n",
mu);
892 Print(
"// dimension (local) = %d\n// multiplicity = %d\n", di,
mu);
909 if ((
l == 1) &&(
mu == 0))
918static void hDegree0(ideal S, ideal
Q,
const ring tailRing)
967 memset(
hpur0, 0, ((r->N) + 1) *
sizeof(
int));
980 if (mc <= 0 ||
hMu < 0)
1019 int Nstc,
varset var,
int Nvar,poly hEdge)
1021 int iv = Nvar -1,
k = var[Nvar], a, a0, a1,
b,
i;
1033 for (
i = Nvar;
i>0;
i--)
1041 hStepS(sn, Nstc, var, Nvar, &a, &
x);
1058 hStepS(sn, Nstc, var, Nvar, &a, &
x);
1059 hElimS(sn, &
b, a0, a, var, iv);
1061 hPure(sn, a0, &a1, var, iv, pn, &
i);
1103 printf(
"\nThis is HC:\n");
1104 for(
int ii=0;ii<=
idElem(S);ii++)
1164 int x,
y=stc[0][Nvar];
1176 int x,
y=stc[0][Nvar];
1189 int i,
j, Istc = Nstc;
1192 for (
i=Nstc-1;
i>=0;
i--)
1197 if(stc[
i][
j] != 0)
break;
1211 for (
i=Nstc-1;
i>=0;
i--)
1213 if (stc[
i] && (stc[
i][Nvar] >=
y))
1243 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1256 scAll(Nvar-1, deg-d);
1266 scAll(Nvar-1, deg-ideg);
1268 }
while (ideg >= 0);
1273 int Ivar, Istc,
i,
j;
1279 for (
i=Nstc-1;
i>=0;
i--)
1281 for (
j=Nvar;
j;
j--){
if(stc[
i][
j])
break; }
1284 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1290 for (
i=Nstc-1;
i>=0;
i--)
if(deg >= stc[
i][1])
return;
1305 if (deg <
x) ideg = deg;
1315 x =
scMax(Nstc, sn, Nvar);
1322 if (ideg < 0)
return;
1324 for (
i=Nstc-1;
i>=0;
i--)
1326 if (ideg < sn[
i][Nvar])
1354 int Ivar, Istc,
i,
j;
1360 ideg =
scMin(Nstc, stc, 1);
1376 x =
scMax(Nstc, sn, Nvar);
1383 if (ideg < 0)
return;
1385 for (
i=Nstc-1;
i>=0;
i--)
1387 if (ideg < sn[
i][Nvar])
1466 if (mv!=
NULL) deg_ei -= (*mv)[
i-1];
1467 if ((deg < 0) || (deg_ei>=0))
1587static 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)
1591 if (cache[
v] != -2)
return cache;
1597 for (
int w = 0;
w <
G->cols();
w++)
1609 cycles =
si_max(cycles, cache[
w]);
1613 int pathIndexOfW = -1;
1614 for (
int i = path.size() - 1;
i >= 0;
i--) {
1615 if (cyclic[path[
i]] == 1) {
1619 cyclic[path[
i]] =
TRUE;
1631 assume(pathIndexOfW != -1);
1632 for (
int i = path.size() - 1;
i >= pathIndexOfW;
i--) {
1633 cache =
countCycles(
G, path[
i], path, visited, cyclic, cache);
1634 if (cache[path[
i]] == -1)
1639 cycles =
si_max(cycles, cache[path[
i]] + 1);
1655 std::vector<int> path;
1656 std::vector<BOOLEAN> visited;
1657 std::vector<BOOLEAN> cyclic;
1658 std::vector<int> cache;
1659 visited.resize(n,
FALSE);
1660 cyclic.resize(n,
FALSE);
1661 cache.resize(n, -2);
1665 for (
int v = 0;
v < n;
v++)
1670 cycles =
si_max(cycles, cache[
v]);
1686 numberOfNormalWords = 0;
1692 numberOfNormalWords = 1;
1700 int numberOfNewNormalWords = 0;
1702 for (
int j = nVars - 1;
j >= 0;
j--)
1704 for (
int i =
last;
i >= 0;
i--)
1708 if (words->m[
i] !=
NULL)
1726 numberOfNewNormalWords++;
1734 numberOfNormalWords += numberOfNewNormalWords;
1750 ideal words =
idInit(maxElems);
1751 int last, numberOfNormalWords;
1768 for (
int i = 0;
i < upToLength;
i++)
1770 ideal words =
idInit(maxElems);
1771 int last, numberOfNormalWords;
1774 return numberOfNormalWords;
1786 WerrorS(
"Ufnarovski graph not implemented for l <= 0");
1793 int n =
IDELEMS(standardWords);
1795 for (
int i = 0;
i < n;
i++)
1797 for (
int j = 0;
j < n;
j++)
1799 poly
v = standardWords->m[
i];
1800 poly
w = standardWords->m[
j];
1803 bool overlap =
true;
1804 for (
int k = 1;
k <= (
l - 1) * lV;
k++)
1844 WerrorS(
"GK-Dim not implemented for rings");
1850 if (_G->m[
i] !=
NULL)
1854 WerrorS(
"GK-Dim not implemented for modules");
1859 WerrorS(
"GK-Dim not implemented for bi-modules");
1874 int ncGenCount =
currRing->LPncGenCount;
1875 if (lV - ncGenCount == 0)
1880 if (lV - ncGenCount == 1)
1885 if (lV - ncGenCount >= 2)
1901 WerrorS(
"GK-Dim not defined for 0-ring");
1911 int ncGenCount =
currRing->LPncGenCount;
1917 if (
IDELEMS(
G) == lV - ncGenCount - 1)
1922 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
1929 ideal standardWords;
1951 int rows =
M->rows();
1952 int cols =
M->cols();
1954 std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
1956 for (
int i = 0;
i < rows;
i++)
1958 for (
int j = 0;
j < cols;
j++)
1967static void vvPrint(
const std::vector<std::vector<int> >& mat)
1969 for (
int i = 0;
i < mat.size();
i++)
1971 for (
int j = 0;
j < mat[
i].size();
j++)
1979static void vvTest(
const std::vector<std::vector<int> >& mat)
1983 int cols = mat[0].size();
1984 for (
int i = 1;
i < mat.size();
i++)
1986 if (cols != mat[
i].
size())
1987 WerrorS(
"number of cols in matrix inconsistent");
1994 mat.erase(mat.begin() + row);
1999 for (
int i = 0;
i < mat.size();
i++)
2001 mat[
i].erase(mat[
i].begin() + col);
2007 for (
int i = 0;
i < mat[row].size();
i++)
2009 if (mat[row][
i] != 0)
2017 for (
int i = 0;
i < mat.size();
i++)
2019 if (mat[
i][col] != 0)
2027 for (
int i = 0;
i < mat.size();
i++)
2035static std::vector<std::vector<int> >
vvMult(
const std::vector<std::vector<int> >& a,
const std::vector<std::vector<int> >&
b)
2039 int ca = a.size() > 0 ? a[0].size() : 0;
2040 int cb =
b.size() > 0 ?
b[0].size() : 0;
2044 WerrorS(
"matrix dimensions do not match");
2045 return std::vector<std::vector<int> >();
2048 std::vector<std::vector<int> >
res(ra, std::vector<int>(cb));
2049 for (
int i = 0;
i < ra;
i++)
2051 for (
int j = 0;
j < cb;
j++)
2054 for (
int k = 0;
k < ca;
k++)
2055 sum += a[
i][
k] *
b[
k][
j];
2066 std::vector<int> path;
2067 std::vector<BOOLEAN> visited;
2068 std::vector<BOOLEAN> cyclic;
2069 std::vector<int> cache;
2070 visited.resize(n,
FALSE);
2071 cyclic.resize(n,
FALSE);
2072 cache.resize(n, -2);
2074 for (
int v = 0;
v < n;
v++)
2092 WerrorS(
"K-Dim not implemented for rings");
2098 if (_G->m[
i] !=
NULL)
2102 WerrorS(
"K-Dim not implemented for modules");
2107 WerrorS(
"K-Dim not implemented for bi-modules");
2126 int ncGenCount =
currRing->LPncGenCount;
2127 if (lV - ncGenCount == 0)
2132 if (lV - ncGenCount == 1)
2137 if (lV - ncGenCount >= 2)
2153 WerrorS(
"K-Dim not defined for 0-ring");
2159 Print(
"max deg: %ld\n", maxDeg);
2165 PrintS(
"Computing normal words normally...\n");
2169 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
2175 int ncGenCount =
currRing->LPncGenCount;
2179 return numberOfNormalWords;
2181 if (
IDELEMS(
G) == lV - ncGenCount - 1)
2186 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
2194 PrintS(
"Computing Ufnarovski graph...\n");
2196 ideal standardWords;
2211 Print(
"Ufnarovski graph is %dx%d.\n", UG->
rows(), UG->
cols());
2214 PrintS(
"Checking whether Ufnarovski graph is acyclic...\n");
2222 std::vector<std::vector<int> > vvUG =
iv2vv(UG);
2223 for (
int i = 0;
i < vvUG.size();
i++)
2233 Print(
"Simplified Ufnarovski graph to %dx%d.\n", (
int)vvUG.size(), (
int)vvUG.size());
2238 PrintS(
"Computing normal words via Ufnarovski graph...\n");
2239 std::vector<std::vector<int> > UGpower = vvUG;
2244 PrintS(
"Start count graph entries.\n");
2245 for (
int i = 0;
i < UGpower.size();
i++)
2247 for (
int j = 0;
j < UGpower[
i].size();
j++)
2249 numberOfNormalWords += UGpower[
i][
j];
2255 PrintS(
"Done count graph entries.\n");
2256 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
2260 PrintS(
"Start mat mult.\n");
2261 UGpower =
vvMult(UGpower, vvUG);
2263 PrintS(
"Done mat mult.\n");
2269 return numberOfNormalWords;
static int si_max(const int a, const int b)
static int si_min(const int a, const int b)
void mu(int **points, int sizePoints)
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)
int scMult0Int(ideal S, ideal Q, const ring tailRing)
static ideal lp_computeNormalWords(int length, ideal M)
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)
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)
void scComputeHC(ideal S, ideal Q, int ak, poly &hEdge, ring tailRing)
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 hDegree0(ideal S, ideal Q, const ring tailRing)
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 int hZeroMult(scmon pure, scfmon stc, int Nstc, varset var, int Nvar)
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 S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
void hDegreeSeries(intvec *s1, intvec *s2, int *co, int *mu)
void hComp(scfmon exist, int Nexist, int ak, scfmon stc, int *Nstc)
scfmon hInit(ideal S, ideal Q, int *Nexist, ring tailRing)
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)
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 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 void p_Delete(poly *p, const ring r)
static unsigned pLength(poly a)
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Compatiblity 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_Ring(const ring r)
static BOOLEAN rField_is_Z(const 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
int idElem(const ideal F)
count non-zero elements
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
#define id_TestTail(A, lR, tR)