ApCoCoALib:OrderIdeal

User documentation for files OrderIdeal.C and OrderIdeal.H

The class [OrderIdeal] represents an order ideal, i.e. a finite set of terms that is closed under divisors.

The order ideal is handled by its corner terms, i.e. not every term contained in it is actually stored.

Functions for [OrderIdeal]s

---

Let "terms" and "border" be std::set<PPMonoidElem> objects, "t" a PPMonoidElem object, and "O" an OrderIdeal object.

  OrderIdeal(PPMonoid)          -- create an empty order ideal

  OrderIdeal(PPMonoid, terms)   -- create an order ideal spanned by the terms
                                    of set "terms"

   cout << O                     -- print O on cout

  OrderIdeal::myEnlarge(terms)  -- enlarge the order ideal by the terms of set
                                   "terms"; the enlarged order ideal will be
                                   spanned by the previously contained terms and
                                   the terms of set "terms"
  OrderIdeal::myClear()         -- delete all corner terms; the order ideal is
                                   now empty
  OrderIdeal::myCorners()       -- return a std::set<PPMonoidElem> reference that
                                   contains the corner terms of the order ideal
  OrderIdeal::myBorder(border)  -- compute the border of the order ideal and store
                                   the result in "border"
  OrderIdeal::IamEmpty()        -- returns "true" if the order ideal ist empty
  OrderIdeal::myContains(t)     -- returns "true" if the term "t" is contained in
                                   the order ideal
  OrderIdeal::myPPM()           -- returns a reference to the PPMonoid to which
                                   every term of the order ideal belongs to

Maintainer documentation for files OrderIdeal.C and OrderIdeal.H

As mentioned in the preface, internally only the corner terms of an order ideal are stored but not every term that is actually contained in it.

To check if a term is contained in the order ideal it suffices to check if it divides any of the corner terms.

During the process of creation or enlargement of an order ideal the corner term set will be enlarged and may contain more terms that are necessary to describe the order ideal. The member function "myTidyOrderIdeal" is used to determine which terms safely can be removed from the corner term set.

Computation of the border of an order ideal

Each corner term t_c of the order ideal is expanded by multiplying it with an indeterminant x_i. Let t be the term x_i*t_c. Then the function "myBorderWalk" is used to compute the border terms that can be extracted from t recursively (and inefficiently) by computing factors of t that have the same x_i exponent. If a factor of t lies in the order ideal, no more factors of that factor are computed to reduce computation time at least a bit.

Bugs, Shortcomings and other ideas

At the moment every call of "OrderIdeal::myBorder(border)" leads to a full computation of the border of the order ideal. Maybe some kind of mechanism should be included that checks if the order ideal has been changed since the last computation of its border and only triggers a border computation if necessary.

Also the computation of the border of an order ideal should be implemented in a more efficient way in the future.