#24232 closed enhancement (fixed)

Simplifications in calculus on manifolds via the expression tree

Reported by: egourgoulhon Owned by:
Priority: major Milestone: sage-8.2
Component: geometry Keywords: manifold calculus
Cc: rws, tscrim, rllozes, mmancini Merged in:
Authors: Eric Gourgoulhon Reviewers: Travis Scrimshaw, Ralf Stephan, Richard L Lozes
Report Upstream: N/A Work issues:
Branch: ec105bb (Commits) Commit: ec105bbb42a97c9ac2bff745112688c655a0ecb4
Dependencies: Stopgaps:

Description

This ticket performs a full reimplementation of the functions

  • sage.manifolds.utilities.simplify_sqrt_real
  • sage.manifolds.utilities.simplify_abs_trig

which are involved in calculus on manifolds (see here). Instead of manipulating string representations of symbolic expressions, as previously, this ticket is based on direct manipulations of the expression tree, via the introduction of two subclasses of ExpressionTreeWalker.

Regarding the functionalities, the code in this ticket leads to the same improvements as those described in #24199, which was based on string manipulations.

Change History (20)

comment:1 Changed 13 months ago by egourgoulhon

  • Branch set to public/manifolds/simplif_tree-24232
  • Cc rws tscrim rllozes mmancini added
  • Commit set to 7e5baa5a956794176c965cd5555c83e79d37b20b
  • Status changed from new to needs_review

New commits:

7e5baa5Reimplement simplifications in calculus on manifolds via the expression tree

comment:2 follow-up: Changed 13 months ago by tscrim

Quick comment, these methods are unnecessary as __init__ will be naturally inherited and so, this would help keep possible bugs out:

    def __init__(self, ex):
        r"""
        Construct a SimplifySqrtReal object.

        TESTS::

            sage: from sage.manifolds.utilities import SimplifySqrtReal
            sage: s = SimplifySqrtReal(1+sqrt((x+1)^2))
            sage: type(s)
            <class 'sage.manifolds.utilities.SimplifySqrtReal'>

        """
        ExpressionTreeWalker.__init__(self, ex)

Moreover, the test does not feel so useful, so I would just delete the whole thing.

comment:3 Changed 13 months ago by git

  • Commit changed from 7e5baa5a956794176c965cd5555c83e79d37b20b to 61d97c242aaa27f446d58af4e15fbe6d16dfe3f8

Branch pushed to git repo; I updated commit sha1. New commits:

61d97c2Remove unnecessary __init__ and slightly change in the treatment of 1/sqrt(...)

comment:4 in reply to: ↑ 2 Changed 13 months ago by egourgoulhon

Replying to tscrim:

Quick comment, these methods are unnecessary as __init__ will be naturally inherited and so, this would help keep possible bugs out:

Moreover, the test does not feel so useful, so I would just delete the whole thing.

Thank you for pointing this. You are of course perfectly right! The above commit suppresses the __init__'s. Moreover, it changes slightly the way pow(x,-1/2) is dealt with: the inverse is now taken at the very end of the simplification. This is more coherent and, on some tests I've performed, this leads to slightly better results.

comment:5 Changed 13 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

LGTM as far as I can tell. Ralf, do you have any comments/suggestions?

comment:6 follow-ups: Changed 13 months ago by rws

  • Milestone changed from sage-8.1 to sage-8.2
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Ralf Stephan
  • Status changed from needs_review to positive_review

Sorry coming late. The tree walking is done and documented well except it would enhance the code somewhat to not call the walker from within the walker, but instead simply call the walker in a loop as long as the result is different from the original. This is still efficient. However note in this case that the most efficient way to compare expressions structurally is to call ex1._gobj.is_equal(ex2._gobj) in a Cython file. Still fast in Python is (ex1-ex2).is_trivial_zero(). I'll open a ticket that exposes is_equal for Python users.

So, for me this is good and, as the other reviewers and patchbots are happy, positive.

comment:7 in reply to: ↑ 6 Changed 13 months ago by rws

Replying to rws:

...but instead simply call the walker in a loop as long as the result is different from the original.

Even better would be to set a flag when you change something and loop as long as the flag is set. If you define the walker class inside the function that calls it you don't even need to make the flag global.

comment:8 in reply to: ↑ 6 Changed 13 months ago by egourgoulhon

Replying to rws:

Sorry coming late.

Well, showing up in a ticket less than 24 h after its creation is not what I would call late ;-) Thank you for your feedback!

The tree walking is done and documented well except it would enhance the code somewhat to not call the walker from within the walker, but instead simply call the walker in a loop as long as the result is different from the original. This is still efficient.

If I understand correctly (which is not guaranteed...), this would change the ordering of simplification. Take for instance the expression

ex = sqrt(a + sqrt(b))

where a and b are potentially complicated expressions. As it is currently, the walker will simplify first sqrt(b) (to c say) and then sqrt(a+c). If we call the walker in a loop as long as the outcome changes, it will first try to simplify sqrt(a + sqrt(b)), leaving sqrt(b) as it is. In the second round only, it will try to simplify sqrt(b). Am I correct? If yes, this would mean that the current version simplifies nested sqrt's from the innermost one to the outermost one, while the loop version will do the opposite. For other type of operations, this may be equivalent, but simplifications are more likely to succeed if we start from the smaller parts, i.e. the innermost ones, like sqrt(b). Do you agree?

However note in this case that the most efficient way to compare expressions structurally is to call ex1._gobj.is_equal(ex2._gobj) in a Cython file. Still fast in Python is (ex1-ex2).is_trivial_zero(). I'll open a ticket that exposes is_equal for Python users.

