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 1700 of file hdegree.cc.

1701{
1702 if (length <= 0){
1703 poly one = pOne();
1704 if (p_LPDivisibleBy(M, one, currRing)) // 1 \in M => no normal words at all
1705 {
1706 pDelete(&one);
1707 last = -1;
1708 numberOfNormalWords = 0;
1709 }
1710 else
1711 {
1712 words->m[0] = one;
1713 last = 0;
1714 numberOfNormalWords = 1;
1715 }
1716 return;
1717 }
1718
1719 _lp_computeNormalWords(words, numberOfNormalWords, length - 1, M, minDeg, last);
1720
1721 int nVars = currRing->isLPring - currRing->LPncGenCount;
1722 int numberOfNewNormalWords = 0;
1723
1724 for (int j = nVars - 1; j >= 0; j--)
1725 {
1726 for (int i = last; i >= 0; i--)
1727 {
1728 int index = (j * (last + 1)) + i;
1729
1730 if (words->m[i] != NULL)
1731 {
1732 if (j > 0) {
1733 words->m[index] = pCopy(words->m[i]);
1734 }
1735
1736 int varOffset = ((length - 1) * currRing->isLPring) + 1;
1737 pSetExp(words->m[index], varOffset + j, 1);
1738 pSetm(words->m[index]);
1739 pTest(words->m[index]);
1740
1741 if (length >= minDeg && p_LPDivisibleBy(M, words->m[index], currRing))
1742 {
1743 pDelete(&words->m[index]);
1744 words->m[index] = NULL;
1745 }
1746 else
1747 {
1748 numberOfNewNormalWords++;
1749 }
1750 }
1751 }
1752 }
1753
1754 last = nVars * last + nVars - 1;
1755
1756 numberOfNormalWords += numberOfNewNormalWords;
1757}
int i
Definition: cfEzgcd.cc:132
int j
Definition: facHensel.cc:110
STATIC_VAR poly last
Definition: hdegree.cc:1172
static void _lp_computeNormalWords(ideal words, int &numberOfNormalWords, int length, ideal M, int minDeg, int &last)
Definition: hdegree.cc:1700
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 1609 of file hdegree.cc.

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

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

◆ 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 1040 of file hdegree.cc.

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

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

◆ iv2vv()

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

Definition at line 1971 of file hdegree.cc.

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

◆ lp_computeNormalWords()

static ideal lp_computeNormalWords ( int  length,
ideal  M 
)
static

Definition at line 1759 of file hdegree.cc.

1760{
1761 long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
1762 for (int i = 1; i < IDELEMS(M); i++)
1763 {
1764 minDeg = si_min(minDeg, pTotaldegree(M->m[i]));
1765 }
1766
1767 int nVars = currRing->isLPring - currRing->LPncGenCount;
1768
1769 int maxElems = 1;
1770 for (int i = 0; i < length; i++) // maxElems = nVars^n
1771 maxElems *= nVars;
1772 ideal words = idInit(maxElems);
1773 int last, numberOfNormalWords;
1774 _lp_computeNormalWords(words, numberOfNormalWords, length, M, minDeg, last);
1775 idSkipZeroes(words);
1776 return words;
1777}
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 1779 of file hdegree.cc.

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

◆ lp_gkDim()

int lp_gkDim ( const ideal  _G)

Definition at line 1861 of file hdegree.cc.

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

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

◆ lp_ufnarovskiGraph()

intvec * lp_ufnarovskiGraph ( ideal  G,
ideal &  standardWords 
)

Definition at line 1800 of file hdegree.cc.

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

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

◆ scAllKbase()

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

Definition at line 1283 of file hdegree.cc.

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

◆ scComputeHC()

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

Definition at line 1100 of file hdegree.cc.

