The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

NAME

MVPoly - Language Commands

SYNOPSIS

MVPoly is an implementation of a simple mult-variate symbolic math package oriented towards polynomial and monomial operations.

DESCRIPTION

Provided with the MVPoly library is a simple interpreter interfacing to the library. Although the language is simple, it still provides a great deal of functionality. The commands available are as follows:

Next to each variable sensitive command is the symbol [X], where X is the number of variables the command is valid for. For single variable commands, X=1, and for an arbitrary number of variablees, X=N.

Two commands, monOrder and varOrder MUST always preceed any polynomial declarations or operations simply because the define the 'environment' in which the polynomials and monomials live.

monOrder(ORDER) REQUIRED

Fix a monomial ordering. Any existing polynomials will be converted to the new ordering and any new polynomials will use this ordering. The available orderings are:

        tdeg            Total Degree (single variable case only) 
        lex             Lexicographic ordering
        grlex           Graded Lexicographic ordering.
        grevlex         Graded Reverse Lexicographic ordering.

        For a detailed description of these orderings, refer to REFERENCES.

IMPORTANT: A monomial ordering MUST fixed before any polynomials are created. This way, each polynomial knows how to construct itself given the existing variables and variable ordering.

varOrder(v1,...,vn) REQUIRED

Fix a variable ordering.

        For instance, suppose we wanted to have the relationship, x > y > z, we would declare this variable ordering via:

        varOrder(x,y,z)

        Consequently, when given z, x^3, y^2, for instance, the monomial would be constructed as:

         x^3y^2z

IMPORTANT: If mult-variate polynomials are used, a variable order must be fixed before any operations are performed. This way, each monomial knows how to construct itself.

VAR = FUNCTION(...)
VAR = EXPRESSION

These two statement forms provide the core of variable assignments. Variable names are case sensitive and there can be no white space in the name (not unlike most languages). For example:

        v1 = x^3+3x-7;

        and
        
        v2 = gcd(f,g);
        v3 = mult(v2,m);  

value(VAR)

Return the value of VAR. This function is used primary to avoid confusion in the following case:

        monOrder(tdeg);
        f = x;

verbose

By default, the polynomials display themselves as simply as possible. For instance:

        +1x^1y^3z^0 

        is displayed as

        xy

Toggling the verbose state will cause the polynomial to display itself in its complete form. This format is useful if the user wants to see completely the state of every component of the polynomial.

NOTE: the syntax for verbose is

        verbose()

Future plans include enhancements to this statement to create various verbose configurations for differnt modes of debugging and displays.

state

Display all the variables and orderings currently defined.

print(VARIABLE)
print(STRING)

Display the contents of the respective argument.

gbasis(p1,p2,...,pn) [N]

Computed the Groebner Basis of ideal generated by polynomials p1,p2,...,pn using the simple Buchberger's algorithm. Since the simple algorithm is being used, the basis is likely to be neither unique nor reduced unique for the given polynomials.

spoly(p1,p2) [N]

Determine the S-Polynomial for polynomials p1 and p2.

monLCM(p1,p2) [N]

Determine the monomial Least Common Multiple for polynomials p1 and p2. The function uses the leading term of each p1 and p2 in its operation.

reduce(p)

Attempt to reduce polynomial p and make it look like 'something' Maple might give as a result. This is done by using the two strategies:

1) Reduce each coefficient to as close to 1 as possible.

2) If the leading term has a negative coefficient, then multiply each coefficient by -1.

gcd(p1,p2) [1]

Calculate the Greatest Common Divisor for polynomials p1 and p2.

quo(p1,p2) [1]

Determine the quotient of p1 / p2.

rem(p1,p2) [N]

Determine the remainder of p1 / p2.

divide(p1,p2,...,pn) [N]

Perform polynomial division: p1 / p2,...,pn. The result is a polynomial list: [q1,...,qt,r], where t = n - 1. At this time there is no way to access the elements of the list directly other than via printing the assigned variable. For example,

f = divide(p1,p2,p3,p4,p5); print(f);

is the only way to see the contents of f.

normalf(p1,p2,...,pn) [N]

Determine the Normal Form of p1,p2,...,pn. That is, do the polynomial division and return the remainder.

mult(p1,p2) [N]
subtract(p1,p2) [N]
add(p1,p2) [N]

Algebraic operations: *,-,+ respectively.

EXAMPLES

Example 1

An example illustrating single variable polynomials and calculating the greatest common divisor of two polynomials.

        monOrder(tdeg);
        varOrder(x);
        f = x^3-3x+2;
        g = x^6-1;
        gcd = gcd(f,g);
        print(f);
        print(g);
        print(gcd);
        reduce(gcd);
        print(gcd);
Example 2

This example illustrates the effect of the various monomial orderings on a multi-variate polynomial.

        monOrder(lex);
        varOrder(x,y,z);
        f = -xyz - x^2yz + x^3yz - xy^2 + xy^3z - xyz^2 + xyz^3;
        print("Monomial Ordering: LEX");
        print(f);
        monOrder(grlex);
        print("Monomial Ordering: GRLEX");
        print(f);
        monOrder(grevlex);
        print("Monomial Ordering: GREVLEX");
        print(f);
Example 3

Various simple algebraic operations on two single variable polynomials.

        monOrder(grlex);
        varOrder(x,y,z);
        f = x^6-1;
        g = x^4-1;
        q = quo(f,g);
        r = rem(f,g);
        print(f);
        print(g);
        print(q);
        print(r);
        c = mult(q,g);
        s = add(c,r);
        print(s);
Example 4

The least common multiple and S-Polynomials are calcluated here from and f and g. The operation monLCM uses the leading terms of f and g in its operation.

        monOrder(grlex);
        varOrder(x,y);
        f = x^3y^2-x^2y^3+x;
        g = 3x^4y+y^2;
        print(f);
        print(g);
        h = monLCM(f,g);
        print(h);
        s = spoly(f,g);
        print(s);
Example 5

Calculating the Groebner Basis is straight forward as illustrated here. The two polynomials, s and h, are calculated as a validation the basis is correct. That is, they have nothing to do with the operation of gbasis, but are useful in illustrating the steps of calculating a Groebner Basis.

        monOrder(grlex);
        varOrder(x,y);
        f = x^3-2xy; 
        g = x^2y-2y^2+x; 
        print(f);
        print(g);
        h = monLCM(f,g);
        print(h);
        s = spoly(f,g);
        print(s);
        gb = gbasis(f,g);
        print(gb);

REFERENCES

The algorithms implemented in this library were soley based on the work presented in the book:

        "Ideals, Varieties, and Algorithms"
        An Introduction to Computational Algebraic Geometry and Commutative Algebra
        Second Edition
        David Cox, John Little, Donal O'Shea
        Springer-Verlag 1997
        ISBN 0-387-94680-2

AUTHOR

        Brian Guarraci

        email:  bguarrac@hotmail.com