I've seen it is #24236. This will be very useful, thank you!

comment:9 follow-up: Changed 13 months ago by rws

If I understand correctly (which is not guaranteed...), this would change the ordering of simplification.

Depends on the type of walker which is depth-first with any ExpressionTreeWalker as I understand, so the outcome would be actually the same.

comment:10 in reply to: ↑ 9 Changed 13 months ago by egourgoulhon

Replying to rws:

If I understand correctly (which is not guaranteed...), this would change the ordering of simplification.

Depends on the type of walker which is depth-first with any ExpressionTreeWalker as I understand, so the outcome would be actually the same.

Thanks for your answer. However, I am afraid I still don't understand; when you suggest to not call the walker from within the walker, this amounts to suppress these lines:

                if 'sqrt(' in str(argum):
                    argum = self(argum)  # treatment of nested sqrt's

correct? Then in the example of comment:8, how are we going to reach first sqrt(b)? To be depth-first, it seems to me that some recursion is required, as in the above self(argum).

comment:11 follow-up: Changed 13 months ago by rws

The recursion is provided by the superclasses of the walker.

comment:12 in reply to: ↑ 11 Changed 13 months ago by egourgoulhon

Replying to rws:

The recursion is provided by the superclasses of the walker.

No, it does not seem to be the case, because of the return simpl in line 190 of https://git.sagemath.org/sage.git/tree/src/sage/manifolds/utilities.py?id=0c7b9ea177eeb653de9a2987ea60920acaa96d88

Consider for instance the following example; with the current version, we have

sage: from sage.manifolds.utilities import SimplifySqrtReal
sage: SimplifySqrtReal(sqrt(1 + sqrt(x^2)))()
sqrt(abs(x) + 1)

which is correct, given we have no sign assumption on x. Now, if we replace argum = self(argum) in line 170 of the above file by pass, we get

sage: from sage.manifolds.utilities import SimplifySqrtReal
sage: SimplifySqrtReal(sqrt(1 + sqrt(x^2)))()
sqrt(x + 1)

which is a wrong result; it shows that only the outermost sqrt has been treated, by passing its argument (i.e. 1 + sqrt(x^2)) to radcan, which has oversimplified it to x + 1. Even if we call the walker in a loop until no change happens, there is no way that the x + 1 get transformed to abs(x) + 1. Am I missing something?

comment:13 follow-up: Changed 13 months ago by rws

First, it was nonsense from me to say the walker should not call itself. I forgot that this is done all the time by walkers. Also I naively gave you a solution idea from a different case. Then my dislike just boils down to the usage of str(). The first usage could be replaced with ...has(sqrt(w0)) or ... has(1/sqrt(w0)) with w0=SR.wild(). You test on top of the function for w0^(1/2) and later using str for w0^(1/2) and w0^(-1/2) but you can replace it all with ...match(w0^(1/2)) and ...match(w0^(-1/2)).

I'm sorry that my directions were so completely off this time and that I also forgot to tell about GiNaC/Pynac pattern matching, which of course is faster than any Python solution because expressions are wrapped C++ objects.

comment:14 in reply to: ↑ 13 ; follow-up: Changed 13 months ago by egourgoulhon

Replying to rws:

I'm sorry that my directions were so completely off this time

No problem at all.

and that I also forgot to tell about GiNaC/Pynac pattern matching, which of course is faster than any Python solution because expressions are wrapped C++ objects.

Thank you for your suggestion! I am just implementing the wildcard solution at the moment.

comment:15 in reply to: ↑ 14 Changed 13 months ago by egourgoulhon

  • Status changed from positive_review to needs_work

Replying to egourgoulhon:

Thank you for your suggestion! I am just implementing the wildcard solution at the moment.

Hence the needs_work status.

comment:16 Changed 13 months ago by git

  • Commit changed from 61d97c242aaa27f446d58af4e15fbe6d16dfe3f8 to ec105bbb42a97c9ac2bff745112688c655a0ecb4

Branch pushed to git repo; I updated commit sha1. New commits:

ec105bbUse of wildcards for pattern search in simplifications regarding calculus on manifolds

comment:17 Changed 13 months ago by egourgoulhon

  • Status changed from needs_work to needs_review

The last commit gets rid of any string manipulation in SimplifySqrtReal and SimplifyAbsTrig, following the suggestion in comment:13.

comment:18 follow-up: Changed 13 months ago by rllozes

  • Reviewers changed from Travis Scrimshaw, Ralf Stephan to Travis Scrimshaw, Ralf Stephan, Richard L Lozes
  • Status changed from needs_review to positive_review

Builds and tests cleanly atop 8.1.rc0 on an OpenSUSE 42.2 system. So far, randomly selected worksheets complete successfully and correctly.

My only residual concern is that from an architectural perspective, these corrections and optimizations reflect less than adequate functionality in the main Sage simplification chain. Logically, it appears the changes should go live there, but practically, they must remain inside manifolds/utilities.py.

I should add that the code is now easy to comprehend.

Last edited 13 months ago by rllozes (previous) (diff)

comment:19 in reply to: ↑ 18 Changed 13 months ago by egourgoulhon

Replying to rllozes:

Builds and tests cleanly atop 8.1.rc0 on an OpenSUSE 42.2 system. So far, randomly selected worksheets complete successfully and correctly.

Thank you for these extra tests.

Thank you all for the comments, suggestions and the review!

comment:20 Changed 12 months ago by vbraun

  • Branch changed from public/manifolds/simplif_tree-24232 to ec105bbb42a97c9ac2bff745112688c655a0ecb4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.