Long replacement rules

188 views
Skip to first unread message

TB

unread,
Mar 16, 2010, 7:56:45 AM3/16/10
to xAct Tensor Computer Algebra
Hi!

I get problems when I want to generate replacement rules for tensors
or spinors with many indices and large symmetry groups.

MakeRule, does the job, but the number of rules it creates quickly
becomes huge.

For instance, see the example file ProblemLongReplacementRules.nb
There I want to make a replacement rule from
Eq1=\[CapitalOmega][-A, -B, -C, -D, -F] TT[C, D, F, -P, -Q] ==
SS[-A, -B, -P, -Q]
It results in 28 800 rules, and takes a long time to compute.

Does anyone have an idea of how to do a replacement procedure without
having to produce all these rules?

Let us say that we want to substitute Eq1 in
\[CapitalOmega][S, -B, -C, -D, -A] TT[C, D, -H, -S, -Q]

Perhaps it is possible to make a procedure that looks for products of \
[CapitalOmega] and TT with the right number of indices. Then one needs
to make some sort of test that determines if \[CapitalOmega][S, -B, -
C, -D, -A] TT[C, D, -H, -S, -Q] belongs to the right hand side of any
of the 28 800 rules that can be produced from Eq1 withou calculating
all of them. Then one only needs to apply that rule. Unfortunately I
do not know how to do this kind of test.

Any ideas are welcome.

Regards
Thomas

JMM

unread,
Mar 16, 2010, 1:11:29 PM3/16/10
to xAct Tensor Computer Algebra
Hi Thomas,

Let me start by emphasizing that MakeRule is not supposed to be the
solution for every type of rule you might need. Note that there is no
function in Mathematica which tries to construct general rules. That
would be too difficult. What Mathematica provides is a full language
to construct the rules you might want. xTensor also provides tools to
construct your own rules, and I have designed MakeRule to help users
in more or less simple cases, which can be classified with a few
options. Whenever something becomes big (many indices or many tensors
or many contractions, etc), it is better to construct your own rules
specifically for your problem. There is no hope of having MakeRule
being efficient in all possible cases.

In your particular case, I would start with something like this:

myrule := Omega[oinds__] TT[tinds__] :> With[{
dummies = xAct`xTensor`Private`TakeEPairs[{oinds, tinds}],
frees = xAct`xTensor`Private`TakeFrees[{oinds, tinds}]},
somesign SS @@ frees /;
Length@Intersection[dummies, {oinds}] == 3 &&
Length@Intersection[dummies, {tinds}] == 3
]

This is simple because your three tensors are symmetric, and hence we
do not have to worry about where the indices are. It also assumes that
there are no contractions on either of Omega or TT, because would be
zero by symmetry. You see that in a more general case the rule would
be more complicated. This is the sort of thing that would be difficult
to decide by a MakeRule-type function.

That rule uses some private functions of xTensor, to make it faster,
but could be done with FindIndices, FindFreeIndices, etc. Note that I
haven't bothered to sort out signs, and so you have to find out how to
compute the variable "somesign".

I haven't tested this. Let me know if this works for you. Probably the
conditions at the end should be more careful, but you get the idea.

Cheers,
Jose.

TB

unread,
Mar 16, 2010, 3:11:14 PM3/16/10
to xAct Tensor Computer Algebra
Hi!
Thanks for your code.
I managed to extend it to something much more general.

Instead of deciding beforehand, all possible patterns of index
combinations,
one could use the canonicalizer to determine if an expression can be
transformed
into the left hand side of Eq1.
I think this idea can be used in many more cases than my specific
example.

See the file ProblemLongReplacementRules2.nb for details.

Is this general enough so it is worth implementing a procedure that
can produce similar rules from other equations?

Regards
Thomas

TB

unread,
Mar 16, 2010, 3:42:31 PM3/16/10
to xAct Tensor Computer Algebra
Hi again!

I am sorry for sending too many emails to this group.

I just realized that my method did not work as well as I had hoped.

