CoCoA » CoCoALib

Sounds like a generalisation of RingWeyl.
... Werner, are you willing to test it out? ;-)
I was thinking of porting it to cocoa5...

• x[i]*x[j] = q*x[j]*x[i] + tail where tail is smaller than x[j]*x[i] in the term ordering
• x[i]*k = phi(k)*x[i] + tail where phi(k) is another non-zero coeff, and tail depends on k and x[i]

The only change is that I inserted a non-zero coefficient q before the first term on the RHS of the first formula.

An example of the second formula is when x[i] is a derivation and the coefficients are a field of rational functions.

NOTE (20150611) Werner pointed out that in the fully general case q depends on i and j; similarly phi(k) may also depend on i.

For starters Ore algebra as a simple case of polynomial algebras of solvable type should be enough. Their main advantage is that here you should get a closed formula for the multiplication of two monomials (= coefficient * power product). For general solvable algebra even for this computation you can describe only a recursive process.

Werner pointed out that a simplistic implementation is likely to be terribly slow (though perhaps "obviously correct"). In several cases of specific interest there are useful shortcuts.

There is a book by Levandovskyy which contains some brief notes about implementation. In particular it pointed out that it can be worth implementing the product of a power of an indet by a monomial: namely, x[i]^n * (c*pp) where c is in the coeff ring, and pp is a power product. The result is a polynomial.

Werner also pointed out that it is customary in these (non-comm!) algebras to reduce PPs to a "normal form" where the indices of the indets in the PP are in increasing order. For instance, the product of x[2] by x[1]*x[3] gives x[2]*x[1]*x[3] but this must then be normalized to c*x[1]*x[2]*x[3] + tail

We have already done most of these considerations for RingWeyl (except for the coefficient rule).
.. and we also had GBasis working fine.
So, if we just know the rules, we can make a copy of RingWeyl and modify just the multiplication.
In this experimental phase I would not try (yet) to make a general implementation.

Going to a seminar here about G-bases in PBW algebras :-)

NOTE the seminar was OK. The student pointed out that (thanks to Hilbert Functions) a homogeneous GB in a homogeneous PBW algebra can be computed using modular techniques (and probabilistic rational recovery). He did not have a convincing "reliable" way of handling non-homogeneous cases -- of course, the modular technique almost surely works correctly.

NOTE2 an algebra is homogeneous if the tails are the same degree as the head terms of the LHS/RHS.

As I am sitting in a delayed train with too much time at hand, some further comments:

1.) The "book" by Levandovskyy is his Ph.D. thesis. I am not sure whether it was published with some publisher. Probably the best way to obtain it would be to ask Viktor for an electronic copy. There also is a book by Bueso and some coauthors on "Algorithmic methods in non-commutative algebra" which discusses extensively Gröbner bases for this type of algebras. Another very good source is the Ph.D. thesis of Kredel (a student of Weispfenning) which is cited in my book - with probably some further references I now do not think of.

2.) Ore algebra appear in many places. Important instances are rings of linear differential/difference/shift operators. A brief introduction appeared in my book. It should also contain a reference to a nice survey article by Bronstein and Petkovsek. Daniel Robertz and some collaborators developed a Maple package for Ore algebra which contains many advanced operations of interest for systems theory.

3.) It is not only "usual" or "costumary" to write the products in this normal form; this is the defining property of a PBW algebra. The Poincare-Birkhoff-Witt (PBW) theorem asserts for universal enveloping algebras of Lie algebras that the usual terms (i.e. this normal form) provides a vector space basis for the algebras. This is then taken as the defining property of a much larger class of algebras. The main advantage here is that one can use exactly the same data structures as for commutative polynomials.

4.) I looked for a closed form expression for the product of two monomials (=coefficient*power product) in a general Ore algebra. You can indeed write one down (but only in LaTeX and not on Redmine ;-), although it is less nice than in the special case of linear differential operators where it is essentially a variant of the binomial formula. If the monomial on the left has order/degree n, then you must sum over all words of length n over an alphabet with two letters. This should not be too hard to implement. In general algebras of solvable type, I doubt that a closed formula exists. For them you must probably use a recursion over the basic rewrite rules.

