login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit

There is are some domains in Axiom for doing computations with non-commuting variables developed by Michel Petitot. You can find some examples in the Axiom book under the title XPolynomial? but unfortunately the explanations are a little terse. You can also check for documentation in the source files:

## Missing div

The version of OrderedFreeMonoid? in the Axiom library is missing the implementation of the function "div" which provides left and right quotients. Since OrderedFreeMonoid? extends 'FreeMonoid?':http://wiki.axiom-developer.org/axiom--test--1/src/algebra/FreeSpad which in turn includes such a function named divide we should just rename div to divide.

We need left and right quotients to implement the substitution rules in the example below.

)abbrev domain OFMONOID OrderedFreeMonoid
++ Author: Michel Petitot petitot@lifl.fr
++ Date Created: 91
++ Date Last Updated: 7 Juillet 92
++ Fix History: compilation v 2.1 le 13 dec 98
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++    The free monoid on a set \spad{S} is the monoid of finite products of
++ the form \spad{reduce(*,[si ** ni])} where the si's are in S, and the ni's
++ are non-negative integers. The multiplication is not commutative.
++ holds if either \spad{length(x) < length(y)} holds or if these lengths
++ are equal and if \spad{x} is smaller than \spad{y} w.r.t. the lexicographical
++ This domain inherits implementation from \spadtype{FreeMonoid}.
++ Author: Michel Petitot (petitot@lifl.fr)
OrderedFreeMonoid(S: OrderedSet): OFMcategory == OFMdefinition where
NNI ==> NonNegativeInteger
REC ==> Record(gen:S, exp:NNI)
OFMcategory == Join(OrderedMonoid, RetractableTo S) with
"*":    (S, %) -> %
"*":    (%, S) -> %
"**":   (S, NNI) -> %
first: % -> S
rest:  % -> %
mirror: % -> %
lexico: (%,%) -> Boolean
++ w.r.t. the pure lexicographical ordering induced by \spad{S}.
hclf:   (%, %) -> %
++ \spad{hclf(x, y)} returns the highest common left factor
++ that is the largest \spad{d} such that \spad{x = d a} and \spad{y = d b}.
hcrf:   (%, %) -> %
++ \spad{hcrf(x, y)} returns the highest common right
++ that is the largest \spad{d} such that \spad{x = a d} and \spad{y = b d}.
lquo:   (%, %) -> Union(%, "failed")
++ "failed" if \spad{x} is not of the form \spad{y * q}.
rquo:   (%, %) -> Union(%, "failed")
++ "failed" if \spad{x} is not of the form \spad{q * y}.
lquo:   (%, S) -> Union(%, "failed")
rquo:   (%, S) -> Union(%, "failed")
++ \spad{rquo(x, s)} returns the exact right quotient
divide:   (%, %) -> Union(ok:Record(lm: %, rm: %), bad:"failed")
++ \spad{divide(x, y)} returns the left and right exact quotients of
++ "failed" is returned iff \spad{x} is not of the form \spad{l * y * r}.
overlap: (%, %) -> Record(lm: %, mm: %, rm: %)
++ \spad{x = l * m} and \spad{y = m * r} hold and such that
++ that is \spad{overlap(l, r) = [l, 1, r]}.
size:   % -> NNI
nthExpon:  (%, Integer) -> NNI
++ \spad{nthExpon(x, n)} returns the exponent of the
nthFactor: (%, Integer) -> S
factors: % -> List REC
length: % -> NNI
varList: % -> List S
Rep := ListMonoidOps(S, NNI, 1)
-- definitions
lquo(w:%, l:S) ==
x: List REC := listOfMonoms(w)$Rep null x => "failed" fx: REC := first x fx.gen ~= l => "failed" fx.exp = 1 => makeMulti rest(x) makeMulti [[fx.gen, (fx.exp - 1)::NNI ]$REC, :rest x]
rquo(w:%, l:S) ==
u:% := reverse w
(r := lquo (u,l)) case "failed" => "failed"
reverse!(r::%)
length x == reduce("+" ,[f.exp for f in listOfMonoms x], 0)
varList x ==
le: List S := [t.gen for t in listOfMonoms x]
sort!(removeDuplicates(le))
first w ==
x: List REC := listOfMonoms w
null x => error "empty word !!!"
x.first.gen
rest w ==
x: List REC := listOfMonoms w
null x => error "empty word !!!"
fx: REC := first x
fx.exp = 1 => makeMulti rest x
makeMulti [[fx.gen , (fx.exp - 1)::NNI ]$REC , :rest x] lexico(a,b) == -- ordre lexicographique la := listOfMonoms a lb := listOfMonoms b while (not null la) and (not null lb) repeat la.first.gen > lb.first.gen => return false la.first.gen < lb.first.gen => return true if la.first.exp = lb.first.exp then la:=rest la lb:=rest lb else if la.first.exp > lb.first.exp then la:=concat([la.first.gen, (la.first.exp - lb.first.exp)::NNI], rest lb) lb:=rest lb else lb:=concat([lb.first.gen, (lb.first.exp-la.first.exp)::NNI], rest la) la:=rest la empty? la and not empty? lb a < b == -- ordre lexicographique par longueur la:NNI := length a; lb:NNI := length b la = lb => lexico(a,b) la < lb mirror x == reverse(x)$Rep
   Compiling FriCAS source code from file
