cmulRS.html

Function: Cliff5[`cmulRS`] - Clifford product for two Clifford basmonoms and (arbitrary but preferably) symbolic bilinear form

Calling Sequence:

c3 := cmuRS(c1,c2,B)

Parameters:

c1, c2- Clifford monoms (elements of the type: `type/clibasmon` )

B - bilinear form of type `name`, `symbol`, `matrix`, `array` or `&*`(numeric,{name,symbol,array,matrix})

Output:

c3 : a Clifford polynom

Description:

Since the Clifford product provides the main functionality of the CLIFFORD package, the best available mathematics has been incorporated in its code. The user normally does not use the internal functions cmulRS and cmulNUM but the wrapper function ` &c`[K](arg1,arg2,...) which allows one to pass the name of a bilinear form K. The wrapper function can also act on any number of arguments of type clipolynom (since the Clifford product is associative this makes sense) and on a much wider class of types including Clifford matrices of type climatrix or Clifford polynoms in other bases, see Cli5plus .

There is a facility to use one of the internal functions (cmulRS or cmulNUM) when knowledge of the bilinear form allows one to decide which procedure might yield better performance. Moreover, the user can supply a `product` function (not necessarily a Clifford product) acting on two clibasmons, that is, monomials of type clibasmon . The wrapper uses the appropriate function, cmulRS, cmulNUM, or other, which has been selected by the user via a special function Cliff5[useproduct] .

There are two internal Clifford multiplications which are appropriate for different purposes. While cmulNUM is fast on sparse numeric matrices and on numeric matrices in general for dimensions dim_V >= 5, cmulRS was designed for symbolic calculations. Since cmulRS computes reasonably well in the numeric sparse case up to dim_V = 5, it was chosen as the default product of the package. Both internal multiplication procedures, cmulRS and cmulNUM, take two Clifford monomials of type clibasmon as input together with a third argument of type name/symbol/matrix/array which represents the chosen bilinear form.

The evaluation of Clifford products in a Graßmann basis is quite involved and normally is done by a recursive process that uses Chevalley deformation, see cmulNUM . However, during the recursive evaluation many unnecessary terms are calculated which later cancel out at the next recursive call. This feature, while being beneficial when the bilinear form is sparse numeric, since it cuts out many branches of the recursion quite early, prevents fast evaluation in the symbolic case where in general all terms might be non-zero. From this observation, the two possibilities to evaluate the Clifford product have emerged.

To see how to define a new "Clifford product", go to cmul_user_defined for some help.

cmulRS is computed using non-iterative Rota-Stein cliffordization, see [1,2] and the help pages of the Bigebra package for further literature. The cliffordization process is based on Hopf algebra theory. The Clifford product is obtained from the Graßmann wedge product and its Graßmann co-product, see Bigebra[`&gco`] , as follows (in tangle notation):

| |
/ \_/ \
\ B /
\ /
\ /
|

where is the Graßmann exterior wedge product and is the Graßmann exterior co-product, which is obtained from the wedge product by categorial duality, i.e. to every algebra over a linear space V having a product we find a co-algebra having a co-product over the same space by reversing all arrows in all axiomatic commutative diagrams. Note that the co-product splits a single (input) 'factor' x into a tensor product (sum of ordered pairs x_(1)i, x_(2)i ) of (output) factors. The main feature is that every such pair multiplies back to the input if the dual operation of multiplication is applied, i.e. x_(1)i /\ x_(2)i = x for each pair i. The 'cup' like part of the tangle decorated with B is the bilinear form B extended to the whole Graßmann algebra, i.e. the map B : /\V x /\ V -> k, with B : V x V -> k as B(x,y) on vectors. Hence, cmulRS computes on x and y for the given B, later extended to polynoms by bilinearity, as follows:

cmulRS(x,y,B) = (+/-) x_(1)i /\ y_(2)j * B( x_(2)i , y_(1)j )

where n is a dummy describing the cardinality of the required split and the sign is due to the needed permutations to arrage the factors.

The (simplified some further efforts to speed it up are employed in the package) algorithm of cmulRS is as follows:

