[GSoC 2015] Solvers : Extending Solveset

[AMiT Kumar]

Hi, 

I am AMiT Kumar, I would be GSoC Applicant to SymPy this year. I have been following the SymPy Community for quite sometime now and have also got around 11-12 patches Merged in the Code base. So, now, I have got a decent idea of `How things works`.

I would like to work on Solvers as Mentioned on the Ideas Page. Last year Harsh Gupta did a very good job by Rewriting the Univariate solvers (solveset.py), I have gone through his work. After having conversation with him and digging into solveset, I got to know there is still a lot of work which needs to be done.

I could see a couple of entry points on the Ideas page:

https://github.com/sympy/sympy/issues/8725  (I have Merged a PR for this)

https://github.com/sympy/sympy/issues/8711  (Replace all internal solve() calls with solveset() ): TODO

Things, I would like to implement in solveset includes:

Multivariate Equation solving:

I think for solving multivariate equations, the order of variables should be given as input, so that we don't need to have a dict as output and we can return Set, as if we automatically detect variables, we need to output the dict of results.

• Multivariate functions with non point solution: (solvemv)
  

• In [0] solveset((x - 1)*(y - 2), (x, y))
  Out[1] {{1, arbitrary}, {arbitrary, 2}}

or we may return:

Out[1] {{1, (-oo, oo)}, {(-oo, oo), 2}}

• Multivariate functions with point solutions: (solvemv)
  

• In [0] solveset(x**2 + y**2, (x, y))
  Out[1] {0, 0}

Solve System of Equation: (solvesys)

(For system of Equation, we can have this): 

• In [0] solveset([x + y == 1, x - y == 0], (x,y))
  Out[1] {{1/2, 1/2}}

