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;
}

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;
}

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;
}

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;
}

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;
  }
}

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);
      }
    }
  }
}

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));
}

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);
  }
}

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);
  }
}

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;
    }
  }
}

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);
  }
}

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);
  }
}

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;
  }
}

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;
    }
  }
}

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;
}

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;
}

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;
}

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;
}

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;
}

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);
}

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);
}

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;
  }
}

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);
}

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;
}

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;
}

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;
}

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;
  }
}

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);
}

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;
}

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;
}

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);
}

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;
}

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.