help links subscribe changes refresh edit

	FriCAS Library Examples
InputForm ←	↑	→ PolynomialOverFiniteField

NoncommutativePolynomials

Edit detail for NoncommutativePolynomials revision 1 of 1

	1
Editor: test1 Time: 2018/03/30 18:22:09 GMT+0
Note:

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

- src/algebra/xpoly.spad

- src/algebra/xlpoly.spad

and HyperDoc example page about XPOLY

In FriCAS algebra is simplified and there is no longer OrderedFreeMonoid,
we just use FreeMonoid below.

We need left and right quotients which are provided by 'divide' to implement the substitution rules
in the example below.


Test left and right exact quotients.
\begin{axiom}
m1:=(x*y*y*z)$FMONOID(Symbol)
m2:=(x*y)$FMONOID(Symbol)
lquo(m1,m2)
m3:=(y*y)$FMONOID(Symbol)
divide(m1,m2)
divide(m1,m3)
m4:=(y^3)$FMONOID(Symbol)
divide(m1,m4)
\end{axiom}

This option is required to compile the functions that follow.
\begin{axiom}
)set function compile on
\end{axiom}

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
 
\begin{axiom}
--Generic elements of k
--OVAR = OrderedVariableList
C==>OVAR [a,b]
--Commutative Field: k=Q[a,b]
--Q = FRAC INT = Fration Integer
--SMP = SparseMultivariatePolynomials
K==>SMP(FRAC INT,C)
--Non-commutative variables
V==>OVAR [x,y]
--Non-commutative Algebra: h=k[x,y]
--XDPOLY XDistributedPolynomial
H==>XDPOLY(V,K)
--Free monoid
M==>FMONOID V

--Record giving result of division
Rec==>Record(lm : M, rm : M)

--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 Rec => monomial(1, (n::Rec).lm)$H * (y::V*x::V*y::V)$H * monomial(1, (n::Rec).rm)$H
  --x*x=a*x+b
  n:=divide(w,(x::V^2)$M)$M
  n case Rec => monomial(1, (n::Rec).lm)$H * (a::K*x::V+b::K)$H * monomial(1, (n::Rec).rm)$H
  --y*y=a*y+b
  n:=divide(w,(y::V^2)$M)$M
  n case Rec => monomial(1, (n::Rec).lm)$H * (a::K*y::V+b::K)$H * monomial(1, (n::Rec).rm)$H
  --no change
  monomial(1, w)$H
--Apply rules to a term. Keep coefficients 
newterm(x:Record(k:M,c:K)):H==x.c*subs(x.k)
--Reconstruct polynomial, term-by-term
newpoly(t:H):H==reduce(+,map(newterm,listOfTerms(t)))
\end{axiom}

Example calculations:
\begin{axiom}
p1:=(x::V+y::V)$H^2
newpoly(p1)
p2:=(x::V+y::V)$H^3
newpoly(p2)
\end{axiom}

'newpoly' above applies rules once.  However
the rules above should be applied more than once - they should be applied
until no more changes are possible.  This is done below:

\begin{axiom}
reduce(p:H):H ==
  p2 := newpoly(p)
  p3 := newpoly(p2)
  while p3 ~= p2 repeat
   p2 := p3
   p3 := newpoly(p2)
  p3

reduce(p2)

\end{axiom}

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

src/algebra/xpoly.spad
src/algebra/xlpoly.spad

and HyperDoc example page about XPOLY

In FriCAS algebra is simplified and there is no longer OrderedFreeMonoid?, we just use FreeMonoid below.

We need left and right quotients which are provided by divide to implement the substitution rules in the example below.

Test left and right exact quotients.

fricas

(1) -> m1:=(x*y*y*z)$FMONOID(Symbol)

$\label{eq1}x \ {{y}^{2}}\ z$

(1)

Type: FreeMonoid(Symbol)

fricas

m2:=(x*y)$FMONOID(Symbol)

$\label{eq2}x \ y$

(2)

Type: FreeMonoid(Symbol)

fricas

lquo(m1,m2)

$\label{eq3}y \ z$

(3)

Type: Union(FreeMonoid(Symbol),...)

fricas

m3:=(y*y)$FMONOID(Symbol)

$\label{eq4}{y}^{2}$

(4)

Type: FreeMonoid(Symbol)

fricas

divide(m1,m2)

$\label{eq5}\left[{lm = 1}, \:{rm ={y \ z}}\right]$

(5)

Type: Union(Record(lm: FreeMonoid(Symbol),rm: FreeMonoid(Symbol)),...)

fricas

divide(m1,m3)

$\label{eq6}\left[{lm = x}, \:{rm = z}\right]$

(6)

Type: Union(Record(lm: FreeMonoid(Symbol),rm: FreeMonoid(Symbol)),...)

fricas

m4:=(y^3)$FMONOID(Symbol)

$\label{eq7}{y}^{3}$

(7)

Type: FreeMonoid(Symbol)

fricas

divide(m1,m4)

$\label{eq8}\verb#"failed"#$

(8)

Type: Union("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==>FMONOID V

Type: Void

fricas

--Record giving result of division
Rec==>Record(lm : M, rm : M)

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 Rec => monomial(1, (n::Rec).lm)$H * (y::V*x::V*y::V)$H * monomial(1, (n::Rec).rm)$H
  --x*x=a*x+b
  n:=divide(w,(x::V^2)$M)$M
  n case Rec => monomial(1, (n::Rec).lm)$H * (a::K*x::V+b::K)$H * monomial(1, (n::Rec).rm)$H
  --y*y=a*y+b
  n:=divide(w,(y::V^2)$M)$M
  n case Rec => monomial(1, (n::Rec).lm)$H * (a::K*y::V+b::K)$H * monomial(1, (n::Rec).rm)$H
  --no change
  monomial(1, w)$H

   Function declaration subs : FreeMonoid(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: FreeMonoid(
      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 FreeMonoid(OrderedVariableList([x,
      y])) -> XDistributedPolynomial(OrderedVariableList([x,y]),
      SparseMultivariatePolynomial(Fraction(Integer),
      OrderedVariableList([a,b])))

fricas

Compiling function newterm with type Record(k: FreeMonoid(
      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])))

newpoly above applies rules once. However the rules above should be applied more than once - they should be applied until no more changes are possible. This is done below:

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

fricas

reduce(p2)

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 reduce with type XDistributedPolynomial(
      OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction(
      Integer),OrderedVariableList([a,b]))) -> XDistributedPolynomial(
      OrderedVariableList([x,y]),SparseMultivariatePolynomial(Fraction(
      Integer),OrderedVariableList([a,b])))

$\label{eq13}{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}$

(13)

Type: XDistributedPolynomial(OrderedVariableList([x,y]),SparseMultivariatePolynomial?(Fraction(Integer),OrderedVariableList([a,b])))