OrdvArith

© 2005 John Abbott
GNU Free Documentation License, Version 1.2



index page

User documentation for OrdvArith

Further features of PPOrdering for CoCoA library developers

There are many more operations on a PPOrdering object than those listed above. These further operations are used in the implementation of some sorts of PPMonoid, and some sorts of (distributed multivariate) polynomial. Run-time efficiency is the primary reason for the existence of these functions: so be warned that cleanliness is sometimes sacrificed at the altar of speed.

To better understand the what and the why of a PPOrdering, let us begin by setting the scene. We recall that for all practical purposes an arithmetic ordering on power products can be specified by a matrix of integers M as follows:

Let t1 = x_1^e_1 * x_2^e_2 * ... * x_n^e_n be a power product, and t2 = x_1^f_1 * x_2^f_2 * ... * x_n^f_n be another. Then we call (e_1, e_2,..., e_n) the exponent vector for t1, and similarly for t2. For brevity we shall write expv(t1), etc.

The matrix M determines the ordering thus: we say that t1 < t2 iff M*expv(t1) comes before M*expv(t2) in lex ordering. We call the product M*expv(t1) the order vector for t1, and for brevity we shall write ordv(t1) to denote it.

Typically the matrix M is subject to some suitability criteria, e.g. M should be square and invertible. We shall assume henceforth that M has been chosen so that all order vectors contain only non-negative entries. While reading the rest of these notes it may be convenient to think of M as being non-singular, so that there is a 1-1 correspondence between power products and their order vectors.

Now the scene has been set, we can explain what a PPOrdering object does. Abstractly, we can think of the PPOrdering as embodying the matrix M; in practice shortcuts are taken if M has a recognised special structure. A PPOrdering offers a number of simple operations on order vectors including conversion to and from an exponent vector.

Before listing the operations a PPOrdering offers, let me emphasise that a PPOrdering NEVER allocates memory: the caller must always supply a pointer to enough free memory (this is relevant mainly for conversion between order vectors and exponent vectors). An exponent vector is taken to be a C array of NumIndets(PPO) entries each of type PPOrdering::ExpvElem where the i-th entry is the i-th exponent. An order vector is taken to be a C array of OrdvWords(PPO) entries each of type PPOrdering::OrdvElem -- the entries do not admit an easy interpretation.

    OrdvWords(PPO)                  -- "size" that an order vector must have
                                       (see note in text above)
    PPO->myInit(ordv)               -- initialize an order vector to zero
    PPO->myInitFromExpv(ordv, expv) -- initialize an order vector from an exponent vector
    PPO->myAssign(l_ordv, r_ordv)   -- assign r_ordv to l_ordv
    PPO->myMul(ordv, ordv1, ordv2)  -- ordv = ordv1 * ordv2
    PPO->myDiv(ordv, ordv1, ordv2)  -- ordv = ordv1 / ordv2 (quotient MUST exist)
    PPO->myMulIndetPower(ordv, var, exp) -- ordv *= var^exp
    PPO->myCmp(l_ordv, r_ordv)      -- return -1,0,+1 according as l_ordv <,=,> r_ordv
    PPO->myCmpExpvs(l_expv, r_expv) -- return -1,0,+1 according as l_expv <,=,> r_expv
    PPO->myComputeExpv(expv, ordv)  -- convert ordv into expv
    PPO->myLog(ordv, var)           -- return power of var in PP corresponding to ordv (result is an unsigned type)
    PPO->myDeg(d, ordv)             -- compute degree of ordv, putting result in d
    PPO->myCmpDeg(ordv1, ordv2)     -- return -1,0,+1 according as deg(ordv1) <,=,> deg(ordv2)
    PPO->myIsOne(ordv)              -- return true iff ordv corr to the power product 1
    PPO->myOutput(OMOut, ordv)      -- output ordv on an OpenMath channel

NOTES

To Write a New Concrete PPOrdering Class