For instance
\[CapitalOmega][-A, -P, -C, -D, -F] TT[C, D, F, -B, -Q]
will not be treated by the rules because it has a different order of
the free indices.
This means that one might need to produce the same number of rules
as the number of permutations of the free indices (reduced by the
symmetries). 6 in this case. (Times 2 for the different signs.)

This is more difficult to write, but it could work in for many cases
where MakeRule is not the prefered choice.

Regards
Thomas

JMM

unread,
Mar 17, 2010, 7:50:24 PM3/17/10
to xAct Tensor Computer Algebra
Hi Thomas,

I like your idea, but it is not clear how well it scales for more
complicated problems, because in this example we use heavily the fact
that you work with symmetric spinors.

Concerning the problem you mention, it is easy to solve: This is a
small modification of your code, also introducing a Which construct to
avoid having two rules:

myrule := Omega[oinds__] TT[tinds__] :>
With[{
dummies = xAct`xTensor`Private`TakeEPairs[{oinds, tinds}],
frees = xAct`xTensor`Private`TakeFrees[{oinds, tinds}] },

With[{LHS = (TT[C, D, F, ##] & @@ Complement[{tinds}, dummies])
(Omega[-C, -D, -F, ##] & @@ Complement[{oinds},
dummies]) },
Which[
ToCanonical[ Omega[oinds] TT[tinds] - LHS ] === 0, SS @@
frees,
ToCanonical[ Omega[oinds] TT[tinds] + LHS ] === 0, - SS @@


frees
]
] /;
Length@Intersection[dummies, {oinds}] == 3 &&
Length@Intersection[dummies, {tinds}] == 3
]

Cheers,
Jose.

TB

unread,
Mar 18, 2010, 8:40:55 AM3/18/10
to xAct Tensor Computer Algebra
Hi!
This is probably the best way for the particular example, but I am
more interested in a way to generare this kind of rules from quite
general equations.

I managed to slightly modify EqualExpressionsQ to do the missing
parts. See the file ProblemLongReplacementRules3b.nb for details.

I think this idea is general enough to work as an alternative to
MakeRule
in the cases with many symmetries and dummy indices.

I think it does the minimal ammount of tests, except that it uses all
permutations of the free indices. This is still quick for my examples,
but
it could be improved for more complicated ones. Many permutations will
be
equivalent due to the symmetries, but I do not know how to compute
this.
Do you know how to compute all permutations that are not equivalent
with
respect to the symmetries of the free indices of a tensor?
I think this can be related to the ToCanonical[%/.Sym-
>ImposeSymmetry]
problem we discussed earlier.

I tried to write a procedure that can renerate rules like this for
arbitrary products of two tensors. This can also be found in
ProblemLongReplacementRules3b.nb.

Do you like the idea?
Do you think it is worth implementing something as general as MakeRule
for this method?

Regards
Thomas

TB

unread,
Mar 23, 2010, 12:08:41 PM3/23/10
to xAct Tensor Computer Algebra
Hi!

I have tried to find a good and quick way to generate a list of all
permutations of the free indices that are not equivalent with respect
to the symmetries of the free indices.
Unfortunately I have not succeeded.
I can find the group of all permutations of the free indices (G1), and
the group of symmetries of the expression that only involves the free
indices (G2).
Say that one want to do this for expr1:

inds1 = FindIndices@Evaluate@expr1
dummies1 = xAct`xTensor`Private`TakeEPairs@inds1
dummiespos1 = List @@ (First@First@Position[inds1, #, 1] & /@
dummies1)
G1 = Last@Last@SymmetryOf@expr1
G2 = Stabilizer[dummiespos1, G1]

The next problem I suppose is to generate a list of all cosets of G2
in the group G1. Is there a way to do this without generating a list
of all elements in G1 and then elliminate the ones that are not
needed?

The symmetries of the free indices can probably be larger than G2 due
to some strange symmetry that could for instance interchange two free
indices at the same time as two pairs of dymmy indices are
interchanged. It would be complicated to compute this, and for this
purpose one would not gain much, if anything at all.

Another thing:
I found that MakeRule does not care about symmetries of covariant
derivatives with several indices. When working with space spinors one
will have covariant derivatives with two indices that are symmetric,
so there are real cases when one needs this.

Regards
Thomas

TB

unread,
Mar 23, 2010, 12:14:19 PM3/23/10
to xAct Tensor Computer Algebra
I am sorry I mixed up the code.
This is what I did mean to send:

inds1 = FindIndices@Evaluate@expr1
frees1 = FindFreeIndices@Evaluate@expr1


dummies1 = xAct`xTensor`Private`TakeEPairs@inds1
dummiespos1 = List @@ (First@First@Position[inds1, #, 1] & /@
dummies1)

G1=xAct`xTensor`Private`symperms[inds1, frees1]
G2 = Stabilizer[dummiespos1, Last@Last@SymmetryOf@expr1]

Regards
Thomas

JMM

unread,
Mar 23, 2010, 1:14:18 PM3/23/10
to xAct Tensor Computer Algebra
Hi Thomas,

> I have tried to find a good and quick way to generate a list of all
> permutations of the free indices that are not equivalent with respect
> to the symmetries of the free indices.
> Unfortunately I have not succeeded.

It is not a trivial thing.

> I can find the group of all permutations of the free indices (G1), and
> the group of symmetries of the expression that only involves the free
> indices (G2).
> Say that one want to do this for expr1:

(copied here the code from your second email)

>
> inds1 = FindIndices@Evaluate@expr1
> frees1 = FindFreeIndices@Evaluate@expr1

> dummies1 = xAct`xTensor`Private`TakeEPairs@inds1
> dummiespos1 = List @@ (First@First@Position[inds1, #, 1] & /@ dummies1)

> G1=xAct`xTensor`Private`symperms[inds1, frees1]
> G2 = Stabilizer[dummiespos1, Last@Last@SymmetryOf@expr1]

OK.

> The next problem I suppose is to generate a list of all cosets of G2
> in the group G1. Is there a way to do this without generating a list
> of all elements in G1 and then elliminate the ones that are not
> needed?

A list of representatives of the cosets is called a "transversal", and
can be computed using the strong-generating-set description of the
groups, though not very efficiently. Unfortunately xPerm does not yet
have that algorithm. I'll add it at some point. The need for this
algorithm has appeared already, for different reasons, in other
discussions with Alfonso Garcia-Parrado and Guillaume Faye.

> The symmetries of the free indices can probably be larger than G2 due
> to some strange symmetry that could for instance interchange two free
> indices at the same time as two pairs of dymmy indices are
> interchanged. It would be complicated to compute this, and for this
> purpose one would not gain much, if anything at all.

Yes. You use a pointwise stabilizer to compute G2, but what is needed
is a setwise stabilizer, another algorithm not yet present in xPerm.

> Another thing:
> I found that MakeRule does not care about symmetries of covariant
> derivatives with several indices. When working with space spinors one
> will have covariant derivatives with two indices that are symmetric,
> so there are real cases when one needs this.

I've just had a look at the corresponding part of xTensor.nb,
subsection 10.2. Copied from there, in relation to the function
SymmetryEquivalentsOfTensor, which is the function actually called by
MakeRule :

"It would be very simple to generalize this function to arbitrary
expressions (change SymmetryGroupOfTensor to SymmetryOf and compute
indices with FindIndices)"

Perhaps you can modify SymmetryEquivalentsOfTensor to do what you
want. I don't have the time to do this myself.

Cheers,
Jose.

TB

unread,
Apr 7, 2010, 6:51:56 PM4/7/10
to xAct Tensor Computer Algebra
Hi!
I managed to write a code that generates replacement rules for all
cases where the left hand side is a product of tensors.
See the file ProblemLongReplacementRules7.nb

The permutations of the free indices are computed using the pointwise
stabilizer of the symmetry group of the left hand side.
This can be extended to a setwise stabilizer when that is implemented.
The transversal was already implemented in xPerm, so I used that.
There might be better algorithms, but at least it seems to work.

I do not know if my way of coding is safe and efficient, so if anyone
has any comments on this - let me know.
The code is not properly tested yet.

Regards
Thomas Bäckdahl

> ...
>
> read more »

Reply all
Reply to author
Forward
0 new messages