CoCoALib-0.9905 date: 23 May 2007

CoCoA::SparsePolyRing Class Reference

#include <SparsePolyRing.H>

Inheritance diagram for CoCoA::SparsePolyRing:

Inheritance graph
List of all members.

Public Member Functions

 SparsePolyRing (const SparsePolyRingBase *RingPtr)
const SparsePolyRingBaseoperator-> () const
 allow member fns to be called
const RingBasemyRawPtr () const
 Used by "downcasting" functions IsRingFp, AsRingFp, etc.

Detailed Description

      Copyright (c)  2005,2007  John Abbott
      Permission is granted to copy, distribute and/or modify this document
      under the terms of the GNU Free Documentation License, Version 1.2;
      with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
      A copy of the licence is included in the file COPYING in this directory.

User documentation for SparsePolyRing (and elements of a SparsePolyRing)

SparsePolyRing is an abstract class representing rings of polynomials;
in particular, rings of sparse multivariate polynomials with a special
view towards computing Groebner bases and other related operations.
This means that the operations offered by a SparsePolyRing on its own
values are strongly oriented towards those needed by Buchberger's

Currently there are four functions to create a polynomial ring:
  NewPolyRing(CoeffRing, NumIndets)
    This creates a sparse polynomial ring with coefficients in [CoeffRing]
    and having [NumIndets] indeterminates.  The PP ordering is [StdDegRevLex].
    CoCoALib chooses automatically some names for the indeterminates
    (currently the names are x[0], x[1], ... , x[NumIndets-1]).

  NewPolyRing(CoeffRing, IndetNames)
    This creates a sparse polynomial ring with coefficients in [CoeffRing]
    and having indeterminates whose names are given in [IndetNames] (which
    is of type [vector<symbol>]).  The PP ordering is [StdDegRevLex].

  NewPolyRing(CoeffRing, IndetNames, ord)
    This creates a sparse polynomial ring with coefficients in [CoeffRing]
    and having indeterminates whose names are given in [IndetNames] (which
    is of type [vector<symbol>]).  The PP ordering is given by [ord].

  NewPolyRing(CoeffRing, PPM)
    This creates a sparse polynomial ring with coefficients in [CoeffRing] and
    with power products in [PPM] which is a power product monoid which specifies
    how many indeterminates, their names, and the ordering on them.

A polynomial is viewed abstractly as a formal sum of ordered terms; each
term is a formal product of a non-zero coefficient (belonging to the
coefficient ring), and a power product of indeterminates (belonging to the
PPMonoid of the ring).  The ordering is determined by the ordering on the
power products: distinct terms in a polynomial must have distinct power
products.  The zero polynomial is conceptually the formal sum of no terms;
all other polynomials have a "leading term" being the one with the largest
power product in the given ordering.

Operations on a SparsePolyRing
We list here the operations available for an object of type [SparsePolyRing];
you should also consult the documentation in PolyRing.txt for operations on
more general sorts of polynomial ring.

Let P be an object of type [SparsePolyRing].  Let R be an object of type [ring].

  NumIndets(P)         -- the number of indeterminates in P.
  CoeffRing(P)         -- the ring of coefficients of P.
  PPM(P)               -- the PPMonoid of P.
  GradingDim(P)        -- the dimension of the grading on P (may be 0).

  IsSparsePolyRing(R)  -- returns true if the [ring] R is indeed a [SparsePolyRing].
  AsSparsePolyRing(R)  -- returns a [SparsePolyRing] refering to the ring underlying R.

  indets(P)            -- a [const std::vector<RingElems>] whose i-th
                          element is the i-th indeterminate in P.
  indet(P,i)           -- the i-th indet of P as a [RingElem].
  IndetPower(P,i,n)    -- the n-th power of the i-th indet of P as a [RingElem].

Operations on Elements of a SparsePolyRing

In addition to the standard [ring] and [PolyRing] operations, elements of a
[SparsePolyRing] may used in other functions.
Let P denote a [SparsePolyRing].
Let f denote a non-const element of P.
Let f1, f2 denote const elements of P.
Let expv be a [vector<long>] of size equal to the number of indeterminates.

owner(f1)            -- the owner of f as a ring; NB to get the owner as
                        a SparsePolyRing use AsSparsePolyRing(owner(f1)).
NumTerms(f1)         -- the number of terms in f1.
LPP(f1)              -- the leading PP of f1; it is an element of PPM(P).
wdeg(f1)             -- the weighted degree of the leading PP of f1; error if f1 is 0.
                        NB result is of type [CoCoA::degree] (see degree.txt).
                        [contrast with StdDeg(f1) and deg(f1) defined in PolyRing.txt]
CmpWDeg(f1, f2)      -- compare the weighted degrees of the LPPs of f1 and f2;
                        result is <0 =0 >0 according as deg(f1) < = > deg(f2)