• For inequality solver (or for solvers in general) we also need to extend singularities module (though useful in general), so as to prevent getting wrong results, caused due to incorrect simplification of expression, as we saw in this issue: https://github.com/sympy/sympy/issues/8715 , Example: x + 1/x > -2 + 1/x  this inequality is written as expr = expr. lhs - expr.rhs , which cancels 1/x and gives wrong result, by including singular point in the solution.
• inequality solver in solveset currently uses inequalities.py (dependent on solve) (some discussion here: https://groups.google.com/forum/#!topic/sympy/Yp5NqrXmp2U). It is related to the next point below. 
  
• All internal solve() calls needs to be replaced with solveset() , this is very important for bringing out the solveset from sandbox to eventually replace solve().   (we need to consider the output API (return type) also while replacing).
  
• We also need to extend the set - boolean (relational) conversion methods to handle multivariate variables.
  
• Complex set Infrastructure is also not there (though I see a WIP PR for that), and yes we also need to see what other set capabilities we need to implement to support various other kinds of solutions.
  

And also other solvers as mentioned on ideas page like 'Equations solvable by LambertW function' also needs to work.

I would love to get feedback from the community before presenting my proposal.

Cheers!

AMiT Kumar

3rd Year Undergrad

Delhi Technological University

www.iamit.in

[Jason Moore]

Amit,

This sounds good. You should move this content to the SymPy wiki and use it as a starting point for your application submission.

Jason
moorepants.info
+01 530-601-9791

--
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 http://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/c786148f-3ea3-411f-b24c-93dc0174b381%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[AMiT Kumar]

Thanks, Jason

I have pasted this in my Application Draft and moved to Sympy Wiki:

https://github.com/sympy/sympy/wiki/GSoC-2015-Application-AMiT-Kumar--Solvers-:-Extending-Solveset

Cheers!

AMiT Kumar

3rd Year Undergrad

Delhi Technological University

www.iamit.in

[Harsh Gupta]

Great that you are working on solvers.

> Multivariate functions with non point solution: (solvemv)

> ```python

> In [0] solveset((x - 1)*(y - 2), (x, y))

> Out[1] {{1, arbitrary}, {arbitrary, 2}}

> ```

> or we may return:

> `Out[1] {{1, (-oo, oo)}, {(-oo, oo), 2}}`

The output should rather be a set of ProductSets rather than a set of sets.

General FiniteSet is unordered so {(-oo, oo), 2} is same as {2, (-oo, oo)}.

This example shows how you can define and use a product set.

```

In [9]: s = FiniteSet(2)*Interval(-oo, oo)

In [10]: s

Out[10]: {2} x (-oo, oo)

In [11]: (2, 0) in s

Out[11]: True

```

> Solve System of Equation: (solvesys)

> (For system of Equation, we can have this):

> ```python

> In [0] solveset([x + y == 1, x - y == 0], (x,y))

> Out[1] {{1/2, 1/2}}

> ```

It has the same issue as I mentioned above {1/2, 1/2} is unordered. You can use a FinteSet set of ordered tuple.

```

In [14]: FiniteSet((S(1)/2, S(1)/2))

Out[14]: {(1/2, 1/2)}

```

> we also need to extend singularities module (though useful in general)

+1

I suggest that you create a detailed plan of "how" you are going to solve

multivariate equations and how will you find a singular point.  I did a shallow

study of the current multivariate solver in `solve`.  The writeup is here:

http://hargup.github.io/posts/week-7.html Try searching for some literature,

dig into other older CAS and probably you should ask professor Fateman for

help. He can be harsh but if you have a thick skin he can be a lot of help too.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/51ec7e79-71d0-43e8-8cd9-d34b63af493e%40googlegroups.com.

[AMiT Kumar]

The output should rather be a set of ProductSets rather than a set of sets.

General FiniteSet is unordered so {(-oo, oo), 2} is same as {2, (-oo, oo)}.

This example shows how you can define and use a product set.

```

In [9]: s = FiniteSet(2)*Interval(-oo, oo)

In [10]: s

Out[10]: {2} x (-oo, oo)

In [11]: (2, 0) in s

Out[11]: True

```

Yes, I agree that would be much better.

 

> Solve System of Equation: (solvesys)

> (For system of Equation, we can have this):

> ```python

> In [0] solveset([x + y == 1, x - y == 0], (x,y))

> Out[1] {{1/2, 1/2}}

> ```

It has the same issue as I mentioned above {1/2, 1/2} is unordered. You can use a FinteSet set of ordered tuple.

```

In [14]: FiniteSet((S(1)/2, S(1)/2))

Out[14]: {(1/2, 1/2)}

```

I did gave a thought about returning FiniteSet of

ordered tuple, I thought It would look like a Set 

of Interval. 

Now since we don't return Interval like this,

so this should be good. I agree.

 

> we also need to extend singularities module (though useful in general)

+1

I suggest that you create a detailed plan of "how" you are going to solve

multivariate equations and how will you find a singular point.  I did a shallow

study of the current multivariate solver in `solve`.  The writeup is here:

http://hargup.github.io/posts/week-7.html 

I have gone through that write up, that looks good to me.

I will create a detailed plan as soon as things get more clear.

 

Try searching for some literature,

I found this http://www.research.ed.ac.uk/portal/files/413486/Solving_Symbolic_Equations_%20with_PRESS.pdf

on the Mailing list here: https://groups.google.com/forum/#!searchin/sympy/PROLOG/sympy/moSEFHop0n4/dRMJJOKVjRwJ

I am not sure how good it is, as Prof. Fateman's comments isn't very convincing about it:

You could look at it, but I think that, unless it has been changed since

I last looked, it has nothing at all to offer vs. an algorithmic approach.  

And some real problems in that it returns answers that are wrong, sometimes.

 

Though I am looking for some reasearch papers,

can you point me to some, which are good enough? 

 

dig into other older CAS

maybe like maxima?

 

and probably you should ask professor Fateman for

help. He can be harsh but if you have a thick skin he can be a lot of help too.

Sure, I will try to get some help from him.

 

 Cheers!

AMiT Kumar

[AMiT Kumar]

Yesterday I had a talk with Harsh regarding the Project, 

here is the summary:

He suggested me to make a more detailed plan for 

implementation of multivariate solver. I am working on that.

(Suggestions from the community are extremely welcome.)

We discussed about a few more things to implement

which would be quite useful, in sympy.calculus:

General Methods in Calculus:

(These methods would be very useful for differential calculus.)

• is_monotonic 
  
• is_increasing 
  
• is_strictly_increasing
  
• is_decreasing 
  
• is_strictly_decreasing
  

He also suggested me a couple of things which he (Harsh) planned to implement last year in his GSoC Project, including singularities, but was not able to complete, Now I would take that work, as far as Radical denesting is concerned, I would work on it if time permits. I think It's not a good idea to work on too many things, as last year we underestimated the work, that's why we were not able to complete all the things mentioned in Harsh's proposal.

I would keep this thread updated, parallel to my progress on my proposal.

Thanks,

AMiT Kumar

3rd Year Undergrad

Delhi Technological University

www.iamit.in

[AMiT Kumar]

Hi,

I was trying to explore solvers for multivariate functions in other 

CAS like Maple and Mathematica and Maxima,

Here is the documentation I found about solvers in Maxima: 

https://github.com/andrejv/maxima/blob/master/share/algebra/solver/solver1-en.html

I think we need to be very specific about the problem set we are 

going to tackle for 'Multivariate Functions' in the solveset.

Here are the cases where we encounter Multivariate Functions:

* System of Multivariate Equations:

This is a lot of work in the Polynomials module, which needs to 

be done, before addressing it in solvers.

* Multivariate Inequalities:

This can also not be addressed in solvers until we have CAD 

(Cylindrical Algebraic Decomposition), which is itself a GSoC

Project.

The couple of cases which are in the scope of current discussion are:

* Multivariate Single Equation with Point solution.

We can only solve equations which are of the form (x - a)*(y - b)*(z - c)*... 

or convertible to this form. 

Though other popular CAS are also not good for solving equations other than

this form. If we don't know the solution we can just return it in terms of other 

variables as in next case.

* Multivariate Single Equation with non-point solution.

In this case, we can output results in the form of the 

other variables: For Example:

In []: solve(x**2 + y**3 == 1, (x, y))
Out[]: {x, sqrt(1 - y**3)}  # x: arbitrary

Similiar to Wolframalpha: http://www.wolframalpha.com/input/?i=solve%28x**2+%2B+y**2+%3D%3D+1%29

Or else in this case we could have some functionality for curve 

detection (maybe using geometry module), to return information about 

curves in cases like:

In []: solve(x**2 + y**2 == 4)
Out[]: {Circle, (0, 0), 2}

(as Here we know that the output: x = +/-sqrt(y**2 - 1) is not of much significance.)

We need not worry much about multivariate, the focus should be more on:

1) Solving Transcendental equations, such as 'Equation solvable by LambertW.

