Non-commutative multiplication

[Ilya Zakharevich <ilya@Math.Berkeley.EDU>]

It should not be hard to update gmul() to support non-commuting
variables in the simplest cases, when PBW theorem holds, and the
"currently supported" monomials still form a basis.  Recall that PARI
uses an "almost sparse" representation; for the purpose of this
discussion one can think of this representation as of a linear
combination of monomials. In turn, a monomial is just a collection of
degrees of the variables; [so x*y*z associates 1 to x, y, and z, and 0
to the rest of variables].

In what follows, assume that the form of the PARI output
(lower-ordinal variables on the right) is what the monomial means in
the non-commutative case.  Also assume that the variables "were
introduced" in the opposite lexicographical order, so PARI outputs
a*b*c as abc.

Two cases of PBW immediately come to mind, when n*m is const*m*n +
"lower degrees terms".  E.g., the rest may be linear, or have
variables "before" n and m.

As I said, one can easily implement this in PARI.  The only "problem"
is that gmul() is recursive, and often calls itself after swapping the
arguments (apparently, swapping is done to simplify the logic).  There
may be two ways to correct the situation:

 a) disable swapping in gmul() [moderate, but still significant amount
    of work];

 b) add an extra argument [long is_swapped] to gmul() (and related
    functions), and make gmul() into a macro which makes is_swapped=0.

The solution "a" may slow down things due to the code bloat hurting
the code cache; the solution "b" will slow down things since most of
the time the argument is going to be ignored.

My impressions is that the cost of "b" should be negligible
nevertheless.  Any thoughts?

Yours,
Ilya