5.) The only issue for all polynomial algebras of solvable type is the implementation of the multiplication. For all other things - up to complete Gröbner bases computations - you should be able to use your commutative code (however, it is unclear whether heuristics which are good in the commutative case remain good - but this is of course only an efficiency issue). Computations will typically be (much) more expensive. Not only because each multiplication is more expensive, but also because normal form computations tend to produce polynomials with larger support. That's again an effect of the multiplication: the product of two monomials is no longer a monomial, but generally a polynomial with potentially many terms.

6.) There are many names for closely related types of polynomial algebra and even the same name may be used with different meanings by different peoples. Some common names are: polynomial algebras of solvable type, PBW algebras, G-algebra, weakly non-commutative algebras. My definition of a polynomial algebra of solvable type (which is probably the most general one around) is with respect to a fixed term order and requires essentially a compatibility condition between the product and the term order which ensures that leading terms show the desired behaviour under multiplication. In my definition I allow both that the variables obey non-trivial commutation rules and that the variables operate on the coefficients. As far as I can see, this latter possibility is excluded in the definition of a G-algebra which underlies Levandovskyy's Plural package. In my opinion, this entails that Ore algebra cannot be handled by Plural, as Ore algebras are operator algebras where the variables operate on the coefficients. But may be Viktor has found a trick to circumvent this restriction (if yes, then probably only at the expense of enlarging the number of variables which is usually not a good idea, if you have Gröbner bases computations in mind).

If I understood well (I asked Viktor Levandovskyy ;-) the definition in #2 is actually of G-Algebras, and Ore-Algebras are more complicated but can be computed by G-Algebras.
Is that correct? (I need to understand the definition well before starting to implement ;-)

No. In my understanding, John correctly described in #2 also Ore algebras (taking into account the note he later added). In G-algebras, people usually do not allow that the variables operate on the coefficients, i.e. the second rule in #2 simply becomes x[i]*k = k*x[i] and all the "action" is the first rule. By contrast, in an Ore algebra the variables commute - i.e. the first rule in #2 is now trivial: x[i]*x[j]=x[j]*x[i] - but the "variables" are actually operators doing something non-trivial with the coefficients. Thus both G-algebras and Ore algebras are just complementary particular cases of the more general structure of a polynomial algebra of solvable type that John described. Victor (and many other people) have concentrated on the G-algebra case and there should indeed be a trick how you can simulate Ore algebras with it (Victor told me this also once, but I forgot the details). Some people in Aachen including Daniel Robertz (now Plymouth) wrote a Maple package for Ore algebras. Heinz Kredel, a former student of Weispfenning, implemented the general case. His Ph.D. thesis "Solvable Polynomial Rings" appeared in Shaker Verlag (a German publisher specialised on theses) - may be somewhere in Genoa a copy is available. It contains a chapter on implementation aspects. Unfortunately, it seems that even on these illegal Russian sites no electronic version of it is available ;-)

At least for the moment, I would be very happy to have just Ore algebras available, as I am mainly interested in the case of linear differential or difference operators. In fact, it appears to me that Ore algebras should be simpler to implement than G-algebras, as in an Ore algebra I can write down a closed formula for the multiplication of two terms (it is not nice, but should be comparatively straightforward to implement). If the variables obey non-trivial commutation rules, then you must probably interpret these as a rewriting system and each multiplication corresponds to an application of this rewriting system. May be Victor has some good ideas about how this can be implemented efficiently, but to me it sounds more involved than the Ore algebra case and I also think that computations become much slower when you have such non-trivial commutation rules. In a recent paper, Kredel mentions that in his new Java based implementation already computed products of terms are stored in a table. That is probably a good strategy, but of course requires more work in the implementation.