2) Linear Systems (system of linear equations)

3) Modularising the current code.

4) What else set infrastructure we need.

I would also like to discuss more about the sub-modules in which the

current solve needs to broken, such as: linear systems, 

transcendental Equations, etc.

[AMiT Kumar]

One correction:

* System of Multivariate Equations:

We CAN implement this for comparatively lower order polynomial in new solveset.

The only thing We can't implement is Multivariate inequalities, as we will need CAD for that.

[Aaron Meurer]

On Sat, Feb 28, 2015 at 10:53 PM, AMiT Kumar <dtu....@gmail.com> wrote:
> One correction:
> * System of Multivariate Equations:
> We CAN implement this for comparatively lower order polynomial in new
> solveset.
>
> The only thing We can't implement is Multivariate inequalities, as we will
> need CAD for that.

It's still a good idea to think about them when designing the APIs, as
we will hopefully eventually get a CAD implementation.

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 http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/de89e1e3-d053-439d-bb9a-32777f3a6b80%40googlegroups.com.

[AMiT Kumar]

On Monday, March 2, 2015 at 12:33:51 AM UTC+5:30, Aaron Meurer wrote:

On Sat, Feb 28, 2015 at 10:53 PM, AMiT Kumar <dtu....@gmail.com> wrote:
> One correction:
> * System of Multivariate Equations:
> We CAN implement this for comparatively lower order polynomial in new
> solveset.
>
> The only thing We can't implement is Multivariate inequalities, as we will
> need CAD for that.

It's still a good idea to think about them when designing the APIs, as
we will hopefully eventually get a CAD implementation. 

Indeed.

I agree on that.

[AMiT Kumar]

Hi,

I saw that the solving of linear systems is also a Mess in 

the current solve, There is lot of duplication of Methods/Algorithms 

in the current code, as mentioned by Aaron in this PR. 

Ref: https://github.com/sympy/sympy/pull/2580

We need to have a General linear solve for solving system of

