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.

spad
)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.
++ For two elements \spad{x} and \spad{y} the relation \spad{x < y}
++ 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
++ ordering induced by \spad{S}.
++ 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, %) -> % ++ \spad{s * x} returns the product of \spad{x} by \spad{s} on the left. "*": (%, S) -> % ++ \spad{x * s} returns the product of \spad{x} by \spad{s} on the right. "**": (S, NNI) -> % ++ \spad{s ** n} returns the product of \spad{s} by itself \spad{n} times. first: % -> S ++ \spad{first(x)} returns the first letter of \spad{x}. rest: % -> % ++ \spad{rest(x)} returns \spad{x} except the first letter. mirror: % -> % ++ \spad{mirror(x)} returns the reversed word of \spad{x}. lexico: (%,%) -> Boolean ++ \spad{lexico(x,y)} returns \spad{true} iff \spad{x} is smaller than \spad{y} ++ w.r.t. the pure lexicographical ordering induced by \spad{S}. hclf: (%, %) -> % ++ \spad{hclf(x, y)} returns the highest common left factor ++ of \spad{x} and \spad{y}, ++ 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 ++ factor of \spad{x} and \spad{y}, ++ that is the largest \spad{d} such that \spad{x = a d} and \spad{y = b d}. lquo: (%, %) -> Union(%, "failed") ++ \spad{lquo(x, y)} returns the exact left quotient of \spad{x} ++ by \spad{y} that is \spad{q} such that \spad{x = y * q}, ++ "failed" if \spad{x} is not of the form \spad{y * q}. rquo: (%, %) -> Union(%, "failed") ++ \spad{rquo(x, y)} returns the exact right quotient of \spad{x} ++ by \spad{y} that is \spad{q} such that \spad{x = q * y}, ++ "failed" if \spad{x} is not of the form \spad{q * y}. lquo: (%, S) -> Union(%, "failed") ++ \spad{lquo(x, s)} returns the exact left quotient of \spad{x} ++ by \spad{s}. rquo: (%, S) -> Union(%, "failed") ++ \spad{rquo(x, s)} returns the exact right quotient ++ of \spad{x} by \spad{s}. divide: (%, %) -> Union(ok:Record(lm: %, rm: %), bad:"failed") ++ \spad{divide(x, y)} returns the left and right exact quotients of ++ \spad{x} by \spad{y}, that is \spad{[l, r]} such that \spad{x = l * y * r}. ++ "failed" is returned iff \spad{x} is not of the form \spad{l * y * r}. overlap: (%, %) -> Record(lm: %, mm: %, rm: %) ++ \spad{overlap(x, y)} returns \spad{[l, m, r]} such that ++ \spad{x = l * m} and \spad{y = m * r} hold and such that ++ \spad{l} and \spad{r} have no overlap, ++ that is \spad{overlap(l, r) = [l, 1, r]}. size: % -> NNI ++ \spad{size(x)} returns the number of monomials in \spad{x}. nthExpon: (%, Integer) -> NNI ++ \spad{nthExpon(x, n)} returns the exponent of the ++ \spad{n-th} monomial of \spad{x}. nthFactor: (%, Integer) -> S ++ \spad{nthFactor(x, n)} returns the factor of the \spad{n-th} ++ monomial of \spad{x}. factors: % -> List REC ++ \spad{factors(a1\^e1,...,an\^en)} returns \spad{[[a1, e1],...,[an, en]]}. length: % -> NNI ++ \spad{length(x)} returns the length of \spad{x}. varList: % -> List S ++ \spad{varList(x)} returns the list of variables of \spad{x}.
OFMdefinition == FreeMonoid(S) add 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
spad
   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/7995627460190382989-25px001.spad
      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)

\label{eq1}x \ {{y}^{2}}\  z(1)
Type: OrderedFreeMonoid?(Symbol)
fricas
m2:=(x*y)$OFMONOID(Symbol)

\label{eq2}x \  y(2)
Type: OrderedFreeMonoid?(Symbol)
fricas
lquo(m1,m2)

\label{eq3}y \  z(3)
Type: Union(OrderedFreeMonoid?(Symbol),...)
fricas
m3:=(y*y)$OFMONOID(Symbol)

\label{eq4}{y}^{2}(4)
Type: OrderedFreeMonoid?(Symbol)
fricas
divide(m1,m2)

\label{eq5}\left[{lm = 1}, \:{rm ={y \  z}}\right](5)
Type: Union(ok: Record(lm: OrderedFreeMonoid?(Symbol),rm: OrderedFreeMonoid?(Symbol)),...)
fricas
divide(m1,m3)

\label{eq6}\left[{lm = x}, \:{rm = z}\right](6)
Type: Union(ok: Record(lm: OrderedFreeMonoid?(Symbol),rm: OrderedFreeMonoid?(Symbol)),...)
fricas
m4:=(y^3)$OFMONOID(Symbol)

\label{eq7}{y}^{3}(7)
Type: OrderedFreeMonoid?(Symbol)
fricas
divide(m1,m4)

\label{eq8}\mbox{\tt "failed"}(8)
Type: Union(bad: failed,...)

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( Integer),OrderedVariableList([a,b]))) has been added to workspace.
Type: Void

Example calculations:

fricas
p1:=(x::V+y::V)$H^2

\label{eq9}{{y}^{2}}+{y \  x}+{x \  y}+{{x}^{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])))

\label{eq10}{2 \  b}+{a \  y}+{a \  x}+{y \  x}+{x \  y}(10)
Type: XDistributedPolynomial?(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b])))
fricas
p2:=(x::V+y::V)$H^3

\label{eq11}{{y}^{3}}+{{{y}^{2}}\  x}+{y \  x \  y}+{y \ {{x}^{2}}}+{x \ {{y}^{2}}}+{x \  y \  x}+{{{x}^{2}}\  y}+{{x}^{3}}(11)
Type: XDistributedPolynomial?(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b])))
fricas
newpoly(p2)

\label{eq12}{3 \  b \  y}+{3 \  b \  x}+{a \ {{y}^{2}}}+{2 \  a \  y \  x}+{2 \  a \  x \  y}+{a \ {{x}^{2}}}+{2 \  y \  x \  y}(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)

\label{eq13}{3 \  b \  y}+{3 \  b \  x}+{a \ {{y}^{2}}}+{2 \  a \  y \  x}+{2 \  a \  x \  y}+{a \ {{x}^{2}}}+{2 \  y \  x \  y}(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

\label{eq14}{2 \  b \  a}+{{\left({{a}^{2}}+{3 \  b}\right)}\  y}+{{\left({{a}^{2}}+{3 \  b}\right)}\  x}+{2 \  a \  y \  x}+{2 \  a \  x \  y}+{2 \  y \  x \  y}(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( Integer),OrderedVariableList([a,b]))) has been added to workspace. Compiled code for newpoly has been cleared.
Type: Void




  Subject:   Be Bold !!
  ( 13 subscribers )  
Please rate this page: