Do we know how other computer algebra systems solve this problem? How robust are the algorithms behind wolframalpha.com ?
On Tue, Jan 21, 2014 at 6:00 PM, Aaron Meurer <asmeu...@gmail.com> wrote: > On Tue, Jan 21, 2014 at 4:55 AM, Harsh Gupta <gupta.hars...@gmail.com> > wrote: > > Hi, I'm Harsh Gupta I will be GSOC applicant this year. I want to discuss > > the solvers idea given on the Idea's > > page.https://github.com/sympy/sympy/wiki/GSoC-2014-Ideas#solvers > > Great to hear it. As noted on the ideas page, this one will require a > good deal of thought to be done in the application, so let's start > discussing. > > > > > Some of the aspect of the idea are discussed at > > https://groups.google.com/forum/?fromgroups=#!starred/sympy/8TM8cnuzkG8. > > > > > > Aaron Meurer said: > > > >> I think with TransformationSet we can do quite a bit. That handles > >> sets like {f(x) | x in A}. I think what is missing is the basic set > >> builder {x | P(x)}, where P(x) is a boolean predicate. > > > > > > > > Matthew Rocklin said: > > > >>> > Real issue here - how to represent some solutions (e.g. sin(x)==0). > >> > >> In sets we would represent this with > >> In [1]: imageset(k, pi*k, S.Integers) > >> Out[1]: {π⋅k | k ∊ ℤ} > > > > > > Implementing a general set builder will be very useful, we will need to > > define basic set operations like union > > and intersection on them. We might use a syntax like `BuildSet(expr, > > sym_in_inputset, cond)` > > > > In [1]: BuildSet(pi*k, (k, S.Integers), True).intersect(0, 10) > > Out[1]: {pi, 2*pi, 3*pi} > > So probably a good idea would be to look at the kinds of things that > solve might potentially want to return, and see where the deficiencies > are in the sets module. Things can get more complicated if you > consider higher dimensional sets. > > > > > > > Matthew Rocklin said: > > > >> It sounds like maybe solve should return a Set. > > > > > > I think it will be necessary to return set if we want to represent the > > solution of expressions like `floor(x) - 5`. > > See https://code.google.com/p/sympy/issues/detail?id=3975. > > One problem I see with returning sets is that it can break a lot of > existing > > code. > > Yes, this is a problem. I think we should create custom objects that > extend sets that allow to keep the current interface, like sols[0] or > sols[0][x]. The current interface is of course quite a few interfaces, > which is part of what makes it such a mess, but I think the dict=True > way is the cleanest. > > > > > > > As mentioned in the idea page we need to have a method to check if solve > > returns all the solutions. For polynomials or expressions which are > > solved by converting to polynomials we can compare the degree of the > > polynomial to the number of solutions returned. > > > > Other method can be verifying the number of the solutions by using the > > derivative of the function. Say we are given a *continuous* and > > *differentiable* function f(x) and it's derivative w.r.t x is g(x), > > then if g(x) has n solutions then f(x) cannot have more than n + 1 > > solutions. So, if the solve returns n + 1 solutions for f(x) then we are > > guaranteed that we have found all the solutions. > > For this we will need a discontinuity finder and we will also have to > make > > sure that we have found all the solutions for g(x), i.e., the derivative > of > > f(x), which can be done recursively or by using other methods. > > How do you determine the points of discontinuity of a function? In > general, you need to use solve (e.g., to find when you are dividing by > 0). Hopefully you wouldn't try to recursively solve the same > expression, or you would get nowhere, except infinite recursion. But > it does need the same functionality, because if you have expr = p/q, > you need to be sure you know *all* the zeros of q to be sure where > expr is discontinuous. > > > > > A third way can be using numerical solver. Say we use solve to find the > > solution of f(x) for some interval [a, b] then we can also run the > numerical > > solver for f(x) on [a, b] > > if the number of solutions by numerical solver and symbolic solve matches > > then we can be pretty sure that we have found out all the solutions of > f(x) > > in [a, b]. > > This has limitations too. Among them are: > > - Numerical solvers make no such guarantee either. They just try to > find solutions using whatever method and return them when they do. > > - Numerical solvers can be unstable for certain kinds of expressions. > > - If you have symbolic parameters, this doesn't work so well. At best, > you can try a multidimensional numerical solver, but your chances of > finding all solutions in a higher dimensional space are even worse. > > But this can definitely be used to weed out cases where we don't find > all the solutions. I was personally envisioning a more cautious > algorithm that only returns true when it is absolutely sure at each > stage, but I'm unclear just how far we can get with such a thing using > our current heuristics. > > An audit of the current solve code might be in order. In particular, > I'd like to know: > > 1. what are the different "solvers"? (if we split solve into "hints" > like with dsolve, these would be the different hints), and > 2. which are algorithmically complete (i.e., we know they will give > all solutions, or they can detect somehow if they may have missed > one)? > > And this may raise auxiliary questions, like: > > - to what degree can the different solvers be separated? For instance, > one solver (I'm not sure if it's actually implemented) would use > decompose() to solve recursively. How would such "recursive solvers" > look in a hints system? > > - of those that are heuristic (not algorithmically complete), can they > be improved? > > Another thing I'd like to know is if there's literature on solving > algorithms, particularly solving transcendental equations, and very > particularly on if there are any complete algorithms out there for > some class of equations. > > By the way, one algorithm, relating to solving, which we don't have > implemented yet is CAS (cylindrical algebraic decomposition). This > would be a GSoC project in itself to implement, though. > > Aaron Meurer > > > > > -- > > Harsh > > > > -- > > 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+unsubscr...@googlegroups.com. > > To post to this group, send email to sympy@googlegroups.com. > > Visit this group at http://groups.google.com/group/sympy. > > For more options, visit https://groups.google.com/groups/opt_out. > > -- > 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+unsubscr...@googlegroups.com. > To post to this group, send email to sympy@googlegroups.com. > Visit this group at http://groups.google.com/group/sympy. > For more options, visit https://groups.google.com/groups/opt_out. > -- 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+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out.