linear Equation in the new `solveset`.

Something similiar to Mathematica's LinearSolve: 

http://reference.wolfram.com/language/ref/LinearSolve.html

Method to convert system of Equation to Matrix  Form would also be

useful.

Ref: https://groups.google.com/forum/#!topic/sympy/Wqs1OhTBexg/discussion

As of now, I am doing an Audit of solving of Linear systems to 

tackle this Problem.

[AMiT Kumar]

Hi,

I was thinking, How about designing the  solveset similiar 

to the ODE Module . Something like hints system to classify solvers?

Example:

primaryhint = [

    "univariate",

    "multivariate",

    "single_eq",

    "multiple_eq"

    ]

subhints = [

    'solve_linear_system'

    'linear_trig',

    'polynomial',

    'transcendental',

    'piecewise',

    'relational'

    'solve_lambertw'

    'miscellaneous'

    ]

def classify_solver(f, symbols=None):

    """

    Clasifies the input equation(s)/function(s) to solve for, into possible

    hints such as linear, univariate, multivariate, etc.

    """

    hints = []
   
   # Methods to classify Equations

def solveset(f, symbol=None):
    
    if eq_type == 'linear':
        solve_linear(f, symbol)
  
    if eq_type == 'linear_system':
        solve_linear_system(f, symbol)

    .
    .
    . and so on

In that case we will be able to add new solvers, without messing with 

the others, and we will have a more robust and flexible framework

which will be easy to extend.

I think, building a robust framework, which felicitates further 

development, worth much more than adding new solvers.

Thoughts from the community are invited.

AMiT Kumar

[Joachim Durchholz]

Am 08.03.2015 um 07:18 schrieb AMiT Kumar:
> I think, building a robust framework, which felicitates further
> development, worth much more than adding new solvers.

+1

I can't comment much on how such a framework would need to look like
because I know too little about what solving methods exist and what
kinds of services they'd need, but given the sheer number of solvers
it's clear that making a framework will pay off.

solveset already is such a framework.
Building a subframework on top of solveset, specialized for the needs of
ODE solving, would certainly be helpful.

Note that to build a framework (or subframework), experience with or
knowledge about existing solvers will be very important; it's the guide
to selecting what kinds of services you want (and do not want) in the
framework. It's not a good idea to add a service "just in case", because
(a) it requires that coder for new solvers will have to look at it and
decide whether it's useful to them or not, (b) each additional feature
adds design constraints.
So without knowledge about solving methods, there is a very real danger
that you end up coding features that nobody needs and that make it
harder to code or use the features that are really needed.
Actually this happens a lot even with people with lots of experience in
the field. It is the main reason why the first incarnation of most
frameworks is stillborn (but still essential because it is where
experience is collected).

IOW if you do a framework project, it will be immensely more worth it if
you can do it for a few years and help it mature.

[Aaron Meurer]

That sounds good, except as I noted at
https://groups.google.com/forum/#!msg/sympy/42GdMJ9ssyM/swC6bHVunP8J,
it's very important to build this around a framework of rewriting and
decomposition. You want to be able solve, f(g(x)) = 0, where f is a
polynomial and g is a lambertW (for example). You want the hints to
be as simple as possible, and any complicated equations to be solvable
by an application of possibly many hints. This is more complicated
than what the ODE solver does.

Rewriting basically boils down to simplifying the matching portion of
the hints. This is something that is not done very well in the ODE
system, so I would only look there to see how it is lacking.

You want each hint to match a simple pattern, and then have some set
of rules on how to rewrite different expressions to that pattern
mathematically, even if they don't match it structurally. I would take
a look at the rules system used in the fu algorithm, and in the unify
submodule. Also take a look at Francesco's pattern matching
suggestions (search the mailing list and the wiki).

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 http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/5b7393ef-7d4d-46f9-bfcd-dbbeb38639c4%40googlegroups.com.

[AMiT Kumar]

Hi,

Sorry for late reply, (I was busy with Mid terms & Assignments).

Based on the above Ideas, I have made the draft of my Proposal on SymPy wiki, Please have a look:

https://github.com/sympy/sympy/wiki/GSoC-2015-Application-AMiT-Kumar--Solvers-:-Extending-Solveset

Thanks,

AMiT Kumar

3rd Year Undergrad

