help links subscribe changes refresh edit

	SandBoxTensorProduct
SandBoxHopfAlgebra ←	↑

SandBoxTensorProductPolynomial

Edit detail for SandBoxTensorProductPolynomial revision 11 of 12

	1 2 3 4 5 6 7 8 9 10 11 12
Editor: Bill Page Time: 2008/08/26 13:49:28 GMT-7
Note: associativity

http://en.wikipedia.org/wiki/Tensor_product

A tensor product is "the most general bilinear operation" available in a specified domain of computation, satisfying:

$\label{eq1} (v_1+v_2)\otimes w - (v_1\otimes w+v_2\otimes w) = 0$

(1)

$\label{eq2} v\otimes (w_1+w_2) - (v\otimes w_1+v\otimes w_2) = 0$

(2)

$\label{eq3} cv\otimes w=v\otimes cw=c(v\otimes w)$

(3)

We can use the domain constructor Sum [SandBoxSum]?

axiom

)lib SUM

   Sum is now explicitly exposed in frame initial 
   Sum will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/SUM.NRLIB/code.fasl

First we can define some recursive operations on the polynomials

axiom

scanPoly(p,n) == _
  (p=0 => 0; mapMonomial(leadingMonomial(p),n)+scanPoly(reductum p,n))

Type: Void

axiom

mapMonomial(p,n) == _
  monomial(coefficient(p,degree p),scanIndex(degree(p),n))$SMP(Integer,Sum(Symbol,Symbol))

Type: Void

axiom

scanIndex(p,n) == _
  (zero? p => 0$IndexedExponents(Sum(Symbol,Symbol)); _
    monomial(leadingCoefficient(p), _
      if n=1 then in1(leadingSupport(p))$Sum(Symbol,Symbol) _
             else in2(leadingSupport(p))$Sum(Symbol,Symbol) _
    )$IndexedExponents(Sum(Symbol,Symbol))+ _
      scanIndex(reductum(p),n))

Type: Void

For example:

axiom

-- functions are first compiled here
--
scanPoly(x,1)

axiom

Compiling function scanIndex with type (IndexedExponents Symbol,
      Integer) -> IndexedExponents Sum(Symbol,Symbol)

axiom

Compiling function mapMonomial with type (Polynomial Integer,Integer
      ) -> SparseMultivariatePolynomial(Integer,Sum(Symbol,Symbol))

axiom

Compiling function scanPoly with type (Polynomial Integer,Integer)
       -> SparseMultivariatePolynomial(Integer,Sum(Symbol,Symbol))

axiom

Compiling function scanPoly with type (Polynomial Integer,Integer)
       -> SparseMultivariatePolynomial(Integer,Sum(Symbol,Symbol)) 

;;;     ***       |*2;scanPoly;3;initial| REDEFINED

axiom

Compiling function scanPoly with type (Variable x,Integer) -> 
      SparseMultivariatePolynomial(Integer,Sum(Symbol,Symbol))

$\label{eq4}x_{1}$

(4)

Type: SparseMultivariatePolynomial?(Integer,Sum(Symbol,Symbol))

injects the polynomial x in to the tensor product. So now the full tensor product is just:

axiom

tensorPoly(p,q) == _
  scanPoly(p,1)*scanPoly(q,2)

Type: Void

For example:

axiom

p:=2*x^2+3

$\label{eq5}{2 \ {x^2}}+ 3$

(5)

Type: Polynomial Integer

axiom

q:=5*x*y+7*y+11

$\label{eq6}{{\left({5 \ x}+ 7 \right)}\ y}+{11}$

(6)

Type: Polynomial Integer

axiom

r:=tensorPoly(p,q)

axiom

Compiling function tensorPoly with type (Polynomial Integer,
      Polynomial Integer) -> SparseMultivariatePolynomial(Integer,Sum(
      Symbol,Symbol))

$\label{eq7}{{\left({{\left({{10}\ {{x_{1}}^2}}+{15}\right)}\ {x_{2}}}+{{1 4}\ {{x_{1}}^2}}+{21}\right)}\ {y_{2}}}+{{22}\ {{x_{1}}^2}}+{3 3}$

(7)

