On Tue, Jan 21, 2014 at 4:55 AM, Harsh Gupta <[email protected]> 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 [email protected]. > To post to this group, send email to [email protected]. > 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 [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out.
