[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.1 Distributed polynomial

A distributed polynomial is a polynomial with a special internal representation different from the ordinary one.

An ordinary polynomial (having type 2) is internally represented in a format, called recursive representation. In fact, it is represented as an uni-variate polynomial with respect to a fixed variable, called main variable of that polynomial, where the other variables appear in the coefficients which may again polynomials in such variables other than the previous main variable. A polynomial in the coefficients is again represented as an uni-variate polynomial in a certain fixed variable, the main variable. Thus, by this recursive structure of polynomial representation, it is called the ‘recursive representation.’

(x+y+z)^2 = 1 x^2 + (2 y + (2 z)) x + ((2 z) y + (1 z^2 ))

On the other hand, we call a representation the distributed representation of a polynomial, if a polynomial is represented, according to its original meaning, as a sum of monomials, where a monomial is the product of power product of variables and a coefficient. We call a polynomial, represented in such an internal format, a distributed polynomial. (This naming may sounds something strange.)

(x+y+z)^2 = 1 x^2 + 2 xy + 2 xz + 1 y^2 + 2 yz +1 z^2$

For computation of Groebner basis, efficient operation is expected if polynomials are represented in a distributed representation, because major operations for Groebner basis are performed with respect to monomials. From this view point, we provide the object type distributed polynomial with its object identification number 9, and objects having such a type are available by Asir language.

Here, we provide several definitions for the later description.

term

The power product of variables, i.e., a monomial with coefficient 1. In an Asir session, it is displayed in the form like

<<0,1,2,3,4>>

and also can be input in such a form. This example shows a term in 5 variables. If we assume the 5 variables as a, b, c, d, and e, the term represents b*c^2*d^3*e^4 in the ordinary expression.

term order

Terms are ordered according to a total order with the following properties.

  1. For all t t > 1.
  2. For all t, s, u t > s implies tu > su.

Such a total order is called a term ordering. A term ordering is specified by a variable ordering (a list of variables) and a type of term ordering (an integer, a list or a matrix).

monomial

The product of a term and a coefficient. In an Asir session, it is displayed in the form like

2*<<0,1,2,3,4>>

and also can be input in such a form.

head term
head monomial
head coefficient

Monomials in a distributed polynomial is sorted by a total order. In such representation, we call the monomial that is maximum with respect to the order the head monomial, and its term and coefficient the head term and the head coefficient respectively.

ChangeLog


[ << ] [ < ] [ Up ] [ > ] [ >> ]

This document was generated on December 14, 2024 using texi2html 5.0.