Improved canonicalization algorithm

[Ben Niehoff]

Hi all,

I have written a paper on an improved canonicalization algorithm which may be of interest to those of you working on xAct.  It is especially aimed at improving performance with symmetric and antisymmetric tensors, but it contains other improvements for the general case:

https://arxiv.org/abs/1702.08114

Cheers,
Ben Niehoff

[Thomas Bäckdahl]

Hi!

This is very interesting.

I don't know if you have noted that the xPerm implementation is unfortunately not the full Butler-Portugal algorithm because at one point a base change should be made. This is skipped in the current implementation resulting in a slightly quicker algorithm, but without full canonicalization. This means that some expressions with several terms are not canonicalized to zero even if they are zero due to single term symmetries. This is not dangerous, but not as good as it is supposed to be. The Mathematica code version of xPerm uses a base change though, but the implementation is much slower.

I started to implement a base change algorithm in xPerm (available in the latest version), but I have not had time to change the main canonicalization algorithm to use it.

Feel free to take a look at it and perhaps implement your version too. I would suggest to add it as a new function in the external c-code so it will be easy to compare with the old one and use the old one if something breaks. The external c-code is a bit cumbersome to work with due to the C90 standard and memory allocation etc., but it can be done.

Kindest regards

Thomas

--
You received this message because you are subscribed to the Google Groups "xAct Tensor Computer Algebra" group.
To unsubscribe from this group and stop receiving emails from it, send an email to xact+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kasper Peeters]

> I would suggest to add it as a new function in the external
> c-code so it will be easy to compare with the old one and use the old
> one if something breaks. The external c-code is a bit cumbersome to
> work with due to the C90 standard and memory allocation etc., but it
> can be done.

I have a version of xperm.c which compiles fine on current standard
compilers (e.g. clang on macOS) without requiring the C90 oddities.
Available in the cadabra2 repository at

http://github.com/kpeeters/cadabra2

in the 'core/modules/xperm_new.cc' file (and associated .hh). You need
to compile it with a C++ compiler because I used some C++ things
internally, but you can still call the functions from C. Have not yet
tried to use it from within xAct though.

However, I agree with Thomas that it is a bit cumbersome and could do
with more documentation. It _might_ be a better long term solution to
write a clean version from scratch, using the C++ standard library
throughout for memory management, though you don't have to explain
to me how that would eat your time...

Cheers,
Kasper

[Ben Niehoff]

Hi Thomas,

I don't know if you have noted that the xPerm implementation is unfortunately not the full Butler-Portugal algorithm because at one point a base change should be made. This is skipped in the current implementation resulting in a slightly quicker algorithm, but without full canonicalization. This means that some expressions with several terms are not canonicalized to zero even if they are zero due to single term symmetries. This is not dangerous, but not as good as it is supposed to be.

I'm a little confused by this.  It seems to me that one can always canonicalize fully, including detecting whether a term is zero, without making a base change; in fact, the base change only affects one's definition of "canonical", because it changes the sort order of the index labels.  Is there a particular example you can give of where the current implementation in xPerm fails to fully simplify an expression?
 

The Mathematica code version of xPerm uses a base change though, but the implementation is much slower.

I started to implement a base change algorithm in xPerm (available in the latest version), but I have not had time to change the main canonicalization algorithm to use it.

Feel free to take a look at it and perhaps implement your version too. I would suggest to add it as a new function in the external c-code so it will be easy to compare with the old one and use the old one if something breaks. The external c-code is a bit cumbersome to work with due to the C90 standard and memory allocation etc., but it can be done.

I am certainly aiming to write a clean version of the algorithm in C.  I might not get to it right away, I have several projects going on at the moment.  :)

Ben

[Thomas Bäckdahl]

Hi!

See this example for a case when a spinor expression which is zero is not canonicalized to zero with the external c-code but is canonicalized to zero without the c-code. This is due to the base change in the algorithm. If you set up the symmetry of the tensor to be the same group but with a different base you can get zero.

Regards
Thomas

--
You received this message because you are subscribed to the Google Groups "xAct Tensor Computer Algebra" group.

To unsubscribe from this group and stop receiving emails from it, send an email to xact+uns...@googlegroups.com.

[Ben Niehoff]

Hi Thomas,

Thanks for the example.  I have just verified that my algorithm correctly returns zero in this situation, and I definitely use only the lexicographic base order, with no on-the-fly base changes.  So I'm not sure what xperm.c isn't seeing here.

Ben