Ilya Zakharevich on Tue, 8 Apr 2003 16:02:54 -0700 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Non-commutative multiplication |
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