polyd http://www.openmath.org/cd/polyd.ocd 2003-04-01 1999-07-07 experimental 2 0 This CD contains operators to deal with polynomials and more precisely Distributed Multivariate Polynomials. Original OpenMath v1.1 Poly 1997 Update to Current Format 1999-07-07 DPC Move the names of rings to setname.ocd 1999-11-09 JHD Delete those items moved to the new poly.ocd 1999-11-14 JHD This is our attempt at defining a first Content Dictionary to deal with polynomials. There are many possible choices for a polynomial CD, and several questions to answer. The reader may feel that this content dictionary is quite different in spirit from the "Basic" one. Although it basically defines a set of concepts related to polynomials (such as degree, factorization, resultant...), there are two new points here: - a certain emphasis on representation issues (including structural constraints on some OM objects), - an attempt to specify some "computational behaviour" of an OM application that handles (part of) this CD. As some people may disagree with some of our choices, we will try to justify them in this rather long foreword. 1. Representation issues One of the interest of OM is certainly to enable the use of specialized servers. It is important to promote the writing of OM-compliant servers by placing as few constraints as possible on the programmers of these packages. This CD has been designed with the idea that it could be simple to use for a server dealing only with polynomial computations. Hence we have used a particular representation for polynomials (distributed with dense monomials). This representation is rather abstract in the sense that it does not introduce names for variables. It explicitly contains the polynomial ring a polynomial belongs to as the set of the coefficients and the number of variables. It seems (from our experience) that this information is necessary for most specialized servers. Expressing constraints on the structure of OM objects made from the symbols in this CD is not always easy. One of the main reason is that a symbol such as "gcd" is meant to denote the GCD of a set of polynomials, no matter how the polynomials are represented. Such a function should thus accept both "symbolic" arguments (a list of symbolic object meant to be polynomials) and the polynomials in the specific representation defined in this CD. Of course, another solution will be to have one "gcd" for one (or several) particular representation and another "gcd" to express the general notion of polynomial "gcd". We though that the solution we chose was more in the spirit of "Basic" and the discussions of the last OpenMath meeting. A question which is not entirely answered is whether or not it is interesting to have "symbolic" objects inside some constructors (such as a power which is not an OM integer in "Monom" or a symbolic "PolyRingD" (a variable) as an argument of "DMP"). We explicitly forbid that in the first version of this CD. Note that we did not try to express the constraints with signatures in this version because we did not find a really satisfactory solution. 2. Specifying some "computational behaviour" Of course it would be of no use to exactly specify the behaviour of any OM application that receives an OM object. There are (at least) two reasons for that: - an OM object is intended to represent a mathematical object and thus the same OM object could be sent to a typesetter as well as to a symbolic computation system, - even when dealing with programs that compute, exact specifications could be impossible or too much constraining for a given system. On the other hand, we believe that one of the goal of OM is certainly that a program needing to factorize an integer could transparently use Maple, Axiom or Pari to do the job. This is of course possible only if all severs that "implement" (in the sense of really performing) the mathematical notion of integer factorization answer in a similar way. In other words, we should not hesitate to specify what a particulary useful class of OM applications (the "computing" ones) should return (the form of the result) everytime compliance to this specification is simple enough because it is obviously very useful. We have tried to express this idea in this CD through some comments and the use of symbols such as "factored" or "groebner_basis" that describe the required results of some functions. The general "compliance" rule can be stated as: an OM application that understands this CD and implements some of the polynomials operation described is required to implement them using the constructors defined in this CD, as indicated in the comments associated with the operations. This means that if the OM version of a computer algebra system claims to implement polynomial factorization, another application can send him an OM object as described in the "factor" comment (the symbol "factor" applied to one argument, a DMP) and the result will be return as defined : a "factored" symbol whose arguments are described in the corresponding entry of the poly CD. Definition of data-structure constructors The polynomial x^2*y^6 + 3*y^5 can be encoded as DMP(poly_ring_d(Z, 2), SDMP(term(1, 2, 6), term(3, 0, 5))) The polynomial 2*y^3*z^5 + x + 1 can be DMP(poly_ring_d(Q, 3), SDMP(term(2, 0, 3, 5), term(1, 1, 0, 0), term(1, 0, 0, 0))) Note that these are not real encodings but a "term-like" encoding (whose understanding should be trivial) meant for the human readers of this dictionary. Of course, actual encodings can be more compact... DMP The constructor of DMPs. The first argument is the polynomial ring containing the polynomial and the second is a "SDMP". Should be of the form DMP(PolyRingD(...), SDMP(...)) DMPL The constructor for lists of multivariate polynomial members of the same polynomial ring. The first argument is a polynomial ring and the rest are "SDMP"s. DMPL can be attributed with the "ordering" symbol to indicate a particular ordering for monomials of all its polynomials. Should be of the form DMPL(PolyRingD(...), SDMP(...)+) SDMP The constructor for multivariate polynomials without any indication of variables or domain for the coefficients. Its arguments are just "monomial"s. No monomials should differ only by the coefficient (i.e it is not permitted to have both "2*x*y" and "x*y" as monomials in a SDMP). SDMP can be attributed with the "ordering" symbol to indicate a particular ordering of its monomials. This attribute shall not be set if the SDMP is part of DMPL that has this attribute set. term The constructor of monomials. Valid applications are of the form Term(coeff, exp1, exp2, ... expn) which represents the monomial coeff * var1^exp1*...varn^expn where n is the number of variables, expi are non-negative integers. Polynomial rings constructors poly_ring_d The constructor of polynomial ring. The first argument is a ring (the ring of the coefficients), the second is the number of variables as an integer. Definitions related to orderings ordering Used as an attribute to indicate an ordering of the monomials in a polynomial or list of polynomials. The value of this attribute should be one of the constructors specifying ordering. The following orders on monomials have their standards definitions, see, for example, "Ideals, Varieties and Algorithms", D. Cox, J.B. Little and D. O'Shea, Springer Verlag. lexicographic The lexicographic ordering of monomials. reverse_lexicographic The reverse lexicographic ordering of monomials graded_lexicographic Total degree order, graded with the lexicographic ordering. graded_reverse_lexicographic Total degree order, graded with the reverse lexicographic ordering. elimination This is an ordering, which is partially in terms of one ordering, and partially in terms of another. First argument is a number of variables. Second is ordering to apply on the first so many variables. Third is an ordering on the rest, to be used to break ties. 1 We need a few more orderings... Definition of some other constructors groebner_basis The constructor for a Groebner basis (reduced, minimal). The first argument is an ordering, the second is the Groebner Basis itself (with respect to the ordering) that should be represented as a DMPL. Definition of operations plus The sum. The argument is a DMPL. The sum lies within the same "PolyRingD" i.e. a program implementing this operation should return a DMP with the same "poly_ring_d". times The product. The argument is a DMPL. The product lies within the same "PolyRingD" i.e. a program implementing this operation should return a DMP with the same "poly_ring_d". power The power. First argument is a DMP, second argument is the integer power. The power lies within the same "PolyRingD" i.e. a program implementing this operation should return a DMP with the same "poly_ring_d". groebner The groebner basis (reduced, minimal) of a set of polynomials, with respect to a given ordering. First argument is an ordering, the second is a list of polynomials. A program that can compute the basis is required to return a "groebner_basis" object. reduce The reduction of a polynomial with respect to a Groebner basis. First argument is a DMP, the second argument is a groebner_basis object. i.e. a program implementing this operation should return a DMP which represents the polynomial reduced with respect to the Groebner basis.