My Project
Loading...
Searching...
No Matches
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
 
int scDimIntRing (ideal vid, ideal Q)
 scDimInt for ring-coefficients
 
static void hIndSolve (scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
 
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)
 
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< intcountCycles (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 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 1672 of file hdegree.cc.

1673{
1674 if (length <= 0){
1675 poly one = pOne();
1676 if (p_LPDivisibleBy(M, one, currRing)) // 1 \in M => no normal words at all
1677 {
1678 pDelete(&one);
1679 last = -1;
1681 }
1682 else
1683 {
1684 words->m[0] = one;
1685 last = 0;
1687 }
1688 return;
1689 }
1690
1692
1693 int nVars = currRing->isLPring - currRing->LPncGenCount;
1694 int numberOfNewNormalWords = 0;
1695
1696 for (int j = nVars - 1; j >= 0; j--)
1697 {
1698 for (int i = last; i >= 0; i--)
1699 {
1700 int index = (j * (last + 1)) + i;
1701
1702 if (words->m[i] != NULL)
1703 {
1704 if (j > 0) {
1705 words->m[index] = pCopy(words->m[i]);
1706 }
1707
1708 int varOffset = ((length - 1) * currRing->isLPring) + 1;
1709 pSetExp(words->m[index], varOffset + j, 1);
1710 pSetm(words->m[index]);
1711 pTest(words->m[index]);
1712
1714 {
1715 pDelete(&words->m[index]);
1716 words->m[index] = NULL;
1717 }
1718 else
1719 {
1721 }
1722 }
1723 }
1724 }
1725
1726 last = nVars * last + nVars - 1;
1727
1729}
int i
Definition cfEzgcd.cc:132
int j
Definition facHensel.cc:110
STATIC_VAR poly last
Definition hdegree.cc:1144
static void _lp_computeNormalWords(ideal words, int &numberOfNormalWords, int length, ideal M, int minDeg, int &last)
Definition hdegree.cc:1672
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)
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 1581 of file hdegree.cc.

1582{
1583 intvec* G = ivCopy(_G); // modifications must be local
1584
1585 if (cache[v] != -2) return cache; // value is already cached
1586
1587 visited[v] = TRUE;
1588 path.push_back(v);
1589
1590 int cycles = 0;
1591 for (int w = 0; w < G->cols(); w++)
1592 {
1593 if (IMATELEM(*G, v + 1, w + 1)) // edge v -> w exists in G
1594 {
1595 if (!visited[w])
1596 { // continue with w
1598 if (cache[w] == -1)
1599 {
1600 cache[v] = -1;
1601 return cache;
1602 }
1603 cycles = si_max(cycles, cache[w]);
1604 }
1605 else
1606 { // found new cycle
1607 int pathIndexOfW = -1;
1608 for (int i = path.size() - 1; i >= 0; i--) {
1609 if (cyclic[path[i]] == 1) { // found an already cyclic vertex
1610 cache[v] = -1;
1611 return cache;
1612 }
1613 cyclic[path[i]] = TRUE;
1614
1615 if (path[i] == w) { // end of the cycle
1616 assume(IMATELEM(*G, v + 1, w + 1) != 0);
1617 IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v -> w
1618 pathIndexOfW = i;
1619 break;
1620 } else {
1621 assume(IMATELEM(*G, path[i - 1] + 1, path[i] + 1) != 0);
1622 IMATELEM(*G, path[i - 1] + 1, path[i] + 1) = 0; // remove edge vi-1 -> vi
1623 }
1624 }
1625 assume(pathIndexOfW != -1); // should never happen
1626 for (int i = path.size() - 1; i >= pathIndexOfW; i--) {
1628 if (cache[path[i]] == -1)
1629 {
1630 cache[v] = -1;
1631 return cache;
1632 }
1633 cycles = si_max(cycles, cache[path[i]] + 1);
1634 }
1635 }
1636 }
1637 }
1638 cache[v] = cycles;
1639
1640 delete G;
1641 return cache;
1642}
static int si_max(const int a, const int b)
Definition auxiliary.h:124
#define TRUE
Definition auxiliary.h:100
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:1581
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:387

◆ graphGrowth()

static int graphGrowth ( const intvec * G)
static

Definition at line 1645 of file hdegree.cc.

1646{
1647 // init
1648 int n = G->cols();
1649 std::vector<int> path;
1650 std::vector<BOOLEAN> visited;
1651 std::vector<BOOLEAN> cyclic;
1652 std::vector<int> cache;
1653 visited.resize(n, FALSE);
1654 cyclic.resize(n, FALSE);
1655 cache.resize(n, -2);
1656
1657 // get max number of cycles
1658 int cycles = 0;
1659 for (int v = 0; v < n; v++)
1660 {
1662 if (cache[v] == -1)
1663 return -1;
1664 cycles = si_max(cycles, cache[v]);
1665 }
1666 return cycles;
1667}
#define FALSE
Definition auxiliary.h:96

◆ hCheck1()

static BOOLEAN hCheck1 ( indset sm,
scmon pure )
static

Definition at line 463 of file hdegree.cc.

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

◆ hCheck2()

static indset hCheck2 ( indset sm,
scmon pure )
static

Definition at line 489 of file hdegree.cc.

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

◆ hCheckIndep()

static void hCheckIndep ( scmon pure)
static

Definition at line 541 of file hdegree.cc.

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

◆ hDegree()

static void hDegree ( ideal S,
ideal Q )
static

Definition at line 800 of file hdegree.cc.