cmulRS(x,y,B) [x,y two Graßmann monoms, B the name,... of a bilinear form]
begin
lstx <- list of indices from x
lsty <- list of indices from y
NX <- |lstx|
NY <- |lsty|
funx <- a function which maps the integers 1..NX onto the elements of lstx keeping their order
funy <- a function which maps the integers 1..NY onto the elements of lsty keeping their order
## this will allow to calculate with arbitrary indices and to compute the necessary signs with some ease
psetx <- power set of {1..NX} # actually a list in a certain order
# the ith and (2^NX+1-i)th element are disjoint adding up to the set {1..NX}
psety <- power set of {1..NY} # actually a list in a certain order
# the ith and (2^NY+1-i)th element are disjoint adding up to the set {1..NY}
## for faster computation we sort this power sets by grade
## we compute the sign for any term in the power set (that's tricky)
psetx <- sort psetx by grade
psety <- sort psety by grade
pSgnx <- sum_(i in psetx) (-1)^sum_(j in psetx[i]) (psetx[i][j]-j)
pSgny <- sum_(i in psety) (-1)^sum_(j in psety[i]) (psety[i][j]-j)
## now we need a subroutine for the cup tangle computing the bilinear form
cup(x,y,B)
begin
if |x| <> |y| then RETURN(0) fi
if |x| = 0 then RETURN(1) fi
if |x| = 1 then RETURN(B[x[1],y[1]]) fi
RETURN( sum_(j in 1..|x|)
(-1)^(j-1)*B(x[1],y[j])*
*cup(x[2..-1],y/y[j],B) )
end cup
## now we compute the double sum, to gain efficiency we do this grade wise
## note thate there are r over NX r-vectors in psetx, analogous for psety
max_grade <- |lstx <- convert_to_set union lsty <- convert_to_set|
res <- 0, pos1 <- 0
for j from 0 to NX # iterate over all j-vectors of psetx
begin
F1 <- N1!/((N1-j)!*j!) # number of terms (N1 over j)
pos2 <- 0
for i from 0 to min(N2,max_grade-j) # iterate over all i-vectors of psety
# which do not exceed max_grade (others are zero)
begin
F2 <- N2!/((N2-i)!*i!) # number of terms (N2 over i)
for n from 1 to F1 # for all j-vectors
begin
for m from 1 to F2 # for all i-vectors
begin
res <- res +
pSgnx[pos1+n]*pSgny[pos2+m]*
*cup(fun1(psetx[PN1-pos1-n]),fun2(psety[pos2+m]),lname)*
makeclibasmon -> ([fun1 -> psetx[pos1+n],fun2 -> psety[PN2-pos2-m])])
end
end
pos2 <- pos2+F2
end
pos1 <- pos1+F1;
end
reorder -> res # reoder map all basis elements into standard order
end cmulRS

It is clear from this algorithm that only such terms are considered which might be non-zero: If all B[i,j] are non-zero and different so that no cancellation takes place between them, all these terms will survive. The combinatorial power of the Hopf algebraic approach is clearly demonstated with this algorithm and its behaviour in benchmarks.

References:
[1] G.-C. Rota, J.A. Stein, Plethystic Hopf algebras, Proc. Natl. Acad. Sci. USA 91, 1994:13057-13061
[2] R. Ablamowicz, B. Fauser, Effective algorithms for evaluating Clifford products, pre-print 2001

Examples:

> restart:with(Cliff5):

We check for some special cases and use arbitrary bilinear forms, e.g. B, K, T ...

> cmulRS(0,e1we2,K);
cmulRS(Id,Id,K);
cmulRS(Id,ei,-K);
cmulRS(ei,Id,K);
cmulRS(e1,e2,-K);
cmulRS(ei,ej,B);
cmulRS(ei,ej,-B);

Now let us go for more complicated monoms:

> cmulRS(e1we2,e2we3,B);
cmulRS(e1we2,e2we3,-B);
cmulRS(e1we2,e1we2we3,T);
cmulRS(e1we2,e1we2we3,-T);

To perform some benchmarks, we need some random basmonoms:

> rd:=rand(0..7):
rdmonom:=proc(N) makeclibasmon([op({seq(rd(),i=1..N)} minus {0} )]) end:
rdmonom(rd()),rdmonom(rd()),rdmonom(rd());

We iterate over MAX basmonoms and compute their mutual products. Since we expect cmulRS to be faster as cmulNUM in the symbolic case, we explore this case here, for a benchmark with a sparse numeric matrix B see Cliff5[cmulNUM] .

> MAX:=10:
monlist:=[seq(rdmonom(rd()),i=1..MAX)];
tm:=time():
for i from 1 to MAX do
for j from 1 to MAX do
cmulRS(monlist[i],monlist[j],B);
od:od:
tm:=time()-tm:
printf("computation with cmulRS needed %f seconds",tm);
tm:=time():
for i from 1 to MAX do
for j from 1 to MAX do
cmulNUM(monlist[i],monlist[j],B);
od:od:
tm:=time()-tm:
printf("computation with cmulNUM needed %f seconds",tm);

computation with cmulRS needed 1.452000 seconds

computation with cmulNUM needed 11.677000 seconds

Hence we find the desired result. The relative factor of performance between these functions changes with the randomly chosen basmonoms and due to the garbage collection in Maple, etc., but we find roughly a factor 8 in this setting, which is reasonable.

Note that one can gain speed in the computation of Clifford products in the BIGEBRA package by using it in the Bigebra[`&map`] function. This is possible since the tensor product is multilinear and the entries are reduced to be only clibasmons, however the tensor product has to be evaluated.

> _CLIENV[_SILENT]:=true:with(Bigebra):

Warning, new definition for init

Warning, new definition for drop_t

Warning, new definition for gco_d_monom

Warning, new definition for gco_monom

> t1:=&t(a*e1+e2,b*e1we2,e3);

> &map(t1,1,cmulRS,B);
&map(t1,2,cmulRS,B);

> ## ERROR: Note that prefactors are suppressed in unevaluated &t's !!!!!
&map('`&t`'(a*e1,b*e2,e3),1,cmulRS,B);
&map(&t(a*e1,b*e2,e3),1,cmulRS,B);

>

See Also: Cliff5[cmulNUM] , Cliff5[`&c`] , Cliff5[`type/clibasmon`] , Bigebra[&map]