[GiNaC-list] Performance of simplify_indexed on long chains of Dirac matrices

[Vladimir V. Kisil]

	Dear Vladyslav,

	I made some attempts but failed to optimise the GiNaC
  performance in contracting Dirac gammas. In my opinion the reason is,
  that the competitors are tailored for this particular problem and
  the ideology of GiNaC does not allow it to be as effective.

  GiNaC is highly extendable from its design. A user may define a new
  object which will be able to contract with the pre-defined Dirac
  gammas in any manner, which the user will define in his code. So, the
  core GiNaC does not have a choice but proceed in very general (an
  inefficient!) manner: contract or permute one Dirac gamma with
  something else, then make an expansion of the new expression and then
  recursively apply all the previous steps to every new
  sub-expression. So, the number of sub-expression and recursive calls
  (exponentially?) grows with the increment of number of Dirac gammas in
  the initial product.

  If you do need a fast computations with Dirac gammas in GiNaC, then
  you have to derive a new class for them straight from GiNaC::basic and
  implement those algorithms, which other software use. Present gammas
  are derived from GiNaC::indexed and have to obey all generic rules
  implemented in simplify_indexed() method, which are very costly.

  Best wishes,
  Vladimir
-- 
Vladimir V. Kisil     email: kisilv at maths.leeds.ac.uk
                        www: http://www.maths.leeds.ac.uk/~kisilv/
Book: Geometry of Mobius Transformations
http://www.worldscientific.com/worldscibooks/10.1142/p835
>>>>> On Tue, 06 Jan 2015 02:04:41 +0100, Vladyslav Shtabovenko <v.shtabovenko at tum.de> said:

    VS> Dear Vladimir, for the optimization strategy I would have a look
    VS> at what FORM does.

    VS> The algorithm is described here
    VS> <http://www.nikhef.nl/~form/maindir/documentation/reference/online/online.html#gammaalgebra>

    VS> and the corresponding C code is available on GitHub:

    VS> <https://github.com/vermaseren/form/blob/master/sources/opera.c>

    VS> Cheers, Vladyslav



    VS> Am 04.01.2015 um 20:36 schrieb Vladimir V. Kisil:
    >>>>>>> On Sun, 04 Jan 2015 18:53:51 +0100, Vladyslav Shtabovenko
    >>>>>>> <v.shtabovenko at tum.de> said:
    VSh> 1) By repeatedly applying the anticommutation relations to move
    VSh> g_mu through all other matrices to g^mu. This is the easiest
    VSh> but also the slowest way to implement.
    >> 
    >> This is what GiNaC is using, as far as I understand.
    >> 
    VSh> (people mostly care only about traces), it might be reasonable
    VSh> to look at the performance of dirac_trace instead.
    >> 
    >> IMHO, this routine still uses clifford::eval_ncmul(), which I
    >> think is the principal bottleneck.
    >> 
    VSh> takes around 5 seconds on my machine, a similar code with FORM
    VSh> requires less than 0.01 seconds. With FeynCalc
    >> 
    >> Probably, GiNaC will never do a particular task as good as a
    >> specialised software. GiNaC allows to mix all types of objects in
    >> a single expression, so all simplifying algorithms need to be of
    >> a very plain generic nature.
    >> 
    VSh> So I think that it would be very nice if someone of the GiNaC
    VSh> developers could have a look at this issue.
    >> 
    >> I am not familiar with Dirac matrices close enough to optimise
    >> the performance beyond the simple anticommutation. It will be
    >> good if you can come with some optimisation suggestions of
    >> clifford::eval_ncmul().
    >> 
    >> Best wishes, Vladimir
    >>