source: git/kernel/p_polys.h @ 87beab7

spielwiese
Last change on this file since 87beab7 was b84b400, checked in by Motsak Oleksandr <motsak@…>, 16 years ago
*motsak: cosmetik change (filename correction in the header) git-svn-id: file:///usr/local/Singular/svn/trunk@10835 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 17.7 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/***************************************************************
5 *  File:    p_polys.h
6 *  Purpose: declaration of poly stuf which are independent of
7 *           currRing
8 *  Author:  obachman (Olaf Bachmann)
9 *  Created: 9/00
10 *  Version: $Id: p_polys.h,v 1.8 2008-07-04 14:21:30 motsak Exp $
11 *******************************************************************/
12#ifndef P_POLYS_H
13#define P_POLYS_H
14
15#include "structs.h"
16#include "polys-impl.h"
17/*
18 Some general remarks:
19 We divide poly operations into roughly 4 categories:
20 Level 2: operations on monomials/polynomials with constant time,
21          or operations which are just dispatchers to other
22          poly routines
23          - implemented in: pInline2.h
24          - debugging only if PDEBUG >= 2
25          - normally inlined, unless PDEBUG >= 2 || NO_INLINE2
26 Level 1: operations on monomials with time proportional to length
27          - implemented in: pInline1.h
28          - debugging only if PDEBUG >= 1
29          - normally inlined, unless PDEBUG >= 1 || NO_INLINE1
30 Level 0: short operations on polynomials with time proportional to
31          length of poly
32          - implemented in pInline0.cc
33          - debugging if PDEBUG
34          - normally _not_ inlined: can be forced with
35            #define DO_PINLINE0
36            #include "pInline0.h"
37 Misc   : operations on polynomials which do not fit in any of the
38          above categories
39          - implemented in: polys*.cc
40          - never inlined
41          - debugging if PDEBUG >= 0
42
43 You can set PDEBUG on a per-file basis, before including "mod2.h" like
44   #define PDEBUG 2
45   #include "mod2.h"
46 However, PDEBUG will only be in effect, if !NDEBUG.
47*/
48
49/***************************************************************
50 *
51 * Primitives for accessing and setting fields of a poly
52 * poly must be != NULL
53 *
54 ***************************************************************/
55// next
56#define pNext(p)            _pNext(p)
57#define pIter(p)            _pIter(p)
58
59// coeff
60#define pGetCoeff(p)        _pGetCoeff(p)
61// deletes old coeff before setting the new one
62#define pSetCoeff0(p,n)     _pSetCoeff0(p,n)
63#define p_GetCoeff(p,r)     _pGetCoeff(p)
64#define p_SetCoeff0(p,n,r)  _pSetCoeff0(p,n)
65// deletes old p->coef and sets new one
66PINLINE2 number p_SetCoeff(poly p, number n, ring r);
67
68// get Order
69PINLINE2 Order_t p_GetOrder(poly p, ring r);
70// don't use this
71PINLINE2 Order_t p_SetOrder(poly p, long order, ring r);
72
73// Component
74#define p_GetComp(p, r)     _p_GetComp(p, r)
75PINLINE2 unsigned long p_SetComp(poly p, unsigned long c, ring r);
76PINLINE2 unsigned long p_IncrComp(poly p, ring r);
77PINLINE2 unsigned long p_DecrComp(poly p, ring r);
78PINLINE2 unsigned long p_AddComp(poly p, unsigned long v, ring r);
79PINLINE2 unsigned long p_SubComp(poly p, unsigned long v, ring r);
80
81// Exponent
82PINLINE2 int p_GetExp(poly p, int v, ring r);
83PINLINE2 int p_SetExp(poly p, int v, int e, ring r);
84PINLINE2 int p_IncrExp(poly p, int v, ring r);
85PINLINE2 int p_DecrExp(poly p, int v, ring r);
86PINLINE2 int p_AddExp(poly p, int v, int ee, ring r);
87PINLINE2 int p_SubExp(poly p, int v, int ee, ring r);
88PINLINE2 int p_MultExp(poly p, int v, int ee, ring r);
89PINLINE2 int p_GetExpSum(poly p1, poly p2, int i, ring r);
90PINLINE2 int p_GetExpDiff(poly p1, poly p2, int i, ring r);
91
92/***************************************************************
93 *
94 * Allocation/Initalization/Deletion
95 * except for pDeleteLm and pHead, all polys must be != NULL
96 *
97 ***************************************************************/
98PINLINE2 poly p_New(ring r);
99PINLINE2 poly p_New(ring r, omBin bin);
100PINLINE1 poly p_Init(ring r);
101PINLINE1 poly p_Init(ring r, omBin bin);
102PINLINE1 poly p_LmInit(poly p, ring r);
103PINLINE1 poly p_LmInit(poly s_p, ring s_r, ring d_p);
104PINLINE1 poly p_LmInit(poly s_p, ring s_r, ring d_p, omBin d_bin);
105PINLINE1 poly p_Head(poly p, ring r);
106PINLINE2 void p_DeleteLm(poly *p, ring r);
107PINLINE2 void p_DeleteLm(poly p, ring r);
108PINLINE2 void p_LmFree(poly p, ring r);
109PINLINE2 void p_LmFree(poly *p, ring r);
110PINLINE2 poly p_LmFreeAndNext(poly p, ring r);
111PINLINE2 void p_LmDelete(poly p, ring r);
112PINLINE2 void p_LmDelete(poly *p, ring r);
113PINLINE2 poly p_LmDeleteAndNext(poly p, ring r);
114
115/***************************************************************
116 *
117 * Operation on ExpVectors: assumes polys != NULL
118 *
119 ***************************************************************/
120// ExpVextor(d_p) = ExpVector(s_p)
121PINLINE1 void p_ExpVectorCopy(poly d_p, poly s_p, ring r);
122// adjustments for negative weights
123PINLINE1 void p_MemAdd_NegWeightAdjust(poly p, ring r);
124PINLINE1 void p_MemSub_NegWeightAdjust(poly p, ring r);
125// ExpVector(p1) += ExpVector(p2)
126PINLINE1 void p_ExpVectorAdd(poly p1, poly p2, ring r);
127// ExpVector(p1) -= ExpVector(p2)
128PINLINE1 void p_ExpVectorSub(poly p1, poly p2, ring r);
129// ExpVector(p1) += ExpVector(p2) - ExpVector(p3)
130PINLINE1 void p_ExpVectorAddSub(poly p1, poly p2, poly p3, ring r);
131// ExpVector(pr) = ExpVector(p1) + ExpVector(p2)
132PINLINE1 void p_ExpVectorSum(poly pr, poly p1, poly p2, ring r);
133// ExpVector(pr) = ExpVector(p1) + ExpVector(p2)
134PINLINE1 void p_ExpVectorDiff(poly pr, poly p1, poly p2, ring r);
135// returns TRUE if ExpVector(p1) == ExpVector(p2), FALSE, otherwise
136PINLINE1 BOOLEAN p_ExpVectorEqual(poly p1, poly p2, ring r);
137// returns sum of all exponents of p
138PINLINE1 unsigned long p_ExpVectorQuerSum(poly p, ring r);
139
140PINLINE1 void p_GetExpV(poly p, int *ev, ring r);
141PINLINE1 void p_SetExpV(poly p, int *ev, ring r);
142
143
144/***************************************************************
145 *
146 * Comparisons: they are all done without regarding coeffs
147 *
148 ***************************************************************/
149PINLINE1 int p_LmCmp(poly p, poly q, ring r);
150#define p_LmCmpAction(p, q, r, actionE, actionG, actionS) \
151  _p_LmCmpAction(p, q, r, actionE, actionG, actionS)
152
153// returns 1 if ExpVector(p)==ExpVector(q): does not compare numbers !!
154#define p_LmEqual(p1, p2, r) p_ExpVectorEqual(p1, p2, r)
155
156// pCmp: args may be NULL
157// returns: (p2==NULL ? 1 : (p1 == NULL ? -1 : p_LmCmp(p1, p2)))
158PINLINE2 int p_Cmp(poly p1, poly p2, ring r);
159
160
161/***************************************************************
162 *
163 * Divisiblity tests, args must be != NULL, except for
164 * pDivisbleBy
165 *
166 ***************************************************************/
167PINLINE1 BOOLEAN p_DivisibleBy(poly a, poly b, ring r);
168PINLINE1 BOOLEAN p_LmDivisibleBy(poly a, poly b, ring r);
169PINLINE1 BOOLEAN p_LmDivisibleByNoComp(poly a, poly b, ring r);
170unsigned long p_GetShortExpVector(poly a, ring r);
171PINLINE1 BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a,
172                                      poly b, unsigned long not_sev_b, ring r);
173
174PINLINE1 BOOLEAN p_DivisibleBy(poly a, ring r_a, poly b, ring r_b);
175PINLINE1 BOOLEAN p_LmDivisibleBy(poly a, ring r_a, poly b, ring r_b);
176PINLINE1 BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, ring r_a,
177                                      poly b, unsigned long not_sev_b, ring r_b);
178
179/***************************************************************
180 *
181 * Misc things on Lm
182 *
183 ***************************************************************/
184// test if the monomial is a constant as a vector component
185// i.e., test if all exponents are zero
186PINLINE1 BOOLEAN p_LmIsConstantComp(const poly p, const ring r);
187PINLINE1 BOOLEAN p_LmIsConstant(const poly p, const ring r);
188
189// return TRUE, if p_LmExpVectorAdd stays within ExpBound of ring r,
190//       FALSE, otherwise
191PINLINE1 BOOLEAN p_LmExpVectorAddIsOk(const poly p1, const poly p2, ring r);
192
193/***************************************************************
194 *
195 * Misc things on polys
196 *
197 ***************************************************************/
198// return the maximal exponent of p
199PINLINE2 unsigned long p_GetMaxExp(poly p, ring r);
200// return the maximal exponent of p in form of the maximal long var
201unsigned long p_GetMaxExpL(poly p, ring r, unsigned long l_max = 0);
202// return monomial r such that GetExp(r,i) is maximum of all
203// monomials in p; coeff == 0, next == NULL, ord is not set
204poly p_GetMaxExpP(poly p, ring r);
205
206// suppose that l is a long var in r, return maximal exponent of l
207PINLINE2 unsigned long p_GetMaxExp(unsigned long l, ring r);
208// similar, except assume that l constains number_of_exps exponents
209PINLINE2 unsigned long p_GetMaxExp(const unsigned long l, const ring r, const int number_of_exps);
210
211// return the TotalDegree of the long var l
212PINLINE2 unsigned long p_GetTotalDegree(const unsigned long l, const ring r);
213// return the total degree of the long var l containing number_of_exp exponents
214PINLINE2 unsigned long p_GetTotalDegree(const unsigned long l, const ring r, const int number_of_exps);
215
216
217// like the respective p_LmIs* routines, except that p might be empty
218PINLINE1 BOOLEAN p_IsConstantComp(const poly p, const ring r);
219PINLINE1 BOOLEAN p_IsConstant(const poly p, const ring r);
220PINLINE0 BOOLEAN p_IsConstantPoly(const poly p, const ring r);
221
222// return TRUE if all monoms have the same component
223BOOLEAN   p_OneComp(poly p, ring r);
224
225// return i, if head depends only on var(i)
226int       p_IsPurePower(const poly p, const ring r);
227
228// return i, if poly depends only on var(i)
229int       p_IsUnivariate(poly p, const ring r);
230
231// set entry e[i] to 1 if var(i) occurs in p, ignore var(j) if e[j]>0
232// return #(e[i]>0)
233int      p_GetVariables(poly p, int * e, const ring r);
234
235// returns the poly representing the integer i
236poly      p_ISet(int i, ring r);
237
238// returns the poly representing the number n, destroys n
239poly      p_NSet(number n, ring r);
240
241/***************************************************************
242 *
243 * Copying/Deletion of polys: args may be NULL
244 *
245 ***************************************************************/
246// returns a copy of p
247PINLINE2 poly p_Copy(poly p, const ring r);
248// returns a copy of p with Lm(p) from lmRing and Tail(p) from tailRing
249PINLINE2 poly p_Copy(poly p, const ring lmRing, const ring tailRing);
250// deletes *p, and sets *p to NULL
251PINLINE2 void p_Delete(poly *p, const ring r);
252PINLINE2 void p_Delete(poly *p, const ring lmRing, const ring tailRing);
253
254// copys monomials of p, allocates new monomials from bin,
255// deletes monomoals of p
256PINLINE2 poly p_ShallowCopyDelete(poly p, const ring r, omBin bin);
257// simial but does it only for leading monomial
258PINLINE1 poly p_LmShallowCopyDelete(poly p, const ring r, omBin bin);
259// simply deletes monomials, does not free coeffs
260void p_ShallowDelete(poly *p, const ring r);
261
262 
263
264/***************************************************************
265 *
266 * Copying/Deleteion of polys: args may be NULL
267 *  - p/q as arg mean a poly
268 *  - m a monomial
269 *  - n a number
270 *  - pp (resp. qq, mm, nn) means arg is constant
271 *  - p (resp, q, m, n)     means arg is destroyed
272 *
273 ***************************************************************/
274// returns -p, p is destroyed
275PINLINE2 poly p_Neg(poly p, const ring r);
276
277// returns p*n, p is const (i.e. copied)
278PINLINE2 poly pp_Mult_nn(poly p, number n, const ring r);
279// returns p*n, destroys p
280PINLINE2 poly p_Mult_nn(poly p, number n, const ring r);
281PINLINE2 poly p_Mult_nn(poly p, number n, const ring lmRing, const ring tailRing);
282
283// returns p*m, does neither destroy p nor m
284PINLINE2 poly pp_Mult_mm(poly p, poly m, const ring r);
285// returns p*m, destroys p, const: m
286PINLINE2 poly p_Mult_mm(poly p, poly m, const ring r);
287
288// returns p+q, destroys p and q
289PINLINE2 poly p_Add_q(poly p, poly q, const ring r);
290// like p_Add_q, except that if lp == pLength(lp) lq == pLength(lq)
291// then lp == pLength(p+q)
292PINLINE2 poly p_Add_q(poly p, poly q, int &lp, int lq, const ring r);
293
294// return p - m*q, destroys p; const: q,m
295PINLINE2 poly p_Minus_mm_Mult_qq(poly p, poly m, poly q, const ring r);
296// like p_Minus_mm_Mult_qq, except that if lp == pLength(lp) lq == pLength(lq)
297// then lp == pLength(p -m*q)
298PINLINE2 poly p_Minus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq,
299                                 poly spNoether, const ring r);
300// returns p + m*q destroys p, const: q, m
301PINLINE2 poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, const ring r);
302
303// returns p + m*q destroys p, const: q, m
304PINLINE2 poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq,
305                                const ring r);
306
307// returns p*q, destroys p and q
308PINLINE2 poly p_Mult_q(poly p, poly q, const ring r);
309// returns p*q, does neither destroy p nor q
310PINLINE2 poly pp_Mult_qq(poly p, poly q, const ring r);
311
312// returns p*Coeff(m) for such monomials pm of p, for which m is divisble by pm
313PINLINE2 poly pp_Mult_Coeff_mm_DivSelect(poly p, const poly m, const ring r);
314
315// returns p*Coeff(m) for such monomials pm of p, for which m is divisble by pm
316// if lp is length of p on input then lp is length of returned poly on output
317PINLINE2 poly pp_Mult_Coeff_mm_DivSelect(poly p, int &lp, const poly m, const ring r);
318
319// returns merged p and q, assumes p and q have no monomials which are equal
320PINLINE2 poly p_Merge_q(poly p, poly c, const ring r);
321// sorts p using bucket sort: returns sorted poly
322// assumes that monomials of p are all different
323// reverses it first, if revert == TRUE, use this if input p is "almost" sorted
324// correctly
325PINLINE2 poly p_SortMerge(poly p, const ring r, BOOLEAN revert = FALSE);
326// like SortMerge, except that p may have equal monimals
327PINLINE2 poly p_SortAdd(poly p, const ring r, BOOLEAN revert = FALSE);
328
329/***************************************************************
330 *
331 * Misc stuff
332 *
333 ***************************************************************/
334PINLINE2 void p_Setm(poly p, const ring r);
335p_SetmProc p_GetSetmProc(ring r);
336
337// TODO:
338#define p_SetmComp  p_Setm
339
340// sets component of poly a to i, returns length of a
341PINLINE0   int p_SetCompP(poly a, int i, ring r);
342PINLINE0   int p_SetCompP(poly a, int i, ring lmRing, ring tailRing);
343PINLINE0   long p_MaxComp(poly p, ring lmRing, ring tailRing);
344inline long p_MaxComp(poly p,ring lmRing) {return p_MaxComp(p,lmRing,lmRing);}
345PINLINE0   long p_MinComp(poly p, ring lmRing, ring tailRing);
346inline long p_MinComp(poly p,ring lmRing) {return p_MinComp(p,lmRing,lmRing);}
347
348/***************************************************************
349 *
350 * poly things which are independent of ring
351 *
352 ***************************************************************/
353PINLINE0 int       pLength(poly a);
354PINLINE0 poly      pLast(poly a, int &length);
355inline   poly      pLast(poly a) { int l; return pLast(a, l);}
356PINLINE0 poly pReverse(poly p);
357
358
359/***************************************************************
360 *
361 * I/O
362 *
363 ***************************************************************/
364char*     p_String(poly p, ring lmRing, ring tailRing);
365char*     p_String0(poly p, ring lmRing, ring tailRing);
366void      p_Write(poly p, ring lmRing, ring tailRing);
367void      p_Write0(poly p, ring lmRing, ring tailRing);
368void      p_wrp(poly p, ring lmRing, ring tailRing);
369
370PINLINE2 char*     p_String(poly p, ring p_ring);
371PINLINE2 char*     p_String0(poly p, ring p_ring);
372PINLINE2 void      p_Write(poly p, ring p_ring);
373PINLINE2 void      p_Write0(poly p, ring p_ring);
374PINLINE2 void      p_wrp(poly p, ring p_ring);
375
376
377/***************************************************************
378 *
379 * Degree stuff -- see p_polys.cc for explainations
380 *
381 ***************************************************************/
382extern pLDegProc pLDeg;
383extern pFDegProc pFDeg;
384int  pWeight(int i, ring r);
385long pDeg(poly p, ring r);
386long pTotaldegree(poly p, ring r);
387long pWFirstTotalDegree(poly p, ring r);
388long pWTotaldegree(poly p, ring r);
389long pWDegree(poly p, ring r);
390long pLDeg0(poly p,int *l, ring r);
391long pLDeg0c(poly p,int *l, ring r);
392long pLDegb(poly p,int *l, ring r);
393long pLDeg1(poly p,int *l, ring r);
394long pLDeg1c(poly p,int *l, ring r);
395long pLDeg1_Deg(poly p,int *l, ring r);
396long pLDeg1c_Deg(poly p,int *l, ring r);
397long pLDeg1_Totaldegree(poly p,int *l, ring r);
398long pLDeg1c_Totaldegree(poly p,int *l, ring r);
399long pLDeg1_WFirstTotalDegree(poly p,int *l, ring r);
400long pLDeg1c_WFirstTotalDegree(poly p,int *l, ring r);
401BOOLEAN p_EqualPolys(poly p1, poly p2, ring r);
402/***************************************************************
403 *
404 * PDEBUG stuff
405 *
406 ***************************************************************/
407#ifdef PDEBUG
408// Returns TRUE if m is monom of p, FALSE otherwise
409BOOLEAN pIsMonomOf(poly p, poly m);
410// Returns TRUE if p and q have common monoms
411BOOLEAN pHaveCommonMonoms(poly p, poly q);
412
413// p_Check* routines return TRUE if everything is ok,
414// else, they report error message and return false
415
416// check if Lm(p) is from ring r
417BOOLEAN p_LmCheckIsFromRing(poly p, ring r);
418// check if Lm(p) != NULL, r != NULL and initialized && Lm(p) is from r
419BOOLEAN p_LmCheckPolyRing(poly p, ring r);
420// check if all monoms of p are from ring r
421BOOLEAN p_CheckIsFromRing(poly p, ring r);
422// check r != NULL and initialized && all monoms of p are from r
423BOOLEAN p_CheckPolyRing(poly p, ring r);
424// check if r != NULL and initialized
425BOOLEAN p_CheckRing(ring r);
426// only do check if cond
427
428
429#define pIfThen(cond, check) do {if (cond) {check;}} while (0)
430
431BOOLEAN _p_Test(poly p, ring r, int level);
432BOOLEAN _p_LmTest(poly p, ring r, int level);
433BOOLEAN _pp_Test(poly p, ring lmRing, ring tailRing, int level);
434
435#define p_Test(p,r)     _p_Test(p, r, PDEBUG)
436#define p_LmTest(p,r)   _p_LmTest(p, r, PDEBUG)
437#define pp_Test(p, lmRing, tailRing)    _pp_Test(p, lmRing, tailRing, PDEBUG)
438
439#else // ! PDEBUG
440
441#define pIsMonomOf(p, q)        (TRUE)
442#define pHaveCommonMonoms(p, q) (TRUE)
443#define p_LmCheckIsFromRing(p,r)  ((void)0)
444#define p_LmCheckPolyRing(p,r)    ((void)0)
445#define p_CheckIsFromRing(p,r)  ((void)0)
446#define p_CheckPolyRing(p,r)    ((void)0)
447#define p_CheckRing(r)          ((void)0)
448#define P_CheckIf(cond, check)  ((void)0)
449
450#define p_Test(p,r)     (1)
451#define p_LmTest(p,r)   (1)
452#define pp_Test(p, lmRing, tailRing) (1)
453
454#endif
455
456#include "pInline2.h"
457#include "pInline1.h"
458
459#endif // P_POLYS_H
460
Note: See TracBrowser for help on using the repository browser.