1101{
1102 id_LmTest(S, currRing);
1103 if (Q!=NULL) id_LmTest(Q, currRing);
1104
1105 int i;
1106 int k = ak;
1107 #ifdef HAVE_RINGS
1108 if (rField_is_Ring(currRing) && (currRing->OrdSgn == -1))
1109 {
1110 //consider just monic generators (over rings with zero-divisors)
1111 ideal SS=id_Head(S,currRing);
1112 for(i=0;i<=idElem(S);i++)
1113 {
1114 if((SS->m[i]!=NULL)
1115 && ((p_IsPurePower(SS->m[i],currRing)==0)
1116 ||(!n_IsUnit(pGetCoeff(SS->m[i]), currRing->cf))))
1117 {
1118 p_Delete(&SS->m[i],currRing);
1119 }
1120 }
1121 S=id_Copy(SS,currRing);
1122 idSkipZeroes(S);
1123 }
1124 #if 0
1125 printf("\nThis is HC:\n");
1126 for(int ii=0;ii<=idElem(S);ii++)
1127 {
1128 pWrite(S->m[ii]);
1129 }
1130 //getchar();
1131 #endif
1132 #endif
1133 if(idElem(S) == 0)
1134 return;
1135 hNvar = (currRing->N);
1136 hexist = hInit(S, Q, &hNexist);
1137 if (k!=0)
1139 else
1140 hNstc = hNexist;
1141 assume(hNexist > 0);
1142 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
1143 hvar = (varset)omAlloc((hNvar + 1) * sizeof(int));
1144 hpure = (scmon)omAlloc((1 + (hNvar * hNvar)) * sizeof(int));
1145 stcmem = hCreate(hNvar - 1);
1146 for (i = hNvar; i>0; i--)
1147 hvar[i] = i;
1149 if ((hNvar > 2) && (hNstc > 10))
1151 memset(hpure, 0, (hNvar + 1) * sizeof(int));
1152 hPure(hexist, 0, &hNstc, hvar, hNvar, hpure, &hNpure);
1154 if (hEdge!=NULL)
1155 pLmFree(hEdge);
1156 hEdge = pInit();
1157 pWork = pInit();
1159 pSetComp(hEdge,ak);
1160 hKill(stcmem, hNvar - 1);
1161 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
1162 omFreeSize((ADDRESS)hvar, (hNvar + 1) * sizeof(int));
1163 omFreeSize((ADDRESS)hpure, (1 + (hNvar * hNvar)) * sizeof(int));
1165 pLmFree(pWork);
1166}
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:901
#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:69
#define id_LmTest(A, lR)
Definition: simpleideals.h:90

◆ scDegKbase()

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

Definition at line 1293 of file hdegree.cc.

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

◆ 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 * hSecondSeries(intvec *hseries1)
Definition: hilb.cc:706
intvec * hFirstSeries(ideal A, intvec *module_w, ideal Q, intvec *wdegree)
Definition: hilb.cc:2155
void hDegreeSeries(intvec *s1, intvec *s2, int *co, int *mu)
Definition: hilb.cc:741

◆ 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);
109 if (hNvar)
110 {
111 memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
112 hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
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);
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 1175 of file hdegree.cc.

1176{
1177 poly q = pInit();
1178 pSetCoeff0(q,nInit(1));
1179 pSetExpV(q,act);
1180 pNext(q) = NULL;
1181 last = pNext(last) = q;
1182}
#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 1430 of file hdegree.cc.

1431{
1432 ideal res = idInit(pLength(q), rank);
1433 polyset mm = res->m;
1434 do
1435 {
1436 *mm = q; ++mm;
1437
1438 const poly p = pNext(q);
1439 pNext(q) = NULL;
1440 q = p;
1441
1442 } while (q!=NULL);
1443
1444 id_Test(res, currRing); // WRONG RANK!!!???
1445 return res;
1446}
static int pLength(poly a)
Definition: p_polys.h:190
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);
323 if (hNvar!=0)
324 {
325 memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
326 hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
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 1374 of file hdegree.cc.

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

◆ scKBase()

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

Definition at line 1448 of file hdegree.cc.

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

◆ scMax()

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

Definition at line 1184 of file hdegree.cc.

1185{
1186 int x, y=stc[0][Nvar];
1187 for (; i;)
1188 {
1189 i--;
1190 x = stc[i][Nvar];
1191 if (x > y) y = x;
1192 }
1193 return y;
1194}
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 1196 of file hdegree.cc.

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

◆ scMult0Int()

long scMult0Int ( ideal  S,
ideal  Q 
)

Definition at line 950 of file hdegree.cc.

951{
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;
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 {
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 1208 of file hdegree.cc.

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

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

◆ vvDeleteRow()

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

Definition at line 2014 of file hdegree.cc.

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

◆ vvIsColumnZero()

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

Definition at line 2037 of file hdegree.cc.

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

◆ vvIsRowZero()

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

Definition at line 2027 of file hdegree.cc.

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

◆ vvIsZero()

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

Definition at line 2047 of file hdegree.cc.

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

◆ 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 2057 of file hdegree.cc.

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

◆ vvPrint()

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

Definition at line 1989 of file hdegree.cc.

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

◆ vvTest()

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

Definition at line 2001 of file hdegree.cc.

2002{
2003 if (mat.size() > 0)
2004 {
2005 int cols = mat[0].size();
2006 for (int i = 1; i < mat.size(); i++)
2007 {
2008 if (cols != mat[i].size())
2009 WerrorS("number of cols in matrix inconsistent");
2010 }
2011 }
2012}
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 1173 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 1172 of file hdegree.cc.

◆ pWork

STATIC_VAR poly pWork

Definition at line 1027 of file hdegree.cc.