GSoC 2018: Completing Solvers

[Yathartha Joshi]

Hello everyone, I am Yathartha Joshi a final year B.Tech CSE undergrad. I am willing to be a part of GSoC 2018 for the project Solvers: Completing Solveset.
Solveset has been under constant development from 2014, and then 2015, and 2016 and a lot of implementation have been done so far but there is still a lot of things that needs to be implemented so that solveset can take over solve completely and therefore this will be my focus during GSoC period.

My major focus during the period will be implementing transolve, a part of which I have tried to implement in #13045, it will include the following solvers:

 - logarithmic

 - exponential

 - equation solvable by lambertW function

 - improving and implementing trigonometric solver

 - bivariate solver

Apart from these, another group of equations that would make solveset more powerful can be:

 - solving modular equations #13178. 

 - solving Abs equations for complex domain. 

There are some minor fixes that need to be done in solveset:

 - improving set infrastructure (helping #12011 to get merged)

 - making nonlinsolve more powerful.

I guess these are the problems that needs to be done to complete solveset. I might have left some points here (I will be updating if I found anything that needs to be done), also feedbacks are appreciated if there is anything more to be done. Also I have opened discussions here #12243 and here #12340 for discussing the project.

Thanks!

Looking forward to feedback and guidance for the project.

[Amit Kumar]

Hi Yathartha,

Thanks for your interest in working on solveset. I am glad to hear that.

The things you have mentioned are completely worth well over a

summer. I would definitely focus a lot on transolve. It is the most

crucial part of solvers. To go about it take a look at the

_tsolve function in old solve and document each and every aspect

of how it works, something like this:

https://github.com/sympy/sympy/wiki/solvers#transcendent-equations-_tsolve

Then see how you can generalise those things to be more modular,

write down a proper and explicit plan for its implementation which

includes all the abstractions and functionalities. Then a comparison

of old approach and the new approach and how it is better. You should

have a clear plan of what exactly you are going to do to import it to

solveset. It would be a great proposal if you have answered what, how

and why of everything you plan to implement.

Feel free to ask any questions you have.

Cheers,

Amit

[Yathartha Joshi]

Sure I will look into the way `_tsolve` solves and try to conclude how it will be implemented in solveset, meanwhile can you have look at #13045, I have tried to implement exponential and log solver in it. If it looks good to you I can carry out work from there onwards.

[Yathartha Joshi]

I have started a wiki page [here](https://github.com/sympy/sympy/wiki/Implementing-transolve-in-solveset). I will be updating it time to time.

Thanks!

On Sunday, March 11, 2018 at 6:01:00 PM UTC+5:30, Amit Kumar wrote:

[Amit Kumar]

I will have a look at that PR. 

On Monday, March 12, 2018 at 4:54:57 AM UTC, Yathartha Joshi wrote:

I have started a wiki page [here](https://github.com/sympy/sympy/wiki/Implementing-transolve-in-solveset). I will be updating it time to time.

Thanks for starting the wiki.

Cheers,

Amit

[Yathartha Joshi]

Hey Amit,

I was wondering, for solving trigonometric equations we can have different helpers (if one cannot solve, try solving with other helper and so on) and we can have different heuristics in those helpers

Like currently equations are solved by rewriting to `exp` (helper#1), if still equation is unsolved we can have another helper that would solve using `solve_decomposition` (helper#2), and another helper that could take help of the `fu` module to simplify equations (helper#3) and then solve it (there can be more helpers). In this way, we can cover a lot of trigonometric equations.

 - Equations that can be decomposed can be solved using `solve_decomposition` helper

 

     eg: >>> f = sin(3*x) - 1

           >>> solve_decomposition(f, x, S.Reals)

           ImageSet(Lambda(_n, 2*_n*pi/3 + pi/6), S.Integers)

We can also implement trigonometric solver in transolve, but I guess `_solve_trig` should handle it

[Amit Kumar]

Hey Yathartha,

That sounds good.

Cheers!
Amit

[Yathartha Joshi]

Okay! Thanks.

Also, I was thinking was making absolute value expressions to work in complex domain. I found a few equations that have complex solutions:

• http://www.wolframalpha.com/input/?i=solve(abs(x-2)+%2Babs(x)+-+7,+x) 
  
• http://www.wolframalpha.com/input/?i=solve(abs(x-2)+-2+,+x)
  
• http://www.wolframalpha.com/input/?i=solve(abs(x-2)+%2Babs(x+%2B4)+-+16,+x)

I was trying to figure out a possible way to solve this, but I am facing difficulty in getting to the solution. I tried asking the question here, and got the only possible way. Can you provide me with some suggestions regarding this? Is there a specific reason as to why solveset (and even solve) is not made to solve in complex domain.

[Yathartha Joshi]

I have created a proposal here. It would be great if you could review it and suggest any changes.

Thanks in advance.

Yathartha

[Aaron Meurer]

When I click on that link it says I don't have access.

I recommend starting your proposal on
https://summerofcode.withgoogle.com and linking the draft proposal
there. That will make it easier to find in the future.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/aecef52c-4e2e-40b0-9b1c-3cf7c022374c%40googlegroups.com.
>
> For more options, visit https://groups.google.com/d/optout.

[Yathartha Joshi]

Sorry I just gave the access to amit kumar, I have changed it, please have a look.

Thanks!

[Aaron Meurer]

Regarding BigUnion, what is the point of having it and IndexSet that
can only represent a finite number of sets? Union can already do this
without the indirection. I'm also unclear where this will be needed
for solveset.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/862ac528-e77b-46e6-b751-e5ef532a2e46%40googlegroups.com.

[Yathartha Joshi]

What I understood about BigUnion and BigIntersection from here. BigUnion for set of finitesets will work similar to union but for set of imagesets (infinite sets) we will be returning a unified solution.

say for eg: [2*n , 2*n - 1 for n in Integers] passing it to Bigunion will yield something like [n for n in Integers] and BigIntersection would yield EmptySet.

See https://github.com/sympy/sympy/issues/9815#issuecomment-373978030

In solveset when union of imagesets are returned we can apply big union to get the unified result (probably could help the _union of imagesets once its implemented). 

IndexSet will be implemented to get access to set of sets through indexing, a number of sets will be passed as parameters and an instance of IndexSet will be returned with indices mapped to each of the sets in the sets. This way we can get access to a set of sets. 

>>> X = IndexSet(FiniteSet(1, 2, ,3), FiniteSet(4, 5)); X
>>> X[0]
FiniteSet(1, 2 ,3)
>>>X[1]
FiniteSet(4, 5)

[Aaron Meurer]

I'm not seeing an instance where IndexSet is useful. For finite
collections of sets, it is redundant, as Union and Intersection can
already take a finite number of arguments. For infinite collections,
whatever symbol you index over would already exist in the collection
itself (for instance, n in Interval(2*n, 2*n + 1))

And you still haven't answered where infinite unions are needed for solveset.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/34765644-ae2a-4332-9a17-52e54c056f9c%40googlegroups.com.

[Yathartha Joshi]

I am not sure of IndexSet usage but the reason I thought of it was that whenever we need to represent arbitrary set we have a notion of indexing so that is why I thought of having IndexSet.

https://math.stackexchange.com/questions/485244/indexed-families-and-arbitrary-sets-notation

http://www.math.umaine.edu/~farlow/sec22.pdf

> And you still haven't answered where infinite unions are needed for solveset.

I thought of using BigUnion where there is a union of more than one imagesets, (like in case of trigonometric equations)

>>> solveset(sin(x), x, S.Reals)
Union(ImageSet(Lambda(_n, 2*_n*pi), S.Integers), ImageSet(Lambda(_n, 2*_n*pi + pi), S.Integers))
# (sin(2*x) + sin(4*x) + sin(6*x)) will have lots of union of imagesets

BigUnion could give `ImageSet(Lambda(_n, _n*pi), S.Integers)`, (although _union of imageset is under development, BigUnion can act as helper)

I guess this is an idea that is in an initial stage (and that is why I can't imagine it in larger scale), and if you suggest that it won't be feasible I would rather remove it from the proposal.

Thanks

Yathartha 

[Aaron Meurer]

On Fri, Mar 23, 2018 at 6:56 AM, Yathartha Joshi <yatha...@gmail.com> wrote:
> I am not sure of IndexSet usage but the reason I thought of it was that
> whenever we need to represent arbitrary set we have a notion of indexing so
> that is why I thought of having IndexSet.
> https://math.stackexchange.com/questions/485244/indexed-families-and-arbitrary-sets-notation
> http://www.math.umaine.edu/~farlow/sec22.pdf

You do need indexing to represent U A_i in general, but my point is
that ImageSet as you've defined it shouldn't be necessary.

To represent something like U [2*n, 2*n + 1] would require something
like BigUnion(Interval(2*n, 2*n + 1), n, Integers). The indexing is
done by the symbol that's used to define the set. We could also make
some way to create an arbitrary set parameterized by a variable, like
A_k so that U_{k \in I} A_k can be represented (do we currently have
any kind of arbitrary set object?).

>
>> And you still haven't answered where infinite unions are needed for
>> solveset.
>
> I thought of using BigUnion where there is a union of more than one
> imagesets, (like in case of trigonometric equations)
>
>>>> solveset(sin(x), x, S.Reals)
> Union(ImageSet(Lambda(_n, 2*_n*pi), S.Integers), ImageSet(Lambda(_n, 2*_n*pi
> + pi), S.Integers))
> # (sin(2*x) + sin(4*x) + sin(6*x)) will have lots of union of imagesets
> BigUnion could give `ImageSet(Lambda(_n, _n*pi), S.Integers)`, (although
> _union of imageset is under development, BigUnion can act as helper)

I'm still not following why it is needed, since this is still a union
of a finite number of sets (even though the sets themselves are
infinite). But maybe I'm missing something.

However, I suppose it could be useful for inequalities, and possibly
solutions in the complex domain or in higher dimensions. For instance,
sin(x) >= 0 has a solution set U_{n integer} [2*n*pi, (2*n + 1)*pi].

>
> I guess this is an idea that is in an initial stage (and that is why I can't
> imagine it in larger scale), and if you suggest that it won't be feasible I
> would rather remove it from the proposal.

I think it is feasible. BigUnion is probably quite straightforward to
implement, once we agree on an API.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/5f6aa7cc-6d9e-4ef6-8190-5f9581d858bc%40googlegroups.com.

[Yathartha Joshi]

Sorry for my late response (I was busy traveling). I see what you are trying to suggest of implementing for imageset, but I am still not sure about it whether it will be a good idea or not.

I will open an issue-cum-discussion for discussing the API.

Thanks!

Yathartha

[Amit Kumar]

I had a look at your PR 13045 & made some comments.