Opened 5 years ago
Closed 5 years ago
#24232 closed enhancement (fixed)
Simplifications in calculus on manifolds via the expression tree
Reported by:  Eric Gourgoulhon  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  geometry  Keywords:  manifold calculus 
Cc:  Ralf Stephan, Travis Scrimshaw, Richard L Lozes, Marco Mancini  Merged in:  
Authors:  Eric Gourgoulhon  Reviewers:  Travis Scrimshaw, Ralf Stephan, Richard L Lozes 
Report Upstream:  N/A  Work issues:  
Branch:  ec105bb (Commits, GitHub, GitLab)  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 5 years ago by
Branch:  → public/manifolds/simplif_tree24232 

Cc:  Ralf Stephan Travis Scrimshaw Richard L Lozes Marco Mancini added 
Commit:  → 7e5baa5a956794176c965cd5555c83e79d37b20b 
Status:  new → needs_review 
comment:2 followup: 4 Changed 5 years 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 5 years ago by
Commit:  7e5baa5a956794176c965cd5555c83e79d37b20b → 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 Changed 5 years 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 5 years ago by
Reviewers:  → Travis Scrimshaw 

LGTM as far as I can tell. Ralf, do you have any comments/suggestions?
comment:6 followups: 7 8 Changed 5 years ago by
Milestone:  sage8.1 → sage8.2 

Reviewers:  Travis Scrimshaw → Travis Scrimshaw, Ralf Stephan 
Status:  needs_review → 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 Changed 5 years 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 Changed 5 years 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 5 years 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 Changed 5 years 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 5 years ago by
The recursion is provided by the superclasses of the walker.
comment:12 Changed 5 years 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 5 years 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 followup: 15 Changed 5 years 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 Changed 5 years ago by
Status:  positive_review → 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 5 years ago by
Commit:  61d97c242aaa27f446d58af4e15fbe6d16dfe3f8 → 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 5 years ago by
Status:  needs_work → 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 5 years ago by
Reviewers:  Travis Scrimshaw, Ralf Stephan → Travis Scrimshaw, Ralf Stephan, Richard L Lozes 

Status:  needs_review → 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 Changed 5 years 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 5 years ago by
Branch:  public/manifolds/simplif_tree24232 → ec105bbb42a97c9ac2bff745112688c655a0ecb4 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
Reimplement simplifications in calculus on manifolds via the expression tree