help links subscribe changes refresh edit

	SandBoxTensorProduct
SandBoxHopfAlgebra ←	↑

SandBoxTensorProductPolynomial

Edit detail for SandBoxTensorProductPolynomial revision 10 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/SUM

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)

   >> System error:
   Couldn't load "/var/zope2/var/LatexWiki/SUM.NRLIB/SUM": file does not exist.

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{eq4}{2 \ {x^2}}+ 3$

(4)

Type: Polynomial(Integer)

axiom

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

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

(5)

Type: Polynomial(Integer)

axiom

r:=tensorPoly(p,q)

   >> System error:
   Couldn't load "/var/zope2/var/LatexWiki/SUM.NRLIB/SUM": file does not exist.

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

axiom

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

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

(6)

Type: Polynomial(Integer)

axiom

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

axiom

Compiling function tensorPoly with type (Polynomial(Integer),
      Polynomial(Integer)) -> NonNegativeInteger 

   >> System error:
   The function |*2;scanPoly;2;initial| is undefined.

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 FriCAS source code from file 
      /var/zope2/var/LatexWiki/7467299293205133182-25px007.spad using 
      old system 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 
   compiling local scanIndex : (IndexedExponents VAR,Integer) -> IndexedExponents Sum(VAR,VAR)
Time: 0.41 SEC.

   compiling local mapMonomial : (P,Integer) -> SparseMultivariatePolynomial(R,Sum(VAR,VAR))
Time: 0.01 SEC.

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

   compiling local / : (P,P) -> SparseMultivariatePolynomial(R,Sum(VAR,VAR))
Time: 0.01 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |TensorProduct| REDEFINED

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

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

   Cumulative Statistics for Constructor TensorProduct
      Time: 0.44 seconds

   finalizing NRLIB TPROD 
   Processing TensorProduct for Browser database:
--->/usr/local/lib/fricas/target/x86_64-unknown-linux/../../src/algebra/TENSOR.spad-->TensorProduct((\/ (SMP P P))): Not documented!!!!
--->/usr/local/lib/fricas/target/x86_64-unknown-linux/../../src/algebra/TENSOR.spad-->TensorProduct(constructor): Not documented!!!!
--->/usr/local/lib/fricas/target/x86_64-unknown-linux/../../src/algebra/TENSOR.spad-->TensorProduct(): Missing Description
; compiling file "/var/zope2/var/LatexWiki/TPROD.NRLIB/TPROD.lsp" (written 27 FEB 2011 06:47:54 PM):
; compiling (/VERSIONCHECK 2)
; compiling (DEFUN |TPROD;scanIndex| ...)
; compiling (DEFUN |TPROD;mapMonomial| ...)
; compiling (DEFUN |TPROD;scanPoly| ...)
; compiling (DEFUN |TPROD;/| ...)
; compiling (DEFUN |TensorProduct| ...)
; compiling (DEFUN |TensorProduct;| ...)
; compiling (MAKEPROP (QUOTE |TensorProduct|) ...)

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

axiom

test( p\/q = r )

   Internal Error
   The function \/ with signature hashcode is missing from domain 
      TensorProduct(Integer)(Symbol)(Polynomial (Integer))

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 FriCAS source code from file 
      /var/zope2/var/LatexWiki/6972063761479466203-25px009.spad using 
      old system 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 
   compiling local scanIndex1 : IndexedExponents VAR1 -> IndexedExponents Sum(VAR1,VAR2)
Time: 0.08 SEC.

   compiling local scanIndex2 : IndexedExponents VAR2 -> IndexedExponents Sum(VAR1,VAR2)
Time: 0.02 SEC.

   compiling local mapMonomial1 : P -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
Time: 0.01 SEC.

   compiling local mapMonomial2 : Q -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
Time: 0 SEC.

   compiling local scanPoly1 : P -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
Time: 0.01 SEC.

   compiling local scanPoly2 : Q -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
Time: 0 SEC.

   compiling local / : (P,Q) -> SparseMultivariatePolynomial(R,Sum(VAR1,VAR2))
Time: 0.01 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |TensorProduct2| REDEFINED

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

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

   Cumulative Statistics for Constructor TensorProduct2
      Time: 0.13 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/TPROD2.lsp" (written 27 FEB 2011 06:48:06 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;/| ...)
; compiling (DEFUN |TensorProduct2| ...)
; compiling (DEFUN |TensorProduct2;| ...)
; compiling (MAKEPROP (QUOTE |TensorProduct2|) ...)

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

axiom

test( p\/q = r )

   Internal Error
   The function \/ with signature hashcode is missing from domain 
      TensorProduct(Integer)(Symbol)(Polynomial (Integer))

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

axiom

(p\/q)\/w

   Internal Error
   The function \/ with signature hashcode is missing from domain 
      TensorProduct(Integer)(Symbol)(Polynomial (Integer))