multivariate polynomials and printing to output

[Sherm Ostrowsky]

From time to time, users have complained (and I have complained, too) about the fact that MathPiper sometimes outputs multiple-term expressions in an order determined by rules not immediately apparent. 

Although a bit inconvenient at times, this causes no real harm, I believe.

But when we come to working with multivariate polynomials, it may be especially important to be able to output the terms to the screen (or other device) in a specific order.  And I'm pretty sure MathPiper will not cooperate.

I doubt that this will ever interfere with the correct operation of algorithmic processes, since these are usually written using an internal structure which IS completely under the programmer's control.  But when it comes time to display the outputs, the results may be "correct" mathematically, yet still leave a lot to be desired from a pedagogical point-of-view.

Let me be more specific.  When working with multivariate polynomials in the context, say, of Groebner Bases calculations, it is very significant that the terms of the polynomial be ordered in certain ways, in order that the algorithms being used will (a) be efficient, and (b) produce results which are easy to use in further computations.  It all boils down to this:  when you divide one polynomial by another, it is easy to see that for univariates (as for integers!) the divisor and dividend must be ordered from highest terms to lowest, and furthermore, there is no question of what you mean by "higher" and "lower", here.  But for multivariates, not only is there no CLEAR consensus as to whether, for example, x^2yz^3  is  bigger or smaller than x^4z, but in fact for some purposes you want to do it one way, and for other purposes you want to do it another way.

Various "term ordering" methods have been studied, and given names such as "LEX", "GRLEX", "GREVLEX", etc.  It turns out to be the case, for example, that Groebner Basis calculations made using the "LEX" ordering are much more useful for "solving" systems of nonlinear multivariate polynomial equations than are those made using other term ordering methods.  But unfortunately, the calculation of Groebner Bases this way usually takes a lot longer, and may result in more unwieldy results, than other methods.  For efficiency of calculation and compactness of results, the GREVLEX method is usually preferred over all others, but these results may not be immediately applicable to "solving" systems, without considerably more work.  And so on.

Now let's see what happens with MathPiper.  I have been working on implementing these algorithms.  I am still a long way from having a useable product.  But I can already see the form in which my answers will be generated and stated.  A multivariate polynomial in, say, x,y,z, is representable in a "sparse" notation such as the following.  Let the polynomial be given as  2*x*y^2*z - 3*z^2 + 4*x^3 - 5*x^2*z^2.  It has four monomials, which in terms of their exponents on x,y,z in that order, are {1,2,1}, {0,0,2}, {3,0,0}, and {2,0,2}.  The respective coefficients are {2,-3,4,-5}, here.  The four terms are thus represented as the list-of-lists {{2,1,2,1},{-3,0,0,2},{4,3,0,0},{-5,2,0,2}}.  This kind of notation is clear and unambiguous. 

Working with this notation, the polynomial in LEX ordering looks like this: {{4,3,0,0},{-5,2,0,2},{2,1,2,1},{-3,0,0,2}}.
In GRLEX it looks like this: {{-5,2,0,2},{2,1,2,1},{4,3,0,0},{-3,0,0,2}}.
In GREVLEX it looks like this:  {{2,1,2,1},{-5,2,0,2},{4,3,0,0},{-3,0,0,2}}.

Rewriting these results in the usual form of a polynomial, we would get:
LEX:           4*x^3-5*x^2*z^2+2*x*y^2*z-3*z^2.
GRLEX:      -5*x^2*z^2+2*x*y^2*z+4*x^3-3*z^2.
GREVLEX:  2*x*y^2*z-5*x^2*z^2+4*x^3-3*z^2.

It would be useful to be able to display them in exactly the form shown. 
Now let's enter them into MathPiper, and see what comes out:

In> 4*x^3-5*x^2*z^2+2*x*y^2*z-3*z^2
Result: 4*x^3-5*x^2*z^2+2*x*y^2*z-3*z^2

In> -5*x^2*z^2+2*x*y^2*z+4*x^3-3*z^2.
Result: 2*x*y^2*z-5*x^2*z^2+4*x^3-3*z^2.

In> 2*x*y^2*z-5*x^2*z^2+4*x^3-3*z^2
Result: 2*x*y^2*z-5*x^2*z^2+4*x^3-3*z^2

This is not really "bad", but we have no control over it, and it does not show what we want to exhibit.

Comments?

Sherm

[Ted Kosan]

Sherm wrote:

> It would be useful to be able to display them in exactly the form shown.
> Now let's enter them into MathPiper, and see what comes out:
>
> In> 4*x^3-5*x^2*z^2+2*x*y^2*z-3*z^2
> Result: 4*x^3-5*x^2*z^2+2*x*y^2*z-3*z^2
>
> In> -5*x^2*z^2+2*x*y^2*z+4*x^3-3*z^2.
> Result: 2*x*y^2*z-5*x^2*z^2+4*x^3-3*z^2.
>
> In> 2*x*y^2*z-5*x^2*z^2+4*x^3-3*z^2
> Result: 2*x*y^2*z-5*x^2*z^2+4*x^3-3*z^2
>
> This is not really "bad", but we have no control over it, and it does not
> show what we want to exhibit.
>
> Comments?

Tracing one of these expressions shows how it is being transformed by the rules:

%mathpiper
TraceOn();
-5*x^2*z^2+2*x*y^2*z+4*x^3-3*z^2.;
TraceOff();
%/mathpiper

A trace with less output can be obtained by using TraceSome:

%mathpiper
TraceSome("+,-")-5*x^2*z^2+2*x*y^2*z+4*x^3-3*z^2.;
%/mathpiper

The trace output seems to indicate that there is no formatting-related
transformations being done on the result expression.

Reduce has an internal format for polynomials and an output format for
polynomials which can be controlled with switches. The following
paragraph from page 149 of "Reduce: Software for Algebraic
Computation" by Rayna describes what happens when output formatting of
polynomials is turned off:

"The formatting, factoring, re-ordering, and so on which have been
described in several of the preceding sections take considerable time.
If the Reduce user doesn't care about any of these features, and
wants to speed up printing, he can use the command OFF PRI$ to
instruct the output package to display expressions in a form closely
reflecting the form in which they are stored internally. The output is
still in familiar algebraic form, but the ORDERING AND GROUPING OF
TERMS MAY SEEM ERATIC." (the emphasis is mine).

Since MathPiper does not make heavy use of switches, my thought is for
you to create some xxxForm functions (perhaps called LexForm,
GrlexForm, and GrevlexForm?) which will return expressions which are
formatted the way you would like them to be.

Ted

[Sherm Ostrowsky]

Interesting.  That seems like it might do the job.  Thanks.

Sherm

[Sherm Ostrowsky]

I have done this, and it works.  The output is a String, so no external formatting can get in the way.

Sherm

[Ted Kosan]

Sherm wrote:

> I have done this, and it works.  The output is a String, so no external
> formatting can get in the way.

That's great!

I am looking forward to when you commit these new functions to the
repository so that I can play with them.

Ted