If you plan to write a new concrete class derived from PPOrderingBase then you must know about these virtual member functions:

     myMulSpecial(ordv, ordv1, ordv2)
     myDivSpecial(ordv, ordv1, ordv2)
     myCmpSpecial(l_ordv, r_ordv)

Their existence and their curious names arise from the need to make myMul, myDiv and myCmp inline for the common case of densely represented order vectors. If you plan to add a new concrete PPOrdering which is based on densely represented order vectors then have a look at the implementations in the PPOrderingDense files.

If you are considering implementing some other sort of concrete PPOrdering, read on. The inline functions myMul, myDiv and myCmp use the value of the data member PPOrderingBase::myOrdvWordsForCmp to decide what to do: if the value is non-zero, they assume a dense representation is being used and execute the corresponding loop, otherwise they call corresponding "special" virtual function to do all the work. You will probably need to set myOrdvWordsForCmp to zero, and you must place your implementations for product, quotient and comparison in the "special" functions.

[I know this is ugly, but cannot see how else to guarantee that the dense case can be compiled inline]

Maintainer documentation for OrdvArith

The implementation of PPOrderingBase is closely tied to those of PPMonoid and DistrMPolyInlPP. Be aware of this if you want to change PPOrderingBase at all.

On the whole, PPOrderingBase is a fairly straightforward abstract class: - it has an intrusive reference count; - it defines numerous pure virtual functions; - it has four data members.

The main oddities and other points of note are below.

Data member myNumIndets is required when dealing with exponent vectors (since C vectors do not record their own length). It is the number of valid entries in a C vector representing an exponent vector.

Data member myGradingDim specifies how many initial components of an order vector comprise the grading. It is needed in myDeg.

Data member myOrdvWords is used only to supply the return value to the friend function OrdvWords. This value is needed so that a caller can allocate the correct amount of space in which to build a new order vector value. By default this is initialized to a huge value, so that it will quickly become evident at run-time if it hasn't been initialized to a sane value.

Data member myOrdvWordsForCmp is used in myMul, myDiv and myCmp to choose between an inline function and a virtual call. Its value may be non-zero and different from myOrdvWords if a redundant representation is being used (e.g. for a DegRevLex ordering). By default this is initialized to a huge value, so that it will quickly become evident at run-time if it hasn't been initialized to a sane value.

The member functions myMul, myDiv, and myCmp are non-virtual so that the compiler can implement them inline: at run-tme they check the data member myOrdvWordsForCmp to decide whether to the use the inline function or delegate to a "shadow" virtual function. This rather ugly arrangement was necessary to achieve acceptable run-time performance.

The member function myMulIndetPower is not pure because a reasonable generic implementation exists. Similarly, myOutput(OMOut, ordv) is not pure.

Bugs, Shortcomings and other ideas

This documentation has been salvaged from an old version of PPOrdering.txt. It probably needs major modification.

In some ways, myCmp could simply be operator(); thus calls would look like ord(ordv1, ordv2) where ord is an object of type PPOrdering.

Are the typedefs PPOrdering::OrdvElem and PPOrdering::ExpvElem really independent?

Why is myOrdvBuffer a C++ vector<> instead just a C vector???

We need a way to handle order vectors which have large integer entries! (also ordering matrices with large integer entries). Recall that some ordvs may involve mpz_t integers! Note that the polynomial type needs to know how big an ordv can be: that's what the OrdvWords member function is for.

Should "degrevlex" actually store an extra component so that deg(...,x[0]) can be calculated easily? Do we really need this to be quick? It would be needed for computing GCDs, testing divisibility etc, but these operations would normally be done only on "rich PP" objects -- talk to Anna!

The restriction to order compatible gradings may not be wholly necessary. The PPs in a polynomial homogeneous with respect to a k-dimensional grading are completely specified by n-k of the entries in the order vector, though precisely which entries must be retained depends on the grading and the ordering. Thus a later generalization to non order compatible gradings may not be too painful.

ANNA: must add a section about modular order matrix

The default implementation of myIsIndet is not very efficient, but is it really worth writing many different (efficient) implementations?