# Changeset 458174a in git

Ignore:
Timestamp:
May 2, 2018, 10:45:42 AM (5 years ago)
Branches:
Children:
0f987ab443ee33e628ea90f02a2fddfb9d8fa497
Parents:
Message:
`Merge branch 'spielwiese' into stable`
Files:
8 edited

Unmodified
Removed
• ## Singular/LIB/fpaprops.lib

 r2ba25e PROCEDURES: lpNoetherian();     check whether A/ is (left/right) noetherian lpNoetherian();     check whether A/ is (left/right) Noetherian lpIsSemiPrime();    check whether A/ is semi prime lpIsPrime();        check whether A/ is prime "USAGE: lpNoetherian(G); G an ideal in a Letterplace ring RETURN: int @*      0 not noetherian @*      1 left noetherian @*      2 right noetherian @*      3 noetherian PURPOSE: Check whether A/ is (left/right) noetherian @*      0 not Noetherian @*      1 left Noetherian @*      2 right Noetherian @*      3 Noetherian @*      4 weak Noetherian PURPOSE: Check whether the monomial algebra A/ is (left/right) noetherian ASSUME: - basering is a Letterplace ring @*      - G is a Groebner basis THEORY: lpNoetherian works with the monomial algebra A/. If it gives an affirmative answer for one of the properties, then it holds for both A/ and A/. However, a negative answer applies only to A/ and not necessarily to A/. NOTE: Weak Noetherian means that two-sided ideals in A/ satisfy the acc (ascending chain condition). " { intvec visited; visited[ncols(UG)] = 0; int inFlag, outFlag; int inFlag, outFlag, inOutFlag; for (int v = 1; v <= ncols(UG) && (inFlag + outFlag) != 3; v++) { int inOutFlags = inOrOutCommingEdgeInCycle(UG, v, visited, 0); int inOutFlags = inOutCommingEdgesInCycles(UG, v, visited, 0); if (inOutFlags == 1) { inFlag = 1; } if (inOutFlags == 2) { outFlag = 2; outFlag = 1; } if (inOutFlags == 3) { inFlag = 1; outFlag = 2; outFlag = 1; } if (inOutFlags == 4) { inOutFlag = 1; } if (inOutFlags == 5) { inFlag = 1; inOutFlag = 1; } if (inOutFlags == 6) { outFlag = 1; inOutFlag = 1; } if (inOutFlags == 7) { inFlag = 1; outFlag = 1; inOutFlag = 1; } kill inOutFlags; } kill v; return (3 - inFlag - outFlag); int noetherian = 3 - 1*inFlag - 2*outFlag; if (noetherian == 0) { return (4 - 4*inOutFlag); // weak noetherian } return (noetherian); } example } static proc inOrOutCommingEdgeInCycle(intmat G, int v, intvec visited, intvec path) { static proc inOutCommingEdgesInCycles(intmat G, int v, intvec visited, intvec path) { // Mark the current vertex as visited visited[v] = 1; } int inFlag, outFlag; int inFlag, outFlag, inOutFlag; for (int w = 1; w <= ncols(G) && (inFlag + outFlag) != 3; w++) { if (G[v,w] == 1) { if (visited[w] == 1) { // new cycle if (v == w) { if (visited[w] == 1) { // new cycle int tmpInFlag; int tmpOutFlag; if (v == w) { // cycle is a loop for (int u = 1; u <= ncols(G); u++) { if (G[v,u] && u != v) { outFlag = 2; outFlag = 1; tmpOutFlag = 1; } if (G[u,v] && u != v) { inFlag = 1; tmpInFlag = 1; } } kill u; if (path[i] != v) { if (u != path[i+1]) { // and u is not the next element in the cycle outFlag = 2; outFlag = 1; tmpOutFlag = 1; } } else { if (u != w) { outFlag = 2; outFlag = 1; tmpOutFlag = 1; } } if (u != path[i-1]) { // and u is not the previous element in the cylce inFlag = 1; tmpInFlag = 1; } } else { if (u != v) { inFlag = 1; tmpInFlag = 1; } } } kill i; } if (tmpInFlag > 0 && tmpOutFlag > 0) { // there are both in and outcomming edges in this cycle inOutFlag = 1; } kill tmpInFlag; kill tmpOutFlag; } else { int inOutFlags = inOrOutCommingEdgeInCycle(G, w, visited, path); int inOutFlags = inOutCommingEdgesInCycles(G, w, visited, path); if (inOutFlags == 1) { inFlag = 1; } if (inOutFlags == 2) { outFlag = 2; outFlag = 1; } if (inOutFlags == 3) { inFlag = 1; outFlag = 2; outFlag = 1; } if (inOutFlags == 4) { inOutFlag = 1; } if (inOutFlags == 5) { inFlag = 1; inOutFlag = 1; } if (inOutFlags == 6) { outFlag = 1; inOutFlag = 1; } if (inOutFlags == 7) { inFlag = 1; outFlag = 1; inOutFlag = 1; } kill inOutFlags; } kill w; return (inFlag + outFlag); return (1*inFlag + 2*outFlag + 4*inOutFlag); } ASSUME: - basering is a Letterplace ring - G is a Groebner basis THEORY: lpIsSemiPrime works with the monomial algebra A/. A positive answer holds for both A/ and A/, while a negative answer applies only to A/ and not necessarily to A/. " { ASSUME: - basering is a Letterplace ring - G is a Groebner basis THEORY: lpIsPrime works with the monomial algebra A/. A positive answer holds for both A/ and A/, while a negative answer applies only to A/ and not necessarily to A/. " {
• ## Singular/misc_ip.cc

 r75def9 StringAppendS("AvoidBranching,"); #endif #ifdef HAVE_MULT_MOD #ifdef HAVE_GENERIC_MULT StringAppendS("GenericMult,"); #else StringAppendS("TableMult,"); #endif #ifdef HAVE_INVTABLE StringAppendS("invTable,"); #else StringAppendS("no invTable,"); #endif StringAppendS("\n\t");
• ## factory/ffops.h

 r75def9 long n = a % ff_prime; #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING) #if SIZEOF_LONG==8 n += (n >> 63) & ff_prime; #else n += (n >> 31) & ff_prime; #endif return n; #else
• ## kernel/GBEngine/tgb_internal.h

 r75def9 #define npInit n_Init #define npNeg n_InpNeg #define npInvers n_Invers #define npMult n_Mult #define npIsOne n_IsOne #define npIsZero n_IsZero #define npNeg npNegM #define npInvers npInversM #define npMult npMultM //#define npIsOne n_IsOne #define npIsZero npIsZeroM #else
• ## kernel/mod2.h

 r75def9 #endif #define SINGULAR_PATCHLEVEL 0 #define SINGULAR_PATCHLEVEL 2 #define SINGULAR_VERSION ((SINGULAR_MAJOR_VERSION*1000 + SINGULAR_MINOR_VERSION*100 + SINGULAR_SUB_VERSION*10)+SINGULAR_PATCHLEVEL)
• ## libpolys/coeffs/modulop.cc

 r75def9 } BOOLEAN npIsOne (number a, const coeffs r) { n_Test(a, r); return 1 == (long)a; } BOOLEAN npIsMOne (number a, const coeffs r) { } #ifdef HAVE_DIV_MOD #ifdef USE_NTL_XGCD //ifdef HAVE_NTL // in ntl.a //extern void XGCD(long& d, long& s, long& t, long a, long b); #include #ifdef NTL_CLIENT NTL_CLIENT #endif #endif static inline long InvMod(long a, const coeffs R) { long d, s, t; #ifdef USE_NTL_XGCD XGCD(d, s, t, a, R->ch); assume (d == 1); #else long  u, v, u0, v0, u1, v1, u2, v2, q, r; assume(a>0); u1=1; u2=0; u = a; v = R->ch; while (v != 0) { q = u / v; r = u % v; u = v; v = r; u0 = u2; u2 = u1 - q*u2; u1 = u0; } assume(u==1); s = u1; #endif if (s < 0) return s + R->ch; else return s; } #endif static inline number npInversM (number c, const coeffs r) { n_Test(c, r); #ifndef HAVE_DIV_MOD number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]]; #else long inv=(long)r->npInvTable[(long)c]; if (inv==0) { inv=InvMod((long)c,r); r->npInvTable[(long)c]=inv; } number d = (number)inv; #endif n_Test(d, r); return d; } number npDiv (number a,number b, const coeffs r) { n_Test(b, r); //#ifdef NV_OPS //  if (r->ch>NV_MAX_PRIME) //    return nvDiv(a,b); //#endif if ((long)a==0L) return (number)0L; number d; #ifndef HAVE_DIV_MOD if ((long)b==0L) { return (number)0L; } if ((long)a==0) return (number)0L; number d; #ifndef HAVE_GENERIC_MULT int s = r->npLogTable[(long)a] - r->npLogTable[(long)b]; #ifdef HAVE_GENERIC_ADD if (s < 0) s += r->npPminus1M; #else #if SIZEOF_LONG == 8 s += ((long)s >> 63) & r->npPminus1M; #else s += ((long)s >> 31) & r->npPminus1M; #endif #endif d = (number)(long)r->npExpTable[s]; #else void npKillChar(coeffs r) { #ifdef HAVE_DIV_MOD #ifdef HAVE_INVTABLE if (r->npInvTable!=NULL) omFreeSize( (void *)r->npInvTable, r->ch*sizeof(unsigned short) ); r->npInvTable=NULL; #else { omFreeSize( (void *)r->npInvTable, r->ch*sizeof(unsigned short) ); r->npInvTable=NULL; } #endif #ifndef HAVE_GENERIC_MULT if (r->npExpTable!=NULL) { #endif { #ifdef HAVE_DIV_MOD #ifdef HAVE_INVTABLE r->npInvTable=(unsigned short*)omAlloc0( r->ch*sizeof(unsigned short) ); #elif (!defined(HAVE_MULT_MOD)||(!HAVE_DIV_MOD)) #endif #ifndef HAVE_GENERIC_MULT r->npExpTable=(unsigned short *)omAlloc0( r->ch*sizeof(unsigned short) ); r->npLogTable=(unsigned short *)omAlloc0( r->ch*sizeof(unsigned short) ); } static inline long nvInvMod(long a, const coeffs R) { #ifdef HAVE_DIV_MOD return InvMod(a, R); #else /// TODO: use "long InvMod(long a, const coeffs R)"?! long  s; long  u, u0, u1, u2, q, r; // v0, v1, v2, u1=1; // v1=0; u2=0; // v2=1; u = a; long v = R->ch; while (v != 0) { q = u / v; r = u % v; u = v; v = r; u0 = u2; //      v0 = v2; u2 = u1 - q*u2; //      v2 = v1 - q*v2; u1 = u0; //      v1 = v0; } s = u1; //t = v1; if (s < 0) return s + R->ch; else return s; #endif } static inline number nvInversM (number c, const coeffs r) { long inv=nvInvMod((long)c,r); long inv=npInvMod((long)c,r); return (number)inv; }
• ## libpolys/coeffs/modulop.h

 r75def9 #include "misc/auxiliary.h" // defines are in struct.h // define if a*b is with mod instead of tables //#define HAVE_MULT_MOD // define if a/b is with mod instead of tables //#define HAVE_DIV_MOD //#define HAVE_GENERIC_MULT // define if 1/b is from tables //#define HAVE_INVTABLE // define if an if should be used //#define HAVE_GENERIC_ADD //#undef HAVE_GENERIC_ADD //#undef HAVE_GENERIC_MULT //#undef HAVE_INVTABLE //#define HAVE_GENERIC_ADD 1 //#define HAVE_GENERIC_MULT 1 //#define HAVE_INVTABLE 1 // enable large primes (32749 < p < 2^31-) #define NV_MAX_PRIME 32749 #define FACTORY_MAX_PRIME 536870909 #ifdef USE_NTL_XGCD //ifdef HAVE_NTL // in ntl.a //extern void XGCD(long& d, long& s, long& t, long a, long b); #include #ifdef NTL_CLIENT NTL_CLIENT #endif #endif struct n_Procs_s; typedef struct  n_Procs_s  *coeffs; //    return (number)res; // } #ifdef HAVE_MULT_MOD #ifdef HAVE_GENERIC_MULT static inline number npMultM(number a, number b, const coeffs r) { return 0 == (long)a; } // inline number npMultM(number a, number b, int npPrimeM) // { //   return (number)(((long)a*(long)b) % npPrimeM); // } static inline BOOLEAN npIsOne (number a, const coeffs) { return 1 == (long)a; } static inline long npInvMod(long a, const coeffs R) { long s, t; #ifdef USE_NTL_XGCD long d; XGCD(d, s, t, a, R->ch); assume (d == 1); #else long  u, v, u0, v0, u1, v1, u2, v2, q, r; assume(a>0); u1=1; u2=0; u = a; v = R->ch; while (v != 0) { q = u / v; //r = u % v; r = u - q*v; u = v; v = r; u0 = u2; u2 = u1 - q*u2; u1 = u0; } assume(u==1); s = u1; #endif #ifdef HAVE_GENERIC_ADD if (s < 0) return s + R->ch; else return s; #else #if SIZEOF_LONG == 8 s += (s >> 63) & R->ch; #else s += (s >> 31) & R->ch; #endif return s; #endif } static inline number npInversM (number c, const coeffs r) { n_Test(c, r); #ifndef HAVE_GENERIC_MULT #ifndef HAVE_INVTABLE number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]]; #else long inv=(long)r->npInvTable[(long)c]; if (inv==0) { inv = (long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]]; r->npInvTable[(long)c]=inv; } number d = (number)inv; #endif #else #ifdef HAVE_INVTABLE long inv=(long)r->npInvTable[(long)c]; if (inv==0) { inv=npInvMod((long)c,r); r->npInvTable[(long)c]=inv; } #else long  inv=npInvMod((long)c,r); #endif number d = (number)inv; #endif n_Test(d, r); return d; } // The folloing is reused inside gnumpc.cc, gnumpfl.cc and longrat.cc