Delhi Technological University

www.iamit.in

[Aaron Meurer]

Sorry if you already answered this in the application and I didn't see
it, but what is the difference between primary hints and subhints?

Also, I should point out that you're going to have to remove most (or
maybe all) of your formatting when you submit your proposal in
Melange. I would just try to make it look as good as possible in
Melange, and provide a link to the wiki so people can read it there.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/6247761d-1673-4f10-bfcd-c0b92a555e7b%40googlegroups.com.

[Jason Moore]

FYI: I heard from another past student that using pandoc to convert from github wiki markdown to html works pretty well for the Melange submission.

Jason
moorepants.info
+01 530-601-9791

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6LCoaNKjroiz7sSaHEDtDg%2BRywWSkC4bzUEa6Wh-9mwKw%40mail.gmail.com.

[Aaron Meurer]

If the Malange form is html, couldn't you just copy the html from the
wiki source as well?

Anyway, don't stress about Melange formatting. We know that it's very
difficult to get things formatted well (or at least, I know, since I
was a student twice).

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/CAP7f1AgUg38H%2Bc68AazxcwwY9EHbgDqqfqzb9YvQoXaQMu_k2A%40mail.gmail.com.

[AMiT Kumar]

The primary hints doesn't have much significance, the sub hints

are the main hints which would contain various methods, used 

to solve different equations.

The primary hint is just the primary information we would like to extract from input, (I should rather rename it)

to classify equation on the basis of univariate", "multivariate_or_parametric", "single_eq", "multiple_eq.

For example:

def classify_primaryhint(f):
    """Clasifies expression(s) `f` based on the primaryhints. Primaryhints are
       "univariate", "multivariate_or_parametric", "single_eq", "multiple_eq".


    Examples
    ========


    >>> from sympy import *
    >>> from sympy.solvers.solveset import *
    >>> from sympy.abc import x
    >>> classify_primaryhint(x**2 + 2*x + 1)
    >>> ['single_eq', 'univariate']


    """


    phints = []


    # classify by number of Equations, i.e single_eq or multiple_eq
    if not iterable(f):
        phints.append('single_eq')
        f = sympify(f)
        free_symbols = set(f.free_symbols)


    else:
        free_symbols = []
        for fi in f:
            fi = sympify(fi)
            free_symbols.append(fi.free_symbols)
        if len(f) > 1:
            phints.append('multiple_eq')


    # classify by univariate and multivariate
    if len(free_symbols) == 1:
        phints.append('univariate')
    elif len(free_symbols) > 1:
        phints.append('multivariate')
    return phints

Thanks,

AMiT Kumar

[AMiT Kumar]

@Aaron   @Jason

On Tuesday, March 17, 2015 at 7:19:14 AM UTC+5:30, Aaron Meurer wrote:

If the Malange form is html, couldn't you just copy the html from the
wiki source as well?

I think melange has improved its the editor this year, I have just tried to copy

my Application from the wiki into the Melange, and the Formatting looking exactly

similar to wiki.

[AMiT Kumar]

It looks good only while preview in Melange, but doesn't renders 

same formatting, when It's submitted.

AMiT Kumar

[Chris Smith]

See also https://github.com/sympy/sympy/pull/2580 which started some work related to solving systems of equations.

[AMiT Kumar]

Thanks Chris, for pointing me to that PR, I did had a look at that.

That PR, exposed me to the mess of solving linear systems in solvers.

AMiT Kumar

[AMiT Kumar]

Hi,

Since there is only 1 week left for Student Application Deadline,

I have Uploaded my Proposal on Melange as well:

Project Title: SymPy Improving Solvers : Extending Solveset

Organization: Python Software Foundation

Organization: NumFOCUS

User Name: aktech_amit

Please have a look and suggest changes, I have fixed the formatting as well.

AMiT Kumar

3rd Year Undergrad

Delhi Technological University

www.iamit.in

[AMiT Kumar]

Hi!

I have updated my Proposal by making a few substantial changes, at SymPy wiki:

https://github.com/sympy/sympy/wiki/GSoC-2015-Application-AMiT-Kumar--Solvers-:-Extending-Solveset

Please have a look.

AMiT Kumar

3rd Year Undergrad

Delhi Technological University

www.iamit.in