Skip to content

Generate non-redundant indices of tensors with symmetries efficiently #32318

Closed

Description

@MariusGerbershagen

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.

CC: @slel @mjungmath @egourgoulhon @tscrim

Component: performance

Author: Marius Gerbershagen

Branch/Commit: 08ccd3b

Reviewer: Eric Gourgoulhon, Michael Jung

Issue created by migration from https://trac.sagemath.org/ticket/32318

Activity

  1. added this to the sage-9.4 milestone on Jul 31, 2021
  2. 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
  3. 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
  4. sagetrac-git commented on Aug 1, 2021

    sagetrac-gitmannequin
    Mannequin

    Changed commit from a60d93c to 1c108d8

  5. sagetrac-git commented on Aug 1, 2021

    sagetrac-gitmannequin
    Mannequin

    Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

    1c108d8tensor module components: non-redundant index generator: performance improvements
  6. mjungmath commented on Aug 5, 2021

    @mjungmath
    Contributor
    comment:6

    Haven't checked the algorithm yet, but here are already some minor comments:

    • Why is self._sym copied but self._antisym not? From the first glimpse, a copy doesn't seem to be necessary anyway.
    • Very minor (PEP norm):
    - for k in range(1,len(isym)):
    + for k in range(1, len(isym)):
  7. mjungmath commented on Aug 5, 2021

    @mjungmath
    Contributor
    comment:7

    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!

  8. egourgoulhon commented on Aug 5, 2021

    @egourgoulhon
    Member
    comment:8

    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.

  9. MariusGerbershagen commented on Aug 5, 2021

    @MariusGerbershagen
    ContributorAuthor
    comment:9

    Replying to @egourgoulhon:

    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.

  10. 7 remaining items

  11. egourgoulhon commented on Aug 7, 2021

    @egourgoulhon
    Member
    comment:16

    Thanks for the changes!
    Michael, do you agree with the positive review?

  12. egourgoulhon commented on Aug 7, 2021

    @egourgoulhon
    Member

    Reviewer: Eric Gourgoulhon, Michael Jung

  13. mjungmath commented on Aug 7, 2021

    @mjungmath
    Contributor
    comment:17

    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.

  14. mjungmath commented on Aug 7, 2021

    @mjungmath
    Contributor
    comment:18

    This is a huge improvement though. Thank you Marius!

  15. MariusGerbershagen commented on Aug 7, 2021

    @MariusGerbershagen
    ContributorAuthor
    comment:19

    Replying to @mjungmath:

    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.

    If only python had a goto statement...

  16. slel commented on Aug 7, 2021

    @slel
    Member
    comment:20

    Minor comments, feel free to ignore any or all of them.

    Possible simplification for getting a sorted list:

    -            generator = list(self.non_redundant_index_generator())
    -            generator.sort()
    +            generator = sorted(self.non_redundant_index_generator())

    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:

    - range(len(sym)-1,-1,-1)
    + range(len(sym) - 1, -1, -1)
  17. mjungmath commented on Aug 7, 2021

    @mjungmath
    Contributor
    comment:21

    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.

  18. mjungmath commented on Aug 7, 2021

    @mjungmath
    Contributor
    comment:22

    Replying to @spaghettisalat:

    Replying to @mjungmath:

    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.

    If only python had a goto statement...

    http://entrian.com/goto/ :P

  19. egourgoulhon commented on Aug 9, 2021

    @egourgoulhon
    Member
    comment:23

    Replying to @slel:

    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.

  20. vbraun commented on Sep 5, 2021

    @vbraun
    Member

    Changed branch from public/tensor-indices to 08ccd3b

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions