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);
1098 printf(
"\nThis is HC:\n");
1099 for(
int ii=0;ii<=
idElem(S);ii++)
1158 int x,
y=stc[0][Nvar];
1170 int x,
y=stc[0][Nvar];
1183 int i,
j, Istc = Nstc;
1186 for (
i=Nstc-1;
i>=0;
i--)
1191 if(stc[
i][
j] != 0)
break;
1205 for (
i=Nstc-1;
i>=0;
i--)
1207 if (stc[
i] && (stc[
i][Nvar] >=
y))
1237 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1250 scAll(Nvar-1, deg-d);
1260 scAll(Nvar-1, deg-ideg);
1262 }
while (ideg >= 0);
1267 int Ivar, Istc,
i,
j;
1273 for (
i=Nstc-1;
i>=0;
i--)
1275 for (
j=Nvar;
j;
j--){
if(stc[
i][
j])
break; }
1278 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1284 for (
i=Nstc-1;
i>=0;
i--)
if(deg >= stc[
i][1])
return;
1299 if (deg <
x) ideg = deg;
1309 x =
scMax(Nstc, sn, Nvar);
1316 if (ideg < 0)
return;
1318 for (
i=Nstc-1;
i>=0;
i--)
1320 if (ideg < sn[
i][Nvar])
1348 int Ivar, Istc,
i,
j;
1354 ideg =
scMin(Nstc, stc, 1);
1370 x =
scMax(Nstc, sn, Nvar);
1377 if (ideg < 0)
return;
1379 for (
i=Nstc-1;
i>=0;
i--)
1381 if (ideg < sn[
i][Nvar])
1460 if (mv!=
NULL) deg_ei -= (*mv)[
i-1];
1461 if ((deg < 0) || (deg_ei>=0))
1581static 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)
1585 if (cache[
v] != -2)
return cache;
1591 for (
int w = 0;
w <
G->cols();
w++)
1603 cycles =
si_max(cycles, cache[
w]);
1607 int pathIndexOfW = -1;
1608 for (
int i = path.size() - 1;
i >= 0;
i--) {
1609 if (cyclic[path[
i]] == 1) {
1613 cyclic[path[
i]] =
TRUE;
1625 assume(pathIndexOfW != -1);
1626 for (
int i = path.size() - 1;
i >= pathIndexOfW;
i--) {
1627 cache =
countCycles(
G, path[
i], path, visited, cyclic, cache);
1628 if (cache[path[
i]] == -1)
1633 cycles =
si_max(cycles, cache[path[
i]] + 1);
1649 std::vector<int> path;
1650 std::vector<BOOLEAN> visited;
1651 std::vector<BOOLEAN> cyclic;
1652 std::vector<int> cache;
1653 visited.resize(n,
FALSE);
1654 cyclic.resize(n,
FALSE);
1655 cache.resize(n, -2);
1659 for (
int v = 0;
v < n;
v++)
1664 cycles =
si_max(cycles, cache[
v]);
1680 numberOfNormalWords = 0;
1686 numberOfNormalWords = 1;
1694 int numberOfNewNormalWords = 0;
1696 for (
int j = nVars - 1;
j >= 0;
j--)
1698 for (
int i =
last;
i >= 0;
i--)
1702 if (words->m[
i] !=
NULL)
1720 numberOfNewNormalWords++;
1728 numberOfNormalWords += numberOfNewNormalWords;
1744 ideal words =
idInit(maxElems);
1745 int last, numberOfNormalWords;
1762 for (
int i = 0;
i < upToLength;
i++)
1764 ideal words =
idInit(maxElems);
1765 int last, numberOfNormalWords;
1768 return numberOfNormalWords;
1780 WerrorS(
"Ufnarovski graph not implemented for l <= 0");
1787 int n =
IDELEMS(standardWords);
1789 for (
int i = 0;
i < n;
i++)
1791 for (
int j = 0;
j < n;
j++)
1793 poly
v = standardWords->m[
i];
1794 poly
w = standardWords->m[
j];
1797 bool overlap =
true;
1798 for (
int k = 1;
k <= (
l - 1) * lV;
k++)
1838 WerrorS(
"GK-Dim not implemented for rings");
1844 if (_G->m[
i] !=
NULL)
1848 WerrorS(
"GK-Dim not implemented for modules");
1853 WerrorS(
"GK-Dim not implemented for bi-modules");
1868 int ncGenCount =
currRing->LPncGenCount;
1869 if (lV - ncGenCount == 0)
1874 if (lV - ncGenCount == 1)
1879 if (lV - ncGenCount >= 2)
1895 WerrorS(
"GK-Dim not defined for 0-ring");
1905 int ncGenCount =
currRing->LPncGenCount;
1911 if (
IDELEMS(
G) == lV - ncGenCount - 1)
1916 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
1923 ideal standardWords;
1945 int rows =
M->rows();
1946 int cols =
M->cols();
1948 std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
1950 for (
int i = 0;
i < rows;
i++)
1952 for (
int j = 0;
j < cols;
j++)
1962static void vvPrint(
const std::vector<std::vector<int> >& mat)
1964 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat.size();
i++)
1966 for (std::vector<std::vector<int> >::size_type
j = 0;
j < mat[
i].size();
j++)
1976static void vvTest(
const std::vector<std::vector<int> >& mat)
1980 std::vector<std::vector<int> >::size_type cols = mat[0].size();
1981 for (std::vector<std::vector<int> >::size_type
i = 1;
i < mat.size();
i++)
1983 if (cols != mat[
i].
size())
1984 WerrorS(
"number of cols in matrix inconsistent");
1992 mat.erase(mat.begin() + row);
1997 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat.size();
i++)
1999 mat[
i].erase(mat[
i].begin() + col);
2005 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat[row].size();
i++)
2007 if (mat[row][
i] != 0)
2015 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat.size();
i++)
2017 if (mat[
i][col] != 0)
2025 for (std::vector<std::vector<int> >::size_type
i = 0;
i < mat.size();
i++)
2033static std::vector<std::vector<int> >
vvMult(
const std::vector<std::vector<int> >& a,
const std::vector<std::vector<int> >&
b)
2035 std::vector<std::vector<int> >::size_type ra = a.size();
2036 std::vector<std::vector<int> >::size_type rb =
b.size();
2037 std::vector<std::vector<int> >::size_type ca = a.size() > 0 ? a[0].size() : 0;
2038 std::vector<std::vector<int> >::size_type cb =
b.size() > 0 ?
b[0].size() : 0;
2042 WerrorS(
"matrix dimensions do not match");
2043 return std::vector<std::vector<int> >();
2046 std::vector<std::vector<int> >
res(ra, std::vector<int>(cb));
2047 for (std::vector<std::vector<int> >::size_type
i = 0;
i < ra;
i++)
2049 for (std::vector<std::vector<int> >::size_type
j = 0;
j < cb;
j++)
2052 for (std::vector<std::vector<int> >::size_type
k = 0;
k < ca;
k++)
2053 sum += a[
i][
k] *
b[
k][
j];
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);
2072 for (
int v = 0;
v < n;
v++)
2090 WerrorS(
"K-Dim not implemented for rings");
2096 if (_G->m[
i] !=
NULL)
2100 WerrorS(
"K-Dim not implemented for modules");
2105 WerrorS(
"K-Dim not implemented for bi-modules");
2124 int ncGenCount =
currRing->LPncGenCount;
2125 if (lV - ncGenCount == 0)
2130 if (lV - ncGenCount == 1)
2135 if (lV - ncGenCount >= 2)
2151 WerrorS(
"K-Dim not defined for 0-ring");
2157 Print(
"max deg: %ld\n", maxDeg);
2163 PrintS(
"Computing normal words normally...\n");
2167 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
2173 int ncGenCount =
currRing->LPncGenCount;
2177 return numberOfNormalWords;
2179 if (
IDELEMS(
G) == lV - ncGenCount - 1)
2184 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
2192 PrintS(
"Computing Ufnarovski graph...\n");
2194 ideal standardWords;
2209 Print(
"Ufnarovski graph is %dx%d.\n", UG->
rows(), UG->
cols());
2212 PrintS(
"Checking whether Ufnarovski graph is acyclic...\n");
2220 std::vector<std::vector<int> > vvUG =
iv2vv(UG);
2221 for (std::vector<std::vector<int> >::size_type
i = 0;
i < vvUG.size();
i++)
2231 Print(
"Simplified Ufnarovski graph to %dx%d.\n", (
int)vvUG.size(), (
int)vvUG.size());
2236 PrintS(
"Computing normal words via Ufnarovski graph...\n");
2237 std::vector<std::vector<int> > UGpower = vvUG;
2242 PrintS(
"Start count graph entries.\n");
2243 for (std::vector<std::vector<int> >::size_type
i = 0;
i < UGpower.size();
i++)
2245 for (std::vector<std::vector<int> >::size_type
j = 0;
j < UGpower[
i].size();
j++)
2247 numberOfNormalWords += UGpower[
i][
j];
2253 PrintS(
"Done count graph entries.\n");
2254 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
2258 PrintS(
"Start mat mult.\n");
2259 UGpower =
vvMult(UGpower, vvUG);
2261 PrintS(
"Done mat mult.\n");
2267 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