You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Generate non-redundant indices of tensors with symmetries efficiently #32318
In sage.tensor.modules.comp.CompWithSym, the method generating non-redundant indices is implemented very inefficiently by going through all indices and throwing away the redundant ones. In the worst case scenario of a rank n tensor in n dimensions, we have to iterate through nn indices only to find the single non-redundant one.
This ticket fixes this by changing the implementation to directly generate only non-redundant indices. This gives for example the following improvement for 7 dimensions:
sage: import timeit
sage: from sage.tensor.modules.comp import Components, CompWithSym, CompFullySym, CompFullyAntiSym
sage: V = VectorSpace(QQ, 7)
sage: c = CompFullyAntiSym(QQ, V.basis(), 7)
sage: timeit.timeit(lambda:list(c.non_redundant_index_generator()),number=1)
new implementation:
4.3510999603313394e-05
old implementation:
2.4149506480007403
I also simplified the method generating redundant indices a bit.
changed the title [-]Performace improvements in generating non-redundant indices of tensors with indices[/-][+]Performace improvements in generating non-redundant indices of tensors with symmetries[/+]on Jul 31, 2021
changed the title [-]Performace improvements in generating non-redundant indices of tensors with symmetries[/-][+]Generate non-redundant indices of tensors with symmetries efficiently[/+]on Jul 31, 2021
Very nice by the way. This could make a significant difference in sophisticated computations (especially since this generator is not cached). I am very curious about the timings of the SageManifolds example notebooks!
Thanks for improving significantly the generator of non-redundant indices!
There is an issue with the ordering of the output though, which affects the display of Christoffel symbols: the output shall respect the ordering of the coordinates, i.e. the doctests should not be modified.
Thanks for improving significantly the generator of non-redundant indices!
There is an issue with the ordering of the output though, which affects the display of Christoffel symbols: the output shall respect the ordering of the coordinates, i.e. the doctests should not be modified.
Is that really important? The order in which the components of tensors are displayed is a matter of personal taste, the mathematical results are the same anyway. Generating the indices in exactly the same order as we did previously would make the algorithm significantly more complicated.
I really dislike the usage of flags within loops, in this case step_finished. My intuition tells me, it should be possible to simplify the code much further. But I immediately don't see how.
But this is personal taste, and for now this should be fine.
I really dislike the usage of flags within loops, in this case step_finished. My intuition tells me, it should be possible to simplify the code much further. But I immediately don't see how.
PEP8 recommends 2 spaces before inline comments
(and some suggested rephrasings):
- return # end point reached+ return # end point reached
- sym = self._sym.copy() # we may modify this in the following+ sym = self._sym.copy() # make a copy we can modify
- step_finished = False # each step generates a new index+ step_finished = False # each step generates a new index
+ return # end point reach+ return # end point reached
Longer comments can go on their own line(s)
(and sometimes be made a bit shorter):
- sym.append([pos]) # treat non-symmetrized indices as being symmetrized with themselves+ # treat non-symmetrized indices as symmetrized with themselves+ sym.append([pos])
- return # we went through all indices and didn't- # find one which we can increase, thus we- # have generated all indices+ # we went through all indices and none could be+ # increased, so we have generated all indices+ return
The following give the same boolean:
not any([a in b for b in c]) and not any([a in b for b in d])
all(a not in b for e in (c, d) for b in e)
so one could rewrite:
- if not any([pos in isym for isym in sym]) and not any([pos in isym for isym in antisym]):+ if all(pos not in isym for xsym in (sym, antisym) for isym in xsym):
Calling the flag done rather than step_finished,
one would read: if not done: ....
Possible rewriting given how Python
turns numbers and lists to booleans:
- if not step_finished and i == 0 and len(antisym) == 0:+ if not step_finished and not i and not antisym:
Maybe shorten this comment:
- # this index is at the maximum and we have- # to reset it+ # this index is at the maximum; reset it
Maybe add spaces around + and -, and after commas,
in several instances of:
I ponder, is the outer while-loop even necessary? Couldn't you just split this whole thing into two separated loops and yield within those? Then the code gets much simpler and the flag becomes obsolete.
I really dislike the usage of flags within loops, in this case step_finished. My intuition tells me, it should be possible to simplify the code much further. But I immediately don't see how.
Possible rewriting given how Python
turns numbers and lists to booleans:
- if not step_finished and i == 0 and len(antisym) == 0:+ if not step_finished and not i and not antisym:
Personally, I don't agree with that one. Of course, not i is more pythonic, but I find it less readable than i == 0, especially in the current context, where i is an integer.
Activity
[-]Performace improvements in generating non-redundant indices of tensors with indices[/-][+]Performace improvements in generating non-redundant indices of tensors with symmetries[/+][-]Performace improvements in generating non-redundant indices of tensors with symmetries[/-][+]Generate non-redundant indices of tensors with symmetries efficiently[/+]sagetrac-git commentedon Aug 1, 2021
Changed commit from
a60d93cto1c108d8sagetrac-git commentedon Aug 1, 2021
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
1c108d8tensor module components: non-redundant index generator: performance improvementsmjungmath commentedon Aug 5, 2021
Haven't checked the algorithm yet, but here are already some minor comments:
self._symcopied butself._antisymnot? From the first glimpse, a copy doesn't seem to be necessary anyway.mjungmath commentedon Aug 5, 2021
Very nice by the way. This could make a significant difference in sophisticated computations (especially since this generator is not cached). I am very curious about the timings of the SageManifolds example notebooks!
egourgoulhon commentedon Aug 5, 2021
Thanks for improving significantly the generator of non-redundant indices!
There is an issue with the ordering of the output though, which affects the display of Christoffel symbols: the output shall respect the ordering of the coordinates, i.e. the doctests should not be modified.
MariusGerbershagen commentedon Aug 5, 2021
Replying to @egourgoulhon:
Is that really important? The order in which the components of tensors are displayed is a matter of personal taste, the mathematical results are the same anyway. Generating the indices in exactly the same order as we did previously would make the algorithm significantly more complicated.
7 remaining items
egourgoulhon commentedon Aug 7, 2021
Thanks for the changes!
Michael, do you agree with the positive review?
egourgoulhon commentedon Aug 7, 2021
Reviewer: Eric Gourgoulhon, Michael Jung
mjungmath commentedon Aug 7, 2021
I really dislike the usage of flags within loops, in this case
step_finished. My intuition tells me, it should be possible to simplify the code much further. But I immediately don't see how.But this is personal taste, and for now this should be fine.
mjungmath commentedon Aug 7, 2021
This is a huge improvement though. Thank you Marius!
MariusGerbershagen commentedon Aug 7, 2021
Replying to @mjungmath:
If only python had a goto statement...
slel commentedon Aug 7, 2021
Minor comments, feel free to ignore any or all of them.
Possible simplification for getting a sorted list:
PEP8 recommends 2 spaces before inline comments
(and some suggested rephrasings):
Longer comments can go on their own line(s)
(and sometimes be made a bit shorter):
The following give the same boolean:
not any([a in b for b in c]) and not any([a in b for b in d])all(a not in b for e in (c, d) for b in e)so one could rewrite:
Calling the flag
donerather thanstep_finished,one would read:
if not done: ....Possible rewriting given how Python
turns numbers and lists to booleans:
Maybe shorten this comment:
Maybe add spaces around + and -, and after commas,
in several instances of:
mjungmath commentedon Aug 7, 2021
I ponder, is the outer while-loop even necessary? Couldn't you just split this whole thing into two separated loops and
yieldwithin those? Then the code gets much simpler and the flag becomes obsolete.mjungmath commentedon Aug 7, 2021
Replying to @spaghettisalat:
http://entrian.com/goto/ :P
egourgoulhon commentedon Aug 9, 2021
Replying to @slel:
Personally, I don't agree with that one. Of course,
not iis more pythonic, but I find it less readable thani == 0, especially in the current context, whereiis an integer.vbraun commentedon Sep 5, 2021
Changed branch from public/tensor-indices to
08ccd3b