✅

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

• No release notes entry will be added for this pull request.

**References to other Issues or PRs**
Closes #17838
Closes #11188
re-uses tests from #17838 / #17079 / #18489 (with attribution)

**Brief description of what is fixed or changed**
This PR adds a union handler for Integer-based ImageSets such as those often returned by solveset for trigonometric equations.

Before (i.e. with master):

```
In [1]: solveset(cos(x) + cos(3*x) + cos(5*x), x, S.Reals)
Out[1]:
⎧        π        ⎫   ⎧        3⋅π        ⎫   ⎧        4⋅π        ⎫   ⎧        2⋅π        ⎫   ⎧        5⋅π        ⎫   ⎧        π        ⎫
⎨2⋅n⋅π + ─ | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─ | n ∊ ℤ⎬
⎩        2        ⎭   ⎩         2         ⎭   ⎩         3         ⎭   ⎩         3         ⎭   ⎩         3         ⎭   ⎩        3        ⎭

   ⎧        7⋅π        ⎫   ⎧        5⋅π        ⎫   ⎧        11⋅π        ⎫   ⎧        π        ⎫
 ∪ ⎨2⋅n⋅π + ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ──── | n ∊ ℤ⎬ ∪ ⎨2⋅n⋅π + ─ | n ∊ ℤ⎬
   ⎩         6         ⎭   ⎩         6         ⎭   ⎩         6          ⎭   ⎩        6        ⎭
```
After:

