Loading...
Searching...
No Matches
nc.cc
Go to the documentation of this file.
#define PLURAL_INTERNAL_DECLARATIONS
#include "kernel/mod2.h"
#include "misc/options.h"
#include "polys/simpleideals.h"
#include "polys/prCopy.h"
#include "polys/nc/gb_hack.h"
#include "kernel/polys.h"
#include "kernel/ideals.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/nc.h"
ideal twostd(ideal I) // works in currRing only!
{
ideal J = kStd2(I, currRing->qideal, testHomog, NULL, (bigintmat*)NULL, 0, 0, NULL); // in currRing!!!
idSkipZeroes(J); // ring independent!
const int rN = currRing->N;
loop
{
ideal K = NULL;
const int s = idElem(J); // ring independent
for(int i = 0; i < s; i++)
{
const poly p = J->m[i];
#ifdef PDEBUG
p_Test(p, currRing);
#if 0
PrintS("p: "); // !
p_Write(p, currRing);
#endif
#endif
for (int j = 1; j <= rN; j++) // for all j = 1..N
{
poly varj = p_One( currRing);
p_SetExp(varj, j, 1, currRing);
p_Setm(varj, currRing);
poly q = pp_Mult_mm(p, varj, currRing); // q = J[i] * var(j),
#ifdef PDEBUG
p_Test(varj, currRing);
p_Test(p, currRing);
p_Test(q, currRing);
#if 0
PrintS("Reducing p: "); // !
p_Write(p, currRing);
PrintS("With q: "); // !
p_Write(q, currRing);
#endif
#endif
p_Delete(&varj, currRing);
if (q != NULL)
{
#ifdef PDEBUG
#if 0
Print("Reducing q[j = %d]: ", j); // !
p_Write(q, currRing);
PrintS("With p:");
p_Write(p, currRing);
#endif
#endif
// bug: lm(p) may not divide lm(p * var(i)) in a SCA!
if( p_LmDivisibleBy(p, q, currRing) )
q = nc_ReduceSpoly(p, q, currRing);
#ifdef PDEBUG
p_Test(q, currRing);
#if 0
PrintS("reductum q/p: ");
p_Write(q, currRing);
// PrintS("With J!\n");
#endif
#endif
// if( q != NULL)
q = kNF(J, currRing->qideal, q, 0, KSTD_NF_NONORM); // in currRing!!!
#ifdef PDEBUG
p_Test(q, currRing);
#if 0
PrintS("NF(J/currRing->qideal)=> q: "); // !
p_Write(q, currRing);
#endif
#endif
if (q!=NULL)
{
if (p_IsConstant(q, currRing)) // => return (1)!
{
p_Delete(&q, currRing);
id_Delete(&J, currRing);
if (K != NULL)
id_Delete(&K, currRing);
ideal Q = idInit(1,1); // ring independent!
Q->m[0] = p_One(currRing);
return(Q);
}
// flag = false;
// K += q:
ideal Q = idInit(1,1); // ring independent
Q->m[0]=q;
if( K == NULL )
K = Q;
else
{
ideal id_tmp = idSimpleAdd(K, Q); // in currRing
id_Delete(&K, currRing);
id_Delete(&Q, currRing);
K = id_tmp; // K += Q
}
}
} // if q != NULL
} // for all variables
}
if (K == NULL) // nothing new: i.e. all elements are two-sided
return(J);
// now we update GrBasis J with K
// iSize=IDELEMS(J);
#ifdef PDEBUG
idTest(J); // in currRing!
#if 0
PrintS("J:");
idPrint(J);
PrintLn();
#endif // debug
#endif
#ifdef PDEBUG
idTest(K); // in currRing!
#if 0
PrintS("+K:");
idPrint(K);
PrintLn();
#endif // debug
#endif
int iSize = idElem(J); // ring independent
// J += K:
ideal id_tmp = idSimpleAdd(J,K); // in currRing
id_Delete(&K, currRing); id_Delete(&J, currRing);
#if 1
BITSET save1;
SI_SAVE_OPT1(save1);
si_opt_1|=Sy_bit(OPT_SB_1); // ring independent
J = kStd2(id_tmp, currRing->qideal, testHomog, NULL, (bigintmat*)NULL, 0, iSize); // J = J + K, J - std // in currRing!
SI_RESTORE_OPT1(save1);
#else
J=kStd2(id_tmp, currRing->qideal,testHomog,NULL,NULL,0,0,NULL);
#endif
id_Delete(&id_tmp, currRing);
idSkipZeroes(J); // ring independent
#ifdef PDEBUG
idTest(J); // in currRing!
#if 0
PrintS("J:");
idPrint(J);
PrintLn();
#endif // debug
#endif
} // loop
}
static ideal idPrepareStd(ideal T, ideal s, int k)
{
// T is a left SB, without zeros, s is a list with zeros
#ifdef PDEBUG
if (IDELEMS(s)!=IDELEMS(T))
{
PrintS("ideals of diff. size!!!");
}
#endif
ideal t = idCopy(T);
int j,rs=id_RankFreeModule(s, currRing);
poly p,q;
ideal res = idInit(2*idElem(t),1+idElem(t));
if (rs == 0)
{
for (j=0; j<IDELEMS(t); j++)
{
if (s->m[j]!=NULL) pSetCompP(s->m[j],1);
if (t->m[j]!=NULL) pSetCompP(t->m[j],1);
}
k = si_max(k,1);
}
for (j=0; j<IDELEMS(t); j++)
{
if (s->m[j]!=NULL)
{
p = s->m[j];
q = pOne();
pSetComp(q,k+1+j);
pSetmComp(q);
#if 0
while (pNext(p)) pIter(p);
pNext(p) = q;
#else
p = pAdd(p,q);
s->m[j] = p;
#ifdef PDEBUG
pTest(p);
#endif
#endif
}
}
res = idSimpleAdd(t,s);
idDelete(&t);
res->rank = 1+idElem(T);
return(res);
}
ideal Approx_Step(ideal L)
{
int N=currRing->N;
int i,j; // k=syzcomp
int flag, flagcnt=0, syzcnt=0;
int syzcomp = 0;
ideal I = kStd2(L, currRing->qideal,testHomog,NULL,(bigintmat*)NULL,0,0,NULL);
idSkipZeroes(I);
ideal s_I;
int idI = idElem(I);
ideal trickyQuotient;
if (currRing->qideal !=NULL)
{
trickyQuotient = idSimpleAdd(currRing->qideal,I);
}
else
trickyQuotient = I;
idSkipZeroes(trickyQuotient);
poly *var = (poly *)omAlloc0((N+1)*sizeof(poly));
// poly *W = (poly *)omAlloc0((2*N+1)*sizeof(poly));
resolvente S = (resolvente)omAlloc0((N+1)*sizeof(ideal));
ideal SI, res;
matrix MI;
poly x=pOne();
var[0]=x;
ideal h2, s_h2, s_h3;
poly p,q;
// init vars
for (i=1; i<=N; i++ )
{
x = pOne();
pSetExp(x,i,1);
pSetm(x);
var[i]=pCopy(x);
}
// init NF's
for (i=1; i<=N; i++ )
{
h2 = idInit(idI,1);
flag = 0;
for (j=0; j< idI; j++ )
{
q = pp_Mult_mm(I->m[j],var[i],currRing);
q = kNF(I,currRing->qideal,q,0,0);
if (q!=0)
{
h2->m[j]=pCopy(q);
// p_Shift(&(h2->m[flag]),1, currRing);
flag++;
pDelete(&q);
}
else
h2->m[j]=0;
}
// W[1..IDELEMS(I)]
if (flag >0)
{
// compute syzygies with values in I
// idSkipZeroes(h2);
// h2 = idSimpleAdd(h2,I);
// h2->rank=flag+idI+1;
idTest(h2);
//idShow(h2);
ring orig_ring = currRing;
ring syz_ring = rAssure_SyzComp(orig_ring, TRUE);
syzcomp = 1;
rSetSyzComp(syzcomp, syz_ring);
if (orig_ring != syz_ring)
{
rChangeCurrRing(syz_ring);
s_h2=idrCopyR_NoSort(h2,orig_ring, syz_ring);
// s_trickyQuotient=idrCopyR_NoSort(trickyQuotient,orig_ring);
// rDebugPrint(syz_ring);
s_I=idrCopyR_NoSort(I,orig_ring, syz_ring);
}
else
{
s_h2 = h2;
s_I = I;
// s_trickyQuotient=trickyQuotient;
}
idTest(s_h2);
// idTest(s_trickyQuotient);
Print(".proceeding with the variable %d\n",i);
s_h3 = idPrepareStd(s_I, s_h2, 1);
BITSET save1;
SI_SAVE_OPT1(save1);
si_opt_1|=Sy_bit(OPT_SB_1);
idTest(s_h3);
idDelete(&s_h2);
s_h2=idCopy(s_h3);
idDelete(&s_h3);
PrintS("...computing Syz");
s_h3 = kStd2(s_h2, currRing->qideal,(tHomog)FALSE,NULL,(bigintmat*)NULL,syzcomp,idI);
SI_RESTORE_OPT1(save1);
//idShow(s_h3);
if (orig_ring != syz_ring)
{
idDelete(&s_h2);
for (j=0; j<IDELEMS(s_h3); j++)
{
if (s_h3->m[j] != NULL)
{
if (p_MinComp(s_h3->m[j],syz_ring) > syzcomp) // i.e. it is a syzygy
p_Shift(&s_h3->m[j], -syzcomp, currRing);
else
pDelete(&s_h3->m[j]);
}
}
idSkipZeroes(s_h3);
s_h3->rank -= syzcomp;
rChangeCurrRing(orig_ring);
// s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
rDelete(syz_ring);
}
idTest(s_h3);
S[syzcnt]=kStd2(s_h3,currRing->qideal,(tHomog)FALSE,NULL,(bigintmat*)NULL);
syzcnt++;
idDelete(&s_h3);
} // end if flag >0
else
{
flagcnt++;
}
}
if (flagcnt == N)
{
PrintS("the input is a two--sided ideal");
return(I);
}
if (syzcnt >0)
{
Print("..computing Intersect of %d modules\n",syzcnt);
if (syzcnt == 1)
SI = S[0];
else
SI = idMultSect(S, syzcnt);
//idShow(SI);
MI = id_Module2Matrix(SI,currRing);
res= idInit(MATCOLS(MI),1);
for (i=1; i<= MATCOLS(MI); i++)
{
p = NULL;
for (j=0; j< idElem(I); j++)
{
q = pCopy(MATELEM(MI,j+1,i));
if (q!=NULL)
{
q = pMult(q,pCopy(I->m[j]));
p = pAdd(p,q);
}
}
res->m[i-1]=p;
}
PrintS("final std");
res = kStd2(res, currRing->qideal,testHomog,NULL,(bigintmat*)NULL,0,0,NULL);
idSkipZeroes(res);
return(res);
}
else
{
PrintS("No syzygies");
return(I);
}
}
BITSET
#define BITSET
Definition auxiliary.h:85
si_max
static int si_max(const int a, const int b)
Definition auxiliary.h:125
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
bigintmat
Matrices of numbers.
Definition bigintmat.h:51
Print
#define Print
Definition emacs.cc:80
s
const CanonicalForm int s
Definition facAbsFact.cc:51
res
CanonicalForm res
Definition facAbsFact.cc:60
j
int j
Definition facHensel.cc:110
gb_hack.h
idMultSect
ideal idMultSect(resolvente arg, int length, GbVariant alg)
Definition ideals.cc:472
ideals.h
idDelete
#define idDelete(H)
delete an ideal
Definition ideals.h:29
idSimpleAdd
#define idSimpleAdd(A, B)
Definition ideals.h:42
idPrint
#define idPrint(id)
Definition ideals.h:46
idTest
#define idTest(id)
Definition ideals.h:47
idCopy
ideal idCopy(ideal A)
Definition ideals.h:60
resolvente
ideal * resolvente
Definition ideals.h:18
T
STATIC_VAR jList * T
Definition janet.cc:30
nc.h
kStd2
ideal kStd2(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
generic interface to GB/SB computations, large hilbert vectors
Definition kstd1.cc:2607
kNF
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3229
kstd1.h
KSTD_NF_NONORM
#define KSTD_NF_NONORM
Definition kstd1.h:22
nc_ReduceSpoly
static poly nc_ReduceSpoly(const poly p1, poly p2, const ring r)
Definition nc.h:254
MATELEM
#define MATELEM(mat, i, j)
1-based access to matrix
Definition matpol.h:29
matrix
ip_smatrix * matrix
Definition matpol.h:43
MATCOLS
#define MATCOLS(i)
Definition matpol.h:27
mod2.h
pIter
#define pIter(p)
Definition monomials.h:37
pNext
#define pNext(p)
Definition monomials.h:36
Approx_Step
ideal Approx_Step(ideal L)
Ann: ???
Definition nc.cc:250
idPrepareStd
static ideal idPrepareStd(ideal T, ideal s, int k)
Definition nc.cc:200
twostd
ideal twostd(ideal I)
Compute two-sided GB:
Definition nc.cc:18
omAlloc0
#define omAlloc0(size)
Definition omAllocDecl.h:211
NULL
#define NULL
Definition omList.c:12
si_opt_1
VAR unsigned si_opt_1
Definition options.c:5
options.h
OPT_SB_1
#define OPT_SB_1
Definition options.h:96
SI_SAVE_OPT1
#define SI_SAVE_OPT1(A)
Definition options.h:21
SI_RESTORE_OPT1
#define SI_RESTORE_OPT1(A)
Definition options.h:24
Sy_bit
#define Sy_bit(x)
Definition options.h:31
p_Shift
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition p_polys.cc:4860
p_One
poly p_One(const ring r)
Definition p_polys.cc:1314
p_Write
void p_Write(poly p, ring lmRing, ring tailRing)
Definition polys0.cc:342
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition p_polys.h:1033
p_SetExp
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition p_polys.h:490
p_MinComp
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition p_polys.h:315
p_Setm
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
p_IsConstant
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition p_polys.h:1985
p_LmDivisibleBy
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1912
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
p_Test
#define p_Test(p, r)
Definition p_polys.h:161
rChangeCurrRing
void rChangeCurrRing(ring r)
Definition polys.cc:16
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
polys.h
Compatibility layer for legacy polynomial operations (over currRing).
pAdd
#define pAdd(p, q)
Definition polys.h:204
pTest
#define pTest(p)
Definition polys.h:415
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pSetm
#define pSetm(p)
Definition polys.h:272
pSetCompP
#define pSetCompP(a, i)
Definition polys.h:304
pSetComp
#define pSetComp(p, v)
Definition polys.h:39
pMult
#define pMult(p, q)
Definition polys.h:208
pSetmComp
#define pSetmComp(p)
TODO:
Definition polys.h:274
pSetExp
#define pSetExp(p, i, v)
Definition polys.h:43
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
pOne
#define pOne()
Definition polys.h:316
idrMoveR_NoSort
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:261
idrCopyR_NoSort
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition prCopy.cc:205
prCopy.h
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
PrintLn
void PrintLn()
Definition reporter.cc:314
rAssure_SyzComp
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition ring.cc:4527
rDelete
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:454
rSetSyzComp
void rSetSyzComp(int k, const ring r)
Definition ring.cc:5230
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35
id_Delete
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
Definition simpleideals.cc:123
id_Module2Matrix
matrix id_Module2Matrix(ideal mod, const ring R)
Definition simpleideals.cc:1594
id_RankFreeModule
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
Definition simpleideals.cc:992
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition simpleideals.cc:201
simpleideals.h
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23
idElem
static int idElem(const ideal F)
number of non-zero polys in F
Definition simpleideals.h:69
Q
#define Q
Definition sirandom.c:26
tHomog
tHomog
Definition structs.h:31
testHomog
@ testHomog
Definition structs.h:34
loop
#define loop
Definition structs.h:71