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);
164 for(
unsigned ii=0;ii<(unsigned)
IDELEMS(vv);ii++)
173 for(
unsigned jj = 0;jj<(unsigned)
IDELEMS(vc)-1;jj++)
208 int dn, iv, rad0,
b, c,
x;
245 while(pure[var[iv]]) iv--;
246 hStepR(rad, Nrad, var, iv, &rad0);
255 hIndSolve(pn, Npure + 1, rn, rad0, var, iv);
259 hElimR(rn, &rad0,
b, c, var, iv);
260 hPure(rn,
b, &c, var, iv, pn, &
x);
267 hIndSolve(pure, Npure, rad, Nrad, var, iv);
374 for (iv=(
currRing->N); iv!=0 ; iv--)
376 (*Set)[iv-1] = (pure[iv]==0);
385 int dn, iv, rad0,
b, c,
x;
398 for (iv = Nvar; iv!=0; iv--)
434 while(pure[var[iv]]) iv--;
435 hStepR(rad, Nrad, var, iv, &rad0);
442 hIndMult(pn, Npure + 1, rn, rad0, var, iv);
446 hElimR(rn, &rad0,
b, c, var, iv);
447 hPure(rn,
b, &c, var, iv, pn, &
x);
450 hIndMult(pn, Npure +
x, rn, rad0, var, iv);
454 hIndMult(pure, Npure, rad, Nrad, var, iv);
467 while (sm->nx !=
NULL)
473 if (((*Set)[iv-1] == 0) && (pure[iv] == 0))
494 while (sm->nx !=
NULL)
500 if ((pure[iv] == 1) && ((*Set)[iv-1] == 1))
556 (*Set)[iv-1] = (pure[iv]==0);
565 int dn, iv, rad0,
b, c,
x;
578 for (iv = Nvar; iv; iv--)
593 while(pure[var[iv]]) iv--;
594 hStepR(rad, Nrad, var, iv, &rad0);
605 hElimR(rn, &rad0,
b, c, var, iv);
606 hPure(rn,
b, &c, var, iv, pn, &
x);
621 int iv = Nvar -1, a, a0, a1,
b,
i;
631 for (
i = Nvar;
i;
i--)
638 hStepS(sn, Nstc, var, Nvar, &a, &
x);
642 return (
long)pure[var[Nvar]] *
hZeroMult(pn, sn, a, var, iv);
645 t *= pure[var[Nvar]];
646 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
658 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
667 hStepS(sn, Nstc, var, Nvar, &a, &
x);
668 hElimS(sn, &
b, a0, a, var, iv);
670 hPure(sn, a0, &a1, var, iv, pn, &
i);
676 sum += (long)(
x - x0) *
hZeroMult(pn, sn,
b, var, iv);
681 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
688 sum += (long)(pure[var[Nvar]] - x0) *
hZeroMult(pn, sn,
b, var, iv);
691 t *= (pure[var[Nvar]]-x0);
693 if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
716 if ((i0 > 2) && (
i > 10))
727 int dn, iv, rad0,
b, c,
x;
740 for (iv = Nvar; iv; iv--)
776 while(pure[var[iv]]) iv--;
777 hStepR(rad, Nrad, var, iv, &rad0);
784 hDimMult(pn, Npure + 1, rn, rad0, var, iv);
788 hElimR(rn, &rad0,
b, c, var, iv);
789 hPure(rn,
b, &c, var, iv, pn, &
x);
792 hDimMult(pn, Npure +
x, rn, rad0, var, iv);
796 hDimMult(pure, Npure, rad, Nrad, var, iv);
916 Print(
"// dimension (proj.) = %d\n// degree (proj.) = %d\n", di-1,
mu);
918 Print(
"// dimension (affine) = 0\n// degree (affine) = %d\n",
mu);
921 Print(
"// dimension (local) = %d\n// multiplicity = %d\n", di,
mu);
973 memset(
hpur0, 0, ((r->N) + 1) *
sizeof(
int));
986 if (mc <= 0 ||
hMu < 0)
1015 int Nstc,
varset var,
int Nvar,poly hEdge)
1017 int iv = Nvar -1,
k = var[Nvar], a, a0, a1,
b,
i;
1029 for (
i = Nvar;
i>0;
i--)
1037 hStepS(sn, Nstc, var, Nvar, &a, &
x);
1054 hStepS(sn, Nstc, var, Nvar, &a, &
x);
1055 hElimS(sn, &
b, a0, a, var, iv);
1057 hPure(sn, a0, &a1, var, iv, pn, &
i);
1151 int x,
y=stc[0][Nvar];
1163 int x,
y=stc[0][Nvar];
1176 int i,
j, Istc = Nstc;
1179 for (
i=Nstc-1;
i>=0;
i--)
1184 if(stc[
i][
j] != 0)
break;
1198 for (
i=Nstc-1;
i>=0;
i--)
1200 if (stc[
i] && (stc[
i][Nvar] >=
y))
1230 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1243 scAll(Nvar-1, deg-d);
1253 scAll(Nvar-1, deg-ideg);
1255 }
while (ideg >= 0);
1260 int Ivar, Istc,
i,
j;
1266 for (
i=Nstc-1;
i>=0;
i--)
1268 for (
j=Nvar;
j;
j--){
if(stc[
i][
j])
break; }
1271 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1277 for (
i=Nstc-1;
i>=0;
i--)
if(deg >= stc[
i][1])
return;
1292 if (deg <
x) ideg = deg;
1302 x =
scMax(Nstc, sn, Nvar);
1309 if (ideg < 0)
return;
1311 for (
i=Nstc-1;
i>=0;
i--)
1313 if (ideg < sn[
i][Nvar])
1341 int Ivar, Istc,
i,
j;
1347 ideg =
scMin(Nstc, stc, 1);
1363 x =
scMax(Nstc, sn, Nvar);
1370 if (ideg < 0)
return;
1372 for (
i=Nstc-1;
i>=0;
i--)
1374 if (ideg < sn[
i][Nvar])
1453 if (mv!=
NULL) deg_ei -= (*mv)[
i-1];
1454 if ((deg < 0) || (deg_ei>=0))
1574static 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)
1578 if (cache[
v] != -2)
return cache;
1584 for (
int w = 0;
w <
G->cols();
w++)
1596 cycles =
si_max(cycles, cache[
w]);
1600 int pathIndexOfW = -1;
1601 for (
int i = path.size() - 1;
i >= 0;
i--) {
1602 if (cyclic[path[
i]] == 1) {
1606 cyclic[path[
i]] =
TRUE;
1618 assume(pathIndexOfW != -1);
1619 for (
int i = path.size() - 1;
i >= pathIndexOfW;
i--) {
1620 cache =
countCycles(
G, path[
i], path, visited, cyclic, cache);
1621 if (cache[path[
i]] == -1)
1626 cycles =
si_max(cycles, cache[path[
i]] + 1);
1642 std::vector<int> path;
1643 std::vector<BOOLEAN> visited;
1644 std::vector<BOOLEAN> cyclic;
1645 std::vector<int> cache;
1646 visited.resize(n,
FALSE);
1647 cyclic.resize(n,
FALSE);
1648 cache.resize(n, -2);
1652 for (
int v = 0;
v < n;
v++)
1657 cycles =
si_max(cycles, cache[
v]);
1673 numberOfNormalWords = 0;
1679 numberOfNormalWords = 1;
1687 int numberOfNewNormalWords = 0;
1689 for (
int j = nVars - 1;
j >= 0;
j--)
1691 for (
int i =
last;
i >= 0;
i--)
1695 if (words->m[
i] !=
NULL)
1713 numberOfNewNormalWords++;
1721 numberOfNormalWords += numberOfNewNormalWords;
1737 ideal words =
idInit(maxElems);
1738 int last, numberOfNormalWords;
1755 for (
int i = 0;
i < upToLength;
i++)
1757 ideal words =
idInit(maxElems);
1758 int last, numberOfNormalWords;
1761 return numberOfNormalWords;
1773 WerrorS(
"Ufnarovski graph not implemented for l <= 0");
1780 int n =
IDELEMS(standardWords);
1782 for (
int i = 0;
i < n;
i++)
1784 for (
int j = 0;
j < n;
j++)
1786 poly
v = standardWords->m[
i];
1787 poly
w = standardWords->m[
j];
1790 bool overlap =
true;
1791 for (
int k = 1;
k <= (
l - 1) * lV;
k++)
1831 WerrorS(
"GK-Dim not implemented for rings");
1837 if (_G->m[
i] !=
NULL)
1841 WerrorS(
"GK-Dim not implemented for modules");
1846 WerrorS(
"GK-Dim not implemented for bi-modules");
1861 int ncGenCount =
currRing->LPncGenCount;
1862 if (lV - ncGenCount == 0)
1867 if (lV - ncGenCount == 1)
1872 if (lV - ncGenCount >= 2)
1888 WerrorS(
"GK-Dim not defined for 0-ring");
1898 int ncGenCount =
currRing->LPncGenCount;
1904 if (
IDELEMS(
G) == lV - ncGenCount - 1)
1909 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
1916 ideal standardWords;
1938 int rows =
M->rows();
1939 int cols =
M->cols();
1941 std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
1943 for (
int i = 0;
i < rows;
i++)
1945 for (
int j = 0;
j < cols;
j++)
1955static void vvPrint(
const std::vector<std::vector<int> >& mat)
1957 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat.size();
i++)
1959 for (std::vector<std::vector<int> >::size_type
j = 0;
j < mat[
i].size();
j++)
1969static void vvTest(
const std::vector<std::vector<int> >& mat)
1973 std::vector<std::vector<int> >::size_type cols = mat[0].size();
1974 for (std::vector<std::vector<int> >::size_type
i = 1;
i < mat.size();
i++)
1976 if (cols != mat[
i].
size())
1977 WerrorS(
"number of cols in matrix inconsistent");
1985 mat.erase(mat.begin() + row);
1990 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat.size();
i++)
1992 mat[
i].erase(mat[
i].begin() + col);
1998 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat[row].size();
i++)
2000 if (mat[row][
i] != 0)
2008 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat.size();
i++)
2010 if (mat[
i][col] != 0)
2018 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat.size();
i++)
2026static std::vector<std::vector<int> >
vvMult(
const std::vector<std::vector<int> >& a,
const std::vector<std::vector<int> >&
b)
2028 std::vector<std::vector<int> >::size_type ra = a.size();
2029 std::vector<std::vector<int> >::size_type rb =
b.size();
2030 std::vector<std::vector<int> >::size_type ca = a.size() > 0 ? a[0].size() : 0;
2031 std::vector<std::vector<int> >::size_type cb =
b.size() > 0 ?
b[0].size() : 0;
2035 WerrorS(
"matrix dimensions do not match");
2036 return std::vector<std::vector<int> >();
2039 std::vector<std::vector<int> >
res(ra, std::vector<int>(cb));
2040 for (std::vector<std::vector<int> >::size_type
i = 0;
i < ra;
i++)
2042 for (std::vector<std::vector<int> >::size_type
j = 0;
j < cb;
j++)
2045 for (std::vector<std::vector<int> >::size_type
k = 0;
k < ca;
k++)
2046 sum += a[
i][
k] *
b[
k][
j];
2057 std::vector<int> path;
2058 std::vector<BOOLEAN> visited;
2059 std::vector<BOOLEAN> cyclic;
2060 std::vector<int> cache;
2061 visited.resize(n,
FALSE);
2062 cyclic.resize(n,
FALSE);
2063 cache.resize(n, -2);
2065 for (
int v = 0;
v < n;
v++)
2083 WerrorS(
"K-Dim not implemented for rings");
2089 if (_G->m[
i] !=
NULL)
2093 WerrorS(
"K-Dim not implemented for modules");
2098 WerrorS(
"K-Dim not implemented for bi-modules");
2117 int ncGenCount =
currRing->LPncGenCount;
2118 if (lV - ncGenCount == 0)
2123 if (lV - ncGenCount == 1)
2128 if (lV - ncGenCount >= 2)
2144 WerrorS(
"K-Dim not defined for 0-ring");
2150 Print(
"max deg: %ld\n", maxDeg);
2156 PrintS(
"Computing normal words normally...\n");
2160 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
2166 int ncGenCount =
currRing->LPncGenCount;
2170 return numberOfNormalWords;
2172 if (
IDELEMS(
G) == lV - ncGenCount - 1)
2177 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
2185 PrintS(
"Computing Ufnarovski graph...\n");
2187 ideal standardWords;
2202 Print(
"Ufnarovski graph is %dx%d.\n", UG->
rows(), UG->
cols());
2205 PrintS(
"Checking whether Ufnarovski graph is acyclic...\n");
2213 std::vector<std::vector<int> > vvUG =
iv2vv(UG);
2214 for (std::vector<std::vector<int> >::size_type
i = 0;
i < vvUG.size();
i++)
2224 Print(
"Simplified Ufnarovski graph to %dx%d.\n", (
int)vvUG.size(), (
int)vvUG.size());
2229 PrintS(
"Computing normal words via Ufnarovski graph...\n");
2230 std::vector<std::vector<int> > UGpower = vvUG;
2235 PrintS(
"Start count graph entries.\n");
2236 for (std::vector<std::vector<int> >::size_type
i = 0;
i < UGpower.size();
i++)
2238 for (std::vector<std::vector<int> >::size_type
j = 0;
j < UGpower[
i].size();
j++)
2240 numberOfNormalWords += UGpower[
i][
j];
2246 PrintS(
"Done count graph entries.\n");
2247 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
2251 PrintS(
"Start mat mult.\n");
2252 UGpower =
vvMult(UGpower, vvUG);
2254 PrintS(
"Done mat mult.\n");
2260 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 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)
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)
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