Simplifications in calculus on manifolds via the expression tree

[egourgoulhon]

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.

CC: @rwst @tscrim @rll2021 @man74cio

Component: geometry

Keywords: manifold calculus

Author: Eric Gourgoulhon

Branch/Commit: ec105bb

Reviewer: Travis Scrimshaw, Ralf Stephan, Richard L Lozes

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

[egourgoulhon]

Commit: 7e5baa5

[egourgoulhon]

Branch: public/manifolds/simplif_tree-24232

[egourgoulhon]

New commits:

7e5baa5

Reimplement simplifications in calculus on manifolds via the expression tree

[tscrim]

comment:2

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7e5baa5 to 61d97c2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

61d97c2

Remove unnecessary `__init__` and slightly change in the treatment of 1/sqrt(...)

[egourgoulhon]

comment:4

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.

[tscrim]

comment:5

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

[tscrim]

Reviewer: Travis Scrimshaw

[rwst]

comment:6

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.

[rwst]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Ralf Stephan

[rwst]

comment:7

Replying to @rwst:

...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.

[egourgoulhon]

comment:8

Replying to @rwst:

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!

[rwst]

comment:9

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.

[egourgoulhon]

comment:10

Replying to @rwst:

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).

[rwst]

comment:11

The recursion is provided by the superclasses of the walker.

[egourgoulhon]

comment:12

Replying to @rwst:

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://github.com/sagemath/sagetrac-mirror/blob/develop/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?

[rwst]

comment:13

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.

[egourgoulhon]

comment:14

Replying to @rwst:

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.

[egourgoulhon]

comment:15

Replying to @egourgoulhon:

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

Hence the needs_work status.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ec105bb

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 61d97c2 to ec105bb

[egourgoulhon]

comment:17

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

[475231fa-940f-4aa9-84a8-a9005512eef0]

comment:18

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.

[475231fa-940f-4aa9-84a8-a9005512eef0]

Changed reviewer from Travis Scrimshaw, Ralf Stephan to Travis Scrimshaw, Ralf Stephan, Richard L Lozes

[egourgoulhon]

comment:19

Replying to @rll2021:

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!

[vbraun]

Changed branch from public/manifolds/simplif_tree-24232 to ec105bb