```
In [1]: solveset(cos(x) + cos(3*x) + cos(5*x), x, S.Reals)
Out[1]:
⎧      π        ⎫   ⎧n⋅π   π        ⎫   ⎧n⋅π   π        ⎫
⎨n⋅π + ─ | n ∊ ℤ⎬ ∪ ⎨─── + ─ | n ∊ ℤ⎬ ∪ ⎨─── + ─ | n ∊ ℤ⎬
⎩      2        ⎭   ⎩ 2    3        ⎭   ⎩ 2    6        ⎭
```
(example borrowed from #11188, thanks @Shekharrajak )

Other comments
The union multi dispatch code will only consider pairwise unions, so not all possible simplifications will be recognized. But the improvements are still obvious.

TODO: add some more tests.

Release Notes

- sets

  - Added simplification code for (pairwise) unions of ImageSets whose elements are in arithmetic progression (e.g. those appearing in solution sets of trigonometric equations).


I have just tried to understand #18489 and improved a bit (the changes are no too large, also the description is the same). Further, improvements are welcome to discuss here.

CREDITS :  @ gschintgen , @oscarbenjamin , @ Shekharrajak 
<!-- BEGIN RELEASE NOTES -->
NO ENTRY
<!-- END RELEASE NOTES -->

You should keep the original commits intact when reviving a PR so that they still show as being from the original author.

The reason #18489 did not get merged was because this would be better handled in simplification rather than in the evaluation code. The handler system for union is inherently limited to pairwise unions so implementing this there will never handle all cases. Also there is already too much computation going on in the evaluation of unions etc. This should be handled in a simplify function and should not be something that happens automatically when doing Union(a, b, c, d).

The handler system for union is inherently limited to pairwise unions so implementing this there will never handle all cases.

Can you give an example of this? I think it handles almost all cases.
Like:

>>> n = Symbol('n')
>>> s0 = ImageSet(Lambda(n, 3*n+0), S.Integers)
>>> s1 = ImageSet(Lambda(n, 3*n+1), S.Integers)
>>> s2 = ImageSet(Lambda(n, 3*n+2), S.Integers)
>>> s3 = ImageSet(Lambda(n, 3*n+4), S.Integers)
>>> Union(s0, s1, s2, s3)
Union(ImageSet(Lambda(n, 3*n), Integers), ImageSet(Lambda(n, 3*n + 1), Integers), ImageSet(Lambda(n, 3*n + 2), Integers))
>>> s3 = ImageSet(Lambda(n, 4*n+4), S.Integers)
>>> Union(s0, s1, s2, s3)
Union(ImageSet(Lambda(n, 3*n), Integers), ImageSet(Lambda(n, 3*n + 1), Integers), ImageSet(Lambda(n, 3*n + 2), Integers), ImageSet(Lambda(n, 4*n + 4), Integers))
>>> s3 = ImageSet(Lambda(n, 3*n+6), S.Integers)
>>> Union(s0, s1, s2, s3)
Union(ImageSet(Lambda(n, 3*n), Integers), ImageSet(Lambda(n, 3*n + 1), Integers), ImageSet(Lambda(n, 3*n + 2), Integers))
>>> s2 = ImageSet(Lambda(n, 3*n+4), S.Integers)
>>> Union(s0, s1, s2, s3)
Union(ImageSet(Lambda(n, 3*n), Integers), ImageSet(Lambda(n, 3*n + 1), Integers))

The reason #18489 did not get merged was because this would be better handled in simplification rather than in the evaluation code.

So, this should be copy-pasted in simplify function?

As long as you don't close this branch you can recreate the img_union branch with the original commits intact and then force push here and it will update.

Big headache, but I think I have the original PR along with a single commit of yours which incorporates all of the changes here while retaining original commits. If you agree you can clone my iseta branch and replace your img_union branch with it and then force push here to update. Although there was some concern (@oscarbenjamin ) about the simplification of imageset on integers happening automatically instead of through simplification, it seems reasonable to have this be automatic to me (and the routine is conservative in that it only makes the change if both imagesets involve the integer domain).

Big headache, but I think I have the original PR along with a single commit of yours which incorporates all of the changes here while retaining original commits. If you agree you can clone my iseta branch and replace your img_union branch with it and then force push here to update.

But what is the need for it?
And How can I clone your branch(iseta) from my local machine?

Is it in this way? (from img_union)

git checkout -b iseta
git push -f MaqOwais
git branch -D img_union

Although there was some concern (@oscarbenjamin ) about the simplification of imageset on integers happening automatically instead of through simplification, it seems reasonable to have this be automatic to me (and the routine is conservative in that it only makes the change if both imagesets involve the integer domain).

I do think the same. ( since it only calls this which I think it doesn't matter a lot )

Is it in this way? (from img_union)

I think like this:

git checkout img_union
git branch img_union_bak
git remote add smichr git://github.com/smichr/sympy.git
git checkout smichr/iseta
git branch -D img_union
git checkout -b img_union
git push -f MaqOwais
git branch -D img_union_bak

But what is the need for it?

As mention above, "[y]ou should keep the original commits intact when reviving a PR"

I think this should be git branch img_union

That command is to create, but not move to, a backup branch from the current branch at that point.

I m not sure why it is not recognizing the directory. Perhaps try

git remote add smichr https://github.com/smichr/sympy.git

Also, a problem with this PR is that there is a regression in a test:

master:
>>> nonlinsolve([sin(x) - 1, cos(x)], x)
FiniteSet((ImageSet(Lambda(_n, 2*_n*pi + pi/2), Integers),))
this:
>>> nonlinsolve([sin(x) - 1, cos(x)], x)
FiniteSet((ImageSet(Lambda(_n, _n*pi + pi/2), Integers),))

I think this is what needed?

I think this is what needed?

Are you refering to the 2*n*pi + pi/2 vs n*pi + pi/2? They don't generate the same series of points. The latter generates 3*pi/2 which is not a solution. This problem becomes apparent when Union(ImageSet(Lambda(_n, 2*_n*pi + pi/2), Integers) ImageSet(Lambda(_n, 2*_n*pi + 3*pi/2), Integers)) is sent to the handler of this PR which then simplifies it; the problem is that the Union is being identified as a solution before the 2*n*pi + 3*pi/2 solutions are removed. So the problem predates this PR; this PR just exposes it.

Are you refering to the 2npi + pi/2 vs n*pi + pi/2?

Nope, I was referring to the git changes.

Oh...you got it to update. Now it looks like there are some tests failing. Nevermind on previous comment :-)

I think I've to update the tests locally according to these updates, isn't it?
Or is there anything else missing or any test answer come out to be the wrong one?

Although there was some concern (@oscarbenjamin ) about the simplification of imageset on integers happening automatically instead of through simplification, it seems reasonable to have this be automatic to me (and the routine is conservative in that it only makes the change if both imagesets involve the integer domain).

There is far too much automatic evaluation in sympy and it is problematic for several reasons. It makes sympy slow because the evaluation code runs every time any manipulation is performed (e.g. subs, xreplace, etc). The other reason is that it makes it hard to represent expressions in particular ways when wanted because they keep evaluating into something else. The use of evaluate=False is just a kludge that doesn't really work because any operation like subs etc will undo it e.g.:

In [20]: S1 = ImageSet(Lambda(n, 2*pi*n+x), Integers)

In [21]: S2 = ImageSet(Lambda(n, 2*pi*n+x+pi), Integers)

In [22]: S3 = Union(S1, S2, evaluate=False)

In [23]: S3
Out[23]: {2⋅π⋅n + x │ n ∊ ℤ} ∪ {2⋅π⋅n + x + π │ n ∊ ℤ}

In [24]: S3.subs(x, y)
Out[24]: {n⋅π + y + π │ n ∊ ℤ}

In general I think that we should not add more computation in evaluation. This is particularly problematic in sets because there are not many other routines defined for manipulating sets so every time more is added in evaluation we encourage future code to go there as well.

In this particular case there are strong reasons for not using this approach. The current mechanism of Union evaluation works by calling pairwise handlers to see if any pairs of sets can evaluate together. That is in general an algorithm that is quadratic in the number of sets so we should be very careful about making all of those pairwise handlers efficient. Compare the timings on master:

In [1]: for N in [2, 4, 8, 16]:  # master
   ...:     sets = [ImageSet(Lambda(n, (N+1)*pi*n + m), Integers) for m in range(N)]
   ...:     %time ok = Union(*sets)
   ...: 
CPU times: user 1.52 ms, sys: 39 µs, total: 1.56 ms
Wall time: 1.56 ms
CPU times: user 3.04 ms, sys: 14 µs, total: 3.05 ms
Wall time: 3.06 ms
CPU times: user 6.57 ms, sys: 36 µs, total: 6.61 ms
Wall time: 6.62 ms
CPU times: user 12.8 ms, sys: 43 µs, total: 12.8 ms
Wall time: 12.8 ms

Now look at the PR:

In [1]: for N in [2, 4, 8, 16]:  # PR
   ...:     sets = [ImageSet(Lambda(n, (N+1)*pi*n + m), Integers) for m in range(N)]
   ...:     %time ok = Union(*sets)
   ...: 
CPU times: user 20.2 ms, sys: 361 µs, total: 20.5 ms
Wall time: 20.7 ms
CPU times: user 64.6 ms, sys: 338 µs, total: 65 ms
Wall time: 65.2 ms
CPU times: user 232 ms, sys: 852 µs, total: 233 ms
Wall time: 233 ms
CPU times: user 1.01 s, sys: 9.65 ms, total: 1.02 s
Wall time: 1.03 s

For N=16 this is 100x slower and gives the same result. Much of the reason that sympy is slow is because of do nothing evaluation like this that doesn't improve anything but does waste CPU cycles. Note that we don't just pay the price once. Any manipulation reruns the evaluation code:

In [2]: %time ok2 = ok.xreplace({n: k})
CPU times: user 1.02 s, sys: 5.03 ms, total: 1.02 s
Wall time: 1.02 s

SymPy has tried to work around this with caching but it's not a substitute for having good algorithmic complexity. A simplify_union_of_sets function can do this using a single scan over the args rather than all-to-all pairwise comparison which can be more like O(N) rather than O(N^2).

Finally using only pairwise comparisons like this will inherently fail in any situation where the number of sets to be merged is not a power of 2:

In [3]: S1, S2, S3 = [ImageSet(Lambda(n, 3*pi*n+m), Integers) for m in range(3)]

In [4]: S1 | S2 | S3
Out[4]: {3⋅π⋅n │ n ∊ ℤ} ∪ {3⋅π⋅n + 1 │ n ∊ ℤ} ∪ {3⋅π⋅n + 2 │ n ∊ ℤ}

It isn't possible to merge any two of these pairs and the algorithm does not look beyond pairwise comparison. The approach taken in this PR is fundamentally unable to achieve the kind of simplification that is needed for the output of solveset.

How about this:

diff --git a/sympy/solvers/tests/test_solveset.py b/sympy/solvers/tests/test_solveset.py
index 423a991e3d..0550142b21 100644
--- a/sympy/solvers/tests/test_solveset.py
+++ b/sympy/solvers/tests/test_solveset.py
@@ -1009,11 +1009,12 @@ def test_solve_invalid_sol():
 
 
 def test_solve_trig_simplified():
-    assert solveset_real(sin(x), x) == ImageSet(Lambda(n, n*pi), S.Integers)
-    assert solveset_real(cos(x), x) == \
-        ImageSet(Lambda(n, n*pi + pi/2), S.Integers)
-    assert solveset_real(cos(x) + sin(x), x) == \
-        ImageSet(Lambda(n, n*pi + 3*pi/4), S.Integers)
+    assert dumeq(solveset_real(sin(x), x),
+        ImageSet(Lambda(n, n*pi), S.Integers))
+    assert dumeq(solveset_real(cos(x), x),
+        ImageSet(Lambda(n, n*pi + pi/2), S.Integers))
+    assert dumeq(solveset_real(cos(x) + sin(x), x),
+        ImageSet(Lambda(n, n*pi + 3*pi/4), S.Integers))
 
 
 @XFAIL
@@ -1674,23 +1675,21 @@ def test_solve_nonlinear_trans():
 def test_issue_19050():
     # test_issue_19050 --> TypeError removed
     assert dumeq(nonlinsolve([x + y, sin(y)], [x, y]),
-        FiniteSet((ImageSet(Lambda(n, -2*n*pi), S.Integers), ImageSet(Lambda(n, 2*n*pi), S.Integers)),\
-             (ImageSet(Lambda(n, -2*n*pi - pi), S.Integers), ImageSet(Lambda(n, 2*n*pi + pi), S.Integers))))
+        FiniteSet((ImageSet(Lambda(n, -n*pi), S.Integers),
+        ImageSet(Lambda(n, n*pi), S.Integers))))
     assert dumeq(nonlinsolve([x + y, sin(y) + cos(y)], [x, y]),
-        FiniteSet((ImageSet(Lambda(n, -2*n*pi - 3*pi/4), S.Integers), ImageSet(Lambda(n, 2*n*pi + 3*pi/4), S.Integers)), \
-            (ImageSet(Lambda(n, -2*n*pi - 7*pi/4), S.Integers), ImageSet(Lambda(n, 2*n*pi + 7*pi/4), S.Integers))))
+        FiniteSet((ImageSet(Lambda(n, -n*pi - 3*pi/4), S.Integers),
+        ImageSet(Lambda(n, n*pi + 3*pi/4), S.Integers))))
 
 
 def test_issue_16618():