Type: SparseMultivariatePolynomial?(Integer,Sum(Symbol,Symbol))

axiom

monomials(r)

$\label{eq8}\left[{{10}\ {{x_{1}}^2}\ {x_{2}}\ {y_{2}}}, \:{{15}\ {x_{2}}\ {y_{2}}}, \:{{14}\ {{x_{1}}^2}\ {y_{2}}}, \:{{21}\ {y_{2}}}, \:{{2 2}\ {{x_{1}}^2}}, \:{33}\right]$

(8)

Type: List SparseMultivariatePolynomial?(Integer,Sum(Symbol,Symbol))

Demonstrating the axioms (1) (2) and (3) of the tensor product:

axiom

w:= 13*y^2+17*y+19

$\label{eq9}{{13}\ {y^2}}+{{17}\ y}+{19}$

(9)

Type: Polynomial Integer

axiom

test( tensorPoly(p+q,w) = (tensorPoly(p,w) + tensorPoly(q,w)) )

$\label{eq10} \mbox{\rm true}$

(10)

Type: Boolean

axiom

test( tensorPoly(p,q+w) = (tensorPoly(p,q) + tensorPoly(p,w)) )

$\label{eq11} \mbox{\rm true}$

(11)

Type: Boolean

axiom

test( tensorPoly(p,23*w) = 23*tensorPoly(p,w) )

$\label{eq12} \mbox{\rm true}$

(12)

Type: Boolean

axiom

test( tensorPoly(23*p,w) = 23*tensorPoly(p,w) )

$\label{eq13} \mbox{\rm true}$

(13)

Type: Boolean

I suppose that we could give an inductive proof that this implementation of the tensor product of polynomials is correct ... but for now lets take this demonstration as reassurance.

Re-coding the interpreter functions as library package.

spad

)abbrev package TPROD TensorProduct
macro IE == IndexedExponents(VAR)
macro IEP == IndexedExponents(Sum(VAR,VAR))
macro SMP == SparseMultivariatePolynomial(R,Sum(VAR,VAR))

TensorProduct(R:Ring, VAR: OrderedSet, P:PolynomialCategory(R,IE,VAR)): with
    _\_/: (P,P) -> SMP
  == add
    scanIndex(x:IE,n:Integer):IEP ==
      zero? x => 0
      monomial(leadingCoefficient(x), _
        if n=1 then in1(leadingSupport(x))$Sum(VAR,VAR) _
               else in2(leadingSupport(x))$Sum(VAR,VAR) _
      ) + scanIndex(reductum(x),n)
    mapMonomial(p:P,n:Integer):SMP ==
      monomial(coefficient(p,degree p),scanIndex(degree(p),n))$SMP
    scanPoly(p:P,n:Integer):SMP ==
      p=0 => 0
      mapMonomial(leadingMonomial(p),n)+scanPoly(reductum p,n)

    (p:P \/ q:P):SMP == scanPoly(p,1)*scanPoly(q,2)

spad

   Compiling OpenAxiom source code from file 
      /var/zope2/var/LatexWiki/7467299293205133182-25px007.spad using 
      Spad compiler.
   TPROD abbreviates package TensorProduct 
   processing macro definition IE ==> IndexedExponents VAR 

   processing macro definition IEP ==> IndexedExponents Sum(VAR,VAR) 

   processing macro definition SMP ==> SparseMultivariatePolynomial(R,Sum(VAR,VAR)) 

------------------------------------------------------------------------
   initializing NRLIB TPROD for TensorProduct 
   compiling into NRLIB TPROD 
   Adding $ modemaps
   Adding R modemaps
   Adding VAR modemaps
   Adding P modemaps
   Adding IndexedExponents Sum(VAR,VAR) modemaps
   Adding Integer modemaps
   Adding IndexedExponents VAR modemaps
   compiling local scanIndex : (IndexedExponents VAR,Integer) -> IndexedExponents Sum(VAR,VAR)
   Adding Boolean modemaps
   Adding NonNegativeInteger modemaps
   Adding Sum(VAR,VAR) modemaps
