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)
1041 int Nstc,
varset var,
int Nvar,poly hEdge)
1043 int iv = Nvar -1,
k = var[Nvar], a, a0, a1,
b,
i;
1055 for (
i = Nvar;
i>0;
i--)
1063 hStepS(sn, Nstc, var, Nvar, &a, &
x);
1080 hStepS(sn, Nstc, var, Nvar, &a, &
x);
1081 hElimS(sn, &
b, a0, a, var, iv);
1083 hPure(sn, a0, &a1, var, iv, pn, &
i);
1125 printf(
"\nThis is HC:\n");
1126 for(
int ii=0;ii<=
idElem(S);ii++)
1186 int x,
y=stc[0][Nvar];
1198 int x,
y=stc[0][Nvar];
1211 int i,
j, Istc = Nstc;
1214 for (
i=Nstc-1;
i>=0;
i--)
1219 if(stc[
i][
j] != 0)
break;
1233 for (
i=Nstc-1;
i>=0;
i--)
1235 if (stc[
i] && (stc[
i][Nvar] >=
y))
1265 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1278 scAll(Nvar-1, deg-d);
1288 scAll(Nvar-1, deg-ideg);
1290 }
while (ideg >= 0);
1295 int Ivar, Istc,
i,
j;
1301 for (
i=Nstc-1;
i>=0;
i--)
1303 for (
j=Nvar;
j;
j--){
if(stc[
i][
j])
break; }
1306 for (
i=Nvar;
i;
i--)
act[
i] = 0;
1312 for (
i=Nstc-1;
i>=0;
i--)
if(deg >= stc[
i][1])
return;
1327 if (deg <
x) ideg = deg;
1337 x =
scMax(Nstc, sn, Nvar);
1344 if (ideg < 0)
return;
1346 for (
i=Nstc-1;
i>=0;
i--)
1348 if (ideg < sn[
i][Nvar])
1376 int Ivar, Istc,
i,
j;
1382 ideg =
scMin(Nstc, stc, 1);
1398 x =
scMax(Nstc, sn, Nvar);
1405 if (ideg < 0)
return;
1407 for (
i=Nstc-1;
i>=0;
i--)
1409 if (ideg < sn[
i][Nvar])
1488 if (mv!=
NULL) deg_ei -= (*mv)[
i-1];
1489 if ((deg < 0) || (deg_ei>=0))
1609static 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)
1613 if (cache[
v] != -2)
return cache;
1619 for (
int w = 0;
w <
G->cols();
w++)
1631 cycles =
si_max(cycles, cache[
w]);
1635 int pathIndexOfW = -1;
1636 for (
int i = path.size() - 1;
i >= 0;
i--) {
1637 if (cyclic[path[
i]] == 1) {
1641 cyclic[path[
i]] =
TRUE;
1653 assume(pathIndexOfW != -1);
1654 for (
int i = path.size() - 1;
i >= pathIndexOfW;
i--) {
1655 cache =
countCycles(
G, path[
i], path, visited, cyclic, cache);
1656 if (cache[path[
i]] == -1)
1661 cycles =
si_max(cycles, cache[path[
i]] + 1);
1677 std::vector<int> path;
1678 std::vector<BOOLEAN> visited;
1679 std::vector<BOOLEAN> cyclic;
1680 std::vector<int> cache;
1681 visited.resize(n,
FALSE);
1682 cyclic.resize(n,
FALSE);
1683 cache.resize(n, -2);
1687 for (
int v = 0;
v < n;
v++)
1692 cycles =
si_max(cycles, cache[
v]);
1708 numberOfNormalWords = 0;
1714 numberOfNormalWords = 1;
1722 int numberOfNewNormalWords = 0;
1724 for (
int j = nVars - 1;
j >= 0;
j--)
1726 for (
int i =
last;
i >= 0;
i--)
1730 if (words->m[
i] !=
NULL)
1748 numberOfNewNormalWords++;
1756 numberOfNormalWords += numberOfNewNormalWords;
1772 ideal words =
idInit(maxElems);
1773 int last, numberOfNormalWords;
1790 for (
int i = 0;
i < upToLength;
i++)
1792 ideal words =
idInit(maxElems);
1793 int last, numberOfNormalWords;
1796 return numberOfNormalWords;
1808 WerrorS(
"Ufnarovski graph not implemented for l <= 0");
1815 int n =
IDELEMS(standardWords);
1817 for (
int i = 0;
i < n;
i++)
1819 for (
int j = 0;
j < n;
j++)
1821 poly
v = standardWords->m[
i];
1822 poly
w = standardWords->m[
j];
1825 bool overlap =
true;
1826 for (
int k = 1;
k <= (
l - 1) * lV;
k++)
1866 WerrorS(
"GK-Dim not implemented for rings");
1872 if (_G->m[
i] !=
NULL)
1876 WerrorS(
"GK-Dim not implemented for modules");
1881 WerrorS(
"GK-Dim not implemented for bi-modules");
1896 int ncGenCount =
currRing->LPncGenCount;
1897 if (lV - ncGenCount == 0)
1902 if (lV - ncGenCount == 1)
1907 if (lV - ncGenCount >= 2)
1923 WerrorS(
"GK-Dim not defined for 0-ring");
1933 int ncGenCount =
currRing->LPncGenCount;
1939 if (
IDELEMS(
G) == lV - ncGenCount - 1)
1944 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
1951 ideal standardWords;
1973 int rows =
M->rows();
1974 int cols =
M->cols();
1976 std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
1978 for (
int i = 0;
i < rows;
i++)
1980 for (
int j = 0;
j < cols;
j++)
1989static void vvPrint(
const std::vector<std::vector<int> >& mat)
1991 for (
int i = 0;
i < mat.size();
i++)
1993 for (
int j = 0;
j < mat[
i].size();
j++)
2001static void vvTest(
const std::vector<std::vector<int> >& mat)
2005 int cols = mat[0].size();
2006 for (
int i = 1;
i < mat.size();
i++)
2008 if (cols != mat[
i].
size())
2009 WerrorS(
"number of cols in matrix inconsistent");
2016 mat.erase(mat.begin() + row);
2021 for (
int i = 0;
i < mat.size();
i++)
2023 mat[
i].erase(mat[
i].begin() + col);
2029 for (
int i = 0;
i < mat[row].size();
i++)
2031 if (mat[row][
i] != 0)
2039 for (
int i = 0;
i < mat.size();
i++)
2041 if (mat[
i][col] != 0)
2049 for (
int i = 0;
i < mat.size();
i++)
2057static std::vector<std::vector<int> >
vvMult(
const std::vector<std::vector<int> >& a,
const std::vector<std::vector<int> >&
b)
2061 int ca = a.size() > 0 ? a[0].size() : 0;
2062 int cb =
b.size() > 0 ?
b[0].size() : 0;
2066 WerrorS(
"matrix dimensions do not match");
2067 return std::vector<std::vector<int> >();
2070 std::vector<std::vector<int> >
res(ra, std::vector<int>(cb));
2071 for (
int i = 0;
i < ra;
i++)
2073 for (
int j = 0;
j < cb;
j++)
2076 for (
int k = 0;
k < ca;
k++)
2077 sum += a[
i][
k] *
b[
k][
j];
2088 std::vector<int> path;
2089 std::vector<BOOLEAN> visited;
2090 std::vector<BOOLEAN> cyclic;
2091 std::vector<int> cache;
2092 visited.resize(n,
FALSE);
2093 cyclic.resize(n,
FALSE);
2094 cache.resize(n, -2);
2096 for (
int v = 0;
v < n;
v++)
2114 WerrorS(
"K-Dim not implemented for rings");
2120 if (_G->m[
i] !=
NULL)
2124 WerrorS(
"K-Dim not implemented for modules");
2129 WerrorS(
"K-Dim not implemented for bi-modules");
2148 int ncGenCount =
currRing->LPncGenCount;
2149 if (lV - ncGenCount == 0)
2154 if (lV - ncGenCount == 1)
2159 if (lV - ncGenCount >= 2)
2175 WerrorS(
"K-Dim not defined for 0-ring");
2181 Print(
"max deg: %ld\n", maxDeg);
2187 PrintS(
"Computing normal words normally...\n");
2191 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
2197 int ncGenCount =
currRing->LPncGenCount;
2201 return numberOfNormalWords;
2203 if (
IDELEMS(
G) == lV - ncGenCount - 1)
2208 if (
IDELEMS(
G) <= lV - ncGenCount - 2)
2216 PrintS(
"Computing Ufnarovski graph...\n");
2218 ideal standardWords;
2233 Print(
"Ufnarovski graph is %dx%d.\n", UG->
rows(), UG->
cols());
2236 PrintS(
"Checking whether Ufnarovski graph is acyclic...\n");
2244 std::vector<std::vector<int> > vvUG =
iv2vv(UG);
2245 for (
int i = 0;
i < vvUG.size();
i++)
2255 Print(
"Simplified Ufnarovski graph to %dx%d.\n", (
int)vvUG.size(), (
int)vvUG.size());
2260 PrintS(
"Computing normal words via Ufnarovski graph...\n");
2261 std::vector<std::vector<int> > UGpower = vvUG;
2266 PrintS(
"Start count graph entries.\n");
2267 for (
int i = 0;
i < UGpower.size();
i++)
2269 for (
int j = 0;
j < UGpower[
i].size();
j++)
2271 numberOfNormalWords += UGpower[
i][
j];
2277 PrintS(
"Done count graph entries.\n");
2278 Print(
"%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
2282 PrintS(
"Start mat mult.\n");
2283 UGpower =
vvMult(UGpower, vvUG);
2285 PrintS(
"Done mat mult.\n");
2291 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)
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 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