using old system compiler.
OFMONOID abbreviates domain OrderedFreeMonoid
------------------------------------------------------------------------
initializing NRLIB OFMONOID for OrderedFreeMonoid
compiling into NRLIB OFMONOID
compiling exported lquo : ($,S) -> Union($,failed)
Time: 0.01 SEC.
compiling exported rquo : ($,S) -> Union($,failed)
Time: 0 SEC.
compiling exported length : $-> NonNegativeInteger Time: 0.01 SEC. compiling exported varList :$ -> List S
Time: 0.01 SEC.
compiling exported first : $-> S Time: 0 SEC. compiling exported rest :$ -> $Time: 0 SEC. compiling exported lexico : ($,$) -> Boolean Time: 0.02 SEC. compiling exported < : ($,$) -> Boolean Time: 0 SEC. compiling exported mirror :$ -> $Time: 0 SEC. (time taken in buildFunctor: 0) ;;; *** |OrderedFreeMonoid| REDEFINED ;;; *** |OrderedFreeMonoid| REDEFINED Time: 0 SEC. Cumulative Statistics for Constructor OrderedFreeMonoid Time: 0.05 seconds --------------non extending category---------------------- .. OrderedFreeMonoid(#1) of cat (|Join| (|OrderedMonoid|) (|RetractableTo| |#1|) (CATEGORY |domain| (SIGNATURE * ($ |#1| $)) (SIGNATURE * ($ $|#1|)) (SIGNATURE ** ($ |#1| (|NonNegativeInteger|)))
(SIGNATURE |first| (|#1| $)) (SIGNATURE |rest| ($ $)) (SIGNATURE |mirror| ($ $)) (SIGNATURE |lexico| ((|Boolean|)$ $)) (SIGNATURE |hclf| ($ )) (SIGNATURE |hcrf| ( $)) (SIGNATURE |lquo| ((|Union|$ "failed") ))
(SIGNATURE |rquo| ((|Union| $"failed")$ $)) (SIGNATURE |lquo| ((|Union|$ "failed") $|#1|)) (SIGNATURE |rquo| ((|Union|$ "failed") $|#1|)) (SIGNATURE |divide| ((|Union| (|:| |ok| (|Record| (|:| |lm|$) (|:| |rm| $))) (|:| |bad| "failed"))$ $)) (SIGNATURE |overlap| ((|Record| (|:| |lm|$) (|:| |mm| $) (|:| |rm|$)) ))
(SIGNATURE |size| ((|NonNegativeInteger|) $)) (SIGNATURE |nthExpon| ((|NonNegativeInteger|)$ (|Integer|)))
(SIGNATURE |nthFactor| (|#1| $(|Integer|))) (SIGNATURE |factors| ((|List| (|Record| (|:| |gen| |#1|) (|:| |exp| (|NonNegativeInteger|))))$))
(SIGNATURE |length| ((|NonNegativeInteger|) $)) (SIGNATURE |varList| ((|List| |#1|)$))))    has no  ?^? : (#1,NonNegativeInteger) -> %
finalizing NRLIB OFMONOID
Processing OrderedFreeMonoid for Browser database:
--------constructor---------
--------(* (% S %))---------
--------(* (% % S))---------
--------(** (% S (NonNegativeInteger)))---------
--------(first (S %))---------
--------(rest (% %))---------
--------(mirror (% %))---------
--------(lexico ((Boolean) % %))---------
--------(hclf (% % %))---------
--------(hcrf (% % %))---------
--------(lquo ((Union % failed) % %))---------
--------(rquo ((Union % failed) % %))---------
--------(lquo ((Union % failed) % S))---------
--------(rquo ((Union % failed) % S))---------
--------(divide ((Union (: ok (Record (: lm %) (: rm %))) (: bad failed)) % %))---------
--------(overlap ((Record (: lm %) (: mm %) (: rm %)) % %))---------
--------(size ((NonNegativeInteger) %))---------
--------(nthExpon ((NonNegativeInteger) % (Integer)))---------
--------(nthFactor (S % (Integer)))---------
--------(factors ((List (Record (: gen S) (: exp (NonNegativeInteger)))) %))---------
--------(length ((NonNegativeInteger) %))---------
--------(varList ((List S) %))---------
; compiling file "/var/aw/var/LatexWiki/OFMONOID.NRLIB/OFMONOID.lsp" (written 31 JUL 2013 05:04:21 PM):
; /var/aw/var/LatexWiki/OFMONOID.NRLIB/OFMONOID.fasl written
; compilation finished in 0:00:00.050
------------------------------------------------------------------------
OrderedFreeMonoid is now explicitly exposed in frame initial
OrderedFreeMonoid will be automatically loaded when needed from
/var/aw/var/LatexWiki/OFMONOID.NRLIB/OFMONOID

Test left and right exact quotients.

fricas
m1:=(x*y*y*z)$OFMONOID(Symbol)  (1) Type: OrderedFreeMonoid?(Symbol) fricas m2:=(x*y)$OFMONOID(Symbol)
 (2)
Type: OrderedFreeMonoid?(Symbol)
fricas
lquo(m1,m2)
 (3)
Type: Union(OrderedFreeMonoid?(Symbol),...)
fricas
m3:=(y*y)$OFMONOID(Symbol)  (4) Type: OrderedFreeMonoid?(Symbol) fricas divide(m1,m2)  (5) Type: Union(ok: Record(lm: OrderedFreeMonoid?(Symbol),rm: OrderedFreeMonoid?(Symbol)),...) fricas divide(m1,m3)  (6) Type: Union(ok: Record(lm: OrderedFreeMonoid?(Symbol),rm: OrderedFreeMonoid?(Symbol)),...) fricas m4:=(y^3)$OFMONOID(Symbol)
 (7)
Type: OrderedFreeMonoid?(Symbol)
fricas
divide(m1,m4)
 (8)

This option is required to compile the functions that follow.

fricas
)set function compile on

On Tuesday, February 28, 2006 6:54 AM Fabio S. wrote:

 I would like to build the non-commutative algebra h=k[x,y] and
then I would like to make computations in h using some predefined
rules for x and y. As an example, take the three equations

x*y*x=y*x*y
x*x=a*x+b
y*y=a*y+b

where a and b are (generic, if possible) elements of k.

Then, I would like to be able to reduce polynomials in x and
y according to the previous rules. For example,

(x+y)^2 (=x^2+x*y+y*x+y^2)

should reduce to

a*(x+y)+2*b+x*y+y*x


fricas
--Generic elements of k
--OVAR = OrderedVariableList
C==>OVAR [a,b]
Type: Void
fricas
--Commutative Field: k=Q[a,b]
--Q = FRAC INT = Fration Integer
--SMP = SparseMultivariatePolynomials
K==>SMP(FRAC INT,C)
Type: Void
fricas
--Non-commutative variables
V==>OVAR [x,y]
Type: Void
fricas
--Non-commutative Algebra: h=k[x,y]
--XDPOLY XDistributedPolynomial
H==>XDPOLY(V,K)
Type: Void
fricas
--Free monoid
M==>OFMONOID V
Type: Void
fricas
--Substitution rules are applied to words from the monoid over
--the variables and return polynomials
subs(w:M):H ==
--x*y*x=y*x*y
n:=divide(w,(x::V*y::V*x::V)$M)$M
n case ok => monom(n.ok.lm,1)$H * (y::V*x::V*y::V)$H * monom(n.ok.rm,1)$H --x*x=a*x+b n:=divide(w,(x::V^2)$M)$M n case ok => monom(n.ok.lm,1)$H * (a::K*x::V+b::K)$H * monom(n.ok.rm,1)$H
--y*y=a*y+b
n:=divide(w,(y::V^2)$M)$M
n case ok => monom(n.ok.lm,1)$H * (a::K*y::V+b::K)$H * monom(n.ok.rm,1)$H --no change monom(w,1)$H
Function declaration subs : OrderedFreeMonoid(OrderedVariableList([x
,y])) -> XDistributedPolynomial(OrderedVariableList([x,y]),
SparseMultivariatePolynomial(Fraction(Integer),
OrderedVariableList([a,b]))) has been added to workspace.
Type: Void
fricas
--Apply rules to a term. Keep coefficients
newterm(x:Record(k:M,c:K)):H==x.c*subs(x.k)
Function declaration newterm : Record(k: OrderedFreeMonoid(
OrderedVariableList([x,y])),c: SparseMultivariatePolynomial(
Fraction(Integer),OrderedVariableList([a,b]))) ->
XDistributedPolynomial(OrderedVariableList([x,y]),
SparseMultivariatePolynomial(Fraction(Integer),
OrderedVariableList([a,b]))) has been added to workspace.
Type: Void
fricas
--Reconstruct polynomial, term-by-term
newpoly(t:H):H==reduce(+,map(newterm,listOfTerms(t)))
Function declaration newpoly : XDistributedPolynomial(
OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction(
Integer),OrderedVariableList([a,b]))) -> XDistributedPolynomial(
OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction(
workspace.
Type: Void

Example calculations:

fricas
p1:=(x::V+y::V)$H^2  (9) Type: XDistributedPolynomial?(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b]))) fricas newpoly(p1) fricas Compiling function newpoly with type XDistributedPolynomial( OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction( Integer),OrderedVariableList([a,b]))) -> XDistributedPolynomial( OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction( Integer),OrderedVariableList([a,b]))) fricas Compiling function subs with type OrderedFreeMonoid( OrderedVariableList([x,y])) -> XDistributedPolynomial( OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction( Integer),OrderedVariableList([a,b]))) fricas Compiling function newterm with type Record(k: OrderedFreeMonoid( OrderedVariableList([x,y])),c: SparseMultivariatePolynomial( Fraction(Integer),OrderedVariableList([a,b]))) -> XDistributedPolynomial(OrderedVariableList([x,y]), SparseMultivariatePolynomial(Fraction(Integer), OrderedVariableList([a,b])))  (10) Type: XDistributedPolynomial?(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b]))) fricas p2:=(x::V+y::V)$H^3
 (11)
Type: XDistributedPolynomial?(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b])))
fricas
newpoly(p2)
 (12)
Type: XDistributedPolynomial?(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b])))

rules should be applied more than once --Bill Page, Fri, 03 Mar 2006 19:45:54 -0600 reply
Oops, I just noticed that some of your rules should be applied more than once - I presume that you use the convention with the rules that they should be applied until no more changes are possible - right?

Let's try this:

fricas
pNew := newpoly(p2)
 (13)
Type: XDistributedPolynomial?(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b])))
fricas
while pNew ~= p2 repeat
p2 := pNew
pNew := newpoly(p2)
Type: Void
fricas
pNew
 (14)
Type: XDistributedPolynomial?(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b])))

fricas
reduce(p:H):H ==
p2 := newpoly(p)
p3 := newpoly(p2)
while p3 ~= p2 repeat
p2 := p3
p3 := newpoly(p2)
p3
Function declaration reduce : XDistributedPolynomial(
OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction(
Integer),OrderedVariableList([a,b]))) -> XDistributedPolynomial(
OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction(
Compiled code for newpoly has been cleared.