Opened 22 months ago
Closed 22 months ago
#24232 closed enhancement (fixed)
Simplifications in calculus on manifolds via the expression tree
Reported by:  egourgoulhon  Owned by:  

Priority:  major  Milestone:  sage8.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 22 months ago by
 Branch set to public/manifolds/simplif_tree24232
 Cc rws tscrim rllozes mmancini added
 Commit set to 7e5baa5a956794176c965cd5555c83e79d37b20b
 Status changed from new to needs_review
comment:2 followup: ↓ 4 Changed 22 months ago by
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 22 months ago by
 Commit changed from 7e5baa5a956794176c965cd5555c83e79d37b20b to 61d97c242aaa27f446d58af4e15fbe6d16dfe3f8
Branch pushed to git repo; I updated commit sha1. New commits:
61d97c2  Remove unnecessary __init__ and slightly change in the treatment of 1/sqrt(...)

comment:4 in reply to: ↑ 2 Changed 22 months ago by
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 22 months ago by
 Reviewers set to Travis Scrimshaw
LGTM as far as I can tell. Ralf, do you have any comments/suggestions?
comment:6 followups: ↓ 7 ↓ 8 Changed 22 months ago by
 Milestone changed from sage8.1 to sage8.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 (ex1ex2).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 22 months ago by
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 22 months ago by
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(ex1ex2).is_trivial_zero()
. I'll open a ticket that exposesis_equal
for Python users.
I've seen it is #24236. This will be very useful, thank you!
comment:9 followup: ↓ 10 Changed 22 months ago by
If I understand correctly (which is not guaranteed...), this would change the ordering of simplification.
Depends on the type of walker which is depthfirst with any ExpressionTreeWalker
as I understand, so the outcome would be actually the same.
comment:10 in reply to: ↑ 9 Changed 22 months ago by
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 depthfirst 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 depthfirst, it seems to me that some recursion is required, as in the above self(argum)
.
comment:11 followup: ↓ 12 Changed 22 months ago by
The recursion is provided by the superclasses of the walker.
comment:12 in reply to: ↑ 11 Changed 22 months ago by
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 followup: ↓ 14 Changed 22 months ago by
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 ; followup: ↓ 15 Changed 22 months ago by
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 22 months ago by
 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 22 months ago by
 Commit changed from 61d97c242aaa27f446d58af4e15fbe6d16dfe3f8 to ec105bbb42a97c9ac2bff745112688c655a0ecb4
Branch pushed to git repo; I updated commit sha1. New commits:
ec105bb  Use of wildcards for pattern search in simplifications regarding calculus on manifolds

comment:17 Changed 22 months ago by
 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 followup: ↓ 19 Changed 22 months ago by
 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.
comment:19 in reply to: ↑ 18 Changed 22 months ago by
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 22 months ago by
 Branch changed from public/manifolds/simplif_tree24232 to ec105bbb42a97c9ac2bff745112688c655a0ecb4
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Reimplement simplifications in calculus on manifolds via the expression tree