Time: 0.24 SEC.

   Adding SparseMultivariatePolynomial(R,Sum(VAR,VAR)) modemaps
   Adding Integer modemaps
   compiling local mapMonomial : (P,Integer) -> SparseMultivariatePolynomial(R,Sum(VAR,VAR))
   Adding IndexedExponents VAR modemaps
Time: 0.17 SEC.

   Adding Integer modemaps
   compiling local scanPoly : (P,Integer) -> SparseMultivariatePolynomial(R,Sum(VAR,VAR))
   Adding Boolean modemaps
Time: 0.01 SEC.

   compiling exported \/ : (P,P) -> SparseMultivariatePolynomial(R,Sum(VAR,VAR))
   Adding Integer modemaps
   Adding NonNegativeInteger modemaps
   Adding PositiveInteger modemaps
   Adding Fraction Integer modemaps
Time: 0.11 SEC.

(time taken in buildFunctor:  10)

;;;     ***       |TensorProduct| REDEFINED

;;;     ***       |TensorProduct| REDEFINED
Time: 0.01 SEC.

   Warnings: 
      [1] scanIndex: not known that OrderedSet is of mode CATEGORY(domain,IF(has(VAR,Finite),IF(has(VAR,Finite),Finite,%noBranch),%noBranch),IF(has(VAR,Monoid),IF(has(VAR,Monoid),Monoid,%noBranch),%noBranch),IF(has(VAR,AbelianMonoid),IF(has(VAR,AbelianMonoid),AbelianMonoid,%noBranch),%noBranch),IF(has(VAR,CancellationAbelianMonoid),IF(has(VAR,CancellationAbelianMonoid),CancellationAbelianMonoid,%noBranch),%noBranch),IF(has(VAR,Group),IF(has(VAR,Group),Group,%noBranch),%noBranch),IF(has(VAR,AbelianGroup),IF(has(VAR,AbelianGroup),AbelianGroup,%noBranch),%noBranch),IF(has(VAR,OrderedAbelianMonoidSup),IF(has(VAR,OrderedAbelianMonoidSup),OrderedAbelianMonoidSup,%noBranch),%noBranch),IF(has(VAR,OrderedSet),IF(has(VAR,OrderedSet),OrderedSet,%noBranch),%noBranch),selectsum: % -> Union(acomp: VAR,bcomp: VAR),in1: VAR -> %,in2: VAR -> %)
      [2] mapMonomial: not known that OrderedSet is of mode CATEGORY(domain,IF(has(VAR,Finite),IF(has(VAR,Finite),Finite,%noBranch),%noBranch),IF(has(VAR,Monoid),IF(has(VAR,Monoid),Monoid,%noBranch),%noBranch),IF(has(VAR,AbelianMonoid),IF(has(VAR,AbelianMonoid),AbelianMonoid,%noBranch),%noBranch),IF(has(VAR,CancellationAbelianMonoid),IF(has(VAR,CancellationAbelianMonoid),CancellationAbelianMonoid,%noBranch),%noBranch),IF(has(VAR,Group),IF(has(VAR,Group),Group,%noBranch),%noBranch),IF(has(VAR,AbelianGroup),IF(has(VAR,AbelianGroup),AbelianGroup,%noBranch),%noBranch),IF(has(VAR,OrderedAbelianMonoidSup),IF(has(VAR,OrderedAbelianMonoidSup),OrderedAbelianMonoidSup,%noBranch),%noBranch),IF(has(VAR,OrderedSet),IF(has(VAR,OrderedSet),OrderedSet,%noBranch),%noBranch),selectsum: % -> Union(acomp: VAR,bcomp: VAR),in1: VAR -> %,in2: VAR -> %)

   Cumulative Statistics for Constructor TensorProduct
      Time: 0.54 seconds

   finalizing NRLIB TPROD 
   Processing TensorProduct for Browser database:
--->-->TensorProduct((\/ (SMP P P))): Not documented!!!!
--->-->TensorProduct(constructor): Not documented!!!!
--->-->TensorProduct: Missing Description