801{
802 id_Test(S, currRing);
803 if( Q!=NULL ) id_Test(Q, currRing);
804
805 int di;
806 int mc;
807 hexist = hInit(S, Q, &hNexist);
808 if (!hNexist)
809 {
810 hCo = 0;
811 hMu = 1;
812 return;
813 }
814 //hWeight();
815 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
816 hvar = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
817 hsel = (varset)omAlloc(((currRing->N) + 1) * sizeof(int));
818 hpure = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
819 hpur0 = (scmon)omAlloc((1 + ((currRing->N) * (currRing->N))) * sizeof(int));
820 mc = hisModule;
821 hrad = (scfmon)omAlloc(hNexist * sizeof(scmon));
822 if (!mc)
823 {
824 memcpy(hrad, hexist, hNexist * sizeof(scmon));
825 hstc = hexist;
826 hNrad = hNstc = hNexist;
827 }
828 else
829 hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
830 radmem = hCreate((currRing->N) - 1);
831 stcmem = hCreate((currRing->N) - 1);
832 hCo = (currRing->N) + 1;
833 di = hCo + 1;
834 loop
835 {
836 if (mc)
837 {
838 hComp(hexist, hNexist, mc, hrad, &hNrad);
839 hNstc = hNrad;
840 memcpy(hstc, hrad, hNrad * sizeof(scmon));
841 }
842 if (hNrad)
843 {
844 hNvar = (currRing->N);
847 if (hNvar)
848 {
849 hCo = hNvar;
850 memset(hpure, 0, ((currRing->N) + 1) * sizeof(int));
851 hPure(hrad, 0, &hNrad, hvar, hNvar, hpure, &hNpure);
854 }
855 }
856 else
857 {
858 hNvar = 1;
859 hCo = 0;
860 }
861 if (hCo < di)
862 {
863 di = hCo;
864 hMu = 0;
865 }
866 if (hNvar && (hCo == di))
867 {
868 if (di && (di < (currRing->N)))
870 else if (!di)
871 hMu++;
872 else
873 {
875 if ((hNvar > 2) && (hNstc > 10))
877 memset(hpur0, 0, ((currRing->N) + 1) * sizeof(int));
878 hPure(hstc, 0, &hNstc, hvar, hNvar, hpur0, &hNpure);
881 }
882 }
883 mc--;
884 if (mc <= 0)
885 break;
886 }
887 hCo = di;
888 hKill(stcmem, (currRing->N) - 1);
889 hKill(radmem, (currRing->N) - 1);
890 omFreeSize((ADDRESS)hpur0, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
891 omFreeSize((ADDRESS)hpure, (1 + ((currRing->N) * (currRing->N))) * sizeof(int));
892 omFreeSize((ADDRESS)hsel, ((currRing->N) + 1) * sizeof(int));
893 omFreeSize((ADDRESS)hvar, ((currRing->N) + 1) * sizeof(int));
894 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
895 omFreeSize((ADDRESS)hrad, hNexist * sizeof(scmon));
897 if (hisModule)
898 omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
899}
static long hZeroMult(scmon pure, scfmon stc, int Nstc, varset var, int Nvar)
Definition hdegree.cc:619
static void hDimMult(scmon pure, int Npure, scfmon rad, int Nrad, varset var, int Nvar)
Definition hdegree.cc:724
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
#define omFreeSize(addr, size)
#define omAlloc(size)
#define id_Test(A, lR)
#define Q
Definition sirandom.c:26

◆ hDimMult()

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

Definition at line 724 of file hdegree.cc.

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

1004{
1005 pSetm(pWork);
1006 if (pLmCmp(pWork, hEdge) == currRing->OrdSgn)
1007 {
1008 for (int i = hNvar; i>0; i--)
1010 pSetm(hEdge);
1011 }
1012}
STATIC_VAR poly pWork
Definition hdegree.cc:1001
#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 1014 of file hdegree.cc.

1016{
1017 int iv = Nvar -1, k = var[Nvar], a, a0, a1, b, i;
1018 int x/*, x0*/;
1019 scmon pn;
1020 scfmon sn;
1021 if (iv==0)
1022 {
1023 pSetExp(pWork, k, pure[k]);
1024 hHedge(hEdge);
1025 return;
1026 }
1027 else if (Nstc==0)
1028 {
1029 for (i = Nvar; i>0; i--)
1030 pSetExp(pWork, var[i], pure[var[i]]);
1031 hHedge(hEdge);
1032 return;
1033 }
1034 x = a = 0;
1035 pn = hGetpure(pure);
1036 sn = hGetmem(Nstc, stc, stcmem[iv]);
1037 hStepS(sn, Nstc, var, Nvar, &a, &x);
1038 if (a == Nstc)
1039 {
1040 pSetExp(pWork, k, pure[k]);
1041 hHedgeStep(pn, sn, a, var, iv,hEdge);
1042 return;
1043 }
1044 else
1045 {
1046 pSetExp(pWork, k, x);
1047 hHedgeStep(pn, sn, a, var, iv,hEdge);
1048 }
1049 b = a;
1050 loop
1051 {
1052 a0 = a;
1053 // x0 = x;
1054 hStepS(sn, Nstc, var, Nvar, &a, &x);
1055 hElimS(sn, &b, a0, a, var, iv);
1056 a1 = a;
1057 hPure(sn, a0, &a1, var, iv, pn, &i);
1058 hLex2S(sn, b, a0, a1, var, iv, hwork);
1059 b += (a1 - a0);
1060 if (a < Nstc)
1061 {
1062 pSetExp(pWork, k, x);
1063 hHedgeStep(pn, sn, b, var, iv,hEdge);
1064 }
1065 else
1066 {
1067 pSetExp(pWork, k, pure[k]);
1068 hHedgeStep(pn, sn, b, var, iv,hEdge);
1069 return;
1070 }
1071 }
1072}
int k
Definition cfEzgcd.cc:99
static void hHedgeStep(scmon pure, scfmon stc, int Nstc, varset var, int Nvar, poly hEdge)
Definition hdegree.cc:1014
static void hHedge(poly hEdge)
Definition hdegree.cc:1003
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 562 of file hdegree.cc.

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

◆ hIndep()

static void hIndep ( scmon pure)
static

Definition at line 368 of file hdegree.cc.

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

◆ hIndMult()

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

Definition at line 382 of file hdegree.cc.

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

◆ hIndSolve()

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

Definition at line 205 of file hdegree.cc.

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

◆ hNotZero()

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

Definition at line 353 of file hdegree.cc.

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

◆ hProject()

static void hProject ( scmon pure,
varset sel )
static

Definition at line 701 of file hdegree.cc.

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

◆ hZeroMult()

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

Definition at line 619 of file hdegree.cc.

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

2061{
2062 // init
2063 int n = G->cols();
2064 std::vector<int> path;
2065 std::vector<BOOLEAN> visited;
2066 std::vector<BOOLEAN> cyclic;
2067 std::vector<int> cache;
2068 visited.resize(n, FALSE);
2069 cyclic.resize(n, FALSE);
2070 cache.resize(n, -2);
2071
2072 for (int v = 0; v < n; v++)
2073 {
2075 // check that there are 0 cycles from v
2076 if (cache[v] != 0)
2077 return FALSE;
2078 }
2079 return TRUE;
2080}

◆ iv2vv()

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

Definition at line 1943 of file hdegree.cc.

1944{
1945 int rows = M->rows();
1946 int cols = M->cols();
1947
1948 std::vector<std::vector<int> > mat(rows, std::vector<int>(cols));
1949
1950 for (int i = 0; i < rows; i++)
1951 {
1952 for (int j = 0; j < cols; j++)
1953 {
1954 mat[i][j] = IMATELEM(*M, i + 1, j + 1);
1955 }
1956 }
1957
1958 return mat;
1959}

◆ lp_computeNormalWords()

static ideal lp_computeNormalWords ( int length,
ideal M )
static

Definition at line 1731 of file hdegree.cc.

1732{
1733 long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
1734 for (int i = 1; i < IDELEMS(M); i++)
1735 {
1737 }
1738
1739 int nVars = currRing->isLPring - currRing->LPncGenCount;
1740
1741 int maxElems = 1;
1742 for (int i = 0; i < length; i++) // maxElems = nVars^n
1743 maxElems *= nVars;
1748 return words;
1749}
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
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)

