solvers - added Min/Max support for decompogen #23021

praneethratna · 2022-02-05T14:37:33Z

References to other Issues or PRs

Brief description of what is fixed or changed

Fixes #13612
Closes #13623 and Closes #18517

Before addition:

>>> decompogen(Min(5, x), x)
....
....
....
....
File "sympy\core\compatibility.py", line 462, in default_sort_key
    return item.sort_key(order=order)
  File "sympy\core\cache.py", line 93, in wrapper
    retval = cfunc(*args, **kwargs)
  File "sympy\core\compatibility.py", line 792, in wrapper
    key = make_key(args, kwds, typed) if kwds or typed else args
  File "sympy\core\compatibility.py", line 724, in _make_key
    return _HashedSeq(key)
  File "sympy\core\compatibility.py", line 702, in __init__
    self.hashvalue = hash(tup)
RuntimeError: maximum recursion depth exceeded

After addition:

>>> decompogen(Min(5, x), x)
[Min(5, x), x]

Other comments

Release Notes

solvers
- Added Min/Max support for decompogen.

sympy-bot · 2022-02-05T14:37:41Z

✅

Hi, I am the SymPy bot (v162). I'm here to help you write a release notes entry. Please read the guide on how to write release notes.

Your release notes are in good order.

Here is what the release notes will look like:

solvers
- Added Min/Max support for decompogen. (#23021 by @praneethratna and @smichr)

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.11.

Click here to see the pull request description that was parsed.

<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->


#### Brief description of what is fixed or changed
Fixes #13612
Closes #13623 and Closes #18517

Before addition:
```
>>> decompogen(Min(5, x), x)
....
....
....
....
File "sympy\core\compatibility.py", line 462, in default_sort_key
    return item.sort_key(order=order)
  File "sympy\core\cache.py", line 93, in wrapper
    retval = cfunc(*args, **kwargs)
  File "sympy\core\compatibility.py", line 792, in wrapper
    key = make_key(args, kwds, typed) if kwds or typed else args
  File "sympy\core\compatibility.py", line 724, in _make_key
    return _HashedSeq(key)
  File "sympy\core\compatibility.py", line 702, in __init__
    self.hashvalue = hash(tup)
RuntimeError: maximum recursion depth exceeded
```
After addition:
```
>>> decompogen(Min(5, x), x)
[Min(5, x), x]
```

#### Other comments


#### Release Notes

<!-- Write the release notes for this release below between the BEGIN and END
statements. The basic format is a bulleted list with the name of the subpackage
and the release note for this PR. For example:

* solvers
  * Added a new solver for logarithmic equations.

* functions
  * Fixed a bug with log of integers.

or if no release note(s) should be included use:

NO ENTRY

See https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more
information on how to write release notes. The bot will check your release
notes automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
*  solvers
    *  Added `Min`/`Max` support for `decompogen`.
<!-- END RELEASE NOTES -->

Update

The release notes on the wiki have been updated.

sympy/solvers/decompogen.py

github-actions · 2022-02-05T15:40:57Z

Benchmark results from GitHub Actions

Lower numbers are good, higher numbers are bad. A ratio less than 1
means a speed up and greater than 1 means a slowdown. Green lines
beginning with + are slowdowns (the PR is slower then master or
master is slower than the previous release). Red lines beginning
with - are speedups.

Significantly changed benchmark results (PR vs master)

Significantly changed benchmark results (master vs previous release)

       before           after         ratio
     [907895ac]       [706ab904]
-       217±0.8ms        133±0.5ms     0.61  large_exprs.TimeLargeExpressionOperations.time_subs
-         220±1μs        109±0.2μs     0.50  matrices.TimeMatrixExpression.time_MatMul
-     13.9±0.02ms      7.48±0.04ms     0.54  matrices.TimeMatrixExpression.time_MatMul_doit
-      4.21±0.02s          310±2ms     0.07  polygon.PolygonArbitraryPoint.time_bench01
+     3.27±0.02ms      5.61±0.02ms     1.71  solve.TimeMatrixOperations.time_det(4, 2)
+     3.28±0.01ms      5.59±0.03ms     1.71  solve.TimeMatrixOperations.time_det_bareiss(4, 2)
+      37.7±0.2ms       67.5±0.1ms     1.79  solve.TimeMatrixSolvePyDySlow.time_linsolve(1)
+      38.0±0.1ms       67.4±0.3ms     1.77  solve.TimeMatrixSolvePyDySlow.time_solve(1)

Full benchmark results can be found as artifacts in GitHub Actions
(click on checks at the top of the PR).

sympy/solvers/decompogen.py

sympy/solvers/tests/test_decompogen.py

praneethratna · 2022-02-05T18:19:08Z

@smichr decompogen(Max(u, u**2, y), x) is returning [Max(x, y), 2*x + 3, x**2] as answer but is it correct?

smichr · 2022-02-05T18:35:09Z

but is it correct?

ahh -- that is similar to what you had before. But I don't know much about decompogen; check git blame for a list of people that have worked on the function or check on the mailing list or gitter.

smichr · 2022-02-05T18:38:19Z

"closes" is non-distributive so you have to write "Closes #13623 and #18517" as "closes #13623 and closes #18517" in the OP.

praneethratna · 2022-02-05T18:49:45Z

@smichr The benchmark test is failing is there any fix for it?

praneethratna · 2022-02-05T19:40:31Z

ahh -- that is similar to what you had before. But I don't know much about decompogen; check git blame for a list of people that have worked on the function or check on the mailing list or gitter.

Maybe @aktech can help. He introduced decompogen in #9831.

smichr · 2022-02-05T19:56:19Z

The benchmark test is failing is there any fix for it?

I don't think it is related -- it is failing on my PR, too.

smichr · 2022-02-05T20:00:51Z

sympy/solvers/tests/test_decompogen.py

    raises(TypeError, lambda: decompogen(x < 5, x))
+    u = 2*x + 3
+    raises(TypeError, lambda: decompogen(Max(u, u**2), x))
+    assert decompogen(Max(u, u**2, y), x) == [Max(x, y), 2*x + 3, x**2]


this should be [Max(x, x**2, y), 2*x + 3] according to docstring:

Given an expression ``f``, returns a list ``[f_1, f_2, ..., f_n]``, where:: f = f_1 o f_2 o ... f_n = f_1(f_2(... f_n)) Note: This is a General decomposition function. It also decomposes Polynomials. For only Polynomial decomposition see ``decompose`` in polys. Examples ======== >>> from sympy.abc import x >>> from sympy import decompogen, sqrt, sin, cos >>> decompogen(sin(cos(x)), x) [sin(x), cos(x)]

So if you keep replacing the left expression's x with the expression to the right you should get the original function.
Given [Min(x,x**2, y),2*x+3], start with leftmost, Min(x, x**2, y) and replace x with 2*x+3 to give Min(2*x + 3, (2*x + 3)**2, y), the original expression.

The logic should be something like

args = list(f.args) d0 = None for i,a in enumerate(args): if not a.has_symbol: continue d = decompogen(a, symbol) if d0 is None: d0= d continue if d[1:] != d0[1:]: raise ValueError args[i] = d[0] return [f.func(*args)] + d[1:]

So a test like u = 2*x + 3; decompogen(Min(u, u**2, y, u**3), x) should give [Min(x, x**2, y, x**3), 2*x + y] but there might be re-ordering of the args -- as long as the args are all there it should be fine.

(Really, it seems like decompogen should use cse so decompogen(cos(2*x+3) + sin((2*x+3)**2 + y), x) could give cos(x) + sin(x**2 + y), 2*x + 3. But that is a different issue.)

decompogen(Min(u, u**2, y, u**3), x) is giving a ValueError for this change. Also decompogen(Min(5, x**2), x) now gives [Min(5, x**2)].

if all(a.has(symbol) for a in f.args): raise TypeError('cannot decompose %s' % f) args = list(f.args) d0 = None for i, a in enumerate(args): if not a.has(symbol): continue d = decompogen(a, symbol) if d0 is None: d0 = d continue args[i] = d[0] return [f.subs(args[1], symbol)] + d0

@smichr This change is working and is giving the correct results but I'm not sure whether it is the right way?

smichr · 2022-02-07T05:48:31Z

diff --git a/sympy/solvers/decompogen.py b/sympy/solvers/decompogen.py
index 51d380b86a..6628155129 100644
--- a/sympy/solvers/decompogen.py
+++ b/sympy/solvers/decompogen.py
@@ -40,8 +40,6 @@ def decompogen(f, symbol):
     if symbol not in f.free_symbols:
         return [f]
 
-    result = []
-
     # ===== Simple Functions ===== #
     if isinstance(f, (Function, Pow)):
         if f.is_Pow and f.base == S.Exp1:
@@ -50,21 +48,26 @@ def decompogen(f, symbol):
             arg = f.args[0]
         if arg == symbol:
             return [f]
-        result += [f.subs(arg, symbol)] + decompogen(arg, symbol)
-        return result
+        return [f.subs(arg, symbol)] + decompogen(arg, symbol)
 
     # ===== Min/Max Functions ===== #
     if isinstance(f, (Min, Max)):
         args = list(f.args)
-        iargs = [i for i, a in enumerate(f.args) if a.has(symbol)]
-        if len(iargs) == len(args):
-            raise TypeError('cannot decompose %s' % f)
-        dec = []
-        for i in iargs:
-            dec.extend(decompogen(args[i], symbol))
-            args[i] = symbol
-        result += [f.func(*args)] + list(uniq(dec))
-        return result
+        d0 = None
+        for i, a in enumerate(args):
+            if not a.has_free(symbol):
+                continue
+            d = decompogen(a, symbol)
+            if len(d) == 1:
+                d = [symbol] + d
+            if d0 is None:
+                d0 = d[1:]
+            elif d[1:] != d0:
+                raise TypeError('cannot decompose %s' % f)
+            args[i] = d[0]
+        if d0 == [symbol]:
+            return [f]
+        return [f.func(*args)] + d0
 
     # ===== Convert to Polynomial ===== #
     fp = Poly(f)
@@ -73,13 +76,11 @@ def decompogen(f, symbol):
     if len(gens) == 1 and gens[0] != symbol:
         f1 = f.subs(gens[0], symbol)
         f2 = gens[0]
-        result += [f1] + decompogen(f2, symbol)
-        return result
+        return [f1] + decompogen(f2, symbol)
 
     # ===== Polynomial decompose() ====== #
     try:
-        result += decompose(f)
-        return result
+        return decompose(f)
     except ValueError:
         return [f]
 
diff --git a/sympy/solvers/tests/test_decompogen.py b/sympy/solvers/tests/test_decompogen.py
index 22bcde1d44..e616b322af 100644
--- a/sympy/solvers/tests/test_decompogen.py
+++ b/sympy/solvers/tests/test_decompogen.py
@@ -19,11 +19,11 @@ def test_decompogen():
     assert decompogen(Abs(cos(y)**2 + 3*cos(x) - 4), x) == [Abs(x), 3*x + cos(y)**2 - 4, cos(x)]
     assert decompogen(x, y) == [x]
     assert decompogen(1, x) == [1]
-    assert decompogen(Max(3, x), x) == [Max(3, x), x]
+    assert decompogen(Max(3, x), x) == [Max(3, x)]
     raises(TypeError, lambda: decompogen(x < 5, x))
     u = 2*x + 3
-    raises(TypeError, lambda: decompogen(Max(u, u**2), x))
-    assert decompogen(Max(u, u**2, y), x) == [Max(x, y), 2*x + 3, x**2]
+    assert decompogen(Max(sqrt(u),(u)**2), x) == [Max(sqrt(x), x**2), u]
+    assert decompogen(Max(u, u**2, y), x) == [Max(x, x**2, y), u]
 
 
 def test_decompogen_poly():

Co-authored-by: Christopher Smith <smichr@gmail.com>

praneethratna · 2022-02-07T11:43:21Z

ping @smichr

sympy/solvers/decompogen.py

praneethratna · 2022-02-07T18:19:35Z

@smichr I think the latest test that you've added should be changed.

>>> decompogen(Max(sin(x), u), x)
[Max(2*x + 3, sin(x))]

smichr · 2022-02-07T20:33:41Z

+1 (yes, my test should have wrapped rhs in []. But what you have is fine. Let's go with this.