


                                                               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.