◆ lp_countNormalWords()

static int lp_countNormalWords ( int upToLength,
ideal M )
static

Definition at line 1751 of file hdegree.cc.

1752{
1753 long minDeg = IDELEMS(M) > 0 ? pTotaldegree(M->m[0]) : 0;
1754 for (int i = 1; i < IDELEMS(M); i++)
1755 {
1757 }
1758
1759 int nVars = currRing->isLPring - currRing->LPncGenCount;
1760
1761 int maxElems = 1;
1762 for (int i = 0; i < upToLength; i++) // maxElems = nVars^n
1763 maxElems *= nVars;
1767 idDelete(&words);
1768 return numberOfNormalWords;
1769}
#define idDelete(H)
delete an ideal
Definition ideals.h:29

◆ lp_gkDim()

int lp_gkDim ( const ideal _G)

Definition at line 1833 of file hdegree.cc.

1834{
1836
1837 if (rField_is_Ring(currRing)) {
1838 WerrorS("GK-Dim not implemented for rings");
1839 return -2;
1840 }
1841
1842 for (int i=IDELEMS(_G)-1;i>=0; i--)
1843 {
1844 if (_G->m[i] != NULL)
1845 {
1846 if (pGetComp(_G->m[i]) != 0)
1847 {
1848 WerrorS("GK-Dim not implemented for modules");
1849 return -2;
1850 }
1851 if (pGetNCGen(_G->m[i]) != 0)
1852 {
1853 WerrorS("GK-Dim not implemented for bi-modules");
1854 return -2;
1855 }
1856 }
1857 }
1858
1859 ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
1860 idSkipZeroes(G); // remove zeros
1861 id_DelLmEquals(G, currRing); // remove duplicates
1862
1863 // check if G is the zero ideal
1864 if (IDELEMS(G) == 1 && G->m[0] == NULL)
1865 {
1866 // NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
1867 int lV = currRing->isLPring;
1868 int ncGenCount = currRing->LPncGenCount;
1869 if (lV - ncGenCount == 0)
1870 {
1871 idDelete(&G);
1872 return 0;
1873 }
1874 if (lV - ncGenCount == 1)
1875 {
1876 idDelete(&G);
1877 return 1;
1878 }
1879 if (lV - ncGenCount >= 2)
1880 {
1881 idDelete(&G);
1882 return -1;
1883 }
1884 }
1885
1886 // get the max deg
1887 long maxDeg = 0;
1888 for (int i = 0; i < IDELEMS(G); i++)
1889 {
1891
1892 // also check whether G = <1>
1893 if (pIsConstantComp(G->m[i]))
1894 {
1895 WerrorS("GK-Dim not defined for 0-ring");
1896 idDelete(&G);
1897 return -2;
1898 }
1899 }
1900
1901 // early termination if G \subset X
1902 if (maxDeg <= 1)
1903 {
1904 int lV = currRing->isLPring;
1905 int ncGenCount = currRing->LPncGenCount;
1906 if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
1907 {
1908 idDelete(&G);
1909 return 0;
1910 }
1911 if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
1912 {
1913 idDelete(&G);
1914 return 1;
1915 }
1916 if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
1917 {
1918 idDelete(&G);
1919 return -1;
1920 }
1921 }
1922
1925 if (UG == NULL)
1926 {
1927 idDelete(&G);
1928 return -2;
1929 }
1930 if (errorreported)
1931 {
1932 delete UG;
1933 idDelete(&G);
1934 return -2;
1935 }
1936 int gkDim = graphGrowth(UG);
1937 delete UG;
1938 idDelete(&G);
1939 return gkDim;
1940}
static int graphGrowth(const intvec *G)
Definition hdegree.cc:1645
intvec * lp_ufnarovskiGraph(ideal G, ideal &standardWords)
Definition hdegree.cc:1772
#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:490
#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 2087 of file hdegree.cc.

