cmulNUM.html

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

Calling Sequence:

c3 := cmuNUM(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:

c1 : 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 an 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, but since it 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 chosen bilinear form.

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

The evaluation of Clifford products in a Graßmann basis is quite involved and normally is done by a recursive process that involves Chevalley deformation. This approach has been employed in cmulNUM. However, Hopf algebraic methods can be applied also, see cmulRS . Unfortunately, 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.

We introduce the Chevalley deformation and the Clifford map to explain the algorithm used in cmulNUM. The Clifford map is defined as (x in V, u in /\V)

(u) = LC(x,u,B) + x /\ u = x _|B u + x /\ u
= + B(x,y)*
= a* + b*

One knows how to compute with the wedge x /\ u and the contraction LC(x,u,B) = x _|B u, (see the help page Cliff5[LC] for more information on the left contraction) remember the following relations for x,y, in V and u,v,w, in /\V:

(1) x _|B y = B(x,y)
(2) x _|B (u /\ v) = ( x _|B u) /\ v + u^ /\ (x _|B v)
(3) (u /\ v ) _|B w = u _|B ( v _|B w)

where u^ is the Graßmann grade involution. Hence we can use the Clifford map (Chevaley deformation of the Graßmann algebra) to define a Clifford product of a one-vector and a multivector. Analogous formulas can be given for a right Clifford map using the right contraction. See Cliff5[RC] for help on right contraction. Below, the right contraction is denoted by |_ .

The Clifford product '&c' can now be defined as follows: We have to split off a single element from the first factor of a product of two Graßmann basis monoms and then use Chevalley's Clifford map (parentheses ( ) are employed for better readability and to show precedence of the involved operations, usually contractions have a higher precedence as wedge prodcuts as Clifford product to allow dropping parentheses):

(eaw..webwec) &c (efw..weg) = (eaw..wewb &c ec) &c (efw..weg) - (eaw..web B |_ ec ) &c (efw..weg)
= (eaw..wewb) &c (ec _|B (efw..weg) + ecwefw..weg) - ( eaw..web B |_ ec ) &c (efw..weg)

e.g. for (e1we2) &c (e3we4) we have

(e1we2) &c (e3we4) = ( e1 &c e2 ) &c (e3we4) - (B(e1,e2) Id) &c (e3we4)
= e1 &c (B(e2,e3) e4 - B(e2,e4) e3) + e2we3we4) - B(e1,e2) (Id) &c (e3we4)

a second recursion of the process gives now

= B(e2,e3)B(e1,e4) - B(e2,e4)B(e1,e3) + B(e2,e3) e1we4 - B(e2,e4) e1we3
+ B(e1,e2)e3we4 - B(e1,e3) e2we4 + B(e1,e4) e2we3 + e1we2we3we4 - B(e1,e2)e3we4

with the bolded terms cancelling out. Note that the last term in the rhs was generated (superfluously) in the first step of the recursion.

The Clifford product can be derived from the above recursion. The induction starts with a left factor of grade one or grade zero which is trivial, i.e. Id &c eaw..web = eaw..web. In the case that the left factor is of grade one we use the Clifford product expressed by the Clifford map of Chevalley, i.e. ea &c ebw..wec = ea _|B ebw..wec + eawebw..wec. We make a complete induction in the following way. If the left factor is of higher grade, say n, one application of the recursion yields Clifford products where the left factor side is of grade either n-1 or n-2, hence the recursion stops after at most n-1 steps.

A disadvantage of the recursive approach is that additional terms are produced by shifting Graßmann wedge products into Clifford products to swap one factor to the right. These terms cancel out, but this process increases unnecessarily computing time.

An advantage of the recursive approach occurs when the bilinear form B is numeric and sparse (many zeros in the matrix of B). In this case after any recursion many terms are dropped (since Maple simplifies such expresions immediately) and only a few remaining terms enter the next step of the recursion. If the dimension of V is larg i.e. dim_V >=6, sparse matrices benefit drastically from this process over the Hopf algebraic approch of cmulRS which computes all terms without benefiting from the special (sparse numeric) form of the bilinear form.

One could think about shifting factors from right to left, however this works out in the same way. Moreover, if the grade of the left factor n is greater than the grade m of the right factor, then the recursion stops also (since the terms evaluate to zero) after at most n-1 steps, so no increase in performance can be gained this way.

For clarity and to show our approch we display the (simplified) algorithm of cmulNUM:

cmulNUM(x,y,B) ## x,y, clibasmons and B a bilinear form
begin
if x = 0 or y = 0 then RETURN(0) fi # first assumption about the induction
if y = Id then RETURN(x) fi # Id is unit
lstx <- extract indices from x
NX <- |x|
if NX = 0 then RETURN(coefficient_of(x)*y) # handles terms like a*Id &c u
elif NX = 1 then # first basis of recursion
lsty <- extract indices from y
RETURN( reorder -> (
makeclibasmon(cat->(lstx[1],lsty))
+sum i in 1..|lsty| ((-1)^(i-1)*B[lstx[1],lsty[i]]*makeclibasmon(lsty minus lsty[i]))
));
elif NX = 2 then # second basis of recursion
x1 <- first vector of x
x2 <- second vector of x
RETURN(clibilinear -> cmulNUM(x1,cmulNUM(x2,y,B),B)-B[lstx]*y)
fi # and the actual recursion for the remaining cases
xn <- last vector of x
xr <- first to prelast vectors
RETURN(clibilinear -> ( cmulNUM(xr,cmulNUM(xn,xr,B),B) )
-add (i in 1..NX-1) ((-1)^(i)*B[lst[NX-i],lstx[NX]]*
*cmulNUM(makeclibasmon(lstx minus lstx[i]),y,B)))
end cmulNUM

The function clibilinear is used to make functions bilinear which can act on basmonoms only. A reasonable amount of computation is hidden in this statement.

References:
[1] 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 ...

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

Now let us go for more complicated monoms:

> cmulNUM(e1we2,e2we3,B);
cmulNUM(e1we2we3,e1we2we3,T);
cmulNUM(e1we2we3,e4we5we6,-T);

To perform some benchmarks, we need some random basmonoms:

> dim_V:=9:
rd:=rand(0..dim_V):
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 cmulNUM to be faster as cmulRS in the sparse numeric case, we explore this case here, for a benchmark with a symbolic matrix B see Cliff5[cmulRS] .

> B:=linalg[randmatrix](dim_V,dim_V,sparse,entries=rand(-1..1));

Test the bilinear form (third line):

> seq(cmulNUM(e3,cat(e,i),B),i=1..7);

And benchmark with this bilinear form the two cmul functions:

> 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 22.272000 seconds

computation with cmulNUM needed 14.641000 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 1.4 in this setting, which is reasonable (since we had a mixture of higher and lower grades and only the higher terms compute really faster).

Note that one can increase 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),1,cmulRS,B);
&map(&t(a*e1,b*e2),1,cmulRS,B);

>

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