; compiling file "/var/zope2/var/LatexWiki/TPROD.NRLIB/code.lsp" (written 06 APR 2011 09:29:57 PM):
; compiling (/VERSIONCHECK 2)
; compiling (DEFUN |TPROD;scanIndex| ...)
; compiling (DEFUN |TPROD;mapMonomial| ...)
; compiling (DEFUN |TPROD;scanPoly| ...)
; compiling (DEFUN |TPROD;\\/;2PSmp;4| ...)
; compiling (DEFUN |TensorProduct| ...)
; compiling (DEFUN |TensorProduct;| ...)
; compiling (MAKEPROP (QUOTE |TensorProduct|) ...)

; /var/zope2/var/LatexWiki/TPROD.NRLIB/code.fasl written
; compilation finished in 0:00:00.870
------------------------------------------------------------------------
   TensorProduct is now explicitly exposed in frame initial 
   TensorProduct will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/TPROD.NRLIB/code.fasl

   >> System error:
   The bounding indices 163 and 162 are bad for a sequence of length 162.
See also:
  The ANSI Standard, Glossary entry for "bounding index designator"
  The ANSI Standard, writeup for Issue SUBSEQ-OUT-OF-BOUNDS:IS-AN-ERROR

axiom

test( p\/q = r )

$\label{eq14} \mbox{\rm true}$

(14)

Type: Boolean

axiom

test( (p+q) \/ w = (p\/w) + (q\/w) )

$\label{eq15} \mbox{\rm true}$

(15)

Type: Boolean

axiom

test( p \/ (q+w) = (p\/q) + (p\/w) )

$\label{eq16} \mbox{\rm true}$

(16)

Type: Boolean

axiom

test( p \/ (23*w) = 23*(p\/w) )

$\label{eq17} \mbox{\rm true}$

(17)

Type: Boolean

axiom

test( (23*p) \/ w = 23*(p\/w) )

$\label{eq18} \mbox{\rm true}$

(18)

Type: Boolean

Here's another way to write this - maybe better this way as first step to express associativity of the tensor product.

spad

)abbrev package TPROD2 TensorProduct2
macro IE1 == IndexedExponents(VAR1)
macro IE2 == IndexedExponents(VAR2)
macro S == Sum(VAR1,VAR2)
macro IEP == IndexedExponents(S)
macro SMP == SparseMultivariatePolynomial(R,S)

TensorProduct2(R:Ring, VAR1: OrderedSet, VAR2: OrderedSet, P:PolynomialCategory(R,IE1,VAR1), Q:PolynomialCategory(R,IE2,VAR2)): with
    _\_/: (P,Q) -> SMP
  == add
    scanIndex1(x:IE1):IEP ==
      zero? x => 0
      monomial(leadingCoefficient(x), in1(leadingSupport(x))$S) + scanIndex1(reductum(x))
    scanIndex2(x:IE2):IEP ==
      zero? x => 0
      monomial(leadingCoefficient(x), in2(leadingSupport(x))$S) + scanIndex2(reductum(x))
    mapMonomial1(p:P):SMP ==
      monomial(coefficient(p,degree p),scanIndex1(degree(p)))$SMP
    mapMonomial2(q:Q):SMP ==
      monomial(coefficient(q,degree q),scanIndex2(degree(q)))$SMP
    scanPoly1(p:P):SMP ==
      p=0 => 0
      mapMonomial1(leadingMonomial(p))+scanPoly1(reductum p)
    scanPoly2(q:Q):SMP ==
      q=0 => 0
      mapMonomial2(leadingMonomial(q))+scanPoly2(reductum q)

    (p:P \/ q:Q):SMP == scanPoly1(p)*scanPoly2(q)

spad

   Compiling OpenAxiom source code from file 
      /var/zope2/var/LatexWiki/6972063761479466203-25px009.spad using 
      Spad compiler.
   TPROD2 abbreviates package TensorProduct2 
   processing macro definition IE1 ==> IndexedExponents VAR1 

   processing macro definition IE2 ==> IndexedExponents VAR2 

   processing macro definition S ==> Sum(VAR1,VAR2) 

   processing macro definition IEP ==> IndexedExponents S 

   processing macro definition SMP ==> SparseMultivariatePolynomial(R,S) 