2088{
2089 if (rField_is_Ring(currRing)) {
2090 WerrorS("K-Dim not implemented for rings");
2091 return -2;
2092 }
2093
2094 for (int i=IDELEMS(_G)-1;i>=0; i--)
2095 {
2096 if (_G->m[i] != NULL)
2097 {
2098 if (pGetComp(_G->m[i]) != 0)
2099 {
2100 WerrorS("K-Dim not implemented for modules");
2101 return -2;
2102 }
2103 if (pGetNCGen(_G->m[i]) != 0)
2104 {
2105 WerrorS("K-Dim not implemented for bi-modules");
2106 return -2;
2107 }
2108 }
2109 }
2110
2111 ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
2112 if (TEST_OPT_PROT)
2113 Print("%d original generators\n", IDELEMS(G));
2114 idSkipZeroes(G); // remove zeros
2115 id_DelLmEquals(G, currRing); // remove duplicates
2116 if (TEST_OPT_PROT)
2117 Print("%d non-zero unique generators\n", IDELEMS(G));
2118
2119 // check if G is the zero ideal
2120 if (IDELEMS(G) == 1 && G->m[0] == NULL)
2121 {
2122 // NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
2123 int lV = currRing->isLPring;
2124 int ncGenCount = currRing->LPncGenCount;
2125 if (lV - ncGenCount == 0)
2126 {
2127 idDelete(&G);
2128 return 1;
2129 }
2130 if (lV - ncGenCount == 1)
2131 {
2132 idDelete(&G);
2133 return -1;
2134 }
2135 if (lV - ncGenCount >= 2)
2136 {
2137 idDelete(&G);
2138 return -1;
2139 }
2140 }
2141
2142 // get the max deg
2143 long maxDeg = 0;
2144 for (int i = 0; i < IDELEMS(G); i++)
2145 {
2147
2148 // also check whether G = <1>
2149 if (pIsConstantComp(G->m[i]))
2150 {
2151 WerrorS("K-Dim not defined for 0-ring"); // TODO is it minus infinity ?
2152 idDelete(&G);
2153 return -2;
2154 }
2155 }
2156 if (TEST_OPT_PROT)
2157 Print("max deg: %ld\n", maxDeg);
2158
2159
2160 // for normal words of length minDeg ... maxDeg-1
2161 // brute-force the normal words
2162 if (TEST_OPT_PROT)
2163 PrintS("Computing normal words normally...\n");
2165
2166 if (TEST_OPT_PROT)
2167 Print("%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1);
2168
2169 // early termination if G \subset X
2170 if (maxDeg <= 1)
2171 {
2172 int lV = currRing->isLPring;
2173 int ncGenCount = currRing->LPncGenCount;
2174 if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
2175 {
2176 idDelete(&G);
2177 return numberOfNormalWords;
2178 }
2179 if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
2180 {
2181 idDelete(&G);
2182 return -1;
2183 }
2184 if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
2185 {
2186 idDelete(&G);
2187 return -1;
2188 }
2189 }
2190
2191 if (TEST_OPT_PROT)
2192 PrintS("Computing Ufnarovski graph...\n");
2193
2196 if (UG == NULL)
2197 {
2198 idDelete(&G);
2199 return -2;
2200 }
2201 if (errorreported)
2202 {
2203 delete UG;
2204 idDelete(&G);
2205 return -2;
2206 }
2207
2208 if (TEST_OPT_PROT)
2209 Print("Ufnarovski graph is %dx%d.\n", UG->rows(), UG->cols());
2210
2211 if (TEST_OPT_PROT)
2212 PrintS("Checking whether Ufnarovski graph is acyclic...\n");
2213
2214 if (!isAcyclic(UG))
2215 {
2216 // in this case we have infinitely many normal words
2217 return -1;
2218 }
2219
2220 std::vector<std::vector<int> > vvUG = iv2vv(UG);
2221 for (std::vector<std::vector<int> >::size_type i = 0; i < vvUG.size(); i++)
2222 {
2223 if (vvIsRowZero(vvUG, i) && vvIsColumnZero(vvUG, i)) // i is isolated vertex
2224 {
2225 vvDeleteRow(vvUG, i);
2227 i--;
2228 }
2229 }
2230 if (TEST_OPT_PROT)
2231 Print("Simplified Ufnarovski graph to %dx%d.\n", (int)vvUG.size(), (int)vvUG.size());
2232
2233 // for normal words of length >= maxDeg
2234 // use Ufnarovski graph
2235 if (TEST_OPT_PROT)
2236 PrintS("Computing normal words via Ufnarovski graph...\n");
2237 std::vector<std::vector<int> > UGpower = vvUG;
2238 long nUGpower = 1;
2239 while (!vvIsZero(UGpower))
2240 {
2241 if (TEST_OPT_PROT)
2242 PrintS("Start count graph entries.\n");
2243 for (std::vector<std::vector<int> >::size_type i = 0; i < UGpower.size(); i++)
2244 {
2245 for (std::vector<std::vector<int> >::size_type j = 0; j < UGpower[i].size(); j++)
2246 {
2248 }
2249 }
2250
2251 if (TEST_OPT_PROT)
2252 {
2253 PrintS("Done count graph entries.\n");
2254 Print("%ld normal words up to length %ld\n", numberOfNormalWords, maxDeg - 1 + nUGpower);
2255 }
2256
2257 if (TEST_OPT_PROT)
2258 PrintS("Start mat mult.\n");
2259 UGpower = vvMult(UGpower, vvUG); // TODO: avoid creation of new intvec
2260 if (TEST_OPT_PROT)
2261 PrintS("Done mat mult.\n");
2262 nUGpower++;
2263 }
2264
2265 delete UG;
2266 idDelete(&G);
2267 return numberOfNormalWords;
2268}
#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:2033
static void vvDeleteRow(std::vector< std::vector< int > > &mat, int row)
Definition hdegree.cc:1990
static BOOLEAN vvIsColumnZero(const std::vector< std::vector< int > > &mat, int col)
Definition hdegree.cc:2013
static void vvDeleteColumn(std::vector< std::vector< int > > &mat, int col)
Definition hdegree.cc:1995
static std::vector< std::vector< int > > iv2vv(intvec *M)
Definition hdegree.cc:1943
static int lp_countNormalWords(int upToLength, ideal M)
Definition hdegree.cc:1751
static BOOLEAN isAcyclic(const intvec *G)
Definition hdegree.cc:2060
static BOOLEAN vvIsZero(const std::vector< std::vector< int > > &mat)
Definition hdegree.cc:2023
static BOOLEAN vvIsRowZero(const std::vector< std::vector< int > > &mat, int row)
Definition hdegree.cc:2003
#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 1772 of file hdegree.cc.

1773{
1774 long l = 0;
1775 for (int i = 0; i < IDELEMS(G); i++)
1776 l = si_max(pTotaldegree(G->m[i]), l);
1777 l--;
1778 if (l <= 0)
1779 {
1780 WerrorS("Ufnarovski graph not implemented for l <= 0");
1781 return NULL;
1782 }
1783 int lV = currRing->isLPring;
1784
1786
1787 int n = IDELEMS(standardWords);
1788 intvec* UG = new intvec(n, n, 0);
1789 for (int i = 0; i < n; i++)
1790 {
1791 for (int j = 0; j < n; j++)
1792 {
1793 poly v = standardWords->m[i];
1794 poly w = standardWords->m[j];
1795
1796 // check whether v*x1 = x2*w (overlap)
1797 bool overlap = true;
1798 for (int k = 1; k <= (l - 1) * lV; k++)
1799 {
1800 if (pGetExp(v, k + lV) != pGetExp(w, k)) {
1801 overlap = false;
1802 break;
1803 }
1804 }
1805
1806 if (overlap)
1807 {
1808 // create the overlap
1809 poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing));
1810
1811 // check whether the overlap is normal
1812 bool normal = true;
1813 for (int k = 0; k < IDELEMS(G); k++)
1814 {
1815 if (p_LPDivisibleBy(G->m[k], p, currRing))
1816 {
1817 normal = false;
1818 break;
1819 }
1820 }
1821
1822 if (normal)
1823 {
1824 IMATELEM(*UG, i + 1, j + 1) = 1;
1825 }
1826 }
1827 }
1828 }
1829 return UG;
1830}
int l
Definition cfEzgcd.cc:100
int p
Definition cfModGcd.cc:4086
static ideal lp_computeNormalWords(int length, ideal M)
Definition hdegree.cc:1731
#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 1231 of file hdegree.cc.