-    # AttributeError is removed !
-    eqn = [sin(x)*sin(y), cos(x)*cos(y) - 1]
-    ans = FiniteSet((x, 2*n*pi), (2*n*pi, y), (x, 2*n*pi + pi), (2*n*pi + pi, y))
-    sol = nonlinsolve(eqn, [x, y])
-
-    for i0, j0 in zip(ordered(sol), ordered(ans)):
-        assert len(i0) == len(j0) == 2
-        assert all(a.dummy_eq(b) for a, b in zip(i0, j0))
+    sol = nonlinsolve([sin(x)*sin(y), cos(x)*cos(y) - 1], [x, y])
+    ans = [(x, n*pi), (n*pi, y)]
     assert len(sol) == len(ans)
+    for i, j in zip(ordered(sol), ordered(ans)):
+        assert len(i) == len(j)
+        for a, b in zip(i, j):
+            assert a.dummy_eq(b)
 
 
 def test_issue_5132_1():

The approach taken in this PR is fundamentally unable to achieve the kind of simplification that is needed for the output of solveset.

Excellent answer by @oscarbenjamin here makes the point clear. We cannot add this into the union handler. This will have to be a simplification method or the solvers themselves will have to be more careful about not injecting all solutions like this and then requiring simplification to remove them. This is a good principle: limit complexity at the source.

#21196 (comment)
Actually, I did the same changes locally:- )

After reading this #21196 (comment) we can conclude that a new approach should be built and that should be based on these 2 points...

1. simplification method ( that should be in simplify_union_of_sets )
2. should not only be pairwise comparisons but also able to compare all the sets simultaneously. (single scan over the args rather than all-to-all pairwise comparison)

should be based on these 2

I prefer to base it on the principle that the actor putting in the redundant solutions should be more careful. solve_trig (or similar) is putting them there and should introspect before doing so.

should be based on these 2

I prefer to base it on the principle that the actor putting in the redundant solutions should be more careful. solve_trig (or similar) is putting them there and should introspect before doing so.

I agree but it would still also be good to be able to simplify a union of imagesets.

should be based on these 2

I prefer to base it on the principle that the actor putting in the redundant solutions should be more careful. solve_trig (or similar) is putting them there and should introspect before doing so.

I agree but it would still also be good to be able to simplify a union of imagesets.

Yes, I think the combination of these 2 ideas will do wonders!
Also, I think these ideas should be executed after making _solve_trig smarter under solveset.