[0e1846] | 1 | #ifndef POLYS_H |
---|
| 2 | #define POLYS_H |
---|
| 3 | /**************************************** |
---|
| 4 | * Computer Algebra System SINGULAR * |
---|
| 5 | ****************************************/ |
---|
[41e149] | 6 | /* $Id: polys.h,v 1.12 1998-04-08 12:41:37 pohl Exp $ */ |
---|
[0e1846] | 7 | /* |
---|
[6ae4f5] | 8 | * ABSTRACT - all basic methods to manipulate polynomials |
---|
[0e1846] | 9 | */ |
---|
[51c163] | 10 | #include "polys-impl.h" |
---|
[0e1846] | 11 | |
---|
[51c163] | 12 | typedef poly* polyset; |
---|
[0e1846] | 13 | extern int pVariables; |
---|
| 14 | extern int pOrdSgn; |
---|
| 15 | extern BOOLEAN pLexOrder; |
---|
| 16 | extern BOOLEAN pMixedOrder; |
---|
| 17 | extern poly ppNoether; |
---|
[6a6dccc] | 18 | extern BOOLEAN pVectorOut; |
---|
[51c163] | 19 | // 1 for lex ordering (except ls), -1 otherwise |
---|
| 20 | extern int pLexSgn; |
---|
| 21 | extern int pComponentOrder; |
---|
[0e1846] | 22 | |
---|
| 23 | #ifdef DRING |
---|
| 24 | // D=k[x,d,y] is the Weyl-Algebra [y], y commuting with all others |
---|
| 25 | // M=k[x,x^(-1),y] is a D-module |
---|
| 26 | // all x(1..n),d,x(1..n)^(-1),y(1..k) are considered as "ring variables" v(1..N) |
---|
| 27 | // the map from x(i) to v: |
---|
| 28 | #define pdX(i) (i) |
---|
| 29 | // d(i) |
---|
| 30 | #define pdDX(i) (pdN+i) |
---|
| 31 | // x(i)^(-1) |
---|
| 32 | #define pdIX(i) (pdN+i) |
---|
| 33 | // y(i) |
---|
| 34 | #define pdY(i) (pdN*2+i+1) |
---|
| 35 | // a monomial m belongs to a D-module M iff pdDFlag(m)==0 |
---|
| 36 | // a monomial m belongs to an ideal in the Weyl-Algebra D iff pdDFlag(m)==1 |
---|
[e78cce] | 37 | #define pdDFlag(m) pGetExp(m,pdN*2+1) |
---|
[0e1846] | 38 | |
---|
| 39 | extern int pdN; |
---|
| 40 | extern int pdK; |
---|
| 41 | extern BOOLEAN pDRING; |
---|
| 42 | poly pdSpolyCreate(poly a, poly b); |
---|
| 43 | void pdLcm(poly a, poly b, poly m); |
---|
| 44 | BOOLEAN pdIsConstantComp(poly p); |
---|
| 45 | void spModuleToPoly(poly a1); |
---|
| 46 | void pdSetDFlag(poly p,int i); |
---|
| 47 | #endif |
---|
| 48 | #ifdef SRING |
---|
| 49 | extern int pAltVars; |
---|
| 50 | extern BOOLEAN pSRING; |
---|
| 51 | #endif |
---|
| 52 | #ifdef SDRING |
---|
| 53 | void psAug(poly q, poly done, polyset *s, int *l, int *m); |
---|
| 54 | void pdAug(poly q, polyset *s, int *l, int *m); |
---|
| 55 | #endif |
---|
| 56 | #ifdef SDRING |
---|
| 57 | extern BOOLEAN pSDRING; |
---|
| 58 | #endif |
---|
| 59 | |
---|
| 60 | /* function prototypes */ |
---|
[51c163] | 61 | |
---|
| 62 | /* ---------------- General poly access and iteration macros -----------*/ |
---|
| 63 | // IMPORTANT: Do _NOT_ make _ANY_ assumptions about their actual implementation |
---|
| 64 | |
---|
| 65 | #define pNext(p) _pNext(p) |
---|
| 66 | #define pIter(p) _pIter(p) |
---|
| 67 | |
---|
| 68 | #define pGetCoeff(p) _pGetCoeff(p) |
---|
| 69 | // deletes old coeff before setting the new |
---|
| 70 | #define pSetCoeff(p,n) _pSetCoeff(p,n) |
---|
| 71 | // sets new coeff without deleting the old one |
---|
| 72 | #define pSetCoeff0(p,n) _pSetCoeff0(p,n) |
---|
| 73 | |
---|
| 74 | #define pGetOrder(p) _pGetOrder(p) |
---|
| 75 | |
---|
[e78cce] | 76 | // Gets/Sets Component field w.r.t. of polys of global ring |
---|
[51c163] | 77 | #define pSetComp(p,k) _pSetComp(p,k) |
---|
| 78 | #define pGetComp(p) _pGetComp(p) |
---|
| 79 | #define pIncrComp(p) _pIncrComp(p) |
---|
| 80 | #define pDecrComp(p) _pDecrComp(p) |
---|
| 81 | #define pAddComp(p,v) _pAddComp(p,v) |
---|
| 82 | #define pSubComp(p,v) _pSubComp(p,v) |
---|
| 83 | |
---|
[e78cce] | 84 | // Gets/Sets Component field w.r.t. of polys of ring r |
---|
| 85 | #define pRingSetComp(r,p,k) _pRingSetComp(r,p,k) |
---|
| 86 | #define pRingGetComp(r,p) _pRingGetComp(r,p) |
---|
| 87 | |
---|
| 88 | // Gets/Sets ith exponent poly of global ring |
---|
[51c163] | 89 | #define pGetExp(p,i) _pGetExp(p,i) |
---|
| 90 | #define pSetExp(p,i,v) _pSetExp(p,i,v) |
---|
| 91 | |
---|
[e78cce] | 92 | // Gets/Sets ith exponent of poly of ring r |
---|
| 93 | #define pRingGetExp(r,p,i) _pRingGetExp(r,p,i) |
---|
| 94 | #define pRingSetExp(r,p,i,v) _pRingSetExp(r,p,i,v) |
---|
| 95 | |
---|
[51c163] | 96 | // Increments/decrements ith exponent by one |
---|
| 97 | #define pIncrExp(p,i) _pIncrExp(p,i) |
---|
| 98 | #define pDecrExp(p,i) _pDecrExp(p,i) |
---|
| 99 | |
---|
| 100 | // Gets Difference and sum of ith Exponent of m1, m2 |
---|
| 101 | #define pGetExpSum(m1, m2, i) _pGetExpSum(p1, p2, i) |
---|
| 102 | #define pGetExpDiff(p1, p2, i) _pGetExpDiff(p1, p2, i) |
---|
| 103 | |
---|
| 104 | // Adds/Substracts v to/from the ith Exponent |
---|
| 105 | #define pAddExp(p,i,v) _pAddExp(p,i,v) |
---|
| 106 | #define pSubExp(p,i,v) _pSubExp(p,i,v) |
---|
| 107 | #define pMultExp(p,i,v) _pMultExp(p,i,v) |
---|
| 108 | |
---|
| 109 | // Gets a copy of (resp. sets) the exponent vector, where e is assumed |
---|
| 110 | // to point to (pVariables+1)*sizeof(Exponent_t) memory. Exponents are |
---|
| 111 | // filled in as follows: comp, e_1, .., e_n |
---|
| 112 | #define pGetExpV(p, e) _pGetExpV(p, e) |
---|
| 113 | #define pSetExpV(p, e) _pSetExpV(p, e) |
---|
| 114 | |
---|
| 115 | |
---|
| 116 | /*-------------predicate on polys ----------------------*/ |
---|
[0e1846] | 117 | BOOLEAN pIsConstant(poly p); |
---|
| 118 | BOOLEAN pIsConstantComp(poly p); |
---|
| 119 | int pIsPurePower(poly p); |
---|
| 120 | #define pIsVector(p) (pGetComp(p)!=0) |
---|
| 121 | BOOLEAN pHasNotCF(poly p1, poly p2); /*has no common factor ?*/ |
---|
| 122 | void pSplit(poly p, poly * r); /*p => IN(p), r => REST(p) */ |
---|
[51c163] | 123 | |
---|
[0e1846] | 124 | |
---|
| 125 | /*-------------ring management:----------------------*/ |
---|
| 126 | extern void pChangeRing(int N, int OrdSgn, |
---|
| 127 | int* ord, int* block0, int* block1, |
---|
| 128 | short** wv); |
---|
[47faf56] | 129 | extern void pSetGlobals(ring r, BOOLEAN complete = TRUE); |
---|
[0e1846] | 130 | |
---|
| 131 | /*-----------the ordering of monomials:-------------*/ |
---|
| 132 | extern pSetmProc pSetm; |
---|
| 133 | extern pCompProc pComp0; |
---|
[51c163] | 134 | // this is needed here as long as monomials with negative exponents might be |
---|
| 135 | // compared (see in spolys.cc) |
---|
| 136 | extern pCompProc t_pComp0; |
---|
[0e1846] | 137 | int pComp(poly p1,poly p2); |
---|
| 138 | extern pLDegProc pLDeg; |
---|
| 139 | extern pFDegProc pFDeg; |
---|
| 140 | int pDeg(poly p); |
---|
| 141 | int pTotaldegree(poly p); |
---|
| 142 | int pWTotaldegree(poly p); |
---|
| 143 | |
---|
| 144 | /*-------------pComp for syzygies:-------------------*/ |
---|
| 145 | |
---|
| 146 | void pSetModDeg(intvec *w); |
---|
| 147 | void pSetSchreyerOrdB(polyset nextorder, int length); |
---|
| 148 | void pSetSchreyerOrdM(polyset nextorder, int length, int comps); |
---|
| 149 | int pModuleOrder(); |
---|
| 150 | |
---|
| 151 | /*-------------storage management:-------------------*/ |
---|
[51c163] | 152 | // allocates the space for a new monomial |
---|
| 153 | #define pNew() _pNew() |
---|
| 154 | // allocates a new monomial and initializes everything to 0 |
---|
| 155 | #define pInit() _pInit() |
---|
| 156 | |
---|
| 157 | // frees the space of the monomial m |
---|
| 158 | #define pFree1(m) _pFree1(m) |
---|
| 159 | // frees the space of monoial and frees coefficient |
---|
| 160 | #define pDelete1(m) _pDelete1(m) |
---|
| 161 | // deletes the whole polynomial p |
---|
| 162 | #define pDelete(p) _pDelete(p) |
---|
| 163 | |
---|
| 164 | // makes a simple memcopy of m2 into m1 -- does _not_ allocate memory for m1 |
---|
| 165 | #define pCopy2(m1, m2) _pCopy2(m1, m2) |
---|
| 166 | // Returns a newly allocated copy of the monomial m, initializes coefficient |
---|
| 167 | // and sets the next-fieled to NULL |
---|
| 168 | #define pCopy1(m) _pCopy1(m) |
---|
| 169 | // Returns a newly allocated copy of the monomial m, sets the coefficient to 0, |
---|
| 170 | // and sets the next-fieled to NULL |
---|
| 171 | #define pHead0(p) _pHead0(p) |
---|
| 172 | // Returns a newly allocated copy of the monomial m, copy includes copy of ceoff |
---|
| 173 | // and sets the next-fieled to NULL |
---|
| 174 | #define pHead(p) _pHead(p) |
---|
| 175 | extern poly pHeadProc(poly p); |
---|
| 176 | // Returns copy of the whole polynomial |
---|
| 177 | #define pCopy(p) _pCopy(p) |
---|
[e78cce] | 178 | // Returns a converted copy (in the sense that returned poly is in |
---|
| 179 | // poly of currRing) of poly p which is from ring r -- assumes that |
---|
| 180 | // currRing and r have the same number of variables, i.e. that polys |
---|
| 181 | // from r can be "fetched" into currRing |
---|
| 182 | #define pFetchCopy(r,p) _pFetchCopy(r,p) |
---|
| 183 | |
---|
[51c163] | 184 | |
---|
[c5f63ab] | 185 | // Adds exponents of p2 to exponents of p1; updates Order field |
---|
| 186 | // assumes that exponents > 0 and < MAX_EXPONENT / 2 |
---|
| 187 | #define pMonAddFast(p1, p2) _pMonAddFast(p1, p2) |
---|
[51c163] | 188 | // Is equivalent to pCopy2(p1, p2);pMonAddFast(p1, p3); |
---|
| 189 | #define pCopyAddFast(p1, p2, p3) _pCopyAddFast(p1, p2, p3) |
---|
[c5f63ab] | 190 | // Similar to pCopyAddFast, except that we do not care about the next field |
---|
| 191 | #define pCopyAddFast0(p1, p2, p3) _pCopyAddFast0(p1, p2, p3) |
---|
[f003a9] | 192 | // Similar to pCopyAddFast0, except that we do not recompute the Order, |
---|
| 193 | // but assume that it is the sum of the Order of p2 and p3 |
---|
| 194 | #define pCopyAddFastHomog(p1, p2, p3, Order) \ |
---|
| 195 | _pCopyAddFastHomog(p1, p2, p3, Order) |
---|
[0e1846] | 196 | |
---|
| 197 | poly pmInit(char *s, BOOLEAN &ok); /* monom -> poly */ |
---|
| 198 | void ppDelete(poly * a, ring r); |
---|
| 199 | |
---|
| 200 | /*-------------operations on polynomials:------------*/ |
---|
| 201 | poly pAdd(poly p1, poly p2); |
---|
| 202 | poly pNeg(poly p); |
---|
| 203 | poly pSub(poly a, poly b); |
---|
| 204 | poly pMult(poly a, poly b); |
---|
| 205 | void pMultN(poly a, number c); |
---|
| 206 | poly pMultCopyN(poly a, number c); |
---|
| 207 | poly pPower(poly p, int i); |
---|
| 208 | |
---|
[51c163] | 209 | // return TRUE, if exponent and component of p1 and p2 are equal, |
---|
| 210 | // FALSE otherwise |
---|
| 211 | #define pEqual(p1, p2) _pEqual(p1, p2) |
---|
[0e1846] | 212 | |
---|
[c5f63ab] | 213 | // returns TRUE, if leading monom of a divides leading monom of b |
---|
| 214 | // i.e., if there exists a expvector c > 0, s.t. b = a + c |
---|
[51c163] | 215 | #define pDivisibleBy(a, b) _pDivisibleBy(a,b) |
---|
| 216 | // like pDivisibleBy, except that it is assumed that a!=NULL |
---|
| 217 | #define pDivisibleBy1(a,b) _pDivisibleBy1(a,b) |
---|
[c5f63ab] | 218 | // like pDivisibleBy, assumes a != NULL, does not check components |
---|
[51c163] | 219 | #define pDivisibleBy2(a, b) _pDivisibleBy2(a,b) |
---|
| 220 | |
---|
[0e1846] | 221 | |
---|
| 222 | poly pDivide(poly a, poly b); |
---|
| 223 | poly pDivideM(poly a, poly b); |
---|
| 224 | void pLcm(poly a, poly b, poly m); |
---|
| 225 | poly pDiff(poly a, int k); |
---|
| 226 | poly pDiffOp(poly a, poly b,BOOLEAN multiply); |
---|
| 227 | |
---|
| 228 | int pLength(poly a); |
---|
| 229 | int pMaxComp(poly p); |
---|
| 230 | int pMinComp(poly p); |
---|
| 231 | int pWeight(int c); |
---|
| 232 | void pSetCompP(poly a, int i); |
---|
| 233 | |
---|
[51c163] | 234 | // Quer sum (total degree) of all exponents of leading monomial |
---|
| 235 | #define pExpQuerSum(p1) _pExpQuerSum(p1) |
---|
| 236 | // sum from 1st to "to"th exponent (including the "to" one) |
---|
| 237 | #define pExpQuerSum1(p1, to) _pExpQuerSum1(p1, to) |
---|
| 238 | // sum from "from"th to "to"th exponent (including borders) |
---|
| 239 | #define pExpQuerSum2(p1, from, to) _pExpQuerSum2(p1, from, to) |
---|
| 240 | |
---|
[0e1846] | 241 | char* pString(poly p); |
---|
| 242 | char* pString0(poly p); |
---|
| 243 | void pWrite(poly p); |
---|
| 244 | void pWrite0(poly p); |
---|
| 245 | void wrp(poly p); |
---|
| 246 | |
---|
| 247 | void pEnlargeSet(polyset *p, int length, int increment); |
---|
| 248 | poly pISet(int i); |
---|
[954622] | 249 | #define pOne() pISet(1) |
---|
[0e1846] | 250 | |
---|
| 251 | void pContent(poly p); |
---|
| 252 | void pCleardenom(poly p); |
---|
| 253 | |
---|
[e78cce] | 254 | // homogenizes p by multiplying certain powers of the varnum-th variable |
---|
[0e1846] | 255 | poly pHomogen (poly p, int varnum); |
---|
[e78cce] | 256 | |
---|
| 257 | // replaces the maximal powers of the leading monomial of p2 in p1 by |
---|
| 258 | // the same powers of n, utility for dehomogenization |
---|
[0e1846] | 259 | poly pDehomogen (poly p1,poly p2,number n); |
---|
| 260 | BOOLEAN pIsHomogeneous (poly p); |
---|
[e78cce] | 261 | |
---|
| 262 | // returns the leading monomial of p1 divided by the maximal power of |
---|
| 263 | // that of p2 |
---|
[0e1846] | 264 | poly pDivByMonom (poly p1,poly p2); |
---|
[e78cce] | 265 | |
---|
| 266 | // Returns as i-th entry of P the coefficient of the (i-1) power of |
---|
| 267 | // the leading monomial of p2 in p1 |
---|
[0e1846] | 268 | void pCancelPolyByMonom (poly p1,poly p2,polyset * P,int * SizeOfSet); |
---|
[e78cce] | 269 | |
---|
| 270 | // orders monoms of poly using insertion sort, performs pSetm on each |
---|
| 271 | // monom (i.e. sets Order field) |
---|
| 272 | poly pOrdPolyInsertSetm(poly p); |
---|
| 273 | |
---|
| 274 | // orders monoms of poly using merge sort (ususally faster than |
---|
| 275 | // insertion sort). ASSUMES that pSetm was performed on monoms |
---|
| 276 | // (i.e. that Order field is set correctly) |
---|
| 277 | poly pOrdPolyMerge(poly p); |
---|
| 278 | |
---|
| 279 | poly pPermPoly (poly p, int * perm, ring OldRing, |
---|
| 280 | int *par_perm=NULL, int OldPar=0); |
---|
[0e1846] | 281 | void pSetSyzComp(int k); |
---|
| 282 | |
---|
| 283 | /*BOOLEAN pVectorHasUnitM(poly p, int * k);*/ |
---|
| 284 | BOOLEAN pVectorHasUnitB(poly p, int * k); |
---|
| 285 | void pVectorHasUnit(poly p, int * k, int * len); |
---|
| 286 | poly pTakeOutComp(poly * p, int k); |
---|
| 287 | poly pTakeOutComp1(poly * p, int k); |
---|
| 288 | void pDeleteComp(poly * p,int k); |
---|
| 289 | void pNorm(poly p); |
---|
| 290 | void pNormalize(poly p); |
---|
| 291 | poly pSubst(poly p, int n, poly e); |
---|
| 292 | poly pJet(poly p, int m); |
---|
| 293 | poly pJetW(poly p, int m, short * iv); |
---|
| 294 | int pDegW(poly p, short *w); |
---|
| 295 | |
---|
| 296 | /*-----------type conversions ----------------------------*/ |
---|
| 297 | poly pPolys2Vec(polyset p, int len); |
---|
| 298 | void pVec2Polys(poly v, polyset *p, int *len); |
---|
| 299 | int pVar(poly m); |
---|
| 300 | |
---|
[51c163] | 301 | /*-----------specials for spoly-computations--------------*/ |
---|
[0e1846] | 302 | poly pMultT(poly a, poly e); |
---|
| 303 | int pDivComp(poly p, poly q); |
---|
| 304 | BOOLEAN pCompareChain (poly p,poly p1,poly p2,poly lcm); |
---|
| 305 | BOOLEAN pEqualPolys(poly p1,poly p2); |
---|
| 306 | BOOLEAN pComparePolys(poly p1,poly p2); |
---|
| 307 | |
---|
| 308 | |
---|
| 309 | #ifdef PDEBUG |
---|
| 310 | #define pTest(A) pDBTest(A,__FILE__,__LINE__) |
---|
| 311 | BOOLEAN pDBTest(poly p, char *f, int l); |
---|
| 312 | #else |
---|
| 313 | #define pTest(A) |
---|
| 314 | #define pDBTest(A,B,C) |
---|
| 315 | #endif |
---|
| 316 | #endif |
---|
| 317 | |
---|
[51c163] | 318 | |
---|