1232{
1233 int i;
1234 int d = deg;
1235 if (d == 0)
1236 {
1237 for (i=Nvar; i; i--) act[i] = 0;
1238 scElKbase();
1239 return;
1240 }
1241 if (Nvar == 1)
1242 {
1243 act[1] = d;
1244 scElKbase();
1245 return;
1246 }
1247 do
1248 {
1249 act[Nvar] = d;
1250 scAll(Nvar-1, deg-d);
1251 d--;
1252 } while (d >= 0);
1253}
static void scElKbase()
Definition hdegree.cc:1147
static void scAll(int Nvar, int deg)
Definition hdegree.cc:1231
STATIC_VAR scmon act
Definition hdegree.cc:1145

◆ scAllKbase()

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

Definition at line 1255 of file hdegree.cc.

1256{
1257 do
1258 {
1259 act[Nvar] = ideg;
1260 scAll(Nvar-1, deg-ideg);
1261 ideg--;
1262 } while (ideg >= 0);
1263}

◆ scComputeHC()

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

Definition at line 1074 of file hdegree.cc.

1075{
1076 id_LmTest(S, currRing);
1077 if (Q!=NULL) id_LmTest(Q, currRing);
1078
1079 int i;
1080 int k = ak;
1081 if (rField_is_Ring(currRing) && (currRing->OrdSgn == -1))
1082 {
1083 //consider just monic generators (over rings with zero-divisors)
1085 for(i=0;i<=idElem(S);i++)
1086 {
1087 if((SS->m[i]!=NULL)
1088 && ((p_IsPurePower(SS->m[i],currRing)==0)
1089 ||(!n_IsUnit(pGetCoeff(SS->m[i]), currRing->cf))))
1090 {
1091 p_Delete(&SS->m[i],currRing);
1092 }
1093 }
1094 S=id_Copy(SS,currRing);
1095 idSkipZeroes(S);
1096 }
1097 #if 0
1098 printf("\nThis is HC:\n");
1099 for(int ii=0;ii<=idElem(S);ii++)
1100 {
1101 pWrite(S->m[ii]);
1102 }
1103 //getchar();
1104 #endif
1105 if(idElem(S) == 0)
1106 return;
1107 hNvar = (currRing->N);
1108 hexist = hInit(S, Q, &hNexist);
1109 if (k!=0)
1111 else
1112 hNstc = hNexist;
1113 assume(hNexist > 0);
1114 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
1115 hvar = (varset)omAlloc((hNvar + 1) * sizeof(int));
1116 hpure = (scmon)omAlloc((1 + (hNvar * hNvar)) * sizeof(int));
1117 stcmem = hCreate(hNvar - 1);
1118 for (i = hNvar; i>0; i--)
1119 hvar[i] = i;
1121 if ((hNvar > 2) && (hNstc > 10))
1123 memset(hpure, 0, (hNvar + 1) * sizeof(int));
1124 hPure(hexist, 0, &hNstc, hvar, hNvar, hpure, &hNpure);
1126 if (hEdge!=NULL)
1127 pLmFree(hEdge);
1128 hEdge = pInit();
1129 pWork = pInit();
1131 pSetComp(hEdge,ak);
1132 hKill(stcmem, hNvar - 1);
1133 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
1134 omFreeSize((ADDRESS)hvar, (hNvar + 1) * sizeof(int));
1135 omFreeSize((ADDRESS)hpure, (1 + (hNvar * hNvar)) * sizeof(int));
1137 pLmFree(pWork);
1138}
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:519
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:1227
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
#define id_LmTest(A, lR)