------------------------------------------------------------------------
   initializing NRLIB TPROD2 for TensorProduct2 
   compiling into NRLIB TPROD2 
   Adding $ modemaps
   Adding R modemaps
   Adding VAR1 modemaps
   Adding VAR2 modemaps
   Adding P modemaps
   Adding Q modemaps
   Adding IndexedExponents Sum(VAR1,VAR2) modemaps
   Adding IndexedExponents VAR1 modemaps
   compiling local scanIndex1 : IndexedExponents VAR1 -> IndexedExponents Sum(VAR1,VAR2)
   Adding Boolean modemaps
   Adding Integer modemaps
   Adding NonNegativeInteger modemaps
   Adding Sum(VAR1,VAR2) modemaps
Time: 0.10 SEC.

   Adding IndexedExponents VAR2 modemaps
   compiling local scanIndex2 : IndexedExponents VAR2 -> IndexedExponents Sum(VAR1,VAR2)
   Adding Boolean modemaps
   Adding Integer modemaps
   Adding NonNegativeInteger modemaps
   Adding Sum(VAR1,VAR2) modemaps
Time: 0.04 SEC.

   Adding SparseMultivariatePolynomial(R,Sum(VAR1,VAR2)) modemaps
   compiling local mapMonomial1 : P -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
   Adding IndexedExponents VAR1 modemaps
Time: 0.18 SEC.

   compiling local mapMonomial2 : Q -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
   Adding IndexedExponents VAR2 modemaps
Time: 0.01 SEC.

   compiling local scanPoly1 : P -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
   Adding Boolean modemaps
Time: 0 SEC.

   compiling local scanPoly2 : Q -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
   Adding Boolean modemaps
Time: 0.01 SEC.

   compiling exported \/ : (P,Q) -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
   Adding Fraction Integer modemaps
Time: 0.04 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |TensorProduct2| REDEFINED

;;;     ***       |TensorProduct2| REDEFINED
Time: 0.01 SEC.

   Warnings: 
      [1] scanIndex1: not known that OrderedSet is of mode CATEGORY(domain,IF(has(VAR1,Finite),IF(has(VAR2,Finite),Finite,%noBranch),%noBranch),IF(has(VAR1,Monoid),IF(has(VAR2,Monoid),Monoid,%noBranch),%noBranch),IF(has(VAR1,AbelianMonoid),IF(has(VAR2,AbelianMonoid),AbelianMonoid,%noBranch),%noBranch),IF(has(VAR1,CancellationAbelianMonoid),IF(has(VAR2,CancellationAbelianMonoid),CancellationAbelianMonoid,%noBranch),%noBranch),IF(has(VAR1,Group),IF(has(VAR2,Group),Group,%noBranch),%noBranch),IF(has(VAR1,AbelianGroup),IF(has(VAR2,AbelianGroup),AbelianGroup,%noBranch),%noBranch),IF(has(VAR1,OrderedAbelianMonoidSup),IF(has(VAR2,OrderedAbelianMonoidSup),OrderedAbelianMonoidSup,%noBranch),%noBranch),IF(has(VAR1,OrderedSet),IF(has(VAR2,OrderedSet),OrderedSet,%noBranch),%noBranch),selectsum: % -> Union(acomp: VAR1,bcomp: VAR2),in1: VAR1 -> %,in2: VAR2 -> %)
      [2] mapMonomial1: not known that OrderedSet is of mode CATEGORY(domain,IF(has(VAR1,Finite),IF(has(VAR2,Finite),Finite,%noBranch),%noBranch),IF(has(VAR1,Monoid),IF(has(VAR2,Monoid),Monoid,%noBranch),%noBranch),IF(has(VAR1,AbelianMonoid),IF(has(VAR2,AbelianMonoid),AbelianMonoid,%noBranch),%noBranch),IF(has(VAR1,CancellationAbelianMonoid),IF(has(VAR2,CancellationAbelianMonoid),CancellationAbelianMonoid,%noBranch),%noBranch),IF(has(VAR1,Group),IF(has(VAR2,Group),Group,%noBranch),%noBranch),IF(has(VAR1,AbelianGroup),IF(has(VAR2,AbelianGroup),AbelianGroup,%noBranch),%noBranch),IF(has(VAR1,OrderedAbelianMonoidSup),IF(has(VAR2,OrderedAbelianMonoidSup),OrderedAbelianMonoidSup,%noBranch),%noBranch),IF(has(VAR1,OrderedSet),IF(has(VAR2,OrderedSet),OrderedSet,%noBranch),%noBranch),selectsum: % -> Union(acomp: VAR1,bcomp: VAR2),in1: VAR1 -> %,in2: VAR2 -> %)

   Cumulative Statistics for Constructor TensorProduct2
      Time: 0.39 seconds

   finalizing NRLIB TPROD2 
   Processing TensorProduct2 for Browser database:
--->-->TensorProduct2((\/ (SMP P Q))): Not documented!!!!
--->-->TensorProduct2(constructor): Not documented!!!!
--->-->TensorProduct2: Missing Description
; compiling file "/var/zope2/var/LatexWiki/TPROD2.NRLIB/code.lsp" (written 06 APR 2011 09:29:59 PM):
; compiling (/VERSIONCHECK 2)
; compiling (DEFUN |TPROD2;scanIndex1| ...)
; compiling (DEFUN |TPROD2;scanIndex2| ...)
; compiling (DEFUN |TPROD2;mapMonomial1| ...)
; compiling (DEFUN |TPROD2;mapMonomial2| ...)
; compiling (DEFUN |TPROD2;scanPoly1| ...)
; compiling (DEFUN |TPROD2;scanPoly2| ...)
; compiling (DEFUN |TPROD2;\\/;PQSmp;7| ...)
; compiling (DEFUN |TensorProduct2| ...)
; compiling (DEFUN |TensorProduct2;| ...)
; compiling (MAKEPROP (QUOTE |TensorProduct2|) ...)

; /var/zope2/var/LatexWiki/TPROD2.NRLIB/code.fasl written
; compilation finished in 0:00:00.156
------------------------------------------------------------------------
   TensorProduct2 is now explicitly exposed in frame initial 
   TensorProduct2 will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/TPROD2.NRLIB/code.fasl

   >> System error:
   The bounding indices 163 and 162 are bad for a sequence of length 162.
See also:
  The ANSI Standard, Glossary entry for "bounding index designator"
  The ANSI Standard, writeup for Issue SUBSEQ-OUT-OF-BOUNDS:IS-AN-ERROR

axiom

test( p\/q = r )

$\label{eq19} \mbox{\rm true}$

(19)

Type: Boolean

axiom

test( (p+q) \/ w = (p\/w) + (q\/w) )

$\label{eq20} \mbox{\rm true}$

(20)

Type: Boolean

axiom

test( p \/ (q+w) = (p\/q) + (p\/w) )

$\label{eq21} \mbox{\rm true}$

(21)

Type: Boolean

axiom

test( p \/ (23*w) = 23*(p\/w) )

$\label{eq22} \mbox{\rm true}$

(22)

Type: Boolean

axiom

test( (23*p) \/ w = 23*(p\/w) )

$\label{eq23} \mbox{\rm true}$

(23)

Type: Boolean

Associativity of the tensor product means these two expressions should be identical:

axiom

(p\/q)\/w

$\label{eq24}\begin{array}{@{}l} \displaystyle {{\left({ \begin{array}{@{}l} \displaystyle {{\left({{\left({{130}\ {{{x_{1}}_{1}}^2}}+{195}\right)}\ {{x_{2}}_{1}}}+{{182}\ {{{x_{1}}_{1}}^2}}+{273}\right)}\ {{y_{2}}_{1}}}+ \ \ \displaystyle {{286}\ {{{x_{1}}_{1}}^2}}+{429}$

(24)

Type: SparseMultivariatePolynomial?(Integer,Sum(Sum(Symbol,Symbol),Symbol))

axiom

p\/(q\/w)

$\label{eq25}\begin{array}{@{}l} \displaystyle {{\left({ \begin{array}{@{}l} \displaystyle {{\left({{\left({{130}\ {{x_{1}}^2}}+{195}\right)}\ {{x_{1}}_{2}}}+{{182}\ {{x_{1}}^2}}+{273}\right)}\ {{y_{1}}_{2}}}+ \ \ \displaystyle {{286}\ {{x_{1}}^2}}+{429}$

(25)

Type: SparseMultivariatePolynomial?(Integer,Sum(Symbol,Sum(Symbol,Symbol)))