My Project
Functions | Variables
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 More...
 
int scDimIntRing (ideal vid, ideal Q)
 scDimInt for ring-coefficients More...
 
static void hIndSolve (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
 
intvecscIndIntvec (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)
 
void scDegree (ideal S, intvec *modulweight, ideal Q)
 
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)
 
intveclp_ufnarovskiGraph (ideal G, ideal &standardWords)
 
int lp_gkDim (const ideal _G)
 
static std::vector< std::vector< int > > iv2vv (intvec *M)
 
static void vvPrint (const std::vector< std::vector< int > > &mat)
 
static void vvTest (const std::vector< std::vector< int > > &mat)
 
static void 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()

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

Definition at line 1701 of file hdegree.cc.

1702 {
1703  if (length <= 0){
1704  poly one = pOne();
1705  if (p_LPDivisibleBy(M, one, currRing)) // 1 \in M => no normal words at all
1706  {
1707  pDelete(&one);
1708  last = -1;
1709  numberOfNormalWords = 0;
1710  }
1711  else
1712  {
1713  words->m[0] = one;
1714  last = 0;
1715  numberOfNormalWords = 1;
1716  }
1717  return;
1718  }
1719 
1720  _lp_computeNormalWords(words, numberOfNormalWords, length - 1, M, minDeg, last);
1721 
1722  int nVars = currRing->isLPring - currRing->LPncGenCount;
1723  int numberOfNewNormalWords = 0;
1724 
1725  for (int j = nVars - 1; j >= 0; j--)
1726  {
1727  for (int i = last; i >= 0; i--)
1728  {
1729  int index = (j * (last + 1)) + i;
1730 
1731  if (words->m[i] != NULL)
1732  {
1733  if (j > 0) {
1734  words->m[index] = pCopy(words->m[i]);
1735  }
1736 
1737  int varOffset = ((length - 1) * currRing->isLPring) + 1;
1738  pSetExp(words->m[index], varOffset + j, 1);
1739  pSetm(words->m[index]);
1740  pTest(words->m[index]);
1741 
1742  if (length >= minDeg && p_LPDivisibleBy(M, words->m[index], currRing))
1743  {
1744  pDelete(&words->m[index]);
1745  words->m[index] = NULL;
1746  }
1747  else
1748  {
1749  numberOfNewNormalWords++;
1750  }
1751  }
1752  }
1753  }
1754 
1755  last = nVars * last + nVars - 1;
1756 
1757  numberOfNormalWords += numberOfNewNormalWords;
1758 }
int i
Definition: cfEzgcd.cc:132
int j
Definition: facHensel.cc:110
STATIC_VAR poly last
Definition: hdegree.cc:1173
static void _lp_computeNormalWords(ideal words, int &numberOfNormalWords, int length, ideal M, int minDeg, int &last)
Definition: hdegree.cc:1701
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
#define NULL
Definition: omList.c:12
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
#define pTest(p)
Definition: polys.h:414
#define pDelete(p_ptr)
Definition: polys.h:186
#define pSetm(p)
Definition: polys.h:271
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define pOne()
Definition: polys.h:315
BOOLEAN p_LPDivisibleBy(poly a, poly b, const ring r)
Definition: shiftop.cc:776
#define M
Definition: sirandom.c:25

◆ 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 
)
static

Definition at line 1610 of file hdegree.cc.

1611 {
1612  intvec* G = ivCopy(_G); // modifications must be local
1613 
1614  if (cache[v] != -2) return cache; // value is already cached
1615 
1616  visited[v] = TRUE;
1617  path.push_back(v);
1618 
1619  int cycles = 0;
1620  for (int w = 0; w < G->cols(); w++)
1621  {
1622  if (IMATELEM(*G, v + 1, w + 1)) // edge v -> w exists in G
1623  {
1624  if (!visited[w])
1625  { // continue with w
1626  cache = countCycles(G, w, path, visited, cyclic, cache);
1627  if (cache[w] == -1)
1628  {
1629  cache[v] = -1;
1630  return cache;
1631  }
1632  cycles = si_max(cycles, cache[w]);
1633  }
1634  else
1635  { // found new cycle
1636  int pathIndexOfW = -1;
1637  for (int i = path.size() - 1; i >= 0; i--) {
1638  if (cyclic[path[i]] == 1) { // found an already cyclic vertex
1639  cache[v] = -1;
1640  return cache;
1641  }
1642  cyclic[path[i]] = TRUE;
1643 
1644  if (path[i] == w) { // end of the cycle
1645  assume(IMATELEM(*G, v + 1, w + 1) != 0);
1646  IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v -> w
1647  pathIndexOfW = i;
1648  break;
1649  } else {
1650  assume(IMATELEM(*G, path[i - 1] + 1, path[i] + 1) != 0);
1651  IMATELEM(*G, path[i - 1] + 1, path[i] + 1) = 0; // remove edge vi-1 -> vi
1652  }
1653  }
1654  assume(pathIndexOfW != -1); // should never happen
1655  for (int i = path.size() - 1; i >= pathIndexOfW; i--) {
1656  cache = countCycles(G, path[i], path, visited, cyclic, cache);
1657  if (cache[path[i]] == -1)
1658  {
1659  cache[v] = -1;
1660  return cache;
1661  }
1662  cycles = si_max(cycles, cache[path[i]] + 1);
1663  }
1664  }
1665  }
1666  }
1667  cache[v] = cycles;
1668 
1669  delete G;
1670  return cache;
1671 }
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
#define TRUE
Definition: auxiliary.h:100
Definition: intvec.h:23
const CanonicalForm & w
Definition: facAbsFact.cc:51
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
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:1610
#define IMATELEM(M, I, J)
Definition: intvec.h:85
intvec * ivCopy(const intvec *o)
Definition: intvec.h:145
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define assume(x)
Definition: mod2.h:389

◆ graphGrowth()

static int graphGrowth ( const intvec G)
static

Definition at line 1674 of file hdegree.cc.

1675 {
1676  // init
1677  int n = G->cols();
1678  std::vector<int> path;
1679  std::vector<BOOLEAN> visited;
1680  std::vector<BOOLEAN> cyclic;
1681  std::vector<int> cache;
1682  visited.resize(n, FALSE);
1683  cyclic.resize(n, FALSE);
1684  cache.resize(n, -2);
1685 
1686  // get max number of cycles
1687  int cycles = 0;
1688  for (int v = 0; v < n; v++)
1689  {
1690  cache = countCycles(G, v, path, visited, cyclic, cache);
1691  if (cache[v] == -1)
1692  return -1;
1693  cycles = si_max(cycles, cache[v]);
1694  }
1695  return cycles;
1696 }
#define FALSE
Definition: auxiliary.h:96

◆ hCheck1()

static BOOLEAN hCheck1 ( indset  sm,
scmon  pure 
)
static

Definition at line 465 of file hdegree.cc.

466 {
467  int iv;
468  intvec *Set;
469  while (sm->nx != NULL)
470  {
471  Set = sm->set;
472  iv=(currRing->N);
473  loop
474  {
475  if (((*Set)[iv-1] == 0) && (pure[iv] == 0))
476  break;
477  iv--;
478  if (iv == 0)
479  return FALSE;
480  }
481  sm = sm->nx;
482  }
483  return TRUE;
484 }
#define loop
Definition: structs.h:75

◆ hCheck2()

static indset hCheck2 ( indset  sm,
scmon  pure 
)
static

Definition at line 491 of file hdegree.cc.

492 {
493  int iv;
494  intvec *Set;
495  indset be, a1 = NULL;
496  while (sm->nx != NULL)
497  {
498  Set = sm->set;
499  iv=(currRing->N);
500  loop
501  {
502  if ((pure[iv] == 1) && ((*Set)[iv-1] == 1))
503  break;
504  iv--;
505  if (iv == 0)
506  {
507  if (a1 == NULL)
508  {
509  a1 = sm;
510  }
511  else
512  {
513  hMu2--;
514  be->nx = sm->nx;
515  delete Set;
517  sm = be;
518  }
519  break;
520  }
521  }
522  be = sm;
523  sm = sm->nx;
524  }
525  if (a1 != NULL)
526  {
527  return a1;
528  }
529  else
530  {
531  hMu2++;
532  sm->set = new intvec((currRing->N));
533  sm->nx = (indset)omAlloc0Bin(indlist_bin);
534  return sm;
535  }
536 }
void * ADDRESS
Definition: auxiliary.h:119
VAR omBin indlist_bin
Definition: hdegree.cc:29
VAR int hMu2
Definition: hdegree.cc:27
indlist * indset
Definition: hutil.h:28
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259

◆ hCheckIndep()

static void hCheckIndep ( scmon  pure)
static

Definition at line 543 of file hdegree.cc.

544 {
545  intvec *Set;
546  indset res;
547  int iv;
548  if (hCheck1(ISet, pure))
549  {
550  if (hCheck1(JSet, pure))
551  {
552  res = hCheck2(JSet,pure);
553  if (res == NULL)
554  return;
555  Set = res->set;
556  for (iv=(currRing->N); iv; iv--)
557  {
558  (*Set)[iv-1] = (pure[iv]==0);
559  }
560  }
561  }
562 }
CanonicalForm res
Definition: facAbsFact.cc:60
static indset hCheck2(indset sm, scmon pure)
Definition: hdegree.cc:491
static BOOLEAN hCheck1(indset sm, scmon pure)
Definition: hdegree.cc:465
VAR indset ISet
Definition: hdegree.cc:353
VAR indset JSet
Definition: hdegree.cc:353

◆ hDegree()

static void hDegree ( ideal  S,
ideal  Q 
)
static

Definition at line 802 of file hdegree.cc.

