Loading...
Searching...
No Matches
hdegree.cc File Reference
`#include "kernel/mod2.h"`
`#include "misc/intvec.h"`
`#include "coeffs/numbers.h"`
`#include "kernel/structs.h"`
`#include "kernel/ideals.h"`
`#include "kernel/polys.h"`
`#include "kernel/combinatorics/hutil.h"`
`#include "kernel/combinatorics/hilb.h"`
`#include "kernel/combinatorics/stairc.h"`
`#include "reporter/reporter.h"`
`#include <vector>`
`#include "misc/options.h"`
`#include "polys/shiftop.h"`

Go to the source code of this file.

## Functions

void | hDimSolve (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
int | scDimInt (ideal S, ideal Q)
| ideal dimension
int | scDimIntRing (ideal vid, ideal Q)
| scDimInt for ring-coefficients
static void | hIndSolve (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
intvec * | scIndIntvec (ideal S, ideal Q)
static BOOLEAN | hNotZero (scfmon rad, int Nrad, varset var, int Nvar)
static void | hIndep (scmon pure)
void | hIndMult (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
static BOOLEAN | hCheck1 (indset sm, scmon pure)
static indset | hCheck2 (indset sm, scmon pure)
static void | hCheckIndep (scmon pure)
void | hIndAllMult (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
static long | hZeroMult (scmon pure, scfmon stc, int Nstc, varset var, int Nvar)
static void | hProject (scmon pure, varset sel)
static void | hDimMult (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
static void | hDegree (ideal S, ideal Q)
int | scMultInt (ideal S, ideal Q)
void | scPrintDegree (int co, int mu)
long | scMult0Int (ideal S, ideal Q)
static void | hHedge (poly hEdge)
static void | hHedgeStep (scmon pure, scfmon stc, int Nstc, varset var, int Nvar, poly hEdge)
void | scComputeHC (ideal S, ideal Q, int ak, poly &hEdge)
static void | scElKbase ()
static int | scMax (int i, scfmon stc, int Nvar)
static int | scMin (int i, scfmon stc, int Nvar)
static int | scRestrict (int &Nstc, scfmon stc, int Nvar)
static void | scAll (int Nvar, int deg)
static void | scAllKbase (int Nvar, int ideg, int deg)
static void | scDegKbase (scfmon stc, int Nstc, int Nvar, int deg)
static void | scInKbase (scfmon stc, int Nstc, int Nvar)
static ideal | scIdKbase (poly q, const int rank)
ideal | scKBase (int deg, ideal s, ideal Q, intvec *mv)
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)
static int | graphGrowth (const intvec *G)
static void | _lp_computeNormalWords (ideal words, int &numberOfNormalWords, int length, ideal M, int minDeg, int &last)
static ideal | lp_computeNormalWords (int length, ideal M)
static int | lp_countNormalWords (int upToLength, ideal M)
intvec * | lp_ufnarovskiGraph (ideal G, ideal &standardWords)
int | lp_gkDim (const ideal _G)
static std::vector< std::vector< int > > | iv2vv (intvec *M)
static void | vvDeleteRow (std::vector< std::vector< int > > &mat, int row)
static void | vvDeleteColumn (std::vector< std::vector< int > > &mat, int col)
static BOOLEAN | vvIsRowZero (const std::vector< std::vector< int > > &mat, int row)
static BOOLEAN | vvIsColumnZero (const std::vector< std::vector< int > > &mat, int col)
static BOOLEAN | vvIsZero (const std::vector< std::vector< int > > &mat)
static std::vector< std::vector< int > > | vvMult (const std::vector< std::vector< int > > &a, const std::vector< std::vector< int > > &b)
static BOOLEAN | isAcyclic (const intvec *G)
int | lp_kDim (const ideal _G)

## Variables

VAR int | hCo
VAR int | hMu2
VAR long | hMu
VAR omBin | indlist_bin = omGetSpecBin(sizeof(indlist))
STATIC_VAR scmon | hInd
VAR indset | ISet
VAR indset | JSet
STATIC_VAR poly | pWork
STATIC_VAR poly | last
STATIC_VAR scmon | act

## Function Documentation

## _lp_computeNormalWords()

void _lp_computeNormalWords | ( | ideal | words,
|  | int & | numberOfNormalWords,
|  | int | length,
|  | ideal | M,
|  | int | minDeg,
|  | int & | last )

static

Definition at line 1666 of file hdegree.cc.

{
if (length <= 0){
poly one = pOne();
if (p_LPDivisibleBy(M, one, currRing)) // 1 \in M => no normal words at all
{
pDelete(&one);
last = -1;
numberOfNormalWords = 0;
}
else
{
words->m[0] = one;
last = 0;
numberOfNormalWords = 1;
}
return;
}
_lp_computeNormalWords(words, numberOfNormalWords, length - 1, M, minDeg, last);
int nVars = currRing->isLPring - currRing->LPncGenCount;
int numberOfNewNormalWords = 0;
for (int j = nVars - 1; j >= 0; j--)
{
for (int i = last; i >= 0; i--)
{
int index = (j * (last + 1)) + i;
if (words->m[i] != NULL)
{
if (j > 0) {
words->m[index] = pCopy(words->m[i]);
}
int varOffset = ((length - 1) * currRing->isLPring) + 1;
pSetExp(words->m[index], varOffset + j, 1);
pSetm(words->m[index]);
pTest(words->m[index]);
if (length >= minDeg && p_LPDivisibleBy(M, words->m[index], currRing))
{
pDelete(&words->m[index]);
words->m[index] = NULL;
}
else
{
numberOfNewNormalWords++;
}
}
}
}
last = nVars * last + nVars - 1;
numberOfNormalWords += numberOfNewNormalWords;
}
i
int i
Definition cfEzgcd.cc:132
j
int j
Definition facHensel.cc:110
last
STATIC_VAR poly last
Definition hdegree.cc:1138
_lp_computeNormalWords
static void _lp_computeNormalWords(ideal words, int &numberOfNormalWords, int length, ideal M, int minDeg, int &last)
Definition hdegree.cc:1666
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
NULL
#define NULL
Definition omList.c:12
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
pTest
#define pTest(p)
Definition polys.h:415
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pSetm
#define pSetm(p)
Definition polys.h:272
pSetExp
#define pSetExp(p, i, v)
Definition polys.h:43
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
pOne
#define pOne()
Definition polys.h:316
p_LPDivisibleBy
BOOLEAN p_LPDivisibleBy(poly a, poly b, const ring r)
Definition shiftop.cc:776
M
#define M
Definition sirandom.c:25

## countCycles()

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 )

static

Definition at line 1575 of file hdegree.cc.

{
intvec* G = ivCopy(_G); // modifications must be local
if (cache[v] != -2) return cache; // value is already cached
visited[v] = TRUE;
path.push_back(v);
int cycles = 0;
for (int w = 0; w < G->cols(); w++)
{
if (IMATELEM(*G, v + 1, w + 1)) // edge v -> w exists in G
{
if (!visited[w])
{ // continue with w
cache = countCycles(G, w, path, visited, cyclic, cache);
if (cache[w] == -1)
{
cache[v] = -1;
return cache;
}
cycles = si_max(cycles, cache[w]);
}
else
{ // found new cycle
int pathIndexOfW = -1;
for (int i = path.size() - 1; i >= 0; i--) {
if (cyclic[path[i]] == 1) { // found an already cyclic vertex
cache[v] = -1;
return cache;
}
cyclic[path[i]] = TRUE;
if (path[i] == w) { // end of the cycle
assume(IMATELEM(*G, v + 1, w + 1) != 0);
IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v -> w
pathIndexOfW = i;
break;
} else {
assume(IMATELEM(*G, path[i - 1] + 1, path[i] + 1) != 0);
IMATELEM(*G, path[i - 1] + 1, path[i] + 1) = 0; // remove edge vi-1 -> vi
}
}
assume(pathIndexOfW != -1); // should never happen
for (int i = path.size() - 1; i >= pathIndexOfW; i--) {
cache = countCycles(G, path[i], path, visited, cyclic, cache);
if (cache[path[i]] == -1)
{
cache[v] = -1;
return cache;
}
cycles = si_max(cycles, cache[path[i]] + 1);
}
}
}
}
cache[v] = cycles;
delete G;
return cache;
}
si_max
static int si_max(const int a, const int b)
Definition auxiliary.h:125
TRUE
#define TRUE
Definition auxiliary.h:101
intvec
Definition intvec.h:24
w
const CanonicalForm & w
Definition facAbsFact.cc:51
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
countCycles
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)
Definition hdegree.cc:1575
ivCopy
intvec * ivCopy(const intvec *o)
Definition intvec.h:146
IMATELEM
#define IMATELEM(M, I, J)
Definition intvec.h:86
G
STATIC_VAR TreeM * G
Definition janet.cc:31
assume
#define assume(x)
Definition mod2.h:389

## graphGrowth()

int graphGrowth | ( | const intvec * | G | ) |

static

Definition at line 1639 of file hdegree.cc.

{
// init
int n = G->cols();
std::vector<int> path;
std::vector<BOOLEAN> visited;
std::vector<BOOLEAN> cyclic;
std::vector<int> cache;
visited.resize(n, FALSE);
cyclic.resize(n, FALSE);
cache.resize(n, -2);
// get max number of cycles
int cycles = 0;
for (int v = 0; v < n; v++)
{
cache = countCycles(G, v, path, visited, cyclic, cache);
if (cache[v] == -1)
return -1;
cycles = si_max(cycles, cache[v]);
}
return cycles;
}
FALSE
#define FALSE
Definition auxiliary.h:97

## hCheck1()

BOOLEAN hCheck1 | ( | indset | sm,
|  | scmon | pure )

static

Definition at line 463 of file hdegree.cc.

{
int iv;
intvec *Set;
while (sm->nx != NULL)
{
Set = sm->set;
iv=(currRing->N);
loop
{
if (((*Set)[iv-1] == 0) && (pure[iv] == 0))
break;
iv--;
if (iv == 0)
return FALSE;
}
sm = sm->nx;
}
return TRUE;
}
loop
#define loop
Definition structs.h:71

## hCheck2()

indset hCheck2 | ( | indset | sm,
|  | scmon | pure )

static

Definition at line 489 of file hdegree.cc.

{
int iv;
intvec *Set;
indset be, a1 = NULL;
while (sm->nx != NULL)
{
Set = sm->set;
iv=(currRing->N);
loop
{
if ((pure[iv] == 1) && ((*Set)[iv-1] == 1))
break;
iv--;
if (iv == 0)
{
if (a1 == NULL)
{
a1 = sm;
}
else
{
hMu2--;
be->nx = sm->nx;
delete Set;
omFreeBin((ADDRESS)sm, indlist_bin);
sm = be;
}
break;
}
}
be = sm;
sm = sm->nx;
}
if (a1 != NULL)
{
return a1;
}
else
{
hMu2++;
sm->set = new intvec((currRing->N));
sm->nx = (indset)omAlloc0Bin(indlist_bin);
return sm;
}
}
ADDRESS
void * ADDRESS
Definition auxiliary.h:120
indlist_bin
VAR omBin indlist_bin
Definition hdegree.cc:29
hMu2
VAR int hMu2
Definition hdegree.cc:27
indset
indlist * indset
Definition hutil.h:28
omAlloc0Bin
#define omAlloc0Bin(bin)
Definition omAllocDecl.h:206
omFreeBin
#define omFreeBin(addr, bin)
Definition omAllocDecl.h:259

## hCheckIndep()

void hCheckIndep | ( | scmon | pure | ) |

static

Definition at line 541 of file hdegree.cc.

{
intvec *Set;
indset res;
int iv;
if (hCheck1(ISet, pure))
{
if (hCheck1(JSet, pure))
{
res = hCheck2(JSet,pure);
if (res == NULL)
return;
Set = res->set;
for (iv=(currRing->N); iv; iv--)
{
(*Set)[iv-1] = (pure[iv]==0);
}
}
}
}
res
CanonicalForm res
Definition facAbsFact.cc:60
hCheck2
static indset hCheck2(indset sm, scmon pure)
Definition hdegree.cc:489
hCheck1
static BOOLEAN hCheck1(indset sm, scmon pure)
Definition hdegree.cc:463
ISet
VAR indset ISet
Definition hdegree.cc:351
JSet
VAR indset JSet
Definition hdegree.cc:351

## hDegree()

void hDegree | ( | ideal | S,
|  | ideal | Q )

static

Definition at line 800 of file hdegree.cc.

{
id_Test(S, currRing);
if( Q!=NULL ) id_Test(Q, currRing);
int di;
int mc;
hexist = hInit(S, Q, &hNexist);
if (!hNexist)
{
hCo = 0;
hMu = 1;
return;
}
//hWeight();
hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
hsel = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
hpur0 = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
mc = hisModule;
hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
if (!mc)
{
memcpy(hrad, hexist, hNexist * sizeof(scmon));
hstc = hexist;
hNrad = hNstc = hNexist;
}
else
hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
radmem = hCreate((currRing->N) - 1);
stcmem = hCreate((currRing->N) - 1);
hCo = (currRing->N) + 1;
di = hCo + 1;
loop
{
if (mc)
{
hComp(hexist, hNexist, mc, hrad, &hNrad);
hNstc = hNrad;
memcpy(hstc, hrad, hNrad * sizeof(scmon));
}
if (hNrad)
{
hNvar = (currRing->N);
hRadical(hrad, &hNrad, hNvar);
hSupp(hrad, hNrad, hvar, &hNvar);
if (hNvar)
{
hCo = hNvar;
memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
hLexR(hrad, hNrad, hvar, hNvar);
hDimSolve(hpure, hNpure, hrad, hNrad, hvar, hNvar);
}
}
else
{
hNvar = 1;
hCo = 0;
}
if (hCo < di)
{
di = hCo;
hMu = 0;
}
if (hNvar && (hCo == di))
{
if (di && (di < (currRing->N)))
hDimMult(hpure, hNpure, hrad, hNrad, hvar, hNvar);
else if (!di)
hMu++;
else
{
hStaircase(hstc, &hNstc, hvar, hNvar);
if ((hNvar > 2) && (hNstc > 10))
hOrdSupp(hstc, hNstc, hvar, hNvar);
memset(hpur0, 0, ((currRing->N) + 1) * sizeof(int));
hPure(hstc, 0, &hNstc, hvar, hNvar, hpur0, &hNpure);
hLexS(hstc, hNstc, hvar, hNvar);
hMu += hZeroMult(hpur0, hstc, hNstc, hvar, hNvar);
}
}
mc--;
if (mc <= 0)
break;
}
hCo = di;
hKill(stcmem, (currRing->N) - 1);
hKill(radmem, (currRing->N) - 1);
omFreeSize((ADDRESS)hpur0, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
omFreeSize((ADDRESS)hsel, ((currRing->N) + 1) * sizeof(int));
omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
hDelete(hexist, hNexist);
if (hisModule)
omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
}
hZeroMult
static long hZeroMult(scmon pure, scfmon stc, int Nstc, varset var, int Nvar)
Definition hdegree.cc:619
hDimMult
static void hDimMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:724
hCo
VAR int hCo
Definition hdegree.cc:27
hMu
VAR long hMu
Definition hdegree.cc:28
hDimSolve
void hDimSolve(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:35
hCreate
monf hCreate(int Nvar)
Definition hutil.cc:996
hComp
void hComp(scfmon exist, int Nexist, int ak, scfmon stc, int *Nstc)
Definition hutil.cc:154
hstc
VAR scfmon hstc
Definition hutil.cc:16
hvar
VAR varset hvar
Definition hutil.cc:18
hKill
void hKill(monf xmem, int Nvar)
Definition hutil.cc:1010
hNexist
VAR int hNexist
Definition hutil.cc:19
hLexS
void hLexS(scfmon stc, int Nstc, varset var, int Nvar)
Definition hutil.cc:506
hDelete
void hDelete(scfmon ev, int ev_length)
Definition hutil.cc:140
hpur0
VAR scmon hpur0
Definition hutil.cc:17
stcmem
VAR monf stcmem
Definition hutil.cc:21
hPure
void hPure(scfmon stc, int a, int *Nstc, varset var, int Nvar, scmon pure, int *Npure)
Definition hutil.cc:621
hwork
VAR scfmon hwork
Definition hutil.cc:16
hSupp
void hSupp(scfmon stc, int Nstc, varset var, int *Nvar)
Definition hutil.cc:174
hLexR
void hLexR(scfmon rad, int Nrad, varset var, int Nvar)
Definition hutil.cc:565
hpure
VAR scmon hpure
Definition hutil.cc:17
hrad
VAR scfmon hrad
Definition hutil.cc:16
hisModule
VAR int hisModule
Definition hutil.cc:20
hStaircase
void hStaircase(scfmon stc, int *Nstc, varset var, int Nvar)
Definition hutil.cc:313
radmem
VAR monf radmem
Definition hutil.cc:21
hOrdSupp
void hOrdSupp(scfmon stc, int Nstc, varset var, int Nvar)
Definition hutil.cc:202
hsel
VAR varset hsel
Definition hutil.cc:18
hNpure
VAR int hNpure
Definition hutil.cc:19
hNrad
VAR int hNrad
Definition hutil.cc:19
hInit
scfmon hInit(ideal S, ideal Q, int *Nexist)
Definition hutil.cc:31
hexist
VAR scfmon hexist
Definition hutil.cc:16
hRadical
void hRadical(scfmon rad, int *Nrad, int Nvar)
Definition hutil.cc:411
hNstc
VAR int hNstc
Definition hutil.cc:19
hNvar
VAR int hNvar
Definition hutil.cc:19
scfmon
scmon * scfmon
Definition hutil.h:15
varset
int * varset
Definition hutil.h:16
scmon
int * scmon
Definition hutil.h:14
omFreeSize
#define omFreeSize(addr, size)
Definition omAllocDecl.h:260
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
id_Test
#define id_Test(A, lR)
Definition simpleideals.h:89
Q
#define Q
Definition sirandom.c:26

## hDimMult()

void hDimMult | ( | scmon | pure,
|  | int | Npure,
|  | scfmon | rad,
|  | int | Nrad,
|  | varset | var,
|  | int | Nvar )

static

Definition at line 724 of file hdegree.cc.

{
int dn, iv, rad0, b, c, x;
scmon pn;
scfmon rn;
if (Nrad < 2)
{
dn = Npure + Nrad;
if (dn == hCo)
{
if (!Nrad)
hProject(pure, hsel);
else
{
pn = *rad;
for (iv = Nvar; iv; iv--)
{
x = var[iv];
if (pn[x])
{
pure[x] = 1;
hProject(pure, hsel);
pure[x] = 0;
}
}
}
}
return;
}
iv = Nvar;
dn = Npure+1;
if (dn >= hCo)
{
if (dn > hCo)
return;
loop
{
if(!pure[var[iv]])
{
if(hNotZero(rad, Nrad, var, iv))
{
pure[var[iv]] = 1;
hProject(pure, hsel);
pure[var[iv]] = 0;
}
}
iv--;
if (!iv)
return;
}
}
while(pure[var[iv]]) iv--;
hStepR(rad, Nrad, var, iv, &rad0);
iv--;
if (rad0 < Nrad)
{
pn = hGetpure(pure);
rn = hGetmem(Nrad, rad, radmem[iv]);
pn[var[iv + 1]] = 1;
hDimMult(pn, Npure + 1, rn, rad0, var, iv);
pn[var[iv + 1]] = 0;
b = rad0;
c = Nrad;
hElimR(rn, &rad0, b, c, var, iv);
hPure(rn, b, &c, var, iv, pn, &x);
hLex2R(rn, rad0, b, c, var, iv, hwork);
rad0 += (c - b);
hDimMult(pn, Npure + x, rn, rad0, var, iv);
}
else
{
hDimMult(pure, Npure, rad, Nrad, var, iv);
}
}
x
Variable x
Definition cfModGcd.cc:4090
b
CanonicalForm b
Definition cfModGcd.cc:4111
hNotZero
static BOOLEAN hNotZero(scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:353
hProject
static void hProject(scmon pure, varset sel)
Definition hdegree.cc:701
hGetmem
scfmon hGetmem(int lm, scfmon old, monp monmem)
Definition hutil.cc:1023
hStepR
void hStepR(scfmon rad, int Nrad, varset var, int Nvar, int *a)
Definition hutil.cc:974
hLex2R
void hLex2R(scfmon rad, int e1, int a2, int e2, varset var, int Nvar, scfmon w)
Definition hutil.cc:880
hElimR
void hElimR(scfmon rad, int *e1, int a2, int e2, varset var, int Nvar)
Definition hutil.cc:742
hGetpure
scmon hGetpure(scmon p)
Definition hutil.cc:1052

## hDimSolve()

void hDimSolve | ( | scmon | pure,
|  | int | Npure,
|  | scfmon | rad,
|  | int | Nrad,
|  | varset | var,
|  | int | Nvar )

Definition at line 35 of file hdegree.cc.

{
int dn, iv, rad0, b, c, x;
scmon pn;
scfmon rn;
if (Nrad < 2)
{
dn = Npure + Nrad;
if (dn < hCo)
hCo = dn;
return;
}
if (Npure+1 >= hCo)
return;
iv = Nvar;
while(pure[var[iv]]) iv--;
hStepR(rad, Nrad, var, iv, &rad0);
if (rad0!=0)
{
iv--;
if (rad0 < Nrad)
{
pn = hGetpure(pure);
rn = hGetmem(Nrad, rad, radmem[iv]);
hDimSolve(pn, Npure + 1, rn, rad0, var, iv);
b = rad0;
c = Nrad;
hElimR(rn, &rad0, b, c, var, iv);
hPure(rn, b, &c, var, iv, pn, &x);
hLex2R(rn, rad0, b, c, var, iv, hwork);
rad0 += (c - b);
hDimSolve(pn, Npure + x, rn, rad0, var, iv);
}
else
{
hDimSolve(pure, Npure, rad, Nrad, var, iv);
}
}
else
hCo = Npure + 1;
}

## hHedge()

void hHedge | ( | poly | hEdge | ) |

static

Definition at line 1003 of file hdegree.cc.

{
pSetm(pWork);
if (pLmCmp(pWork, hEdge) == currRing->OrdSgn)
{
for (int i = hNvar; i>0; i--)
pSetExp(hEdge,i, pGetExp(pWork,i));
pSetm(hEdge);
}
}
pWork
STATIC_VAR poly pWork
Definition hdegree.cc:1001
pGetExp
#define pGetExp(p, i)
Exponent.
Definition polys.h:42
pLmCmp
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition polys.h:106

## hHedgeStep()

void hHedgeStep | ( | scmon | pure,
|  | scfmon | stc,
|  | int | Nstc,
|  | varset | var,
|  | int | Nvar,
|  | poly | hEdge )

static

Definition at line 1014 of file hdegree.cc.

{
int iv = Nvar -1, k = var[Nvar], a, a0, a1, b, i;
int x/*, x0*/;
scmon pn;
scfmon sn;
if (iv==0)
{
pSetExp(pWork, k, pure[k]);
hHedge(hEdge);
return;
}
else if (Nstc==0)
{
for (i = Nvar; i>0; i--)
pSetExp(pWork, var[i], pure[var[i]]);
hHedge(hEdge);
return;
}
x = a = 0;
pn = hGetpure(pure);
sn = hGetmem(Nstc, stc, stcmem[iv]);
hStepS(sn, Nstc, var, Nvar, &a, &x);
if (a == Nstc)
{
pSetExp(pWork, k, pure[k]);
hHedgeStep(pn, sn, a, var, iv,hEdge);
return;
}
else
{
pSetExp(pWork, k, x);
hHedgeStep(pn, sn, a, var, iv,hEdge);
}
b = a;
loop
{
a0 = a;
// x0 = x;
hStepS(sn, Nstc, var, Nvar, &a, &x);
hElimS(sn, &b, a0, a, var, iv);
a1 = a;
hPure(sn, a0, &a1, var, iv, pn, &i);
hLex2S(sn, b, a0, a1, var, iv, hwork);
b += (a1 - a0);
if (a < Nstc)
{
pSetExp(pWork, k, x);
hHedgeStep(pn, sn, b, var, iv,hEdge);
}
else
{
pSetExp(pWork, k, pure[k]);
hHedgeStep(pn, sn, b, var, iv,hEdge);
return;
}
}
}
k
int k
Definition cfEzgcd.cc:99
hHedgeStep
static void hHedgeStep(scmon pure, scfmon stc, int Nstc, varset var, int Nvar, poly hEdge)
Definition hdegree.cc:1014
hHedge
static void hHedge(poly hEdge)
Definition hdegree.cc:1003
hLex2S
void hLex2S(scfmon rad, int e1, int a2, int e2, varset var, int Nvar, scfmon w)
Definition hutil.cc:812
hElimS
void hElimS(scfmon stc, int *e1, int a2, int e2, varset var, int Nvar)
Definition hutil.cc:672
hStepS
void hStepS(scfmon stc, int Nstc, varset var, int Nvar, int *a, int *x)
Definition hutil.cc:949

## hIndAllMult()

void hIndAllMult | ( | scmon | pure,
|  | int | Npure,
|  | scfmon | rad,
|  | int | Nrad,
|  | varset | var,
|  | int | Nvar )

Definition at line 562 of file hdegree.cc.

{
int dn, iv, rad0, b, c, x;
scmon pn;
scfmon rn;
if (Nrad < 2)
{
dn = Npure + Nrad;
if (dn > hCo)
{
if (!Nrad)
hCheckIndep(pure);
else
{
pn = *rad;
for (iv = Nvar; iv; iv--)
{
x = var[iv];
if (pn[x])
{
pure[x] = 1;
hCheckIndep(pure);
pure[x] = 0;
}
}
}
}
return;
}
iv = Nvar;
while(pure[var[iv]]) iv--;
hStepR(rad, Nrad, var, iv, &rad0);
iv--;
if (rad0 < Nrad)
{
pn = hGetpure(pure);
rn = hGetmem(Nrad, rad, radmem[iv]);
pn[var[iv + 1]] = 1;
hIndAllMult(pn, Npure + 1, rn, rad0, var, iv);
pn[var[iv + 1]] = 0;
b = rad0;
c = Nrad;
hElimR(rn, &rad0, b, c, var, iv);
hPure(rn, b, &c, var, iv, pn, &x);
hLex2R(rn, rad0, b, c, var, iv, hwork);
rad0 += (c - b);
hIndAllMult(pn, Npure + x, rn, rad0, var, iv);
}
else
{
hIndAllMult(pure, Npure, rad, Nrad, var, iv);
}
}
hCheckIndep
static void hCheckIndep(scmon pure)
Definition hdegree.cc:541
hIndAllMult
void hIndAllMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:562

## hIndep()

void hIndep | ( | scmon | pure | ) |

static

Definition at line 368 of file hdegree.cc.

{
int iv;
intvec *Set;
Set = ISet->set = new intvec((currRing->N));
for (iv=(currRing->N); iv!=0 ; iv--)
{
(*Set)[iv-1] = (pure[iv]==0);
}
ISet = ISet->nx = (indset)omAlloc0Bin(indlist_bin);
hMu++;
}

## hIndMult()

void hIndMult | ( | scmon | pure,
|  | int | Npure,
|  | scfmon | rad,
|  | int | Nrad,
|  | varset | var,
|  | int | Nvar )

Definition at line 382 of file hdegree.cc.

{
int dn, iv, rad0, b, c, x;
scmon pn;
scfmon rn;
if (Nrad < 2)
{
dn = Npure + Nrad;
if (dn == hCo)
{
if (Nrad==0)
hIndep(pure);
else
{
pn = *rad;
for (iv = Nvar; iv!=0; iv--)
{
x = var[iv];
if (pn[x])
{
pure[x] = 1;
hIndep(pure);
pure[x] = 0;
}
}
}
}
return;
}
iv = Nvar;
dn = Npure+1;
if (dn >= hCo)
{
if (dn > hCo)
return;
loop
{
if(!pure[var[iv]])
{
if(hNotZero(rad, Nrad, var, iv))
{
pure[var[iv]] = 1;
hIndep(pure);
pure[var[iv]] = 0;
}
}
iv--;
if (!iv)
return;
}
}
while(pure[var[iv]]) iv--;
hStepR(rad, Nrad, var, iv, &rad0);
iv--;
if (rad0 < Nrad)
{
pn = hGetpure(pure);
rn = hGetmem(Nrad, rad, radmem[iv]);
pn[var[iv + 1]] = 1;
hIndMult(pn, Npure + 1, rn, rad0, var, iv);
pn[var[iv + 1]] = 0;
b = rad0;
c = Nrad;
hElimR(rn, &rad0, b, c, var, iv);
hPure(rn, b, &c, var, iv, pn, &x);
hLex2R(rn, rad0, b, c, var, iv, hwork);
rad0 += (c - b);
hIndMult(pn, Npure + x, rn, rad0, var, iv);
}
else
{
hIndMult(pure, Npure, rad, Nrad, var, iv);
}
}
hIndMult
void hIndMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:382
hIndep
static void hIndep(scmon pure)
Definition hdegree.cc:368

## hIndSolve()

void hIndSolve | ( | scmon | pure,
|  | int | Npure,
|  | scfmon | rad,
|  | int | Nrad,
|  | varset | var,
|  | int | Nvar )

static

Definition at line 205 of file hdegree.cc.

{
int dn, iv, rad0, b, c, x;
scmon pn;
scfmon rn;
if (Nrad < 2)
{
dn = Npure + Nrad;
if (dn < hCo)
{
hCo = dn;
for (iv=(currRing->N); iv; iv--)
{
if (pure[iv])
hInd[iv] = 0;
else
hInd[iv] = 1;
}
if (Nrad)
{
pn = *rad;
iv = Nvar;
loop
{
x = var[iv];
if (pn[x])
{
hInd[x] = 0;
break;
}
iv--;
}
}
}
return;
}
if (Npure+1 >= hCo)
return;
iv = Nvar;
while(pure[var[iv]]) iv--;
hStepR(rad, Nrad, var, iv, &rad0);
if (rad0)
{
iv--;
if (rad0 < Nrad)
{
pn = hGetpure(pure);
rn = hGetmem(Nrad, rad, radmem[iv]);
pn[var[iv + 1]] = 1;
hIndSolve(pn, Npure + 1, rn, rad0, var, iv);
pn[var[iv + 1]] = 0;
b = rad0;
c = Nrad;
hElimR(rn, &rad0, b, c, var, iv);
hPure(rn, b, &c, var, iv, pn, &x);
hLex2R(rn, rad0, b, c, var, iv, hwork);
rad0 += (c - b);
hIndSolve(pn, Npure + x, rn, rad0, var, iv);
}
else
{
hIndSolve(pure, Npure, rad, Nrad, var, iv);
}
}
else
{
hCo = Npure + 1;
for (x=(currRing->N); x; x--)
{
if (pure[x])
hInd[x] = 0;
else
hInd[x] = 1;
}
hInd[var[iv]] = 0;
}
}
hInd
STATIC_VAR scmon hInd
Definition hdegree.cc:203
hIndSolve
static void hIndSolve(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:205

## hNotZero()

BOOLEAN hNotZero | ( | scfmon | rad,
|  | int | Nrad,
|  | varset | var,
|  | int | Nvar )

static

Definition at line 353 of file hdegree.cc.

{
int k1, i;
k1 = var[Nvar];
i = 0;
loop
{
if (rad[i][k1]==0)
return FALSE;
i++;
if (i == Nrad)
return TRUE;
}
}

## hProject()

void hProject | ( | scmon | pure,
|  | varset | sel )

static

Definition at line 701 of file hdegree.cc.

{
int i, i0, k;
i0 = 0;
for (i = 1; i <= (currRing->N); i++)
{
if (pure[i])
{
i0++;
sel[i0] = i;
}
}
i = hNstc;
memcpy(hwork, hstc, i * sizeof(scmon));
hStaircase(hwork, &i, sel, i0);
if ((i0 > 2) && (i > 10))
hOrdSupp(hwork, i, sel, i0);
memset(hpur0, 0, ((currRing->N) + 1) * sizeof(int));
hPure(hwork, 0, &i, sel, i0, hpur0, &k);
hLexS(hwork, i, sel, i0);
hMu += hZeroMult(hpur0, hwork, i, sel, i0);
}

## hZeroMult()

long hZeroMult | ( | scmon | pure,
|  | scfmon | stc,
|  | int | Nstc,
|  | varset | var,
|  | int | Nvar )

static

Definition at line 619 of file hdegree.cc.

{
int iv = Nvar -1, a, a0, a1, b, i;
long sum;
int x, x0;
scmon pn;
scfmon sn;
if (!iv)
return pure[var[1]];
else if (!Nstc)
{
sum = 1;
for (i = Nvar; i; i--)
sum *= pure[var[i]];
return sum;
}
x = a = 0;
pn = hGetpure(pure);
sn = hGetmem(Nstc, stc, stcmem[iv]);
hStepS(sn, Nstc, var, Nvar, &a, &x);
if (a == Nstc)
{
#if SIZEOF_LONG==8
return (long)pure[var[Nvar]] * hZeroMult(pn, sn, a, var, iv);
#else
int64 t=hZeroMult(pn, sn, a, var, iv);
t *= pure[var[Nvar]];
if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
else if (!errorreported) WerrorS("int overflow in vdim 3");
return sum;
#endif
}
else
{
#if SIZEOF_LONG==8
sum = x * hZeroMult(pn, sn, a, var, iv);
#else
int64 t=hZeroMult(pn, sn, a, var, iv);
t *= x;
if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
else if (!errorreported) WerrorS("int overflow in vdim 4");
#endif
}
b = a;
loop
{
a0 = a;
x0 = x;
hStepS(sn, Nstc, var, Nvar, &a, &x);
hElimS(sn, &b, a0, a, var, iv);
a1 = a;
hPure(sn, a0, &a1, var, iv, pn, &i);
hLex2S(sn, b, a0, a1, var, iv, hwork);
b += (a1 - a0);
if (a < Nstc)
{
#if SIZEOF_LONG==8
sum += (long)(x - x0) * hZeroMult(pn, sn, b, var, iv);
#else
int64 t=hZeroMult(pn, sn, b, var, iv);
t *= (x-x0);
t += sum;
if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
else if (!errorreported) WerrorS("int overflow in vdim 1");
#endif
}
else
{
#if SIZEOF_LONG==8
sum += (long)(pure[var[Nvar]] - x0) * hZeroMult(pn, sn, b, var, iv);
#else
int64 t=hZeroMult(pn, sn, b, var, iv);
t *= (pure[var[Nvar]]-x0);
t += sum;
if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
else if (!errorreported) WerrorS("int overflow in vdim 2");
#endif
return sum;
}
}
}
int64
long int64
Definition auxiliary.h:68
errorreported
VAR short errorreported
Definition feFopen.cc:23
WerrorS
void WerrorS(const char *s)
Definition feFopen.cc:24

## isAcyclic()

BOOLEAN isAcyclic | ( | const intvec * | G | ) |

static

Definition at line 2054 of file hdegree.cc.

{
// init
int n = G->cols();
std::vector<int> path;
std::vector<BOOLEAN> visited;
std::vector<BOOLEAN> cyclic;
std::vector<int> cache;
visited.resize(n, FALSE);
cyclic.resize(n, FALSE);
cache.resize(n, -2);
for (int v = 0; v < n; v++)
{
cache = countCycles(G, v, path, visited, cyclic, cache);
// check that there are 0 cycles from v
if (cache[v] != 0)
return FALSE;
}
return TRUE;
}

## iv2vv()

std::vector< std::vector< int > > iv2vv | ( | intvec * | M | ) |

static

Definition at line 1937 of file hdegree.cc.

{
int rows = M->rows();
int cols = M->cols();
std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
mat[i][j] = IMATELEM(*M, i + 1, j + 1);
}
}
return mat;
}

## lp_computeNormalWords()

ideal lp_computeNormalWords | ( | int | length,
|  | ideal | M )

static

Definition at line 1725 of file hdegree.cc.

{
long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
for (int i = 1; i < IDELEMS(M); i++)
{
minDeg = si_min(minDeg, pTotaldegree(M->m[i]));
}
int nVars = currRing->isLPring - currRing->LPncGenCount;
int maxElems = 1;
for (int i = 0; i < length; i++) // maxElems = nVars^n
maxElems *= nVars;
ideal words = idInit(maxElems);
int last, numberOfNormalWords;
_lp_computeNormalWords(words, numberOfNormalWords, length, M, minDeg, last);
idSkipZeroes(words);
return words;
}
si_min
static int si_min(const int a, const int b)
Definition auxiliary.h:126
pTotaldegree
static long pTotaldegree(poly p)
Definition polys.h:283
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition simpleideals.cc:201
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23

## lp_countNormalWords()

int lp_countNormalWords | ( | int | upToLength,
|  | ideal | M )

static

Definition at line 1745 of file hdegree.cc.

{
long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
for (int i = 1; i < IDELEMS(M); i++)
{
minDeg = si_min(minDeg, pTotaldegree(M->m[i]));
}
int nVars = currRing->isLPring - currRing->LPncGenCount;
int maxElems = 1;
for (int i = 0; i < upToLength; i++) // maxElems = nVars^n
maxElems *= nVars;
ideal words = idInit(maxElems);
int last, numberOfNormalWords;
_lp_computeNormalWords(words, numberOfNormalWords, upToLength, M, minDeg, last);
idDelete(&words);
return numberOfNormalWords;
}
idDelete
#define idDelete(H)
delete an ideal
Definition ideals.h:29

## lp_gkDim()

int lp_gkDim | ( | const ideal | _G | ) |

Definition at line 1827 of file hdegree.cc.

{
id_Test(_G, currRing);
if (rField_is_Ring(currRing)) {
WerrorS("GK-Dim not implemented for rings");
return -2;
}
for (int i=IDELEMS(_G)-1;i>=0; i--)
{
if (_G->m[i] != NULL)
{
if (pGetComp(_G->m[i]) != 0)
{
WerrorS("GK-Dim not implemented for modules");
return -2;
}
if (pGetNCGen(_G->m[i]) != 0)
{
WerrorS("GK-Dim not implemented for bi-modules");
return -2;
}
}
}
ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
idSkipZeroes(G); // remove zeros
id_DelLmEquals(G, currRing); // remove duplicates
// check if G is the zero ideal
if (IDELEMS(G) == 1 && G->m[0] == NULL)
{
// NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
int lV = currRing->isLPring;
int ncGenCount = currRing->LPncGenCount;
if (lV - ncGenCount == 0)
{
idDelete(&G);
return 0;
}
if (lV - ncGenCount == 1)
{
idDelete(&G);
return 1;
}
if (lV - ncGenCount >= 2)
{
idDelete(&G);
return -1;
}
}
// get the max deg
long maxDeg = 0;
for (int i = 0; i < IDELEMS(G); i++)
{
maxDeg = si_max(maxDeg, pTotaldegree(G->m[i]));
// also check whether G = <1>
if (pIsConstantComp(G->m[i]))
{
WerrorS("GK-Dim not defined for 0-ring");
idDelete(&G);
return -2;
}
}
// early termination if G \subset X
if (maxDeg <= 1)
{
int lV = currRing->isLPring;
int ncGenCount = currRing->LPncGenCount;
if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
{
idDelete(&G);
return 0;
}
if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
{
idDelete(&G);
return 1;
}
if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
{
idDelete(&G);
return -1;
}
}
ideal standardWords;
intvec* UG = lp_ufnarovskiGraph(G, standardWords);
if (UG == NULL)
{
idDelete(&G);
return -2;
}
if (errorreported)
{
delete UG;
idDelete(&G);
return -2;
}
int gkDim = graphGrowth(UG);
delete UG;
idDelete(&G);
return gkDim;
}
graphGrowth
static int graphGrowth(const intvec *G)
Definition hdegree.cc:1639
lp_ufnarovskiGraph
intvec * lp_ufnarovskiGraph(ideal G, ideal &standardWords)
Definition hdegree.cc:1766
pGetComp
#define pGetComp(p)
Component.
Definition polys.h:38
pIsConstantComp
#define pIsConstantComp(p)
return true if p is either NULL, or if all exponents of p are 0, Comp of p might be !...
Definition polys.h:237
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491
pGetNCGen
#define pGetNCGen(p)
Definition shiftop.h:65
id_Head
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
Definition simpleideals.cc:1483
id_DelLmEquals
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.
Definition simpleideals.cc:354

## lp_kDim()

int lp_kDim | ( | const ideal | _G | ) |

Definition at line 2081 of file hdegree.cc.

{
if (rField_is_Ring(currRing)) {
WerrorS("K-Dim not implemented for rings");
return -2;
}
for (int i=IDELEMS(_G)-1;i>=0; i--)
{
if (_G->m[i] != NULL)
{
if (pGetComp(_G->m[i]) != 0)
{
WerrorS("K-Dim not implemented for modules");
return -2;
}
if (pGetNCGen(_G->m[i]) != 0)
{
WerrorS("K-Dim not implemented for bi-modules");
return -2;
}
}
}
ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
if (TEST_OPT_PROT)
Print("%d original generators\n", IDELEMS(G));
idSkipZeroes(G); // remove zeros
id_DelLmEquals(G, currRing); // remove duplicates
if (TEST_OPT_PROT)
Print("%d non-zero unique generators\n", IDELEMS(G));
// check if G is the zero ideal
if (IDELEMS(G) == 1 && G->m[0] == NULL)
{
// NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
int lV = currRing->isLPring;
int ncGenCount = currRing->LPncGenCount;
if (lV - ncGenCount == 0)
{
idDelete(&G);
return 1;
}
if (lV - ncGenCount == 1)
{
idDelete(&G);
return -1;
}
if (lV - ncGenCount >= 2)
{
idDelete(&G);
return -1;
}
}
// get the max deg
long maxDeg = 0;
for (int i = 0; i < IDELEMS(G); i++)
{
maxDeg = si_max(maxDeg, pTotaldegree(G->m[i]));
// also check whether G = <1>
if (pIsConstantComp(G->m[i]))
{
WerrorS("K-Dim not defined for 0-ring"); // TODO is it minus infinity ?
idDelete(&G);
return -2;
}
}
if (TEST_OPT_PROT)
Print("max deg: %ld\n", maxDeg);
// for normal words of length minDeg ... maxDeg-1
// brute-force the normal words
if (TEST_OPT_PROT)
PrintS("Computing normal words normally...\n");
long numberOfNormalWords = lp_countNormalWords(maxDeg - 1, G);
if (TEST_OPT_PROT)
Print("%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
// early termination if G \subset X
if (maxDeg <= 1)
{
int lV = currRing->isLPring;
int ncGenCount = currRing->LPncGenCount;
if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
{
idDelete(&G);
return numberOfNormalWords;
}
if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
{
idDelete(&G);
return -1;
}
if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
{
idDelete(&G);
return -1;
}
}
if (TEST_OPT_PROT)
PrintS("Computing Ufnarovski graph...\n");
ideal standardWords;
intvec* UG = lp_ufnarovskiGraph(G, standardWords);
if (UG == NULL)
{
idDelete(&G);
return -2;
}
if (errorreported)
{
delete UG;
idDelete(&G);
return -2;
}
if (TEST_OPT_PROT)
Print("Ufnarovski graph is %dx%d.\n", UG->rows(), UG->cols());
if (TEST_OPT_PROT)
PrintS("Checking whether Ufnarovski graph is acyclic...\n");
if (!isAcyclic(UG))
{
// in this case we have infinitely many normal words
return -1;
}
std::vector<std::vector<int> > vvUG = iv2vv(UG);
for (std::vector<std::vector<int> >::size_type i = 0; i < vvUG.size(); i++)
{
if (vvIsRowZero(vvUG, i) && vvIsColumnZero(vvUG, i)) // i is isolated vertex
{
vvDeleteRow(vvUG, i);
vvDeleteColumn(vvUG, i);
i--;
}
}
if (TEST_OPT_PROT)
Print("Simplified Ufnarovski graph to %dx%d.\n", (int)vvUG.size(), (int)vvUG.size());
// for normal words of length >= maxDeg
// use Ufnarovski graph
if (TEST_OPT_PROT)
PrintS("Computing normal words via Ufnarovski graph...\n");
std::vector<std::vector<int> > UGpower = vvUG;
long nUGpower = 1;
while (!vvIsZero(UGpower))
{
if (TEST_OPT_PROT)
PrintS("Start count graph entries.\n");
for (std::vector<std::vector<int> >::size_type i = 0; i < UGpower.size(); i++)
{
for (std::vector<std::vector<int> >::size_type j = 0; j < UGpower[i].size(); j++)
{
numberOfNormalWords += UGpower[i][j];
}
}
if (TEST_OPT_PROT)
{
PrintS("Done count graph entries.\n");
Print("%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
}
if (TEST_OPT_PROT)
PrintS("Start mat mult.\n");
UGpower = vvMult(UGpower, vvUG); // TODO: avoid creation of new intvec
if (TEST_OPT_PROT)
PrintS("Done mat mult.\n");
nUGpower++;
}
delete UG;
idDelete(&G);
return numberOfNormalWords;
}
intvec::cols
int cols() const
Definition intvec.h:96
intvec::rows
int rows() const
Definition intvec.h:97
Print
#define Print
Definition emacs.cc:80
vvMult
static std::vector< std::vector< int > > vvMult(const std::vector< std::vector< int > > &a, const std::vector< std::vector< int > > &b)
Definition hdegree.cc:2027
vvDeleteRow
static void vvDeleteRow(std::vector< std::vector< int > > &mat, int row)
Definition hdegree.cc:1984
vvIsColumnZero
static BOOLEAN vvIsColumnZero(const std::vector< std::vector< int > > &mat, int col)
Definition hdegree.cc:2007
vvDeleteColumn
static void vvDeleteColumn(std::vector< std::vector< int > > &mat, int col)
Definition hdegree.cc:1989
iv2vv
static std::vector< std::vector< int > > iv2vv(intvec *M)
Definition hdegree.cc:1937
lp_countNormalWords
static int lp_countNormalWords(int upToLength, ideal M)
Definition hdegree.cc:1745
isAcyclic
static BOOLEAN isAcyclic(const intvec *G)
Definition hdegree.cc:2054
vvIsZero
static BOOLEAN vvIsZero(const std::vector< std::vector< int > > &mat)
Definition hdegree.cc:2017
vvIsRowZero
static BOOLEAN vvIsRowZero(const std::vector< std::vector< int > > &mat, int row)
Definition hdegree.cc:1997
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition options.h:105
PrintS
void PrintS(const char *s)
Definition reporter.cc:288

## lp_ufnarovskiGraph()

intvec * lp_ufnarovskiGraph | ( | ideal | G,
|  | ideal & | standardWords )

Definition at line 1766 of file hdegree.cc.

{
long l = 0;
for (int i = 0; i < IDELEMS(G); i++)
l = si_max(pTotaldegree(G->m[i]), l);
l--;
if (l <= 0)
{
WerrorS("Ufnarovski graph not implemented for l <= 0");
return NULL;
}
int lV = currRing->isLPring;
standardWords = lp_computeNormalWords(l, G);
int n = IDELEMS(standardWords);
intvec* UG = new intvec(n, n, 0);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
poly v = standardWords->m[i];
poly w = standardWords->m[j];
// check whether v*x1 = x2*w (overlap)
bool overlap = true;
for (int k = 1; k <= (l - 1) * lV; k++)
{
if (pGetExp(v, k + lV) != pGetExp(w, k)) {
overlap = false;
break;
}
}
if (overlap)
{
// create the overlap
poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing));
// check whether the overlap is normal
bool normal = true;
for (int k = 0; k < IDELEMS(G); k++)
{
if (p_LPDivisibleBy(G->m[k], p, currRing))
{
normal = false;
break;
}
}
if (normal)
{
IMATELEM(*UG, i + 1, j + 1) = 1;
}
}
}
}
return UG;
}
l
int l
Definition cfEzgcd.cc:100
p
int p
Definition cfModGcd.cc:4086
lp_computeNormalWords
static ideal lp_computeNormalWords(int length, ideal M)
Definition hdegree.cc:1725
pMult
#define pMult(p, q)
Definition polys.h:208
p_LPVarAt
poly p_LPVarAt(poly p, int pos, const ring r)
Definition shiftop.cc:845

## scAll()

void scAll | ( | int | Nvar,
|  | int | deg )

static

Definition at line 1225 of file hdegree.cc.

{
int i;
int d = deg;
if (d == 0)
{
for (i=Nvar; i; i--) act[i] = 0;
scElKbase();
return;
}
if (Nvar == 1)
{
act[1] = d;
scElKbase();
return;
}
do
{
act[Nvar] = d;
scAll(Nvar-1, deg-d);
d--;
} while (d >= 0);
}
scElKbase
static void scElKbase()
Definition hdegree.cc:1141
scAll
static void scAll(int Nvar, int deg)
Definition hdegree.cc:1225
act
STATIC_VAR scmon act
Definition hdegree.cc:1139

## scAllKbase()

void scAllKbase | ( | int | Nvar,
|  | int | ideg,
|  | int | deg )

static

Definition at line 1249 of file hdegree.cc.

{
do
{
act[Nvar] = ideg;
scAll(Nvar-1, deg-ideg);
ideg--;
} while (ideg >= 0);
}

## scComputeHC()

void scComputeHC | ( | ideal | S,
|  | ideal | Q,
|  | int | ak,
|  | poly & | hEdge )

Definition at line 1074 of file hdegree.cc.

{
if(idElem(S) == 0)
return;
id_LmTest(S, currRing);
if (Q!=NULL) id_LmTest(Q, currRing);
int i;
int k = ak;
ideal SS=id_Head(S,currRing);
if (rField_is_Ring(currRing) && (currRing->OrdSgn == -1))
{
//consider just monic generators (over rings with zero-divisors)
for(i=0;i<=idElem(S);i++)
{
if((SS->m[i]!=NULL)
&& ((p_IsPurePower(SS->m[i],currRing)==0)
||(!n_IsUnit(pGetCoeff(SS->m[i]), currRing->cf))))
{
p_Delete(&SS->m[i],currRing);
}
}
}
S=SS;
idSkipZeroes(S);
hNvar = (currRing->N);
hexist = hInit(S, Q, &hNexist);
if (hNexist==0) return;
if (k!=0)
hComp(hexist, hNexist, k, hexist, &hNstc);
else
hNstc = hNexist;
assume(hNexist > 0);
hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
hvar = (varset)omAlloc((hNvar + 1) * sizeof(int));
hpure = (scmon)omAlloc((1 + (hNvar * hNvar)) * sizeof(int));
stcmem = hCreate(hNvar - 1);
for (i = hNvar; i>0; i--)
hvar[i] = i;
hStaircase(hexist, &hNstc, hvar, hNvar);
if ((hNvar > 2) && (hNstc > 10))
hOrdSupp(hexist, hNstc, hvar, hNvar);
memset(hpure, 0, (hNvar + 1) * sizeof(int));
hPure(hexist, 0, &hNstc, hvar, hNvar, hpure, &hNpure);
hLexS(hexist, hNstc, hvar, hNvar);
if (hEdge!=NULL)
pLmFree(hEdge);
hEdge = pInit();
pWork = pInit();
hHedgeStep(hpure, hexist, hNstc, hvar, hNvar,hEdge);
pSetComp(hEdge,ak);
hKill(stcmem, hNvar - 1);
omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
omFreeSize((ADDRESS)hvar, (hNvar + 1) * sizeof(int));
omFreeSize((ADDRESS)hpure, (1 + (hNvar * hNvar)) * sizeof(int));
hDelete(hexist, hNexist);
pLmFree(pWork);
idDelete(&S);
}
n_IsUnit
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.
Definition coeffs.h:521
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition monomials.h:44
p_IsPurePower
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition p_polys.cc:1227
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
pSetComp
#define pSetComp(p, v)
Definition polys.h:39
pLmFree
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition polys.h:71
pInit
#define pInit()
allocates a new monomial and initializes everything to 0
Definition polys.h:62
idElem
static int idElem(const ideal F)
number of non-zero polys in F
Definition simpleideals.h:69
id_LmTest
#define id_LmTest(A, lR)
Definition simpleideals.h:90

## scDegKbase()

void scDegKbase | ( | scfmon | stc,
|  | int | Nstc,
|  | int | Nvar,
|  | int | deg )

static

Definition at line 1259 of file hdegree.cc.

{
int Ivar, Istc, i, j;
scfmon sn;
int x, ideg;
if (deg == 0)
{
for (i=Nstc-1; i>=0; i--)
{
for (j=Nvar;j;j--){ if(stc[i][j]) break; }
if (j==0){return;}
}
for (i=Nvar; i; i--) act[i] = 0;
scElKbase();
return;
}
if (Nvar == 1)
{
for (i=Nstc-1; i>=0; i--) if(deg >= stc[i][1]) return;
act[1] = deg;
scElKbase();
return;
}
Ivar = Nvar-1;
sn = hGetmem(Nstc, stc, stcmem[Ivar]);
x = scRestrict(Nstc, sn, Nvar);
if (x <= 0)
{
if (x == 0) return;
ideg = deg;
}
else
{
if (deg < x) ideg = deg;
else ideg = x-1;
if (Nstc == 0)
{
scAllKbase(Nvar, ideg, deg);
return;
}
}
loop
{
x = scMax(Nstc, sn, Nvar);
while (ideg >= x)
{
act[Nvar] = ideg;
scDegKbase(sn, Nstc, Ivar, deg-ideg);
ideg--;
}
if (ideg < 0) return;
Istc = Nstc;
for (i=Nstc-1; i>=0; i--)
{
if (ideg < sn[i][Nvar])
{
Istc--;
sn[i] = NULL;
}
}
if (Istc == 0)
{
scAllKbase(Nvar, ideg, deg);
return;
}
j = 0;
while (sn[j]) j++;
i = j+1;
for (; i<Nstc; i++)
{
if (sn[i])
{
sn[j] = sn[i];
j++;
}
}
Nstc = Istc;
}
}
scRestrict
static int scRestrict(int &Nstc, scfmon stc, int Nvar)
Definition hdegree.cc:1174
scAllKbase
static void scAllKbase(int Nvar, int ideg, int deg)
Definition hdegree.cc:1249
scDegKbase
static void scDegKbase(scfmon stc, int Nstc, int Nvar, int deg)
Definition hdegree.cc:1259
scMax
static int scMax(int i, scfmon stc, int Nvar)
Definition hdegree.cc:1150

## scDimInt()

int scDimInt | ( | ideal | S,
|  | ideal | Q )

ideal dimension

Definition at line 78 of file hdegree.cc.

{
id_Test(S, currRing);
if( Q!=NULL ) id_Test(Q, currRing);
int mc;
hexist = hInit(S, Q, &hNexist);
if (!hNexist)
return (currRing->N);
hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
mc = hisModule;
if (!mc)
{
hrad = hexist;
hNrad = hNexist;
}
else
hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
radmem = hCreate((currRing->N) - 1);
hCo = (currRing->N) + 1;
loop
{
if (mc)
hComp(hexist, hNexist, mc, hrad, &hNrad);
if (hNrad)
{
hNvar = (currRing->N);
hRadical(hrad, &hNrad, hNvar);
hSupp(hrad, hNrad, hvar, &hNvar);
if (hNvar)
{
memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
hLexR(hrad, hNrad, hvar, hNvar);
hDimSolve(hpure, hNpure, hrad, hNrad, hvar, hNvar);
}
}
else
{
hCo = 0;
break;
}
mc--;
if (mc <= 0)
break;
}
hKill(radmem, (currRing->N) - 1);
omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
hDelete(hexist, hNexist);
if (hisModule)
omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
return (currRing->N) - hCo;
}

## scDimIntRing()

int scDimIntRing | ( | ideal | vid,
|  | ideal | Q )

scDimInt for ring-coefficients

Definition at line 136 of file hdegree.cc.

{
if (rField_is_Ring(currRing))
{
int i = idPosConstant(vid);
if ((i != -1) && (n_IsUnit(pGetCoeff(vid->m[i]),currRing->cf)))
{ /* ideal v contains unit; dim = -1 */
return(-1);
}
ideal vv = id_Head(vid,currRing);
idSkipZeroes(vv);
i = idPosConstant(vid);
int d;
if(i == -1)
{
d = scDimInt(vv, Q);
if(rField_is_Z(currRing))
d++;
}
else
{
if(n_IsUnit(pGetCoeff(vv->m[i]),currRing->cf))
d = -1;
else
d = scDimInt(vv, Q);
}
//Anne's Idea for std(4,2x) = 0 bug
int dcurr = d;
for(unsigned ii=0;ii<(unsigned)IDELEMS(vv);ii++)
{
if(vv->m[ii] != NULL && !n_IsUnit(pGetCoeff(vv->m[ii]),currRing->cf))
{
ideal vc = idCopy(vv);
poly c = pInit();
pSetCoeff0(c,nCopy(pGetCoeff(vv->m[ii])));
idInsertPoly(vc,c);
idSkipZeroes(vc);
for(unsigned jj = 0;jj<(unsigned)IDELEMS(vc)-1;jj++)
{
if((vc->m[jj]!=NULL)
&& (n_DivBy(pGetCoeff(vc->m[jj]),pGetCoeff(c),currRing->cf)))
{
pDelete(&vc->m[jj]);
}
}
idSkipZeroes(vc);
i = idPosConstant(vc);
if (i != -1) pDelete(&vc->m[i]);
dcurr = scDimInt(vc, Q);
// the following assumes the ground rings to be either zero- or one-dimensional
if((i==-1) && rField_is_Z(currRing))
{
// should also be activated for other euclidean domains as groundfield
dcurr++;
}
idDelete(&vc);
}
if(dcurr > d)
d = dcurr;
}
idDelete(&vv);
return d;
}
return scDimInt(vid,Q);
}
n_DivBy
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:...
Definition coeffs.h:750
scDimInt
int scDimInt(ideal S, ideal Q)
ideal dimension
Definition hdegree.cc:78
idInsertPoly
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
Definition simpleideals.cc:832
idCopy
ideal idCopy(ideal A)
Definition ideals.h:60
idPosConstant
#define idPosConstant(I)
index of generator with leading term in ground ring (if any); otherwise -1
Definition ideals.h:37
pSetCoeff0
#define pSetCoeff0(p, n)
Definition monomials.h:59
nCopy
#define nCopy(n)
Definition numbers.h:15
rField_is_Z
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:515

## scElKbase()

void scElKbase | ( |  | ) |

static

Definition at line 1141 of file hdegree.cc.

{
poly q = pInit();
pSetCoeff0(q,nInit(1));
pSetExpV(q,act);
pNext(q) = NULL;
last = pNext(last) = q;
}
pNext
#define pNext(p)
Definition monomials.h:36
nInit
#define nInit(i)
Definition numbers.h:24
pSetExpV
#define pSetExpV(p, e)
Definition polys.h:98

## scIdKbase()

ideal scIdKbase | ( | poly | q,
|  | const int | rank )

static

Definition at line 1396 of file hdegree.cc.

{
ideal res = idInit(pLength(q), rank);
polyset mm = res->m;
do
{
*mm = q; ++mm;
const poly p = pNext(q);
pNext(q) = NULL;
q = p;
} while (q!=NULL);
id_Test(res, currRing); // WRONG RANK!!!???
return res;
}
pLength
static int pLength(poly a)
Definition p_polys.h:190
polyset
poly * polyset
Definition polys.h:260

## scIndIntvec()

intvec * scIndIntvec | ( | ideal | S,
|  | ideal | Q )

Definition at line 284 of file hdegree.cc.

{
id_Test(S, currRing);
if( Q!=NULL ) id_Test(Q, currRing);
intvec *Set=new intvec((currRing->N));
int mc,i;
hexist = hInit(S, Q, &hNexist);
if (hNexist==0)
{
for(i=0; i<(currRing->N); i++)
(*Set)[i]=1;
return Set;
}
hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
hInd = (scmon)omAlloc0((1 + (currRing->N)) * sizeof(int));
mc = hisModule;
if (mc==0)
{
hrad = hexist;
hNrad = hNexist;
}
else
hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
radmem = hCreate((currRing->N) - 1);
hCo = (currRing->N) + 1;
loop
{
if (mc!=0)
hComp(hexist, hNexist, mc, hrad, &hNrad);
if (hNrad!=0)
{
hNvar = (currRing->N);
hRadical(hrad, &hNrad, hNvar);
hSupp(hrad, hNrad, hvar, &hNvar);
if (hNvar!=0)
{
memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
hLexR(hrad, hNrad, hvar, hNvar);
hIndSolve(hpure, hNpure, hrad, hNrad, hvar, hNvar);
}
}
else
{
hCo = 0;
break;
}
mc--;
if (mc <= 0)
break;
}
for(i=0; i<(currRing->N); i++)
(*Set)[i] = hInd[i+1];
hKill(radmem, (currRing->N) - 1);
omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
omFreeSize((ADDRESS)hInd, (1 + (currRing->N)) * sizeof(int));
omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
hDelete(hexist, hNexist);
if (hisModule)
omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
return Set;
}
omAlloc0
#define omAlloc0(size)
Definition omAllocDecl.h:211

## scInKbase()

void scInKbase | ( | scfmon | stc,
|  | int | Nstc,
|  | int | Nvar )

static

Definition at line 1340 of file hdegree.cc.

{
int Ivar, Istc, i, j;
scfmon sn;
int x, ideg;
if (Nvar == 1)
{
ideg = scMin(Nstc, stc, 1);
while (ideg > 0)
{
ideg--;
act[1] = ideg;
scElKbase();
}
return;
}
Ivar = Nvar-1;
sn = hGetmem(Nstc, stc, stcmem[Ivar]);
x = scRestrict(Nstc, sn, Nvar);
if (x == 0) return;
ideg = x-1;
loop
{
x = scMax(Nstc, sn, Nvar);
while (ideg >= x)
{
act[Nvar] = ideg;
scInKbase(sn, Nstc, Ivar);
ideg--;
}
if (ideg < 0) return;
Istc = Nstc;
for (i=Nstc-1; i>=0; i--)
{
if (ideg < sn[i][Nvar])
{
Istc--;
sn[i] = NULL;
}
}
j = 0;
while (sn[j]) j++;
i = j+1;
for (; i<Nstc; i++)
{
if (sn[i])
{
sn[j] = sn[i];
j++;
}
}
Nstc = Istc;
}
}
scMin
static int scMin(int i, scfmon stc, int Nvar)
Definition hdegree.cc:1162
scInKbase
static void scInKbase(scfmon stc, int Nstc, int Nvar)
Definition hdegree.cc:1340

## scKBase()

ideal scKBase | ( | int | deg,
|  | ideal | s,
|  | ideal | Q,
|  | intvec * | mv )

Definition at line 1414 of file hdegree.cc.

{
if( Q!=NULL) id_Test(Q, currRing);
int i, di;
poly p;
if (deg < 0)
{
di = scDimInt(s, Q);
if (di != 0)
{
//Werror("KBase not finite");
return idInit(1,s->rank);
}
}
stcmem = hCreate((currRing->N) - 1);
hexist = hInit(s, Q, &hNexist);
p = last = pInit();
/*pNext(p) = NULL;*/
act = (scmon)omAlloc(((currRing->N) + 1) * sizeof(int));
*act = 0;
if (!hNexist)
{
scAll((currRing->N), deg);
goto ende;
}
if (!hisModule)
{
if (deg < 0) scInKbase(hexist, hNexist, (currRing->N));
else scDegKbase(hexist, hNexist, (currRing->N), deg);
}
else
{
hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
for (i = 1; i <= hisModule; i++)
{
*act = i;
hComp(hexist, hNexist, i, hstc, &hNstc);
int deg_ei=deg;
if (mv!=NULL) deg_ei -= (*mv)[i-1];
if ((deg < 0) || (deg_ei>=0))
{
if (hNstc)
{
if (deg < 0) scInKbase(hstc, hNstc, (currRing->N));
else scDegKbase(hstc, hNstc, (currRing->N), deg_ei);
}
else
scAll((currRing->N), deg_ei);
}
}
omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
}
ende:
hDelete(hexist, hNexist);
omFreeSize((ADDRESS)act, ((currRing->N) + 1) * sizeof(int));
hKill(stcmem, (currRing->N) - 1);
pLmFree(&p);
if (p == NULL)
return idInit(1,s->rank);
last = p;
return scIdKbase(p, s->rank);
}
s
const CanonicalForm int s
Definition facAbsFact.cc:51
scIdKbase
static ideal scIdKbase(poly q, const int rank)
Definition hdegree.cc:1396

## scMax()

int scMax | ( | int | i,
|  | scfmon | stc,
|  | int | Nvar )

static

Definition at line 1150 of file hdegree.cc.

{
int x, y=stc[0][Nvar];
for (; i;)
{
i--;
x = stc[i][Nvar];
if (x > y) y = x;
}
return y;
}
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53

## scMin()

int scMin | ( | int | i,
|  | scfmon | stc,
|  | int | Nvar )

static

Definition at line 1162 of file hdegree.cc.

{
int x, y=stc[0][Nvar];
for (; i;)
{
i--;
x = stc[i][Nvar];
if (x < y) y = x;
}
return y;
}

## scMult0Int()

long scMult0Int | ( | ideal | S,
|  | ideal | Q )

Definition at line 924 of file hdegree.cc.

{
id_LmTest(S, currRing);
if (Q!=NULL) id_LmTest(Q, currRing);
int mc;
hexist = hInit(S, Q, &hNexist);
if (!hNexist)
{
hMu = -1;
return -1;
}
else
hMu = 0;
const ring r = currRing;
hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
hvar = (varset)omAlloc(((r->N) + 1) * sizeof(int));
hpur0 = (scmon)omAlloc((1 + ((r->N) * (r->N))) * sizeof(int));
mc = hisModule;
if (!mc)
{
hstc = hexist;
hNstc = hNexist;
}
else
hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
stcmem = hCreate((r->N) - 1);
loop
{
if (mc)
{
hComp(hexist, hNexist, mc, hstc, &hNstc);
if (!hNstc)
{
hMu = -1;
break;
}
}
hNvar = (r->N);
for (int i = hNvar; i; i--)
hvar[i] = i;
hStaircase(hstc, &hNstc, hvar, hNvar);
hSupp(hstc, hNstc, hvar, &hNvar);
if ((hNvar == (r->N)) && (hNstc >= (r->N)))
{
if ((hNvar > 2) && (hNstc > 10))
hOrdSupp(hstc, hNstc, hvar, hNvar);
memset(hpur0, 0, ((r->N) + 1) * sizeof(int));
hPure(hstc, 0, &hNstc, hvar, hNvar, hpur0, &hNpure);
if (hNpure == hNvar)
{
hLexS(hstc, hNstc, hvar, hNvar);
hMu += hZeroMult(hpur0, hstc, hNstc, hvar, hNvar);
}
else
hMu = -1;
}
else if (hNvar)
hMu = -1;
mc--;
if (mc <= 0 || hMu < 0)
break;
}
hKill(stcmem, (r->N) - 1);
omFreeSize((ADDRESS)hpur0, (1 + ((r->N) * (r->N))) * sizeof(int));
omFreeSize((ADDRESS)hvar, ((r->N) + 1) * sizeof(int));
omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
hDelete(hexist, hNexist);
if (hisModule)
omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
return hMu;
}

## scMultInt()

int scMultInt | ( | ideal | S,
|  | ideal | Q )

Definition at line 901 of file hdegree.cc.

{
id_Test(S, currRing);
if( Q!=NULL ) id_Test(Q, currRing);
hDegree(S, Q);
return hMu;
}
hDegree
static void hDegree(ideal S, ideal Q)
Definition hdegree.cc:800

## scPrintDegree()

void scPrintDegree | ( | int | co,
|  | int | mu )

Definition at line 910 of file hdegree.cc.

{
int di = (currRing->N)-co;
if (currRing->OrdSgn == 1)
{
if (di>0)
Print("// dimension (proj.) = %d\n// degree (proj.) = %d\n", di-1, mu);
else
Print("// dimension (affine) = 0\n// degree (affine) = %d\n", mu);
}
else
Print("// dimension (local) = %d\n// multiplicity = %d\n", di, mu);
}
mu
static matrix mu(matrix A, const ring R)
Definition matpol.cc:2028

## scRestrict()

int scRestrict | ( | int & | Nstc,
|  | scfmon | stc,
|  | int | Nvar )

static

Definition at line 1174 of file hdegree.cc.

{
int x, y;
int i, j, Istc = Nstc;
y = MAX_INT_VAL;
for (i=Nstc-1; i>=0; i--)
{
j = Nvar-1;
loop
{
if(stc[i][j] != 0) break;
j--;
if (j == 0)
{
Istc--;
x = stc[i][Nvar];
if (x < y) y = x;
stc[i] = NULL;
break;
}
}
}
if (Istc < Nstc)
{
for (i=Nstc-1; i>=0; i--)
{
if (stc[i] && (stc[i][Nvar] >= y))
{
Istc--;
stc[i] = NULL;
}
}
j = 0;
while (stc[j]) j++;
i = j+1;
for(; i<Nstc; i++)
{
if (stc[i])
{
stc[j] = stc[i];
j++;
}
}
Nstc = Istc;
return y;
}
else
return -1;
}
MAX_INT_VAL
const int MAX_INT_VAL
Definition mylimits.h:12

## vvDeleteColumn()

void vvDeleteColumn | ( | std::vector< std::vector< int > > & | mat,
|  | int | col )

static

Definition at line 1989 of file hdegree.cc.

{
for (std::vector<std::vector<int> >::size_type i = 0; i < mat.size(); i++)
{
mat[i].erase(mat[i].begin() + col);
}
}

## vvDeleteRow()

void vvDeleteRow | ( | std::vector< std::vector< int > > & | mat,
|  | int | row )

static

Definition at line 1984 of file hdegree.cc.

{
mat.erase(mat.begin() + row);
}

## vvIsColumnZero()

BOOLEAN vvIsColumnZero | ( | const std::vector< std::vector< int > > & | mat,
|  | int | col )

static

Definition at line 2007 of file hdegree.cc.

{
for (std::vector<std::vector<int> >::size_type i = 0; i < mat.size(); i++)
{
if (mat[i][col] != 0)
return FALSE;
}
return TRUE;
}

## vvIsRowZero()

BOOLEAN vvIsRowZero | ( | const std::vector< std::vector< int > > & | mat,
|  | int | row )

static

Definition at line 1997 of file hdegree.cc.

{
for (std::vector<std::vector<int> >::size_type i = 0; i < mat[row].size(); i++)
{
if (mat[row][i] != 0)
return FALSE;
}
return TRUE;
}

## vvIsZero()

BOOLEAN vvIsZero | ( | const std::vector< std::vector< int > > & | mat | ) |

static

Definition at line 2017 of file hdegree.cc.

{
for (std::vector<std::vector<int> >::size_type i = 0; i < mat.size(); i++)
{
if (!vvIsRowZero(mat, i))
return FALSE;
}
return TRUE;
}

## vvMult()

std::vector< std::vector< int > > vvMult | ( | const std::vector< std::vector< int > > & | a,
|  | const std::vector< std::vector< int > > & | b )

static

Definition at line 2027 of file hdegree.cc.

{
std::vector<std::vector<int> >::size_type ra = a.size();
std::vector<std::vector<int> >::size_type rb = b.size();
std::vector<std::vector<int> >::size_type ca = a.size() > 0 ? a[0].size() : 0;
std::vector<std::vector<int> >::size_type cb = b.size() > 0 ? b[0].size() : 0;
if (ca != rb)
{
WerrorS("matrix dimensions do not match");
return std::vector<std::vector<int> >();
}
std::vector<std::vector<int> > res(ra, std::vector<int>(cb));
for (std::vector<std::vector<int> >::size_type i = 0; i < ra; i++)
{
for (std::vector<std::vector<int> >::size_type j = 0; j < cb; j++)
{
int sum = 0;
for (std::vector<std::vector<int> >::size_type k = 0; k < ca; k++)
sum += a[i][k] * b[k][j];
res[i][j] = sum;
}
}
return res;
}

## Variable Documentation

## act

STATIC_VAR scmon act

Definition at line 1139 of file hdegree.cc.

## hCo

VAR int hCo

Definition at line 27 of file hdegree.cc.

## hInd

STATIC_VAR scmon hInd

Definition at line 203 of file hdegree.cc.

## hMu

VAR long hMu

Definition at line 28 of file hdegree.cc.

## hMu2

VAR int hMu2

Definition at line 27 of file hdegree.cc.

## indlist_bin

VAR omBin indlist_bin = omGetSpecBin(sizeof(indlist))

Definition at line 29 of file hdegree.cc.

## ISet

VAR indset ISet

Definition at line 351 of file hdegree.cc.

## JSet

VAR indset JSet

Definition at line 351 of file hdegree.cc.

## last

STATIC_VAR poly last

Definition at line 1138 of file hdegree.cc.

## pWork

STATIC_VAR poly pWork

Definition at line 1001 of file hdegree.cc.