◆ scDegKbase()

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

Definition at line 1265 of file hdegree.cc.

1266{
1267 int Ivar, Istc, i, j;
1268 scfmon sn;
1269 int x, ideg;
1270
1271 if (deg == 0)
1272 {
1273 for (i=Nstc-1; i>=0; i--)
1274 {
1275 for (j=Nvar;j;j--){ if(stc[i][j]) break; }
1276 if (j==0){return;}
1277 }
1278 for (i=Nvar; i; i--) act[i] = 0;
1279 scElKbase();
1280 return;
1281 }
1282 if (Nvar == 1)
1283 {
1284 for (i=Nstc-1; i>=0; i--) if(deg >= stc[i][1]) return;
1285 act[1] = deg;
1286 scElKbase();
1287 return;
1288 }
1289 Ivar = Nvar-1;
1290 sn = hGetmem(Nstc, stc, stcmem[Ivar]);
1291 x = scRestrict(Nstc, sn, Nvar);
1292 if (x <= 0)
1293 {
1294 if (x == 0) return;
1295 ideg = deg;
1296 }
1297 else
1298 {
1299 if (deg < x) ideg = deg;
1300 else ideg = x-1;
1301 if (Nstc == 0)
1302 {
1303 scAllKbase(Nvar, ideg, deg);
1304 return;
1305 }
1306 }
1307 loop
1308 {
1309 x = scMax(Nstc, sn, Nvar);
1310 while (ideg >= x)
1311 {
1312 act[Nvar] = ideg;
1313 scDegKbase(sn, Nstc, Ivar, deg-ideg);
1314 ideg--;
1315 }
1316 if (ideg < 0) return;
1317 Istc = Nstc;
1318 for (i=Nstc-1; i>=0; i--)
1319 {
1320 if (ideg < sn[i][Nvar])
1321 {
1322 Istc--;
1323 sn[i] = NULL;
1324 }
1325 }
1326 if (Istc == 0)
1327 {
1328 scAllKbase(Nvar, ideg, deg);
1329 return;
1330 }
1331 j = 0;
1332 while (sn[j]) j++;
1333 i = j+1;
1334 for (; i<Nstc; i++)
1335 {
1336 if (sn[i])
1337 {
1338 sn[j] = sn[i];
1339 j++;
1340 }
1341 }
1342 Nstc = Istc;
1343 }
1344}
static int scRestrict(int &Nstc, scfmon stc, int Nvar)
Definition hdegree.cc:1180
static void scAllKbase(int Nvar, int ideg, int deg)
Definition hdegree.cc:1255
static void scDegKbase(scfmon stc, int Nstc, int Nvar, int deg)
Definition hdegree.cc:1265
static int scMax(int i, scfmon stc, int Nvar)
Definition hdegree.cc:1156

◆ 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{
139 {
140 int i = idPosConstant(vid);
141 if ((i != -1) && (n_IsUnit(pGetCoeff(vid->m[i]),currRing->cf)))
142 { /* ideal v contains unit; dim = -1 */
143 return(-1);
144 }
148 int d;
149 if(i == -1)
150 {
151 d = scDimInt(vv, Q);
153 d++;
154 }
155 else
156 {
157 if(n_IsUnit(pGetCoeff(vv->m[i]),currRing->cf))
158 d = -1;
159 else
160 d = scDimInt(vv, Q);
161 }
162 //Anne's Idea for std(4,2x) = 0 bug
163 int dcurr = d;
164 for(unsigned ii=0;ii<(unsigned)IDELEMS(vv);ii++)
165 {
166 if(vv->m[ii] != NULL && !n_IsUnit(pGetCoeff(vv->m[ii]),currRing->cf))
167 {
168 ideal vc = idCopy(vv);
169 poly c = pInit();
170 pSetCoeff0(c,nCopy(pGetCoeff(vv->m[ii])));
171 idInsertPoly(vc,c);
173 for(unsigned jj = 0;jj<(unsigned)IDELEMS(vc)-1;jj++)
174 {
175 if((vc->m[jj]!=NULL)
176 && (n_DivBy(pGetCoeff(vc->m[jj]),pGetCoeff(c),currRing->cf)))
177 {
178 pDelete(&vc->m[jj]);
179 }
180 }
182 i = idPosConstant(vc);
183 if (i != -1) pDelete(&vc->m[i]);
184 dcurr = scDimInt(vc, Q);
185 // the following assumes the ground rings to be either zero- or one-dimensional
186 if((i==-1) && rField_is_Z(currRing))
187 {
188 // should also be activated for other euclidean domains as groundfield
189 dcurr++;
190 }
191 idDelete(&vc);
192 }
193 if(dcurr > d)
194 d = dcurr;
195 }
196 idDelete(&vv);
197 return d;
198 }
199 return scDimInt(vid,Q);
200}
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:748
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:514

◆ scElKbase()

static void scElKbase ( )
static

Definition at line 1147 of file hdegree.cc.

1148{
1149 poly q = pInit();
1150 pSetCoeff0(q,nInit(1));
1151 pSetExpV(q,act);
1152 pNext(q) = NULL;
1153 last = pNext(last) = q;
1154}
#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 1402 of file hdegree.cc.

1403{
1404 ideal res = idInit(pLength(q), rank);
1405 polyset mm = res->m;
1406 do
1407 {
1408 *mm = q; ++mm;
1409
1410 const poly p = pNext(q);
1411 pNext(q) = NULL;
1412 q = p;
1413
1414 } while (q!=NULL);
1415
1416 id_Test(res, currRing); // WRONG RANK!!!???
1417 return res;
1418}
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 284 of file hdegree.cc.

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

◆ scInKbase()

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

Definition at line 1346 of file hdegree.cc.