803 {
804  id_Test(S, currRing);
805  if( Q!=NULL ) id_Test(Q, currRing);
806 
807  int di;
808  int mc;
809  hexist = hInit(S, Q, &hNexist);
810  if (!hNexist)
811  {
812  hCo = 0;
813  hMu = 1;
814  return;
815  }
816  //hWeight();
817  hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
818  hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
819  hsel = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
820  hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
821  hpur0 = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
822  mc = hisModule;
823  hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
824  if (!mc)
825  {
826  memcpy(hrad, hexist, hNexist * sizeof(scmon));
827  hstc = hexist;
828  hNrad = hNstc = hNexist;
829  }
830  else
831  hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
832  radmem = hCreate((currRing->N) - 1);
833  stcmem = hCreate((currRing->N) - 1);
834  hCo = (currRing->N) + 1;
835  di = hCo + 1;
836  loop
837  {
838  if (mc)
839  {
840  hComp(hexist, hNexist, mc, hrad, &hNrad);
841  hNstc = hNrad;
842  memcpy(hstc, hrad, hNrad * sizeof(scmon));
843  }
844  if (hNrad)
845  {
846  hNvar = (currRing->N);
847  hRadical(hrad, &hNrad, hNvar);
848  hSupp(hrad, hNrad, hvar, &hNvar);
849  if (hNvar)
850  {
851  hCo = hNvar;
852  memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
853  hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
854  hLexR(hrad, hNrad, hvar, hNvar);
856  }
857  }
858  else
859  {
860  hNvar = 1;
861  hCo = 0;
862  }
863  if (hCo < di)
864  {
865  di = hCo;
866  hMu = 0;
867  }
868  if (hNvar && (hCo == di))
869  {
870  if (di && (di < (currRing->N)))
872  else if (!di)
873  hMu++;
874  else
875  {
877  if ((hNvar > 2) && (hNstc > 10))
879  memset(hpur0, 0, ((currRing->N) + 1) * sizeof(int));
880  hPure(hstc, 0, &hNstc, hvar, hNvar, hpur0, &hNpure);
881  hLexS(hstc, hNstc, hvar, hNvar);
883  }
884  }
885  mc--;
886  if (mc <= 0)
887  break;
888  }
889  hCo = di;
890  hKill(stcmem, (currRing->N) - 1);
891  hKill(radmem, (currRing->N) - 1);
892  omFreeSize((ADDRESS)hpur0, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
893  omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
894  omFreeSize((ADDRESS)hsel, ((currRing->N) + 1) * sizeof(int));
895  omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
896  omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
897  omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
899  if (hisModule)
900  omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
901 }
static long hZeroMult(scmon pure, scfmon stc, int Nstc, varset var, int Nvar)
Definition: hdegree.cc:621
static void hDimMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition: hdegree.cc:726
VAR int hCo
Definition: hdegree.cc:27
VAR long hMu
Definition: hdegree.cc:28
void hDimSolve(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition: hdegree.cc:35
monf hCreate(int Nvar)
Definition: hutil.cc:996
void hComp(scfmon exist, int Nexist, int ak, scfmon stc, int *Nstc)
Definition: hutil.cc:154
VAR scfmon hstc
Definition: hutil.cc:16
VAR varset hvar
Definition: hutil.cc:18
void hKill(monf xmem, int Nvar)
Definition: hutil.cc:1010
VAR int hNexist
Definition: hutil.cc:19
void hLexS(scfmon stc, int Nstc, varset var, int Nvar)
Definition: hutil.cc:506
void hDelete(scfmon ev, int ev_length)
Definition: hutil.cc:140
VAR scmon hpur0
Definition: hutil.cc:17
VAR monf stcmem
Definition: hutil.cc:21
void hPure(scfmon stc, int a, int *Nstc, varset var, int Nvar, scmon pure, int *Npure)
Definition: hutil.cc:621
VAR scfmon hwork
Definition: hutil.cc:16
void hSupp(scfmon stc, int Nstc, varset var, int *Nvar)
Definition: hutil.cc:174
void hLexR(scfmon rad, int Nrad, varset var, int Nvar)
Definition: hutil.cc:565
VAR scmon hpure
Definition: hutil.cc:17
VAR scfmon hrad
Definition: hutil.cc:16
VAR int hisModule
Definition: hutil.cc:20
void hStaircase(scfmon stc, int *Nstc, varset var, int Nvar)
Definition: hutil.cc:313
VAR monf radmem
Definition: hutil.cc:21
void hOrdSupp(scfmon stc, int Nstc, varset var, int Nvar)
Definition: hutil.cc:202
VAR varset hsel
Definition: hutil.cc:18
VAR int hNpure
Definition: hutil.cc:19
VAR int hNrad
Definition: hutil.cc:19
scfmon hInit(ideal S, ideal Q, int *Nexist)
Definition: hutil.cc:31
VAR scfmon hexist
Definition: hutil.cc:16
void hRadical(scfmon rad, int *Nrad, int Nvar)
Definition: hutil.cc:411
VAR int hNstc
Definition: hutil.cc:19
VAR int hNvar
Definition: hutil.cc:19
scmon * scfmon
Definition: hutil.h:15
int * varset
Definition: hutil.h:16
int * scmon
Definition: hutil.h:14
STATIC_VAR jList * Q
Definition: janet.cc:30
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define id_Test(A, lR)
Definition: simpleideals.h:87

◆ hDimMult()

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

Definition at line 726 of file hdegree.cc.

728 {
729  int dn, iv, rad0, b, c, x;
730  scmon pn;
731  scfmon rn;
732  if (Nrad < 2)
733  {
734  dn = Npure + Nrad;
735  if (dn == hCo)
736  {
737  if (!Nrad)
738  hProject(pure, hsel);
739  else
740  {
741  pn = *rad;
742  for (iv = Nvar; iv; iv--)
743  {
744  x = var[iv];
745  if (pn[x])
746  {
747  pure[x] = 1;
748  hProject(pure, hsel);
749  pure[x] = 0;
750  }
751  }
752  }
753  }
754  return;
755  }
756  iv = Nvar;
757  dn = Npure+1;
758  if (dn >= hCo)
759  {
760  if (dn > hCo)
761  return;
762  loop
763  {
764  if(!pure[var[iv]])
765  {
766  if(hNotZero(rad, Nrad, var, iv))
767  {
768  pure[var[iv]] = 1;
769  hProject(pure, hsel);
770  pure[var[iv]] = 0;
771  }
772  }
773  iv--;
774  if (!iv)
775  return;
776  }
777  }
778  while(pure[var[iv]]) iv--;
779  hStepR(rad, Nrad, var, iv, &rad0);
780  iv--;
781  if (rad0 < Nrad)
782  {
783  pn = hGetpure(pure);
784  rn = hGetmem(Nrad, rad, radmem[iv]);
785  pn[var[iv + 1]] = 1;
786  hDimMult(pn, Npure + 1, rn, rad0, var, iv);
787  pn[var[iv + 1]] = 0;
788  b = rad0;
789  c = Nrad;
790  hElimR(rn, &rad0, b, c, var, iv);
791  hPure(rn, b, &c, var, iv, pn, &x);
792  hLex2R(rn, rad0, b, c, var, iv, hwork);
793  rad0 += (c - b);
794  hDimMult(pn, Npure + x, rn, rad0, var, iv);
795  }
796  else
797  {
798  hDimMult(pure, Npure, rad, Nrad, var, iv);
799  }
800 }
Variable x
Definition: cfModGcd.cc:4082
CanonicalForm b
Definition: cfModGcd.cc:4103
static BOOLEAN hNotZero(scfmon rad, int Nrad, varset var, int Nvar)
Definition: hdegree.cc:355
static void hProject(scmon pure, varset sel)
Definition: hdegree.cc:703
scfmon hGetmem(int lm, scfmon old, monp monmem)
Definition: hutil.cc:1023
void hStepR(scfmon rad, int Nrad, varset var, int Nvar, int *a)
Definition: hutil.cc:974
void hLex2R(scfmon rad, int e1, int a2, int e2, varset var, int Nvar, scfmon w)
Definition: hutil.cc:880
void hElimR(scfmon rad, int *e1, int a2, int e2, varset var, int Nvar)
Definition: hutil.cc:742
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.

37 {
38  int dn, iv, rad0, b, c, x;
39  scmon pn;
40  scfmon rn;
41  if (Nrad < 2)
42  {
43  dn = Npure + Nrad;
44  if (dn < hCo)
45  hCo = dn;
46  return;
47  }
48  if (Npure+1 >= hCo)
49  return;
50  iv = Nvar;
51  while(pure[var[iv]]) iv--;
52  hStepR(rad, Nrad, var, iv, &rad0);
53  if (rad0!=0)
54  {
55  iv--;
56  if (rad0 < Nrad)
57  {
58  pn = hGetpure(pure);
59  rn = hGetmem(Nrad, rad, radmem[iv]);
60  hDimSolve(pn, Npure + 1, rn, rad0, var, iv);
61  b = rad0;
62  c = Nrad;
63  hElimR(rn, &rad0, b, c, var, iv);
64  hPure(rn, b, &c, var, iv, pn, &x);
65  hLex2R(rn, rad0, b, c, var, iv, hwork);
66  rad0 += (c - b);
67  hDimSolve(pn, Npure + x, rn, rad0, var, iv);
68  }
69  else
70  {
71  hDimSolve(pure, Npure, rad, Nrad, var, iv);
72  }
73  }
74  else
75  hCo = Npure + 1;
76 }

◆ hHedge()

static void hHedge ( poly  hEdge)
static

Definition at line 1029 of file hdegree.cc.

1030 {
1031  pSetm(pWork);
1032  if (pLmCmp(pWork, hEdge) == currRing->OrdSgn)
1033  {
1034  for (int i = hNvar; i>0; i--)
1035  pSetExp(hEdge,i, pGetExp(pWork,i));
1036  pSetm(hEdge);
1037  }
1038 }
STATIC_VAR poly pWork
Definition: hdegree.cc:1027
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105

◆ hHedgeStep()

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

Definition at line 1041 of file hdegree.cc.

1043 {
1044  int iv = Nvar -1, k = var[Nvar], a, a0, a1, b, i;
1045  int x/*, x0*/;
1046  scmon pn;
1047  scfmon sn;
1048  if (iv==0)
1049  {
1050  pSetExp(pWork, k, pure[k]);
1051  hHedge(hEdge);
1052  return;
1053  }
1054  else if (Nstc==0)
1055  {
1056  for (i = Nvar; i>0; i--)
1057  pSetExp(pWork, var[i], pure[var[i]]);
1058  hHedge(hEdge);
1059  return;
1060  }
1061  x = a = 0;
1062  pn = hGetpure(pure);
1063  sn = hGetmem(Nstc, stc, stcmem[iv]);
1064  hStepS(sn, Nstc, var, Nvar, &a, &x);
1065  if (a == Nstc)
1066  {
1067  pSetExp(pWork, k, pure[k]);
1068  hHedgeStep(pn, sn, a, var, iv,hEdge);
1069  return;
1070  }
1071  else
1072  {
1073  pSetExp(pWork, k, x);
1074  hHedgeStep(pn, sn, a, var, iv,hEdge);
1075  }
1076  b = a;
1077  loop
1078  {
1079  a0 = a;
1080  // x0 = x;
1081  hStepS(sn, Nstc, var, Nvar, &a, &x);
1082  hElimS(sn, &b, a0, a, var, iv);
1083  a1 = a;
1084  hPure(sn, a0, &a1, var, iv, pn, &i);
1085  hLex2S(sn, b, a0, a1, var, iv, hwork);
1086  b += (a1 - a0);
1087  if (a < Nstc)
1088  {
1089  pSetExp(pWork, k, x);
1090  hHedgeStep(pn, sn, b, var, iv,hEdge);
1091  }
1092  else
1093  {
1094  pSetExp(pWork, k, pure[k]);
1095  hHedgeStep(pn, sn, b, var, iv,hEdge);
1096  return;
1097  }
1098  }
1099 }
int k
Definition: cfEzgcd.cc:99
static void hHedgeStep(scmon pure, scfmon stc, int Nstc, varset var, int Nvar, poly hEdge)
Definition: hdegree.cc:1041
static void hHedge(poly hEdge)
Definition: hdegree.cc:1029
void hLex2S(scfmon rad, int e1, int a2, int e2, varset var, int Nvar, scfmon w)
Definition: hutil.cc:812
void hElimS(scfmon stc, int *e1, int a2, int e2, varset var, int Nvar)
Definition: hutil.cc:672
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 564 of file hdegree.cc.

566 {
567  int dn, iv, rad0, b, c, x;
568  scmon pn;
569  scfmon rn;
570  if (Nrad < 2)
571  {
572  dn = Npure + Nrad;
573  if (dn > hCo)
574  {
575  if (!Nrad)
576  hCheckIndep(pure);
577  else
578  {
579  pn = *rad;
580  for (iv = Nvar; iv; iv--)
581  {
582  x = var[iv];
583  if (pn[x])
584  {
585  pure[x] = 1;
586  hCheckIndep(pure);
587  pure[x] = 0;
588  }
589  }
590  }
591  }
592  return;
593  }
594  iv = Nvar;
595  while(pure[var[iv]]) iv--;
596  hStepR(rad, Nrad, var, iv, &rad0);
597  iv--;
598  if (rad0 < Nrad)
599  {
600  pn = hGetpure(pure);
601  rn = hGetmem(Nrad, rad, radmem[iv]);
602  pn[var[iv + 1]] = 1;
603  hIndAllMult(pn, Npure + 1, rn, rad0, var, iv);
604  pn[var[iv + 1]] = 0;
605  b = rad0;
606  c = Nrad;
607  hElimR(rn, &rad0, b, c, var, iv);
608  hPure(rn, b, &c, var, iv, pn, &x);
609  hLex2R(rn, rad0, b, c, var, iv, hwork);
610  rad0 += (c - b);
611  hIndAllMult(pn, Npure + x, rn, rad0, var, iv);
612  }
613  else
614  {
615  hIndAllMult(pure, Npure, rad, Nrad, var, iv);
616  }
617 }
static void hCheckIndep(scmon pure)
Definition: hdegree.cc:543
void hIndAllMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition: hdegree.cc:564

◆ hIndep()

static void hIndep ( scmon  pure)
static

Definition at line 370 of file hdegree.cc.

371 {
372  int iv;
373  intvec *Set;
374 
375  Set = ISet->set = new intvec((currRing->N));
376  for (iv=(currRing->N); iv!=0 ; iv--)
377  {
378  (*Set)[iv-1] = (pure[iv]==0);
379  }
381  hMu++;
382 }

◆ hIndMult()

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

Definition at line 384 of file hdegree.cc.

386 {
387  int dn, iv, rad0, b, c, x;
388  scmon pn;
389  scfmon rn;
390  if (Nrad < 2)
391  {
392  dn = Npure + Nrad;
393  if (dn == hCo)
394  {
395  if (Nrad==0)
396  hIndep(pure);
397  else
398  {
399  pn = *rad;
400  for (iv = Nvar; iv!=0; iv--)
401  {
402  x = var[iv];
403  if (pn[x])
404  {
405  pure[x] = 1;
406  hIndep(pure);
407  pure[x] = 0;
408  }
409  }
410  }
411  }
412  return;
413  }
414  iv = Nvar;
415  dn = Npure+1;
416  if (dn >= hCo)
417  {
418  if (dn > hCo)
419  return;
420  loop
421  {
422  if(!pure[var[iv]])
423  {
424  if(hNotZero(rad, Nrad, var, iv))
425  {
426  pure[var[iv]] = 1;
427  hIndep(pure);
428  pure[var[iv]] = 0;
429  }
430  }
431  iv--;
432  if (!iv)
433  return;
434  }
435  }
436  while(pure[var[iv]]) iv--;
437  hStepR(rad, Nrad, var, iv, &rad0);
438  iv--;
439  if (rad0 < Nrad)
440  {
441  pn = hGetpure(pure);
442  rn = hGetmem(Nrad, rad, radmem[iv]);
443  pn[var[iv + 1]] = 1;
444  hIndMult(pn, Npure + 1, rn, rad0, var, iv);
445  pn[var[iv + 1]] = 0;
446  b = rad0;
447  c = Nrad;
448  hElimR(rn, &rad0, b, c, var, iv);
449  hPure(rn, b, &c, var, iv, pn, &x);
450  hLex2R(rn, rad0, b, c, var, iv, hwork);
451  rad0 += (c - b);
452  hIndMult(pn, Npure + x, rn, rad0, var, iv);
453  }
454  else
455  {
456  hIndMult(pure, Npure, rad, Nrad, var, iv);
457  }
458 }
void hIndMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition: hdegree.cc:384
static void hIndep(scmon pure)
Definition: hdegree.cc:370

◆ hIndSolve()

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

Definition at line 207 of file hdegree.cc.

209 {
210  int dn, iv, rad0, b, c, x;
211  scmon pn;
212  scfmon rn;
213  if (Nrad < 2)
214  {
215  dn = Npure + Nrad;
216  if (dn < hCo)
217  {
218  hCo = dn;
219  for (iv=(currRing->N); iv; iv--)
220  {
221  if (pure[iv])
222  hInd[iv] = 0;
223  else
224  hInd[iv] = 1;
225  }
226  if (Nrad)
227  {
228  pn = *rad;
229  iv = Nvar;
230  loop
231  {
232  x = var[iv];
233  if (pn[x])
234  {
235  hInd[x] = 0;
236  break;
237  }
238  iv--;
239  }
240  }
241  }
242  return;
243  }
244  if (Npure+1 >= hCo)
245  return;
246  iv = Nvar;
247  while(pure[var[iv]]) iv--;
248  hStepR(rad, Nrad, var, iv, &rad0);
249  if (rad0)
250  {
251  iv--;
252  if (rad0 < Nrad)
253  {
254  pn = hGetpure(pure);
255  rn = hGetmem(Nrad, rad, radmem[iv]);
256  pn[var[iv + 1]] = 1;
257  hIndSolve(pn, Npure + 1, rn, rad0, var, iv);
258  pn[var[iv + 1]] = 0;
259  b = rad0;
260  c = Nrad;
261  hElimR(rn, &rad0, b, c, var, iv);
262  hPure(rn, b, &c, var, iv, pn, &x);
263  hLex2R(rn, rad0, b, c, var, iv, hwork);
264  rad0 += (c - b);
265  hIndSolve(pn, Npure + x, rn, rad0, var, iv);
266  }
267  else
268  {
269  hIndSolve(pure, Npure, rad, Nrad, var, iv);
270  }
271  }
272  else
273  {
274  hCo = Npure + 1;
275  for (x=(currRing->N); x; x--)
276  {
277  if (pure[x])
278  hInd[x] = 0;
279  else
280  hInd[x] = 1;
281  }
282  hInd[var[iv]] = 0;
283  }
284 }
STATIC_VAR scmon hInd
Definition: hdegree.cc:205
static void hIndSolve(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition: hdegree.cc:207

◆ hNotZero()

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

Definition at line 355 of file hdegree.cc.

356 {
357  int k1, i;
358  k1 = var[Nvar];
359  i = 0;
360  loop
361  {
362  if (rad[i][k1]==0)
363  return FALSE;
364  i++;
365  if (i == Nrad)
366  return TRUE;
367  }
368 }

◆ hProject()

static void hProject ( scmon  pure,
varset  sel 
)
static

Definition at line 703 of file hdegree.cc.

704 {
705  int i, i0, k;
706  i0 = 0;
707  for (i = 1; i <= (currRing->N); i++)
708  {
709  if (pure[i])
710  {
711  i0++;
712  sel[i0] = i;
713  }
714  }
715  i = hNstc;
716  memcpy(hwork, hstc, i * sizeof(scmon));
717  hStaircase(hwork, &i, sel, i0);
718  if ((i0 > 2) && (i > 10))
719  hOrdSupp(hwork, i, sel, i0);
720  memset(hpur0, 0, ((currRing->N) + 1) * sizeof(int));
721  hPure(hwork, 0, &i, sel, i0, hpur0, &k);
722  hLexS(hwork, i, sel, i0);
723  hMu += hZeroMult(hpur0, hwork, i, sel, i0);
724 }

◆ hZeroMult()

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

Definition at line 621 of file hdegree.cc.

622 {
623  int iv = Nvar -1, a, a0, a1, b, i;
624  long sum;
625  int x, x0;
626  scmon pn;
627  scfmon sn;
628  if (!iv)
629  return pure[var[1]];
630  else if (!Nstc)
631  {
632  sum = 1;
633  for (i = Nvar; i; i--)
634  sum *= pure[var[i]];
635  return sum;
636  }
637  x = a = 0;
638  pn = hGetpure(pure);
639  sn = hGetmem(Nstc, stc, stcmem[iv]);
640  hStepS(sn, Nstc, var, Nvar, &a, &x);
641  if (a == Nstc)
642  {
643  #if SIZEOF_LONG==8
644  return (long)pure[var[Nvar]] * hZeroMult(pn, sn, a, var, iv);
645  #else
646  int64 t=hZeroMult(pn, sn, a, var, iv);
647  t *= pure[var[Nvar]];
648  if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
649  else if (!errorreported) WerrorS("int overflow in vdim 3");
650  return sum;
651  #endif
652  }
653  else
654  {
655  #if SIZEOF_LONG==8
656  sum = x * hZeroMult(pn, sn, a, var, iv);
657  #else
658  int64 t=hZeroMult(pn, sn, a, var, iv);
659  t *= x;
660  if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
661  else if (!errorreported) WerrorS("int overflow in vdim 4");
662  #endif
663  }
664  b = a;
665  loop
666  {
667  a0 = a;
668  x0 = x;
669  hStepS(sn, Nstc, var, Nvar, &a, &x);
670  hElimS(sn, &b, a0, a, var, iv);
671  a1 = a;
672  hPure(sn, a0, &a1, var, iv, pn, &i);
673  hLex2S(sn, b, a0, a1, var, iv, hwork);
674  b += (a1 - a0);
675  if (a < Nstc)
676  {
677  #if SIZEOF_LONG==8
678  sum += (long)(x - x0) * hZeroMult(pn, sn, b, var, iv);
679  #else
680  int64 t=hZeroMult(pn, sn, b, var, iv);
681  t *= (x-x0);
682  t += sum;
683  if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
684  else if (!errorreported) WerrorS("int overflow in vdim 1");
685  #endif
686  }
687  else
688  {
689  #if SIZEOF_LONG==8
690  sum += (long)(pure[var[Nvar]] - x0) * hZeroMult(pn, sn, b, var, iv);
691  #else
692  int64 t=hZeroMult(pn, sn, b, var, iv);
693  t *= (pure[var[Nvar]]-x0);
694  t += sum;
695  if ((t>=INT_MIN)&&(t<=INT_MAX)) sum=t;
696  else if (!errorreported) WerrorS("int overflow in vdim 2");
697  #endif
698  return sum;
699  }
700  }
701 }
long int64
Definition: auxiliary.h:68
VAR short errorreported
Definition: feFopen.cc:23
void WerrorS(const char *s)
Definition: feFopen.cc:24

◆ isAcyclic()

static BOOLEAN isAcyclic ( const intvec G)
static

Definition at line 2085 of file hdegree.cc.

2086 {
2087  // init
2088  int n = G->cols();
2089  std::vector<int> path;
2090  std::vector<BOOLEAN> visited;
2091  std::vector<BOOLEAN> cyclic;
2092  std::vector<int> cache;
2093  visited.resize(n, FALSE);
2094  cyclic.resize(n, FALSE);
2095  cache.resize(n, -2);
2096 
2097  for (int v = 0; v < n; v++)
2098  {
2099  cache = countCycles(G, v, path, visited, cyclic, cache);
2100  // check that there are 0 cycles from v
2101  if (cache[v] != 0)
2102  return FALSE;
2103  }
2104  return TRUE;
2105 }

◆ iv2vv()

static std::vector<std::vector<int> > iv2vv ( intvec M)
static

Definition at line 1972 of file hdegree.cc.

1973 {
1974  int rows = M->rows();
1975  int cols = M->cols();
1976 
1977  std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
1978 
1979  for (int i = 0; i < rows; i++)
1980  {
1981  for (int j = 0; j < cols; j++)
1982  {
1983  mat[i][j] = IMATELEM(*M, i + 1, j + 1);
1984  }
1985  }
1986 
1987  return mat;
1988 }

◆ lp_computeNormalWords()

static ideal lp_computeNormalWords ( int  length,
ideal  M 
)
static

Definition at line 1760 of file hdegree.cc.

1761 {
1762  long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
1763  for (int i = 1; i < IDELEMS(M); i++)
1764  {
1765  minDeg = si_min(minDeg, pTotaldegree(M->m[i]));
1766  }
1767 
1768  int nVars = currRing->isLPring - currRing->LPncGenCount;
1769 
1770  int maxElems = 1;
1771  for (int i = 0; i < length; i++) // maxElems = nVars^n
1772  maxElems *= nVars;
1773  ideal words = idInit(maxElems);
1774  int last, numberOfNormalWords;
1775  _lp_computeNormalWords(words, numberOfNormalWords, length, M, minDeg, last);
1776  idSkipZeroes(words);
1777  return words;
1778 }
static int si_min(const int a, const int b)
Definition: auxiliary.h:125
static long pTotaldegree(poly p)
Definition: polys.h:282
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)
Definition: simpleideals.h:23

◆ lp_countNormalWords()

static int lp_countNormalWords ( int  upToLength,
ideal  M 
)
static

Definition at line 1780 of file hdegree.cc.

1781 {
1782  long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
1783  for (int i = 1; i < IDELEMS(M); i++)
1784  {
1785  minDeg = si_min(minDeg, pTotaldegree(M->m[i]));
1786  }
1787 
1788  int nVars = currRing->isLPring - currRing->LPncGenCount;
1789 
1790  int maxElems = 1;
1791  for (int i = 0; i < upToLength; i++) // maxElems = nVars^n
1792  maxElems *= nVars;
1793  ideal words = idInit(maxElems);
1794  int last, numberOfNormalWords;
1795  _lp_computeNormalWords(words, numberOfNormalWords, upToLength, M, minDeg, last);
1796  idDelete(&words);
1797  return numberOfNormalWords;
1798 }
#define idDelete(H)
delete an ideal
Definition: ideals.h:29

◆ lp_gkDim()

int lp_gkDim ( const ideal  _G)

Definition at line 1862 of file hdegree.cc.

1863 {
1864  id_Test(_G, currRing);
1865 
1866  if (rField_is_Ring(currRing)) {
1867  WerrorS("GK-Dim not implemented for rings");
1868  return -2;
1869  }
1870 
1871  for (int i=IDELEMS(_G)-1;i>=0; i--)
1872  {
1873  if (_G->m[i] != NULL)
1874  {
1875  if (pGetComp(_G->m[i]) != 0)
1876  {
1877  WerrorS("GK-Dim not implemented for modules");
1878  return -2;
1879  }
1880  if (pGetNCGen(_G->m[i]) != 0)
1881  {
1882  WerrorS("GK-Dim not implemented for bi-modules");
1883  return -2;
1884  }
1885  }
1886  }
1887 
1888  ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
1889  idSkipZeroes(G); // remove zeros
1890  id_DelLmEquals(G, currRing); // remove duplicates
1891 
1892  // check if G is the zero ideal
1893  if (IDELEMS(G) == 1 && G->m[0] == NULL)
1894  {
1895  // NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
1896  int lV = currRing->isLPring;
1897  int ncGenCount = currRing->LPncGenCount;
1898  if (lV - ncGenCount == 0)
1899  {
1900  idDelete(&G);
1901  return 0;
1902  }
1903  if (lV - ncGenCount == 1)
1904  {
1905  idDelete(&G);
1906  return 1;
1907  }
1908  if (lV - ncGenCount >= 2)
1909  {
1910  idDelete(&G);
1911  return -1;
1912  }
1913  }
1914 
1915  // get the max deg
1916  long maxDeg = 0;
1917  for (int i = 0; i < IDELEMS(G); i++)
1918  {
1919  maxDeg = si_max(maxDeg, pTotaldegree(G->m[i]));
1920 
1921  // also check whether G = <1>
1922  if (pIsConstantComp(G->m[i]))
1923  {
1924  WerrorS("GK-Dim not defined for 0-ring");
1925  idDelete(&G);
1926  return -2;
1927  }
1928  }
1929 
1930  // early termination if G \subset X
1931  if (maxDeg <= 1)
1932  {
1933  int lV = currRing->isLPring;
1934  int ncGenCount = currRing->LPncGenCount;
1935  if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
1936  {
1937  idDelete(&G);
1938  return 0;
1939  }
1940  if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
1941  {
1942  idDelete(&G);
1943  return 1;
1944  }
1945  if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
1946  {
1947  idDelete(&G);
1948  return -1;
1949  }
1950  }
1951 
1952  ideal standardWords;
1953  intvec* UG = lp_ufnarovskiGraph(G, standardWords);
1954  if (UG == NULL)
1955  {
1956  idDelete(&G);
1957  return -2;
1958  }
1959  if (errorreported)
1960  {
1961  delete UG;
1962  idDelete(&G);
1963  return -2;
1964  }
1965  int gkDim = graphGrowth(UG);
1966  delete UG;
1967  idDelete(&G);
1968  return gkDim;
1969 }
intvec * lp_ufnarovskiGraph(ideal G, ideal &standardWords)
Definition: hdegree.cc:1801
static int graphGrowth(const intvec *G)
Definition: hdegree.cc:1674
#define pGetComp(p)
Component.
Definition: polys.h:37
#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:236
#define rField_is_Ring(R)
Definition: ring.h:485
#define pGetNCGen(p)
Definition: shiftop.h:65
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
void id_DelLmEquals(ideal id, const ring r)
Delete id[j], if Lm(j) == Lm(i) and both LC(j), LC(i) are units and j > i.

◆ lp_kDim()

int lp_kDim ( const ideal  _G)

Definition at line 2112 of file hdegree.cc.

2113 {
2114  if (rField_is_Ring(currRing)) {
2115  WerrorS("K-Dim not implemented for rings");
2116  return -2;
2117  }
2118 
2119  for (int i=IDELEMS(_G)-1;i>=0; i--)
2120  {
2121  if (_G->m[i] != NULL)
2122  {
2123  if (pGetComp(_G->m[i]) != 0)
2124  {
2125  WerrorS("K-Dim not implemented for modules");
2126  return -2;
2127  }
2128  if (pGetNCGen(_G->m[i]) != 0)
2129  {
2130  WerrorS("K-Dim not implemented for bi-modules");
2131  return -2;
2132  }
2133  }
2134  }
2135 
2136  ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
2137  if (TEST_OPT_PROT)
2138  Print("%d original generators\n", IDELEMS(G));
2139  idSkipZeroes(G); // remove zeros
2140  id_DelLmEquals(G, currRing); // remove duplicates
2141  if (TEST_OPT_PROT)
2142  Print("%d non-zero unique generators\n", IDELEMS(G));
2143 
2144  // check if G is the zero ideal
2145  if (IDELEMS(G) == 1 && G->m[0] == NULL)
2146  {
2147  // NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
2148  int lV = currRing->isLPring;
2149  int ncGenCount = currRing->LPncGenCount;
2150  if (lV - ncGenCount == 0)
2151  {
2152  idDelete(&G);
2153  return 1;
2154  }
2155  if (lV - ncGenCount == 1)
2156  {
2157  idDelete(&G);
2158  return -1;
2159  }
2160  if (lV - ncGenCount >= 2)
2161  {
2162  idDelete(&G);
2163  return -1;
2164  }
2165  }
2166 
2167  // get the max deg
2168  long maxDeg = 0;
2169  for (int i = 0; i < IDELEMS(G); i++)
2170  {
2171  maxDeg = si_max(maxDeg, pTotaldegree(G->m[i]));
2172 
2173  // also check whether G = <1>
2174  if (pIsConstantComp(G->m[i]))
2175  {
2176  WerrorS("K-Dim not defined for 0-ring"); // TODO is it minus infinity ?
2177  idDelete(&G);
2178  return -2;
2179  }
2180  }
2181  if (TEST_OPT_PROT)
2182  Print("max deg: %ld\n", maxDeg);
2183 
2184 
2185  // for normal words of length minDeg ... maxDeg-1
2186  // brute-force the normal words
2187  if (TEST_OPT_PROT)
2188  PrintS("Computing normal words normally...\n");
2189  long numberOfNormalWords = lp_countNormalWords(maxDeg - 1, G);
2190 
2191  if (TEST_OPT_PROT)
2192  Print("%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
2193 
2194  // early termination if G \subset X
2195  if (maxDeg <= 1)
2196  {
2197  int lV = currRing->isLPring;
2198  int ncGenCount = currRing->LPncGenCount;
2199  if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
2200  {
2201  idDelete(&G);
2202  return numberOfNormalWords;
2203  }
2204  if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
2205  {
2206  idDelete(&G);
2207  return -1;
2208  }
2209  if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
2210  {
2211  idDelete(&G);
2212  return -1;
2213  }
2214  }
2215 
2216  if (TEST_OPT_PROT)
2217  PrintS("Computing Ufnarovski graph...\n");
2218 
2219  ideal standardWords;
2220  intvec* UG = lp_ufnarovskiGraph(G, standardWords);
2221  if (UG == NULL)
2222  {
2223  idDelete(&G);
2224  return -2;
2225  }
2226  if (errorreported)
2227  {
2228  delete UG;
2229  idDelete(&G);
2230  return -2;
2231  }
2232 
2233  if (TEST_OPT_PROT)
2234  Print("Ufnarovski graph is %dx%d.\n", UG->rows(), UG->cols());
2235 
2236  if (TEST_OPT_PROT)
2237  PrintS("Checking whether Ufnarovski graph is acyclic...\n");
2238 
2239  if (!isAcyclic(UG))
2240  {
2241  // in this case we have infinitely many normal words
2242  return -1;
2243  }
2244 
2245  std::vector<std::vector<int> > vvUG = iv2vv(UG);
2246  for (int i = 0; i < vvUG.size(); i++)
2247  {
2248  if (vvIsRowZero(vvUG, i) && vvIsColumnZero(vvUG, i)) // i is isolated vertex
2249  {
2250  vvDeleteRow(vvUG, i);
2251  vvDeleteColumn(vvUG, i);
2252  i--;
2253  }
2254  }
2255  if (TEST_OPT_PROT)
2256  Print("Simplified Ufnarovski graph to %dx%d.\n", (int)vvUG.size(), (int)vvUG.size());
2257 
2258  // for normal words of length >= maxDeg
2259  // use Ufnarovski graph
2260  if (TEST_OPT_PROT)
2261  PrintS("Computing normal words via Ufnarovski graph...\n");
2262  std::vector<std::vector<int> > UGpower = vvUG;
2263  long nUGpower = 1;
2264  while (!vvIsZero(UGpower))
2265  {
2266  if (TEST_OPT_PROT)
2267  PrintS("Start count graph entries.\n");
2268  for (int i = 0; i < UGpower.size(); i++)
2269  {
2270  for (int j = 0; j < UGpower[i].size(); j++)
2271  {
2272  numberOfNormalWords += UGpower[i][j];
2273  }
2274  }
2275 
2276  if (TEST_OPT_PROT)
2277  {
2278  PrintS("Done count graph entries.\n");
2279  Print("%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
2280  }
2281 
2282  if (TEST_OPT_PROT)
2283  PrintS("Start mat mult.\n");
2284  UGpower = vvMult(UGpower, vvUG); // TODO: avoid creation of new intvec
2285  if (TEST_OPT_PROT)
2286  PrintS("Done mat mult.\n");
2287  nUGpower++;
2288  }
2289 
2290  delete UG;
2291  idDelete(&G);
2292  return numberOfNormalWords;
2293 }
int cols() const
Definition: intvec.h:95
int rows() const
Definition: intvec.h:96
#define Print
Definition: emacs.cc:80
static std::vector< std::vector< int > > iv2vv(intvec *M)
Definition: hdegree.cc:1972
static void vvDeleteRow(std::vector< std::vector< int > > &mat, int row)
Definition: hdegree.cc:2015
static BOOLEAN vvIsColumnZero(const std::vector< std::vector< int > > &mat, int col)
Definition: hdegree.cc:2038
static void vvDeleteColumn(std::vector< std::vector< int > > &mat, int col)
Definition: hdegree.cc:2020
static int lp_countNormalWords(int upToLength, ideal M)
Definition: hdegree.cc:1780
static BOOLEAN isAcyclic(const intvec *G)
Definition: hdegree.cc:2085
static BOOLEAN vvIsZero(const std::vector< std::vector< int > > &mat)
Definition: hdegree.cc:2048
static BOOLEAN vvIsRowZero(const std::vector< std::vector< int > > &mat, int row)
Definition: hdegree.cc:2028
static std::vector< std::vector< int > > vvMult(const std::vector< std::vector< int > > &a, const std::vector< std::vector< int > > &b)
Definition: hdegree.cc:2058
#define TEST_OPT_PROT
Definition: options.h:104
void PrintS(const char *s)
Definition: reporter.cc:284

◆ lp_ufnarovskiGraph()

intvec* lp_ufnarovskiGraph ( ideal  G,
ideal &  standardWords 
)

Definition at line 1801 of file hdegree.cc.

1802 {
1803  long l = 0;
1804  for (int i = 0; i < IDELEMS(G); i++)
1805  l = si_max(pTotaldegree(G->m[i]), l);
1806  l--;
1807  if (l <= 0)
1808  {
1809  WerrorS("Ufnarovski graph not implemented for l <= 0");
1810  return NULL;
1811  }
1812  int lV = currRing->isLPring;
1813 
1814  standardWords = lp_computeNormalWords(l, G);
1815 
1816  int n = IDELEMS(standardWords);
1817  intvec* UG = new intvec(n, n, 0);
1818  for (int i = 0; i < n; i++)
1819  {
1820  for (int j = 0; j < n; j++)
1821  {
1822  poly v = standardWords->m[i];
1823  poly w = standardWords->m[j];
1824 
1825  // check whether v*x1 = x2*w (overlap)
1826  bool overlap = true;
1827  for (int k = 1; k <= (l - 1) * lV; k++)
1828  {
1829  if (pGetExp(v, k + lV) != pGetExp(w, k)) {
1830  overlap = false;
1831  break;
1832  }
1833  }
1834 
1835  if (overlap)
1836  {
1837  // create the overlap
1838  poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing));
1839 
1840  // check whether the overlap is normal
1841  bool normal = true;
1842  for (int k = 0; k < IDELEMS(G); k++)
1843  {
1844  if (p_LPDivisibleBy(G->m[k], p, currRing))
1845  {
1846  normal = false;
1847  break;
1848  }
1849  }
1850 
1851  if (normal)
1852  {
1853  IMATELEM(*UG, i + 1, j + 1) = 1;
1854  }
1855  }
1856  }
1857  }
1858  return UG;
1859 }
int l
Definition: cfEzgcd.cc:100
int p
Definition: cfModGcd.cc:4078
static ideal lp_computeNormalWords(int length, ideal M)
Definition: hdegree.cc:1760
#define pMult(p, q)
Definition: polys.h:207
poly p_LPVarAt(poly p, int pos, const ring r)
Definition: shiftop.cc:845

◆ scAll()

static void scAll ( int  Nvar,
int  deg 
)
static

Definition at line 1260 of file hdegree.cc.

1261 {
1262  int i;
1263  int d = deg;
1264  if (d == 0)
1265  {
1266  for (i=Nvar; i; i--) act[i] = 0;
1267  scElKbase();
1268  return;
1269  }
1270  if (Nvar == 1)
1271  {
1272  act[1] = d;
1273  scElKbase();
1274  return;
1275  }
1276  do
1277  {
1278  act[Nvar] = d;
1279  scAll(Nvar-1, deg-d);
1280  d--;
1281  } while (d >= 0);
1282 }
static void scElKbase()
Definition: hdegree.cc:1176
static void scAll(int Nvar, int deg)
Definition: hdegree.cc:1260
STATIC_VAR scmon act
Definition: hdegree.cc:1174

◆ scAllKbase()

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

Definition at line 1284 of file hdegree.cc.

1285 {
1286  do
1287  {
1288  act[Nvar] = ideg;
1289  scAll(Nvar-1, deg-ideg);
1290  ideg--;
1291  } while (ideg >= 0);
1292 }

◆ scComputeHC()

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

Definition at line 1101 of file hdegree.cc.

1102 {
1103  id_LmTest(S, currRing);
1104  if (Q!=NULL) id_LmTest(Q, currRing);
1105 
1106  int i;
1107  int k = ak;
1108  #ifdef HAVE_RINGS
1109  if (rField_is_Ring(currRing) && (currRing->OrdSgn == -1))
1110  {
1111  //consider just monic generators (over rings with zero-divisors)
1112  ideal SS=id_Head(S,currRing);
1113  for(i=0;i<=idElem(S);i++)
1114  {
1115  if((SS->m[i]!=NULL)
1116  && ((p_IsPurePower(SS->m[i],currRing)==0)
1117  ||(!n_IsUnit(pGetCoeff(SS->m[i]), currRing->cf))))
1118  {
1119  p_Delete(&SS->m[i],currRing);
1120  }
1121  }
1122  S=id_Copy(SS,currRing);
1123  idSkipZeroes(S);
1124  }
1125  #if 0
1126  printf("\nThis is HC:\n");
1127  for(int ii=0;ii<=idElem(S);ii++)
1128  {
1129  pWrite(S->m[ii]);
1130  }
1131  //getchar();
1132  #endif
1133  #endif
1134  if(idElem(S) == 0)
1135  return;
1136  hNvar = (currRing->N);
1137  hexist = hInit(S, Q, &hNexist);
1138  if (k!=0)
1139  hComp(hexist, hNexist, k, hexist, &hNstc);
1140  else
1141  hNstc = hNexist;
1142  assume(hNexist > 0);
1143  hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
1144  hvar = (varset)omAlloc((hNvar + 1) * sizeof(int));
1145  hpure = (scmon)omAlloc((1 + (hNvar * hNvar)) * sizeof(int));
1146  stcmem = hCreate(hNvar - 1);
1147  for (i = hNvar; i>0; i--)
1148  hvar[i] = i;
1150  if ((hNvar > 2) && (hNstc > 10))
1152  memset(hpure, 0, (hNvar + 1) * sizeof(int));
1153  hPure(hexist, 0, &hNstc, hvar, hNvar, hpure, &hNpure);
1154  hLexS(hexist, hNstc, hvar, hNvar);
1155  if (hEdge!=NULL)
1156  pLmFree(hEdge);
1157  hEdge = pInit();
1158  pWork = pInit();
1159  hHedgeStep(hpure, hexist, hNstc, hvar, hNvar,hEdge);
1160  pSetComp(hEdge,ak);
1161  hKill(stcmem, hNvar - 1);
1162  omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
1163  omFreeSize((ADDRESS)hvar, (hNvar + 1) * sizeof(int));
1164  omFreeSize((ADDRESS)hpure, (1 + (hNvar * hNvar)) * sizeof(int));
1166  pLmFree(pWork);
1167 }
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:512
ideal id_Copy(ideal h1, const ring r)
copy an ideal
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
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1226
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
#define pSetComp(p, v)
Definition: polys.h:38
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:70
void pWrite(poly p)
Definition: polys.h:308
#define pInit()
allocates a new monomial and initializes everything to 0
Definition: polys.h:61
static int idElem(const ideal F)
number of non-zero polys in F
Definition: simpleideals.h:67
#define id_LmTest(A, lR)
Definition: simpleideals.h:88

◆ scDegKbase()

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

Definition at line 1294 of file hdegree.cc.

1295 {
1296  int Ivar, Istc, i, j;
1297  scfmon sn;
1298  int x, ideg;
1299 
1300  if (deg == 0)
1301  {
1302  for (i=Nstc-1; i>=0; i--)
1303  {
1304  for (j=Nvar;j;j--){ if(stc[i][j]) break; }
1305  if (j==0){return;}
1306  }
1307  for (i=Nvar; i; i--) act[i] = 0;
1308  scElKbase();
1309  return;
1310  }
1311  if (Nvar == 1)
1312  {
1313  for (i=Nstc-1; i>=0; i--) if(deg >= stc[i][1]) return;
1314  act[1] = deg;
1315  scElKbase();
1316  return;
1317  }
1318  Ivar = Nvar-1;
1319  sn = hGetmem(Nstc, stc, stcmem[Ivar]);
1320  x = scRestrict(Nstc, sn, Nvar);
1321  if (x <= 0)
1322  {
1323  if (x == 0) return;
1324  ideg = deg;
1325  }
1326  else
1327  {
1328  if (deg < x) ideg = deg;
1329  else ideg = x-1;
1330  if (Nstc == 0)
1331  {
1332  scAllKbase(Nvar, ideg, deg);
1333  return;
1334  }
1335  }
1336  loop
1337  {
1338  x = scMax(Nstc, sn, Nvar);
1339  while (ideg >= x)
1340  {
1341  act[Nvar] = ideg;
1342  scDegKbase(sn, Nstc, Ivar, deg-ideg);
1343  ideg--;
1344  }
1345  if (ideg < 0) return;
1346  Istc = Nstc;
1347  for (i=Nstc-1; i>=0; i--)
1348  {
1349  if (ideg < sn[i][Nvar])
1350  {
1351  Istc--;
1352  sn[i] = NULL;
1353  }
1354  }
1355  if (Istc == 0)
1356  {
1357  scAllKbase(Nvar, ideg, deg);
1358  return;
1359  }
1360  j = 0;
1361  while (sn[j]) j++;
1362  i = j+1;
1363  for (; i<Nstc; i++)
1364  {
1365  if (sn[i])
1366  {
1367  sn[j] = sn[i];
1368  j++;
1369  }
1370  }
1371  Nstc = Istc;
1372  }
1373 }
static int scRestrict(int &Nstc, scfmon stc, int Nvar)
Definition: hdegree.cc:1209
static void scAllKbase(int Nvar, int ideg, int deg)
Definition: hdegree.cc:1284
static void scDegKbase(scfmon stc, int Nstc, int Nvar, int deg)
Definition: hdegree.cc:1294
static int scMax(int i, scfmon stc, int Nvar)
Definition: hdegree.cc:1185

◆ scDegree()

void scDegree ( ideal  S,
intvec modulweight,
ideal  Q 
)

Definition at line 926 of file hdegree.cc.

927 {
928  id_Test(S, currRing);
929  if( Q!=NULL ) id_Test(Q, currRing);
930 
931  int co, mu, l;
932  intvec *hseries2;
933  intvec *hseries1 = hFirstSeries(S, modulweight, Q);
934  if (errorreported) return;
935  l = hseries1->length()-1;
936  if (l > 1)
937  hseries2 = hSecondSeries(hseries1);
938  else
939  hseries2 = hseries1;
940  hDegreeSeries(hseries1, hseries2, &co, &mu);
941  if ((l == 1) &&(mu == 0))
942  scPrintDegree((currRing->N)+1, 0);
943  else
944  scPrintDegree(co, mu);
945  if (l>1)
946  delete hseries1;
947  delete hseries2;
948 }
void mu(int **points, int sizePoints)
int length() const
Definition: intvec.h:94
void scPrintDegree(int co, int mu)
Definition: hdegree.cc:912
intvec * hFirstSeries(ideal A, intvec *module_w, ideal Q, intvec *wdegree)
Definition: hilb.cc:2036
void hDegreeSeries(intvec *s1, intvec *s2, int *co, int *mu)
Definition: hilb.cc:732
intvec * hSecondSeries(intvec *hseries1)
Definition: hilb.cc:697

◆ scDimInt()

int scDimInt ( ideal  S,
ideal  Q 
)

ideal dimension

Definition at line 78 of file hdegree.cc.

79 {
80  id_Test(S, currRing);
81  if( Q!=NULL ) id_Test(Q, currRing);
82 
83  int mc;
84  hexist = hInit(S, Q, &hNexist);
85  if (!hNexist)
86  return (currRing->N);
87  hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
88  hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
89  hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
90  mc = hisModule;
91  if (!mc)
92  {
93  hrad = hexist;
94  hNrad = hNexist;
95  }
96  else
97  hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
98  radmem = hCreate((currRing->N) - 1);
99  hCo = (currRing->N) + 1;
100  loop
101  {
102  if (mc)
103  hComp(hexist, hNexist, mc, hrad, &hNrad);
104  if (hNrad)
105  {
106  hNvar = (currRing->N);
107  hRadical(hrad, &hNrad, hNvar);
108  hSupp(hrad, hNrad, hvar, &hNvar);
109  if (hNvar)
110  {
111  memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
112  hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
113  hLexR(hrad, hNrad, hvar, hNvar);
115  }
116  }
117  else
118  {
119  hCo = 0;
120  break;
121  }
122  mc--;
123  if (mc <= 0)
124  break;
125  }
126  hKill(radmem, (currRing->N) - 1);
127  omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
128  omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
129  omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
131  if (hisModule)
132  omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
133  return (currRing->N) - hCo;
134 }

◆ scDimIntRing()

int scDimIntRing ( ideal  vid,
ideal  Q 
)

scDimInt for ring-coefficients

Definition at line 136 of file hdegree.cc.

137 {
138 #ifdef HAVE_RINGS
140  {
141  int i = idPosConstant(vid);
142  if ((i != -1) && (n_IsUnit(pGetCoeff(vid->m[i]),currRing->cf)))
143  { /* ideal v contains unit; dim = -1 */
144  return(-1);
145  }
146  ideal vv = id_Head(vid,currRing);
147  idSkipZeroes(vv);
148  i = idPosConstant(vid);
149  int d;
150  if(i == -1)
151  {
152  d = scDimInt(vv, Q);
153  if(rField_is_Z(currRing))
154  d++;
155  }
156  else
157  {
158  if(n_IsUnit(pGetCoeff(vv->m[i]),currRing->cf))
159  d = -1;
160  else
161  d = scDimInt(vv, Q);
162  }
163  //Anne's Idea for std(4,2x) = 0 bug
164  int dcurr = d;
165  for(unsigned ii=0;ii<(unsigned)IDELEMS(vv);ii++)
166  {
167  if(vv->m[ii] != NULL && !n_IsUnit(pGetCoeff(vv->m[ii]),currRing->cf))
168  {
169  ideal vc = idCopy(vv);
170  poly c = pInit();
171  pSetCoeff0(c,nCopy(pGetCoeff(vv->m[ii])));
172  idInsertPoly(vc,c);
173  idSkipZeroes(vc);
174  for(unsigned jj = 0;jj<(unsigned)IDELEMS(vc)-1;jj++)
175  {
176  if((vc->m[jj]!=NULL)
177  && (n_DivBy(pGetCoeff(vc->m[jj]),pGetCoeff(c),currRing->cf)))
178  {
179  pDelete(&vc->m[jj]);
180  }
181  }
182  idSkipZeroes(vc);
183  i = idPosConstant(vc);
184  if (i != -1) pDelete(&vc->m[i]);
185  dcurr = scDimInt(vc, Q);
186  // the following assumes the ground rings to be either zero- or one-dimensional
187  if((i==-1) && rField_is_Z(currRing))
188  {
189  // should also be activated for other euclidean domains as groundfield
190  dcurr++;
191  }
192  idDelete(&vc);
193  }
194  if(dcurr > d)
195  d = dcurr;
196  }
197  idDelete(&vv);
198  return d;
199  }
200 #endif
201  return scDimInt(vid,Q);
202 }
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
int scDimInt(ideal S, ideal Q)
ideal dimension
Definition: hdegree.cc:78
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
ideal idCopy(ideal A)
Definition: ideals.h:60
#define idPosConstant(I)
index of generator with leading term in ground ring (if any); otherwise -1
Definition: ideals.h:37
#define pSetCoeff0(p, n)
Definition: monomials.h:59
#define nCopy(n)
Definition: numbers.h:15
static BOOLEAN rField_is_Z(const ring r)
Definition: ring.h:509

◆ scElKbase()

static void scElKbase ( )
static

Definition at line 1176 of file hdegree.cc.

1177 {
1178  poly q = pInit();
1179  pSetCoeff0(q,nInit(1));
1180  pSetExpV(q,act);
1181  pNext(q) = NULL;
1182  last = pNext(last) = q;
1183 }
#define pNext(p)
Definition: monomials.h:36
#define nInit(i)
Definition: numbers.h:24
#define pSetExpV(p, e)
Definition: polys.h:97

◆ scIdKbase()

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

Definition at line 1431 of file hdegree.cc.

1432 {
1433  ideal res = idInit(pLength(q), rank);
1434  polyset mm = res->m;
1435  do
1436  {
1437  *mm = q; ++mm;
1438 
1439  const poly p = pNext(q);
1440  pNext(q) = NULL;
1441  q = p;
1442 
1443  } while (q!=NULL);
1444 
1445  id_Test(res, currRing); // WRONG RANK!!!???
1446  return res;
1447 }
static int pLength(poly a)
Definition: p_polys.h:188
poly * polyset
Definition: polys.h:259

◆ scIndIntvec()

intvec* scIndIntvec ( ideal  S,
ideal  Q 
)

Definition at line 286 of file hdegree.cc.

287 {
288  id_Test(S, currRing);
289  if( Q!=NULL ) id_Test(Q, currRing);
290 
291  intvec *Set=new intvec((currRing->N));
292  int mc,i;
293  hexist = hInit(S, Q, &hNexist);
294  if (hNexist==0)
295  {
296  for(i=0; i<(currRing->N); i++)
297  (*Set)[i]=1;
298  return Set;
299  }
300  hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
301  hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
302  hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
303  hInd = (scmon)omAlloc0((1 + (currRing->N)) * sizeof(int));
304  mc = hisModule;
305  if (mc==0)
306  {
307  hrad = hexist;
308  hNrad = hNexist;
309  }
310  else
311  hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
312  radmem = hCreate((currRing->N) - 1);
313  hCo = (currRing->N) + 1;
314  loop
315  {
316  if (mc!=0)
317  hComp(hexist, hNexist, mc, hrad, &hNrad);
318  if (hNrad!=0)
319  {
320  hNvar = (currRing->N);
321  hRadical(hrad, &hNrad, hNvar);
322  hSupp(hrad, hNrad, hvar, &hNvar);
323  if (hNvar!=0)
324  {
325  memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
326  hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
327  hLexR(hrad, hNrad, hvar, hNvar);
329  }
330  }
331  else
332  {
333  hCo = 0;
334  break;
335  }
336  mc--;
337  if (mc <= 0)
338  break;
339  }
340  for(i=0; i<(currRing->N); i++)
341  (*Set)[i] = hInd[i+1];
342  hKill(radmem, (currRing->N) - 1);
343  omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
344  omFreeSize((ADDRESS)hInd, (1 + (currRing->N)) * sizeof(int));
345  omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
346  omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
348  if (hisModule)
349  omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
350  return Set;
351 }
#define omAlloc0(size)
Definition: omAllocDecl.h:211

◆ scInKbase()

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

Definition at line 1375 of file hdegree.cc.

1376 {
1377  int Ivar, Istc, i, j;
1378  scfmon sn;
1379  int x, ideg;
1380 
1381  if (Nvar == 1)
1382  {
1383  ideg = scMin(Nstc, stc, 1);
1384  while (ideg > 0)
1385  {
1386  ideg--;
1387  act[1] = ideg;
1388  scElKbase();
1389  }
1390  return;
1391  }
1392  Ivar = Nvar-1;
1393  sn = hGetmem(Nstc, stc, stcmem[Ivar]);
1394  x = scRestrict(Nstc, sn, Nvar);
1395  if (x == 0) return;
1396  ideg = x-1;
1397  loop
1398  {
1399  x = scMax(Nstc, sn, Nvar);
1400  while (ideg >= x)
1401  {
1402  act[Nvar] = ideg;
1403  scInKbase(sn, Nstc, Ivar);
1404  ideg--;
1405  }
1406  if (ideg < 0) return;
1407  Istc = Nstc;
1408  for (i=Nstc-1; i>=0; i--)
1409  {
1410  if (ideg < sn[i][Nvar])
1411  {
1412  Istc--;
1413  sn[i] = NULL;
1414  }
1415  }
1416  j = 0;
1417  while (sn[j]) j++;
1418  i = j+1;
1419  for (; i<Nstc; i++)
1420  {
1421  if (sn[i])
1422  {
1423  sn[j] = sn[i];
1424  j++;
1425  }
1426  }
1427  Nstc = Istc;
1428  }
1429 }
static int scMin(int i, scfmon stc, int Nvar)
Definition: hdegree.cc:1197
static void scInKbase(scfmon stc, int Nstc, int Nvar)
Definition: hdegree.cc:1375

◆ scKBase()

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

Definition at line 1449 of file hdegree.cc.

1450 {
1451  if( Q!=NULL) id_Test(Q, currRing);
1452 
1453  int i, di;
1454  poly p;
1455 
1456  if (deg < 0)
1457  {
1458  di = scDimInt(s, Q);
1459  if (di != 0)
1460  {
1461  //Werror("KBase not finite");
1462  return idInit(1,s->rank);
1463  }
1464  }
1465  stcmem = hCreate((currRing->N) - 1);
1466  hexist = hInit(s, Q, &hNexist);
1467  p = last = pInit();
1468  /*pNext(p) = NULL;*/
1469  act = (scmon)omAlloc(((currRing->N) + 1) * sizeof(int));
1470  *act = 0;
1471  if (!hNexist)
1472  {
1473  scAll((currRing->N), deg);
1474  goto ende;
1475  }
1476  if (!hisModule)
1477  {
1478  if (deg < 0) scInKbase(hexist, hNexist, (currRing->N));
1479  else scDegKbase(hexist, hNexist, (currRing->N), deg);
1480  }
1481  else
1482  {
1483  hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
1484  for (i = 1; i <= hisModule; i++)
1485  {
1486  *act = i;
1487  hComp(hexist, hNexist, i, hstc, &hNstc);
1488  int deg_ei=deg;
1489  if (mv!=NULL) deg_ei -= (*mv)[i-1];
1490  if ((deg < 0) || (deg_ei>=0))
1491  {
1492  if (hNstc)
1493  {
1494  if (deg < 0) scInKbase(hstc, hNstc, (currRing->N));
1495  else scDegKbase(hstc, hNstc, (currRing->N), deg_ei);
1496  }
1497  else
1498  scAll((currRing->N), deg_ei);
1499  }
1500  }
1501  omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
1502  }
1503 ende:
1505  omFreeSize((ADDRESS)act, ((currRing->N) + 1) * sizeof(int));
1506  hKill(stcmem, (currRing->N) - 1);
1507  pLmFree(&p);
1508  if (p == NULL)
1509  return idInit(1,s->rank);
1510 
1511  last = p;
1512  return scIdKbase(p, s->rank);
1513 }
const CanonicalForm int s
Definition: facAbsFact.cc:51
static ideal scIdKbase(poly q, const int rank)
Definition: hdegree.cc:1431

◆ scMax()

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

Definition at line 1185 of file hdegree.cc.

1186 {
1187  int x, y=stc[0][Nvar];
1188  for (; i;)
1189  {
1190  i--;
1191  x = stc[i][Nvar];
1192  if (x > y) y = x;
1193  }
1194  return y;
1195 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53

◆ scMin()

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

Definition at line 1197 of file hdegree.cc.

1198 {
1199  int x, y=stc[0][Nvar];
1200  for (; i;)
1201  {
1202  i--;
1203  x = stc[i][Nvar];
1204  if (x < y) y = x;
1205  }
1206  return y;
1207 }

◆ scMult0Int()

long scMult0Int ( ideal  S,
ideal  Q 
)

Definition at line 950 of file hdegree.cc.

951 {
952  id_LmTest(S, currRing);
953  if (Q!=NULL) id_LmTest(Q, currRing);
954 
955  int mc;
956  hexist = hInit(S, Q, &hNexist);
957  if (!hNexist)
958  {
959  hMu = -1;
960  return -1;
961  }
962  else
963  hMu = 0;
964 
965  const ring r = currRing;
966 
967  hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
968  hvar = (varset)omAlloc(((r->N) + 1) * sizeof(int));
969  hpur0 = (scmon)omAlloc((1 + ((r->N) * (r->N))) * sizeof(int));
970  mc = hisModule;
971  if (!mc)
972  {
973  hstc = hexist;
974  hNstc = hNexist;
975  }
976  else
977  hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
978  stcmem = hCreate((r->N) - 1);
979  loop
980  {
981  if (mc)
982  {
983  hComp(hexist, hNexist, mc, hstc, &hNstc);
984  if (!hNstc)
985  {
986  hMu = -1;
987  break;
988  }
989  }
990  hNvar = (r->N);
991  for (int i = hNvar; i; i--)
992  hvar[i] = i;
994  hSupp(hstc, hNstc, hvar, &hNvar);
995  if ((hNvar == (r->N)) && (hNstc >= (r->N)))
996  {
997  if ((hNvar > 2) && (hNstc > 10))
999  memset(hpur0, 0, ((r->N) + 1) * sizeof(int));
1000  hPure(hstc, 0, &hNstc, hvar, hNvar, hpur0, &hNpure);
1001  if (hNpure == hNvar)
1002  {
1003  hLexS(hstc, hNstc, hvar, hNvar);
1005  }
1006  else
1007  hMu = -1;
1008  }
1009  else if (hNvar)
1010  hMu = -1;
1011  mc--;
1012  if (mc <= 0 || hMu < 0)
1013  break;
1014  }
1015  hKill(stcmem, (r->N) - 1);
1016  omFreeSize((ADDRESS)hpur0, (1 + ((r->N) * (r->N))) * sizeof(int));
1017  omFreeSize((ADDRESS)hvar, ((r->N) + 1) * sizeof(int));
1018  omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
1020  if (hisModule)
1021  omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
1022  return hMu;
1023 }

◆ scMultInt()

int scMultInt ( ideal  S,
ideal  Q 
)

Definition at line 903 of file hdegree.cc.

904 {
905  id_Test(S, currRing);
906  if( Q!=NULL ) id_Test(Q, currRing);
907 
908  hDegree(S, Q);
909  return hMu;
910 }
static void hDegree(ideal S, ideal Q)
Definition: hdegree.cc:802

◆ scPrintDegree()

void scPrintDegree ( int  co,
int  mu 
)

Definition at line 912 of file hdegree.cc.

913 {
914  int di = (currRing->N)-co;
915  if (currRing->OrdSgn == 1)
916  {
917  if (di>0)
918  Print("// dimension (proj.) = %d\n// degree (proj.) = %d\n", di-1, mu);
919  else
920  Print("// dimension (affine) = 0\n// degree (affine) = %d\n", mu);
921  }
922  else
923  Print("// dimension (local) = %d\n// multiplicity = %d\n", di, mu);
924 }

◆ scRestrict()

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

Definition at line 1209 of file hdegree.cc.

1210 {
1211  int x, y;
1212  int i, j, Istc = Nstc;
1213 
1214  y = MAX_INT_VAL;
1215  for (i=Nstc-1; i>=0; i--)
1216  {
1217  j = Nvar-1;
1218  loop
1219  {
1220  if(stc[i][j] != 0) break;
1221  j--;
1222  if (j == 0)
1223  {
1224  Istc--;
1225  x = stc[i][Nvar];
1226  if (x < y) y = x;
1227  stc[i] = NULL;
1228  break;
1229  }
1230  }
1231  }
1232  if (Istc < Nstc)
1233  {
1234  for (i=Nstc-1; i>=0; i--)
1235  {
1236  if (stc[i] && (stc[i][Nvar] >= y))
1237  {
1238  Istc--;
1239  stc[i] = NULL;
1240  }
1241  }
1242  j = 0;
1243  while (stc[j]) j++;
1244  i = j+1;
1245  for(; i<Nstc; i++)
1246  {
1247  if (stc[i])
1248  {
1249  stc[j] = stc[i];
1250  j++;
1251  }
1252  }
1253  Nstc = Istc;
1254  return y;
1255  }
1256  else
1257  return -1;
1258 }
const int MAX_INT_VAL
Definition: mylimits.h:12

◆ vvDeleteColumn()

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

Definition at line 2020 of file hdegree.cc.

2021 {
2022  for (int i = 0; i < mat.size(); i++)
2023  {
2024  mat[i].erase(mat[i].begin() + col);
2025  }
2026 }

◆ vvDeleteRow()

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

Definition at line 2015 of file hdegree.cc.

2016 {
2017  mat.erase(mat.begin() + row);
2018 }

◆ vvIsColumnZero()

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

Definition at line 2038 of file hdegree.cc.

2039 {
2040  for (int i = 0; i < mat.size(); i++)
2041  {
2042  if (mat[i][col] != 0)
2043  return FALSE;
2044  }
2045  return TRUE;
2046 }

◆ vvIsRowZero()

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

Definition at line 2028 of file hdegree.cc.

2029 {
2030  for (int i = 0; i < mat[row].size(); i++)
2031  {
2032  if (mat[row][i] != 0)
2033  return FALSE;
2034  }
2035  return TRUE;
2036 }

◆ vvIsZero()

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

Definition at line 2048 of file hdegree.cc.

2049 {
2050  for (int i = 0; i < mat.size(); i++)
2051  {
2052  if (!vvIsRowZero(mat, i))
2053  return FALSE;
2054  }
2055  return TRUE;
2056 }

◆ vvMult()

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

Definition at line 2058 of file hdegree.cc.

2059 {
2060  int ra = a.size();
2061  int rb = b.size();
2062  int ca = a.size() > 0 ? a[0].size() : 0;
2063  int cb = b.size() > 0 ? b[0].size() : 0;
2064 
2065  if (ca != rb)
2066  {
2067  WerrorS("matrix dimensions do not match");
2068  return std::vector<std::vector<int> >();
2069  }
2070 
2071  std::vector<std::vector<int> > res(ra, std::vector<int>(cb));
2072  for (int i = 0; i < ra; i++)
2073  {
2074  for (int j = 0; j < cb; j++)
2075  {
2076  int sum = 0;
2077  for (int k = 0; k < ca; k++)
2078  sum += a[i][k] * b[k][j];
2079  res[i][j] = sum;
2080  }
2081  }
2082  return res;
2083 }

◆ vvPrint()

static void vvPrint ( const std::vector< std::vector< int > > &  mat)
static

Definition at line 1990 of file hdegree.cc.

1991 {
1992  for (int i = 0; i < mat.size(); i++)
1993  {
1994  for (int j = 0; j < mat[i].size(); j++)
1995  {
1996  Print("%d ", mat[i][j]);
1997  }
1998  PrintLn();
1999  }
2000 }
void PrintLn()
Definition: reporter.cc:310

◆ vvTest()

static void vvTest ( const std::vector< std::vector< int > > &  mat)
static

Definition at line 2002 of file hdegree.cc.

2003 {
2004  if (mat.size() > 0)
2005  {
2006  int cols = mat[0].size();
2007  for (int i = 1; i < mat.size(); i++)
2008  {
2009  if (cols != mat[i].size())
2010  WerrorS("number of cols in matrix inconsistent");
2011  }
2012  }
2013 }
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600

Variable Documentation

◆ act

Definition at line 1174 of file hdegree.cc.

◆ hCo

VAR int hCo

Definition at line 27 of file hdegree.cc.

◆ hInd

Definition at line 205 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 353 of file hdegree.cc.

◆ JSet

VAR indset JSet

Definition at line 353 of file hdegree.cc.

◆ last

STATIC_VAR poly last

Definition at line 1173 of file hdegree.cc.

◆ pWork

STATIC_VAR poly pWork

Definition at line 1027 of file hdegree.cc.