IsHomogeneous(f);    -- says whether f is homogeneous wrt weighted degree.
homog(f, h);         -- returns f homogenized with indet h (requires GrDim=1 and wdeg(h)=1).
NR(f, v);            -- returns the (normal) remainder of the Division
                        Algorithm by v.  If v is a GBasis this is the Normal Form.

monomial(P,c,pp)     -- returns c*pp as an element of P where c is in CoeffRing(P)
                        and pp is in PPM(P).
monomial(P,c,expv)   -- returns c*x[0]^exps[0]*x[1]^exps[1]*...
                        where c is in CoeffRing(P), and x[i] are the indets of P.

BeginIter(f1)        -- a SparsePolyIter pointing to the first term in f1
EndIter(f1)          -- a SparsePolyIter pointing to one-past-the-last term in f1
                        Changing the value of f1 invalidates all iterators over f1.

!!Use these two functions with great care [c may be 0]:
PushFront(f, c, expv)-- add to f the term c*t
                        where t is the PP with exponent vector expv,
                        and ASSUMING that t > LPP(f) or f==0
PushBack(f, c, expv) -- add to f the term c*t
                        where t is the PP with exponent vector expv,
                        and ASSUMING that t < t' for all t' appearing in f.
the corresponding member functions myPushFront/myPushBack will not
check the validity of these assumpions:  they should have a
"CoCoA_ASSERT" to check in DEBUG mode.

Operations on SparsePolyIters

Let i1 and i2 be two [SparsePolyIter]s running over the same polynomial.
coeff(i1)             -- read-only access to the coeff of the current term
PP(i1)                -- read-only access to the pp of the current term
++i1                  -- advance i1 to next term, return new value of i1
i1++                  -- advance i1 to next term, return copy of old value of i1
i1 == i2              -- true iff i1 and i2 point to the same term;
                         throws [CoCoA::ErrorInfo] with code [ERR::MixedPolyIters]
                         if i1 and i2 are over different polys.
i1 != i2              -- same as !(i1 == i2)
IsEnded(i1)           -- true iff i1 is pointing at the one-past-the-last term

Maintainer documentation for SparsePolyRing

The exact nature of a "term" in a polynomial is hidden from public view:
it is not possible to get at any term in a polynomial by any publicly
accessible function.  This allows wider scope for trying different
implementations of polynomials where the "terms" may be represented in
some implicit manner.  On the other hand, there are many cases where
an algorithm needs to iterate over the terms in a polynomial; some of
these algorithms are "inside" PolyRing (i.e. the abstract class offers
a suitable interface), but many will have to be "outside" for reasons
of modularity and maintainability.  Hence the need to have "iterators"
which run through the terms in a polynomial.

The implementations in SparsePolyRing.C are all very simple: they just conduct
some sanity checks on the function arguments before passing them to the
PolyRing member function which will actually do the work.

Bugs, Shortcomings and other ideas

Too many of the iterator functions are inline.  Make them out of line, then
use profiler to decide which should be inline.

[PushFront] and [PushBack] do not verify that the ordering criteria are

Verify the true need for [myContent], [myRemoveBigContent], [myMulByCoeff],
[myDivByCoeff], [myMul] (by pp).  If the coeff ring has zero divisors then
[myMulByCoeff] could change the structure of the poly!

Verify the need for these member functions:
myIsZeroAddLCs, myMoveLM, myDeleteLM, myDivLM, myCmpLPP, myAppendClear,
myAddClear, myAddMul, myReductionStep, myReductionStepGCD, myDeriv.

Definition at line 95 of file SparsePolyRing.H.

Constructor & Destructor Documentation

CoCoA::SparsePolyRing::SparsePolyRing const SparsePolyRingBase RingPtr  )  [inline, explicit]

Definition at line 299 of file SparsePolyRing.H.

Member Function Documentation

const SparsePolyRingBase * CoCoA::SparsePolyRing::operator->  )  const [inline]

allow member fns to be called

Reimplemented from CoCoA::PolyRing.

Definition at line 304 of file SparsePolyRing.H.

References CoCoA::ring::operator->().

const RingBase* CoCoA::ring::myRawPtr  )  const [inline, inherited]

Used by "downcasting" functions IsRingFp, AsRingFp, etc.

Definition at line 61 of file ring.H.

References CoCoA::SmartPtrIRC< T >::myRawPtr().

Referenced by CoCoA::AsPolyRing(), CoCoA::AsSparsePolyRing(), CoCoA::IsPolyRing(), CoCoA::IsSparsePolyRing(), and CoCoA::operator==().

The documentation for this class was generated from the following file:
Generated on Wed May 23 13:46:32 2007 for CoCoALib by  doxygen 1.4.6