1347{
1348 int Ivar, Istc, i, j;
1349 scfmon sn;
1350 int x, ideg;
1351
1352 if (Nvar == 1)
1353 {
1354 ideg = scMin(Nstc, stc, 1);
1355 while (ideg > 0)
1356 {
1357 ideg--;
1358 act[1] = ideg;
1359 scElKbase();
1360 }
1361 return;
1362 }
1363 Ivar = Nvar-1;
1364 sn = hGetmem(Nstc, stc, stcmem[Ivar]);
1365 x = scRestrict(Nstc, sn, Nvar);
1366 if (x == 0) return;
1367 ideg = x-1;
1368 loop
1369 {
1370 x = scMax(Nstc, sn, Nvar);
1371 while (ideg >= x)
1372 {
1373 act[Nvar] = ideg;
1374 scInKbase(sn, Nstc, Ivar);
1375 ideg--;
1376 }
1377 if (ideg < 0) return;
1378 Istc = Nstc;
1379 for (i=Nstc-1; i>=0; i--)
1380 {
1381 if (ideg < sn[i][Nvar])
1382 {
1383 Istc--;
1384 sn[i] = NULL;
1385 }
1386 }
1387 j = 0;
1388 while (sn[j]) j++;
1389 i = j+1;
1390 for (; i<Nstc; i++)
1391 {
1392 if (sn[i])
1393 {
1394 sn[j] = sn[i];
1395 j++;
1396 }
1397 }
1398 Nstc = Istc;
1399 }
1400}
static int scMin(int i, scfmon stc, int Nvar)
Definition hdegree.cc:1168
static void scInKbase(scfmon stc, int Nstc, int Nvar)
Definition hdegree.cc:1346

◆ scKBase()

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

Definition at line 1420 of file hdegree.cc.

1421{
1422 if( Q!=NULL) id_Test(Q, currRing);
1423
1424 int i, di;
1425 poly p;
1426
1427 if (deg < 0)
1428 {
1429 di = scDimInt(s, Q);
1430 if (di != 0)
1431 {
1432 //Werror("KBase not finite");
1433 return idInit(1,s->rank);
1434 }
1435 }
1436 stcmem = hCreate((currRing->N) - 1);
1437 hexist = hInit(s, Q, &hNexist);
1438 p = last = pInit();
1439 /*pNext(p) = NULL;*/
1440 act = (scmon)omAlloc(((currRing->N) + 1) * sizeof(int));
1441 *act = 0;
1442 if (!hNexist)
1443 {
1444 scAll((currRing->N), deg);
1445 goto ende;
1446 }
1447 if (!hisModule)
1448 {
1449 if (deg < 0) scInKbase(hexist, hNexist, (currRing->N));
1450 else scDegKbase(hexist, hNexist, (currRing->N), deg);
1451 }
1452 else
1453 {
1454 hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
1455 for (i = 1; i <= hisModule; i++)
1456 {
1457 *act = i;
1459 int deg_ei=deg;
1460 if (mv!=NULL) deg_ei -= (*mv)[i-1];
1461 if ((deg < 0) || (deg_ei>=0))
1462 {
1463 if (hNstc)
1464 {
1465 if (deg < 0) scInKbase(hstc, hNstc, (currRing->N));
1466 else scDegKbase(hstc, hNstc, (currRing->N), deg_ei);
1467 }
1468 else
1469 scAll((currRing->N), deg_ei);
1470 }
1471 }
1472 omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
1473 }
1474ende:
1476 omFreeSize((ADDRESS)act, ((currRing->N) + 1) * sizeof(int));
1477 hKill(stcmem, (currRing->N) - 1);
1478 pLmFree(&p);
1479 if (p == NULL)
1480 return idInit(1,s->rank);
1481
1482 last = p;
1483 return scIdKbase(p, s->rank);
1484}
const CanonicalForm int s
Definition facAbsFact.cc:51
static ideal scIdKbase(poly q, const int rank)
Definition hdegree.cc:1402

◆ scMax()

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

Definition at line 1156 of file hdegree.cc.

1157{
1158 int x, y=stc[0][Nvar];
1159 for (; i;)
1160 {
1161 i--;
1162 x = stc[i][Nvar];
1163 if (x > y) y = x;
1164 }
1165 return y;
1166}
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 1168 of file hdegree.cc.

1169{
1170 int x, y=stc[0][Nvar];
1171 for (; i;)
1172 {
1173 i--;
1174 x = stc[i][Nvar];
1175 if (x < y) y = x;
1176 }
1177 return y;
1178}

◆ scMult0Int()

long scMult0Int ( ideal S,
ideal Q )

Definition at line 924 of file hdegree.cc.

925{
927 if (Q!=NULL) id_LmTest(Q, currRing);
928
929 int mc;
930 hexist = hInit(S, Q, &hNexist);
931 if (!hNexist)
932 {
933 hMu = -1;
934 return -1;
935 }
936 else
937 hMu = 0;
938
939 const ring r = currRing;
940
941 hwork = (scfmon)omAlloc(hNexist * sizeof(scmon));
942 hvar = (varset)omAlloc(((r->N) + 1) * sizeof(int));
943 hpur0 = (scmon)omAlloc((1 + ((r->N) * (r->N))) * sizeof(int));
944 mc = hisModule;
945 if (!mc)
946 {
947 hstc = hexist;
948 hNstc = hNexist;
949 }
950 else
951 hstc = (scfmon)omAlloc(hNexist * sizeof(scmon));
952 stcmem = hCreate((r->N) - 1);
953 loop
954 {
955 if (mc)
956 {
957 hComp(hexist, hNexist, mc, hstc, &hNstc);
958 if (!hNstc)
959 {
960 hMu = -1;
961 break;
962 }
963 }
964 hNvar = (r->N);
965 for (int i = hNvar; i; i--)
966 hvar[i] = i;
969 if ((hNvar == (r->N)) && (hNstc >= (r->N)))
970 {
971 if ((hNvar > 2) && (hNstc > 10))
973 memset(hpur0, 0, ((r->N) + 1) * sizeof(int));
974 hPure(hstc, 0, &hNstc, hvar, hNvar, hpur0, &hNpure);
975 if (hNpure == hNvar)
976 {
979 }
980 else
981 hMu = -1;
982 }
983 else if (hNvar)
984 hMu = -1;
985 mc--;
986 if (mc <= 0 || hMu < 0)
987 break;
988 }
989 hKill(stcmem, (r->N) - 1);
990 omFreeSize((ADDRESS)hpur0, (1 + ((r->N) * (r->N))) * sizeof(int));
991 omFreeSize((ADDRESS)hvar, ((r->N) + 1) * sizeof(int));
992 omFreeSize((ADDRESS)hwork, hNexist * sizeof(scmon));
994 if (hisModule)
995 omFreeSize((ADDRESS)hstc, hNexist * sizeof(scmon));
996 return hMu;
997}

