Sage: Ticket #24232: Simplifications in calculus on manifolds via the expression tree
https://trac.sagemath.org/ticket/24232
<p>
This ticket performs a full reimplementation of the functions
</p>
<ul><li><code>sage.manifolds.utilities.simplify_sqrt_real</code>
</li><li><code>sage.manifolds.utilities.simplify_abs_trig</code>
</li></ul><p>
which are involved in calculus on manifolds (see <a class="ext-link" href="http://doc.sagemath.org/html/en/reference/manifolds/sage/manifolds/utilities.html#sage.manifolds.utilities.simplify_chain_real"><span class="icon"></span>here</a>). 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 <a class="ext-link" href="http://doc.sagemath.org/html/en/reference/calculus/sage/symbolic/expression_conversions.html#sage.symbolic.expression_conversions.ExpressionTreeWalker"><span class="icon"></span>ExpressionTreeWalker</a>.
</p>
<p>
Regarding the functionalities, the code in this ticket leads to the same improvements as those described in <a class="closed ticket" href="https://trac.sagemath.org/ticket/24199" title="enhancement: Simplifications in calculus on manifolds with derivatives of symbolic ... (closed: wontfix)">#24199</a>, which was based on string manipulations.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/24232
Trac 1.1.6egourgoulhonFri, 17 Nov 2017 11:15:35 GMTstatus changed; cc, commit, branch set
https://trac.sagemath.org/ticket/24232#comment:1
https://trac.sagemath.org/ticket/24232#comment:1
<ul>
<li><strong>cc</strong>
<em>rws</em> <em>tscrim</em> <em>rllozes</em> <em>mmancini</em> added
</li>
<li><strong>commit</strong>
set to <em>7e5baa5a956794176c965cd5555c83e79d37b20b</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>public/manifolds/simplif_tree-24232</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=7e5baa5a956794176c965cd5555c83e79d37b20b"><span class="icon"></span>7e5baa5</a></td><td><code>Reimplement simplifications in calculus on manifolds via the expression tree</code>
</td></tr></table>
TickettscrimFri, 17 Nov 2017 13:12:07 GMT
https://trac.sagemath.org/ticket/24232#comment:2
https://trac.sagemath.org/ticket/24232#comment:2
<p>
Quick comment, these methods are unnecessary as <code>__init__</code> will be naturally inherited and so, this would help keep possible bugs out:
</p>
<div class="wiki-code"><div class="code"><pre> <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> ex<span class="p">):</span>
<span class="sd">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'>
"""</span>
ExpressionTreeWalker<span class="o">.</span>__init__<span class="p">(</span><span class="bp">self</span><span class="p">,</span> ex<span class="p">)</span>
</pre></div></div><p>
Moreover, the test does not feel so useful, so I would just delete the whole thing.
</p>
TicketgitFri, 17 Nov 2017 16:31:50 GMTcommit changed
https://trac.sagemath.org/ticket/24232#comment:3
https://trac.sagemath.org/ticket/24232#comment:3
<ul>
<li><strong>commit</strong>
changed from <em>7e5baa5a956794176c965cd5555c83e79d37b20b</em> to <em>61d97c242aaa27f446d58af4e15fbe6d16dfe3f8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=61d97c242aaa27f446d58af4e15fbe6d16dfe3f8"><span class="icon"></span>61d97c2</a></td><td><code>Remove unnecessary __init__ and slightly change in the treatment of 1/sqrt(...)</code>
</td></tr></table>
TicketegourgoulhonFri, 17 Nov 2017 16:39:23 GMT
https://trac.sagemath.org/ticket/24232#comment:4
https://trac.sagemath.org/ticket/24232#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:2" title="Comment 2">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Quick comment, these methods are unnecessary as <code>__init__</code> will be naturally inherited and so, this would help keep possible bugs out:
</p>
<p>
Moreover, the test does not feel so useful, so I would just delete the whole thing.
</p>
</blockquote>
<p>
Thank you for pointing this. You are of course perfectly right! The above commit suppresses the <code>__init__</code>'s. Moreover, it changes slightly the way <code>pow(x,-1/2)</code> 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.
</p>
TickettscrimFri, 17 Nov 2017 21:48:47 GMTreviewer set
https://trac.sagemath.org/ticket/24232#comment:5
https://trac.sagemath.org/ticket/24232#comment:5
<ul>
<li><strong>reviewer</strong>
set to <em>Travis Scrimshaw</em>
</li>
</ul>
<p>
LGTM as far as I can tell. Ralf, do you have any comments/suggestions?
</p>
TicketrwsSat, 18 Nov 2017 07:23:43 GMTstatus, reviewer, milestone changed
https://trac.sagemath.org/ticket/24232#comment:6
https://trac.sagemath.org/ticket/24232#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Travis Scrimshaw</em> to <em>Travis Scrimshaw, Ralf Stephan</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-8.1</em> to <em>sage-8.2</em>
</li>
</ul>
<p>
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 <code>ex1._gobj.is_equal(ex2._gobj)</code> in a Cython file. Still fast in Python is <code>(ex1-ex2).is_trivial_zero()</code>. I'll open a ticket that exposes <code>is_equal</code> for Python users.
</p>
<p>
So, for me this is good and, as the other reviewers and patchbots are happy, positive.
</p>
TicketrwsSat, 18 Nov 2017 07:30:49 GMT
https://trac.sagemath.org/ticket/24232#comment:7
https://trac.sagemath.org/ticket/24232#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:6" title="Comment 6">rws</a>:
</p>
<blockquote class="citation">
<p>
...but instead simply call the walker in a loop as long as the result is different from the original.
</p>
</blockquote>
<p>
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.
</p>
TicketegourgoulhonSat, 18 Nov 2017 17:47:04 GMT
https://trac.sagemath.org/ticket/24232#comment:8
https://trac.sagemath.org/ticket/24232#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:6" title="Comment 6">rws</a>:
</p>
<blockquote class="citation">
<p>
Sorry coming late.
</p>
</blockquote>
<p>
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!
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
If I understand correctly (which is not guaranteed...), this would change the ordering of simplification. Take for instance the expression
</p>
<pre class="wiki">ex = sqrt(a + sqrt(b))
</pre><p>
where <code>a</code> and <code>b</code> are potentially complicated expressions. As it is currently, the walker will simplify first <code>sqrt(b)</code> (to <code>c</code> say) and then <code>sqrt(a+c)</code>. If we call the walker in a loop as long as the outcome changes, it will first try to simplify <code>sqrt(a + sqrt(b))</code>, leaving <code>sqrt(b)</code> as it is. In the second round only, it will try to simplify <code>sqrt(b)</code>. 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 <code>sqrt(b)</code>. Do you agree?
</p>
<blockquote class="citation">
<p>
However note in this case that the most efficient way to compare expressions structurally is to call <code>ex1._gobj.is_equal(ex2._gobj)</code> in a Cython file. Still fast in Python is <code>(ex1-ex2).is_trivial_zero()</code>. I'll open a ticket that exposes <code>is_equal</code> for Python users.
</p>
</blockquote>
<p>
I've seen it is <a class="closed ticket" href="https://trac.sagemath.org/ticket/24236" title="enhancement: Structural comparison of expressions (closed: fixed)">#24236</a>. This will be very useful, thank you!
</p>
TicketrwsSun, 19 Nov 2017 07:18:23 GMT
https://trac.sagemath.org/ticket/24232#comment:9
https://trac.sagemath.org/ticket/24232#comment:9
<blockquote class="citation">
<p>
If I understand correctly (which is not guaranteed...), this would change the ordering of simplification.
</p>
</blockquote>
<p>
Depends on the type of walker which is depth-first with any <code>ExpressionTreeWalker</code> as I understand, so the outcome would be actually the same.
</p>
TicketegourgoulhonSun, 19 Nov 2017 10:51:42 GMT
https://trac.sagemath.org/ticket/24232#comment:10
https://trac.sagemath.org/ticket/24232#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:9" title="Comment 9">rws</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
If I understand correctly (which is not guaranteed...), this would change the ordering of simplification.
</p>
</blockquote>
<p>
Depends on the type of walker which is depth-first with any <code>ExpressionTreeWalker</code> as I understand, so the outcome would be actually the same.
</p>
</blockquote>
<p>
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:
</p>
<pre class="wiki"> if 'sqrt(' in str(argum):
argum = self(argum) # treatment of nested sqrt's
</pre><p>
correct?
Then in the example of <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:8" title="Comment 8">comment:8</a>, how are we going to reach first <code>sqrt(b)</code>? To be depth-first, it seems to me that some recursion is required, as in the above <code>self(argum)</code>.
</p>
TicketrwsMon, 20 Nov 2017 09:48:18 GMT
https://trac.sagemath.org/ticket/24232#comment:11
https://trac.sagemath.org/ticket/24232#comment:11
<p>
The recursion is provided by the superclasses of the walker.
</p>
TicketegourgoulhonMon, 20 Nov 2017 13:20:32 GMT
https://trac.sagemath.org/ticket/24232#comment:12
https://trac.sagemath.org/ticket/24232#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:11" title="Comment 11">rws</a>:
</p>
<blockquote class="citation">
<p>
The recursion is provided by the superclasses of the walker.
</p>
</blockquote>
<p>
No, it does not seem to be the case, because of the <code>return simpl</code> in line 190 of <a class="ext-link" href="https://git.sagemath.org/sage.git/tree/src/sage/manifolds/utilities.py?id=0c7b9ea177eeb653de9a2987ea60920acaa96d88"><span class="icon"></span>https://git.sagemath.org/sage.git/tree/src/sage/manifolds/utilities.py?id=0c7b9ea177eeb653de9a2987ea60920acaa96d88</a>
</p>
<p>
Consider for instance the following example; with the current version, we have
</p>
<pre class="wiki">sage: from sage.manifolds.utilities import SimplifySqrtReal
sage: SimplifySqrtReal(sqrt(1 + sqrt(x^2)))()
sqrt(abs(x) + 1)
</pre><p>
which is correct, given we have no sign assumption on <code>x</code>. Now, if we replace <code>argum = self(argum)</code> in line 170 of the above file by <code>pass</code>, we get
</p>
<pre class="wiki">sage: from sage.manifolds.utilities import SimplifySqrtReal
sage: SimplifySqrtReal(sqrt(1 + sqrt(x^2)))()
sqrt(x + 1)
</pre><p>
which is a wrong result; it shows that only the outermost <code>sqrt</code> has been treated, by passing its argument (i.e. <code>1 + sqrt(x^2)</code>) to <code>radcan</code>, which has oversimplified it to <code>x + 1</code>. Even if we call the walker in a loop until no change happens, there is no way that the <code>x + 1</code> get transformed to <code>abs(x) + 1</code>. Am I missing something?
</p>
TicketrwsMon, 20 Nov 2017 14:17:58 GMT
https://trac.sagemath.org/ticket/24232#comment:13
https://trac.sagemath.org/ticket/24232#comment:13
<p>
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 <code>str()</code>. The first usage could be replaced with <code>...has(sqrt(w0)) or ... has(1/sqrt(w0))</code> with <code>w0=SR.wild()</code>. You test on top of the function for <code>w0^(1/2)</code> and later using <code>str</code> for <code>w0^(1/2)</code> and <code>w0^(-1/2)</code> but you can replace it all with <code>...match(w0^(1/2))</code> and <code>...match(w0^(-1/2))</code>.
</p>
<p>
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.
</p>
TicketegourgoulhonMon, 20 Nov 2017 15:46:41 GMT
https://trac.sagemath.org/ticket/24232#comment:14
https://trac.sagemath.org/ticket/24232#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:13" title="Comment 13">rws</a>:
</p>
<blockquote class="citation">
<p>
I'm sorry that my directions were so completely off this time
</p>
</blockquote>
<p>
No problem at all.
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Thank you for your suggestion! I am just implementing the wildcard solution at the moment.
</p>
TicketegourgoulhonMon, 20 Nov 2017 16:10:24 GMTstatus changed
https://trac.sagemath.org/ticket/24232#comment:15
https://trac.sagemath.org/ticket/24232#comment:15
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:14" title="Comment 14">egourgoulhon</a>:
</p>
<blockquote class="citation">
<p>
Thank you for your suggestion! I am just implementing the wildcard solution at the moment.
</p>
</blockquote>
<p>
Hence the needs_work status.
</p>
TicketgitTue, 21 Nov 2017 10:42:02 GMTcommit changed
https://trac.sagemath.org/ticket/24232#comment:16
https://trac.sagemath.org/ticket/24232#comment:16
<ul>
<li><strong>commit</strong>
changed from <em>61d97c242aaa27f446d58af4e15fbe6d16dfe3f8</em> to <em>ec105bbb42a97c9ac2bff745112688c655a0ecb4</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=ec105bbb42a97c9ac2bff745112688c655a0ecb4"><span class="icon"></span>ec105bb</a></td><td><code>Use of wildcards for pattern search in simplifications regarding calculus on manifolds</code>
</td></tr></table>
TicketegourgoulhonTue, 21 Nov 2017 10:45:23 GMTstatus changed
https://trac.sagemath.org/ticket/24232#comment:17
https://trac.sagemath.org/ticket/24232#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
The last commit gets rid of any string manipulation in <code>SimplifySqrtReal</code> and <code>SimplifyAbsTrig</code>, following the suggestion in <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:13" title="Comment 13">comment:13</a>.
</p>
TicketrllozesTue, 21 Nov 2017 18:09:17 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/24232#comment:18
https://trac.sagemath.org/ticket/24232#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Travis Scrimshaw, Ralf Stephan</em> to <em>Travis Scrimshaw, Ralf Stephan, Richard L Lozes</em>
</li>
</ul>
<p>
Builds and tests cleanly atop 8.1.rc0 on an OpenSUSE 42.2 system.
So far, randomly selected worksheets complete successfully and correctly.
</p>
<p>
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.
</p>
<p>
I should add that the code is now easy to comprehend.
</p>
TicketegourgoulhonWed, 22 Nov 2017 15:01:10 GMT
https://trac.sagemath.org/ticket/24232#comment:19
https://trac.sagemath.org/ticket/24232#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/24232#comment:18" title="Comment 18">rllozes</a>:
</p>
<blockquote class="citation">
<p>
Builds and tests cleanly atop 8.1.rc0 on an OpenSUSE 42.2 system.
So far, randomly selected worksheets complete successfully and correctly.
</p>
</blockquote>
<p>
Thank you for these extra tests.
</p>
<p>
Thank you all for the comments, suggestions and the review!
</p>
TicketvbraunMon, 11 Dec 2017 01:02:03 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/24232#comment:20
https://trac.sagemath.org/ticket/24232#comment:20
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/manifolds/simplif_tree-24232</em> to <em>ec105bbb42a97c9ac2bff745112688c655a0ecb4</em>
</li>
</ul>
Ticket