1
CVIT - PROGRAM FOR FAST CALCULATION OF DIRAC'S
GAMMA-MATRICES TRACES
(Version: 1.2. Release: March, 11, 1990)
V.Ilyin, A.Kryukov, A.Rodionov, A.Taranov
Institute for Nuclear Physics
Moscow State University
Moscow, 119899 USSR
Phone 939-58-92
Telex 411483 MGU SU
Fax (011)7095-939-01-26
ABSTRACT
In modern high energy physics the calculation of Feynman
diagrams are still very important. One of the difficulties of
these calculations are trace calculations. So the calculation
of traces of Diracs gamma-matrices were one of first task of
computer algebra systems. All available algorithms are based
on the fact that gamma-matrices constitute a basis of a
Clifford algebra:
{Gm,Gn} = 2gmn.
We present the implementation of an alternative algorithm
based on treating of gamma-matrices as 3-j symbols (details
may be found in [1,2].
The program consists of 5 modules described below.
2
MODULES CROSS REFERENCES
IMMMMMMMM;
: REDUCE GDDDDDDDDDDD<DDDDDD?
HMMMMMMQM< 3ISIMP1
ISIMP23 IMMMMMMMMMMOMMMMMMMMMMMM;
@DDD>DDDDD6 RED_TO_CVIT_INTERFACE :
HMMMMMQMMMMMMMMMMQMMMMMM<
CALC_SPUR3 3REPLACE_BY_VECTOR
3 3REPLACE_BY_VECTORP
3 3GAMMA5P
A V
IOMMMMMMMMMMOMM;
: CVITMAPPING :
HMMMMMMQMMMMMMM<
A
3PRE-CALC-MAP
3CALC_MAP_TAR
3CALC_DENTAR
IMMMMMMOMMMMMM;
: INTERFIERZ :
HMMQMMMMMMMMMQ<
3 3MK-NUMR
3 3STRAND-ALG-TOP
3 A
MAP-TO-STRAND3 IMMMMOMMMMMMM;
INCIDENT13 : EVAL-MAPS :
3 HMMMMMMMMMMQM<
A 3DELETEZ1
3 3CONTRACT-STRAND
IMMMMMMMMMOMMMMMM; 3COLOR-STRAND
: MAP-TO-STRAND GDDDD>DDDY
HMMMMMMMMMMMMMMMM<
Requires of REDUCE version: 3.2, 3.3.
Module RED!_TO!_CVIT!_INTERFACE
Author: A.P.Kryukov
Purpose:interface REDUCE and CVIT package
RED!_TO!_CVIT!_INTERFACE module is intended for
connection of REDUCE with main module of CVIT package. The
main idea is to preserve standard REDUCE syntax for high
3
energy calculations. For realization of this we redefine
SYMBOLIC PROCEDURE ISIMP1 from HEPhys module of REDUCE system.
After loading CVIT package user may use switch CVIT which
is ON by default. If switch CVIT is OFF then calculations of
Diracs matrices traces are performed using standard REDUCE
facilities. If CVIT switch is ON then CVIT package will be
active.
RED!_TO!_CVIT!_INTERFACE module performs some primitive
simplification and control input data independently. For
example it remove GmGm, check parity of the number of Diracs
matrices in each trace etc. There is one principal
restriction concerning G5-matrix. There are no closed form for
trace in non-integer dimension case when trace include G5-
matrix. The next restriction is that if the space-time
dimension is integer then it must be even (2,4,6,...). If
these and other restrictions are violated then the user get
corresponding error message. List of messages is included.
LIST OF IMPORTED FUNCTIONS
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
Function From module
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
ISIMP2 HEPhys
CALC!_SPUR CVITMAPPING
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
4
LIST OF EXPORTED FUNCTION
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
Function To module
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
ISIMP1 HEPhys (redefine)
REPLACE!_BY!_VECTOR EVAL!_MAP
REPLACE!_BY!_VECTORP EVAL!_MAP
GAMMA5P CVITMAPPING, EVAL!_MAP
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
Module CVITMAPPING
Author: A.Ya.Rodionov
Purpose: graphs reduction
CVITMAPPING module is intended for diagrams calculation
according to Cvitanovic - Kennedy algorithm. The top function
of this module CALC!_SPUR is called from
RED!_TO!_CVIT!_INTERFACE interface module. The main idea of
the algorithm consists in diagram simplification according to
rules (1.9') and (1.14) from [1]. The input data - trace of
Diracs gamma matrices (G-matrices) has a form of a list of
identifiers lists with cyclic order. Some of identifiers may
be identical. In this case we assume summation over dummy
indices. So trace Sp(GbGr).Sp(GwGbGcGwGcGr) is represented as
list ((b r) (w b c w c r)).
The first step is to transform the input data to "map"
structure and then to reduce the map to a "simple" one. This
transformation is made by function TRANSFORM!_MAP!_ (top
function). Transformation is made in three steps. At the first
step the input data are transformed to the internal form - a
5
map (by function PREPARE!_MAP!_). At the second step a map is
subjected to Fierz transformations (1.14) (function
MK!_SIMPLE!_MAP!_). At this step of optimization can be maid
(if switch CVITOP is on) by function MK!_FIRZ!_OP. In this
case Fierzing starts with linked vertices with minimal
distance (number of vertices) between them. After Fierz
transformations map is further reduced by vertex
simplification routine MK!_SIMPLE!_VERTEX using (1.9').
Vertices reduced to primitive ones, that is to vertices with
three or less edges. This is the last (third) step in
transformation from input to internal data.
The next step is optional. If switch CVITBTR is on
factorisation of bubble (function FIND!_BUBBLES1) and triangle
(function FIND!_TRIANGLES1) submaps is made. This
factorisation is very efficient for "wheel" diagrams and
unnecessary for "lattice" diagrams. Factorisation is made
recursively by substituting composed edges for bubbles and
composed vertices for triangles. So check (function
SORT!_ATLAS) must be done to test possibility of future
marking procedure. If the check fails then a new attempt to
reorganize atlas (so we call complicated structure witch
consists of MAP, COEFFicient and DENOMinator) is made. This
cause backtracking (but very seldom). Backtracking can be
traced by turning on switch CVITRACE. FIND!_BUBLTR is the top
function of this program's branch.
Then atlases must be prepared (top function
WORLD!_FROM!_ATLAS) for final algebraic calculations. The
resulted object called "world" consists of edges names list
6
(EDGELIST), their marking variants (VARIANTS) and WORLD1
structure. WORLD1 structure differs from WORLD structure in
one point. It contains MAP2 structure instead of MAP
structure. MAP2 is very complicated structure and consist of
VARIANTS, marking plan and GSTRAND. (GSTRAND constructed by
PRE!-CALC!-MAP!_ from INTERFIERZ module.) By marking we
understand marking of edges with numbers according to
Cvitanovic - Kennedy algorithm.
The last step is performed by function CALC!_WORLD. At
this step algebraic calculations are done. Two functions
CALC!_MAP!_TAR and CALC!_DENTAR from INTERFIERZ module make
algebraic expressions in the prefix form. This expressions are
further simplified by function REVAL. This is the REDUCE
system general function for algebraic expressions
simplification. REVAL and SIMP!* are the only REDUCE functions
used in this module.
There are also some functions for printing several
internal structures: PRINT!_ATLAS, PRINT!_VERTEX, PRINT!_EDGE,
PRINT!_COEFF, PRINT!_DENOM. This functions can be used for
debugging.
If an error occur in module CVITMAPPING the error message
"ERROR IN MAP CREATING ROUTINES" is displayed. Error has
number 55. The switch CVITERROR allows to give full
information about error: name of function where error occurs
and names and values of function's arguments. If CVITERROR
switch is on and backtracking fails message about error in
SORT!_ATLAS function is printed. The result of computation
7
however will be correct because in this case factorized
structure is not used. This happens extremely seldom.
List of imported function
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
function from module
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
REVAL REDUCE
SIMP!* REDUCE
CALC!_MAP!_TAR INTERFIERZ
CALC!_DENTAR INTERFIERZ
PRE!-CALC!-MAP!_ INTERFIERZ
GAMMA5P RED!_TO!_CVIT!_INTERFACE
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
List of exported function
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
function to module
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
CALC!_SPUR REDUCE - CVIT interface
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
Data structure
WORLD ::= (EDGELIST,VARIANTS,WORLD1)
WORLD1 ::= (MAP2,COEFF,DENOM)
MAP2 ::= (MAPS,VARIANTS,PLAN)
MAPS ::= (EDGEPAIR . GSTRAND)
MAP1 ::= (EDGEPAIR . MAP)
MAP ::= list of VERTICES (unordered)
EDGEPAIR ::= (OLDEDGELIST . NEWEDGELIST)
COEFF ::= list of WORLDS (unordered)
ATLAS ::= (MAP,COEFF,DENOM)
GSTRAND ::= (STRAND*,MAP,TADPOLES,DELTAS)
VERTEX ::= list of EDGEs (with cyclic order)
EDGE ::= (NAME,PROPERTY,TYPE)
NAME ::= ATOM
PROPERTY ::= (FIRSTPAIR . SECONDPAIR)
TYPE ::= T or NIL
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
*Define in module MAP!-TO!-STRAND.
8
Modules INTERFIERZ, EVAL_MAPS, AND MAP-TO-STRAND.
Author: A.Taranov
Purpose: evaluate single Map
Module INTERFIERZ exports to module CVITMAPPING three
functions: PRE-CALC-MAP_, CALC-MAP_TAR, CALC-DENTAR.
Function PRE-CALC-MAP_ is used for preliminary processing
of a map. It returns a list of the form (STRAND NEWMAP
TADEPOLES DELTAS) where
STRAND is strand structure described in MAP-TO-STRAND module.
NEWMAP is a map structure without "tadepoles" and "deltas".
"Tadepole" is a loop connected with map with only one line
(edge). "Delta" is a single line disconnected from a map.
TADEPOLES is a list of "tadepole" submaps.
DELTAS is a list (CONS E1 E2) where E1 and E2 are
Function CALC_MAP_TAR takes a list of the same form as
returned by PRE-CALC-MAP_, a-list, of the form
(... edge . weight ... ) and returns a prefix form of
algebraic expression corresponding to the map numerator.
Function CALC-DENTAR returns a prefix form of algebraic
expression corresponding to the map denominator.
Module EVAL-MAP exports to module INTERFIERZ functions
MK-NUMR and STRAND-ALG-TOP.
Function MK-NUMR returns a prefix form for some
combinatorial coefficient (Pohgammer symbol).
Function STRAND-ALG-TOP performs an actual computation of
a prefix form of algebraic expression corresponding to the map
9
numerator. This computation is based on a "strand" structure
constructed from the "map" structure"
Module MAP-TO-STRAND exports functions MAP-TO-STRAND,
INCIDENT1 to module INTERFIERZ and functions DELETEZ1,
CONTRACT-STRAND, COLOR-STRAND to module EVAL-MAPS.
Function INCIDENT1 is a selector in "strand" structure.
DELETEZ1 performs auxiliary optimization of "strand".
MAP-TO-STRAND transforms "map" to "strand" structure. The
latter is describe in program module.
CONTRACT-STRAND do strand vertex simplifications of
"strand" and COLOR-STRAND finishes strand generation.
Description of STRAND data structure.
STRAND ::=<LIST OF VERTEX>
VERTEX ::=<NAME> . (<LIST OF ROAD> <LIST OF ROAD>)
ROAD ::=<ID> . NUMBER
NAME ::=NUMBER
LIST OF MESSAGES:
CALC!_SPUR: <vecdim> IS NOT EVEN SPACE-TIME DIMENSION
The dimension of space-time <vecdim> is integer but not
even. Only even numeric dimensions are allowed.
NOSPUR NOT YET IMPLEMENTED
Attempt to calculate trace when NOSPUR switch is on.
This facility is not implemented now.
G5 INVALID FOR VECDIM NEQ 4
Attempt to calculate trace with gamma5-matrix for space-
time dimension not equal to 4.
10
CALC!_SPUR: <expr> HAS NON-UNIT DENOMINATOR
The <expr> has non-unit denominator.
THREE INDICES HAVE NAME <name>
There are three indices with equal names in evaluated
expression.
List of switches
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
switch default comment
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
CVIT ON If it is on then use Kennedy-
Cvitanovic algorithm else use
standard facilities.
CVITOP OFF Fierz optimization switch
CVITBTR ON Bubbles and triangles
factorisation switch
CVITRACE OFF Backtracking tracing switch
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
11
Functions cross references*.
CALC!_SPUR
3
@DD>SIMP!* (REDUCE)
3
@DD>CALC!_SPUR0
3
CDDD>TRANSFORM!_MAP!_
3 3
3 CDDD>MK!_SIMPLE!_VERTEX
3 @DDD>MK!_SIMPLE!_MAP!_
3 3
3 @DDD>MK!_SIMPLE!_MAP!_1
3 3
3 @DDD>MK!_FIERS!_OP
3
CDDD>WORLD!_FROM!_ATLAS
3 3
3 @DDD>CONSTR!_WORLDS
3 3
3 @DDDD>MK!_WORLD1
3 3
3 @DDD>MAP!_2!_FROM!_MAP!_1
3 3
3 CDDD>MARK!_EDGES
3 @DDD>MAP!_1!_TO!_STRAND
3 3
3 @DD>PRE!-CALC!-MAP!_
3 (INTERFIRZ)
3
CDDD>CALC!_WORLD
3 3
3 CDDD>CALC!-MAP!_TAR (INTERFIRZ)
3 CDDD>CALC!-DENTAR (INTERFIRZ)
3 @DDD>REVAL (REDUCE)
3
@DDD>FIND!_BUBLTR
3
@DDD>FIND!_BUBLTR0
3
CDDD>SORT!_ATLAS
@DDD>FIND!_BUBLTR1
3
CDDD>FIND!_BUBLES1
@DDD>FIND!_TRIANGLES1
*Unmarked functions are from CVITMPPING module.
12
References
1. Ilyin V.A., Kryukov A.P., Rodionov A.Ya., Taranov A.Yu.
Fast algorithm for calculation of Diracs gamma-matrices
traces. SIGSAM Bull., 1989, v.23, no.4, pp.15-24.
2. Kennedy A.D. Phys.Rev., 1982, D26, p.1936.
Keywords
REDUCE, GAMMA-MATRIX, TRACE, SPACE-TIME DIMENSION, HIGH
ENERGY PHYSICS.