◆ scMultInt()

int scMultInt ( ideal S,
ideal Q )

Definition at line 901 of file hdegree.cc.

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

◆ scPrintDegree()

void scPrintDegree ( int co,
int mu )

Definition at line 910 of file hdegree.cc.

911{
912 int di = (currRing->N)-co;
913 if (currRing->OrdSgn == 1)
914 {
915 if (di>0)
916 Print("// dimension (proj.) = %d\n// degree (proj.) = %d\n", di-1, mu);
917 else
918 Print("// dimension (affine) = 0\n// degree (affine) = %d\n", mu);
919 }
920 else
921 Print("// dimension (local) = %d\n// multiplicity = %d\n", di, mu);
922}
static matrix mu(matrix A, const ring R)
Definition matpol.cc:2025

◆ scRestrict()

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

Definition at line 1180 of file hdegree.cc.

1181{
1182 int x, y;
1183 int i, j, Istc = Nstc;
1184
1185 y = MAX_INT_VAL;
1186 for (i=Nstc-1; i>=0; i--)
1187 {
1188 j = Nvar-1;
1189 loop
1190 {
1191 if(stc[i][j] != 0) break;
1192 j--;
1193 if (j == 0)
1194 {
1195 Istc--;
1196 x = stc[i][Nvar];
1197 if (x < y) y = x;
1198 stc[i] = NULL;
1199 break;
1200 }
1201 }
1202 }
1203 if (Istc < Nstc)
1204 {
1205 for (i=Nstc-1; i>=0; i--)
1206 {
1207 if (stc[i] && (stc[i][Nvar] >= y))
1208 {
1209 Istc--;
1210 stc[i] = NULL;
1211 }
1212 }
1213 j = 0;
1214 while (stc[j]) j++;
1215 i = j+1;
1216 for(; i<Nstc; i++)
1217 {
1218 if (stc[i])
1219 {
1220 stc[j] = stc[i];
1221 j++;
1222 }
1223 }
1224 Nstc = Istc;
1225 return y;
1226 }
1227 else
1228 return -1;
1229}
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 1995 of file hdegree.cc.

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

◆ vvDeleteRow()

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

Definition at line 1990 of file hdegree.cc.

1991{
1992 mat.erase(mat.begin() + row);
1993}

◆ vvIsColumnZero()

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

Definition at line 2013 of file hdegree.cc.

2014{
2015 for (std::vector<std::vector<int> >::size_type i = 0; i < mat.size(); i++)
2016 {
2017 if (mat[i][col] != 0)
2018 return FALSE;
2019 }
2020 return TRUE;
2021}

◆ vvIsRowZero()

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

Definition at line 2003 of file hdegree.cc.

2004{
2005 for (std::vector<std::vector<int> >::size_type i = 0; i < mat[row].size(); i++)
2006 {
2007 if (mat[row][i] != 0)
2008 return FALSE;
2009 }
2010 return TRUE;
2011}

◆ vvIsZero()

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

Definition at line 2023 of file hdegree.cc.

2024{
2025 for (std::vector<std::vector<int> >::size_type i = 0; i < mat.size(); i++)
2026 {
2027 if (!vvIsRowZero(mat, i))
2028 return FALSE;
2029 }
2030 return TRUE;
2031}

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

2034{
2035 std::vector<std::vector<int> >::size_type ra = a.size();
2036 std::vector<std::vector<int> >::size_type rb = b.size();
2037 std::vector<std::vector<int> >::size_type ca = a.size() > 0 ? a[0].size() : 0;
2038 std::vector<std::vector<int> >::size_type cb = b.size() > 0 ? b[0].size() : 0;
2039
2040 if (ca != rb)
2041 {
2042 WerrorS("matrix dimensions do not match");
2043 return std::vector<std::vector<int> >();
2044 }
2045
2046 std::vector<std::vector<int> > res(ra, std::vector<int>(cb));
2047 for (std::vector<std::vector<int> >::size_type i = 0; i < ra; i++)
2048 {
2049 for (std::vector<std::vector<int> >::size_type j = 0; j < cb; j++)
2050 {
2051 int sum = 0;
2052 for (std::vector<std::vector<int> >::size_type k = 0; k < ca; k++)
2053 sum += a[i][k] * b[k][j];
2054 res[i][j] = sum;
2055 }
2056 }
2057 return res;
2058}

Variable Documentation

◆ act

Definition at line 1145 of file hdegree.cc.

◆ hCo

VAR int hCo

Definition at line 27 of file hdegree.cc.

◆ hInd

Definition at line 203 of file hdegree.cc.

◆ hMu

VAR long hMu

Definition at line 28 of file hdegree.cc.

◆ hMu2

VAR int hMu2

Definition at line 27 of file hdegree.cc.

◆ indlist_bin

VAR omBin indlist_bin = omGetSpecBin(sizeof(indlist))

Definition at line 29 of file hdegree.cc.

◆ ISet

VAR indset ISet

Definition at line 351 of file hdegree.cc.

◆ JSet

VAR indset JSet

Definition at line 351 of file hdegree.cc.

◆ last

STATIC_VAR poly last

Definition at line 1144 of file hdegree.cc.

◆ pWork

STATIC_VAR poly pWork

Definition at line 1001 of file hdegree.cc.