Thanks Aaron for your very informative reply. I will definitely take note of the points you have brought up.
Regards, Thilina Rathnayake. On Mon, Apr 29, 2013 at 11:32 AM, Aaron Meurer <[email protected]> wrote: > On Sun, Apr 28, 2013 at 11:51 PM, Thilina Rathnayake > <[email protected]> wrote: > > Thanks Aaron for your reply. I am proposing this as a GSoC project. > > Sorry, I didn't mention it earlier. However, even if this is not > accepted > > as a > > GSoC project, I would like to work on this. > > OK. In that case, you should get writing on your application, as the > deadline is Friday. What you wrote here is a good start. You will also > need to delineate it into a timeline, think (a lot) about the > interface (my personal opinion is that you should mimic the ODE module > exactly, but your application should demonstrate that you understand > that structure), and give more details to demonstrate that you really > do understand the theory (maybe show how to solve an example problem). > > > > > The two n's are different. I should have used distinct letters instead of > > the n's. > > Sorry for the confusion. > > > > I have assumed that all ai's are nonzero and the above linear Diophantine > > equation (DE) satisfies the condition for the existence of solutions. If > > n>=3, > > then solutions to the above linear equation can always be given using n-1 > > parameters. If we define first n-2 xi's as parameters, then with > another > > parameter m, we can express the solutions for the other two. For n=2, > > solutions > > can be determined using only one parameter, m. For n=1, If a solution > > exists, > > it can be computed by dividing b by a1. I guess I answered your question. > > If not please let me know. > > > > I checked the ODE module and indeed it can be used as a reference model > > for this project. I hope to implement a method DiophantineSolve(), which > > would > > take DE to be solved in the form f(x1, x2, x3, ...xn) = 0 or f(x, y, z) > = 0 > > as an > > argument. All of the proposed equations can be expressed in such a way > by a > > simple > > rearrangement. It will return the solutions/solution if they/one > exist(s). > > > > For inner computations a classification function would be needed as in > ODE > > module. > > That can be used to determine whether the DE is linear, quadratic, > > Pythogrean, .. etc. > > Algorithm used for the solution will depend on the result of this > > classification. > > Yes, I believe the structure can match the ODE module almost exactly, > at least as far as matching having various hints goes. You might also > want to look at the constantsimp stuff if your solutions will result > in a dependence in new, arbitrary parameters. I wouldn't worry about > that for the outset, though, even if that is the case. > > > > > I am still studying the ODE module. I am not familiar with pattern > matcher > > either. > > The pattern matcher is very simple. Just set up the variables you want > to match as Wild, create the pattern expresion, and use matches. The > issue is that it is very stupid in that it matches almost nothing > beyond what you explicitly tell it to. You also need to be careful to > always set the exclude parameter on the Wild objects to exclude your > variables. Otherwise, if you do something like try to match a*x + b*y > against 3*x + 2*y (here a and b are the Wilds and x and y are the > Symbols), you will expect to get {a: 3, b:2}, but you might instead > get {a:0, b:3*x/y + 2}. > > Aaron Meurer > > > I would take a look at that also. Comments and suggestions are > appreciated. > > > > Thanks in advance. > > > > Regards, > > Thilina Rathnayake. > > > > > > On Mon, Apr 29, 2013 at 1:52 AM, Aaron Meurer <[email protected]> > wrote: > >> > >> Just to be clear, is this for GSoC, or is this just something that you > >> want to implement on your own? > >> > >> On Sun, Apr 28, 2013 at 2:07 PM, Thilina Rathnayake > >> <[email protected]> wrote: > >> > Hi, I would like to implement a Diophantine equations module for > Sympy. > >> > You can find my pull request here. It's still not merged. > >> > > >> > I hope to solve following classical Diophantine equations. All the > >> > variables > >> > and constants > >> > used here are integers. > >> > > >> > > >> > 1) a1x1 + a2x2 + a3x3 + ...+ anxn = b (Linear diophantine equation) > >> > Here a1, a2, ... an and b are constants.If solvable (there is a > >> > condition to > >> > determine this), > >> > solving this equation means expressing any two variables using other > >> > variables and an > >> > arbitrary integer n. i.e. solution is given by > >> > x1 = x1, x2 = x2, ... xn-2 = xn-2 , xn-1 = f( x1, x2, ... xn-2, n), > xn-1 > >> > = > >> > g( x1, x2, ... xn-2, n) > >> > f and g are functions to be determined. > >> > >> The n in the indices is different from the other n, right? > >> > >> Is the rank of the system always 2 in this case? > >> > >> > > >> > 2) x12 + x22 + x32 + ... xn2 = k > >> > Here k is a non-negative constant. There will be a number of solutions > >> > depending on > >> > n and k. Solving this means assigning constants a1, a2, ... an to > xi's > >> > respectively. > >> > > >> > 3) x12 + x22 + x32 + ... xn2 = xn+12 (extension of Pythogorean > equation) > >> > Solving this is pretty standard. There is a general primitive solution > >> > set > >> > using n relatively > >> > prime integers. All other solutions can be obtained by multiplying > those > >> > equations by > >> > an arbitrary integer. > >> > > >> > 4) x2 + axy + y2 = z2 > >> > Here a is a constant. If z is a variable, a general solution can be > >> > given to > >> > this equation > >> > using a and three arbitrary integers. If z is a constant actual > >> > solutions > >> > can be given. > >> > > >> > 5) x2 - Dy2 = m2 (Pell's equation) > >> > Here D and m are constants. This has either no solution or infinitely > >> > many > >> > solutions. > >> > ax2 - by2 = 1 and ax2 + bxy + cy2 + dx + ey + f = 0 can also be solved > >> > with > >> > the light > >> > of Pell's equation. > >> > > >> > Lot of Diophantine equations can be converted to one of these forms. > >> > Addition of this kind > >> > a module will be a huge enhancement for Sympy. I would like to know > how > >> > I > >> > can improve > >> > this. Thanks in advance. > >> > >> It sounds like a good start. If this is for GSoC, I'd like to see more > >> details. > >> > >> One thing to be aware of is that you will probably spend more time > >> worrying about how to pattern match these things than writing the > >> algorithms to solve them. SymPy has .match, but it can be limited. > >> For example, you can easily write a pattern to match > >> > >> x1**2 + x2**2 = k > >> > >> But if you can solve that, then you can also solve > >> > >> (x1 - 1)**2 + (x2 - 1)**2 = k > >> > >> or > >> > >> x1**2 - 2*x1 + x2**2 - 2*x2 = k > >> > >> by a simple shift. But the same simple pattern won't match either of > >> these. I ran into this kind of issue all the time when I wrote the ODE > >> module, which works very similarly (by the way, you should take a look > >> at the design there, as I think the design of this module can be very > >> similar). We should extend the pattern matcher's abilities to be able > >> to still succulently write patterns, but to allow them to match more > >> advanced things like shifts automatically. > >> > >> Of course, the worst case scenario is that it won't recognize a given > >> equation as being in a certain form, so it just won't be able to solve > >> as much as it could. So if you want, you could focus on this, or you > >> could leave it to someone else. > >> > >> Aaron Meurer > >> > >> > > >> > > >> > > >> > References > >> > [1] An Introduction to Diophantine Equations, Andreescu, Titu, > Andrica, > >> > Dorin, Cucurezeanu, Ion > >> > [2] http://mathworld.wolfram.com/DiophantineEquation.html > >> > [3] http://en.wikipedia.org/wiki/Diophantine_equation > >> > > >> > Regards, > >> > Thilina Rathnayake. > >> > > >> > -- > >> > 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?hl=en-US. > >> > 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?hl=en-US. > >> 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?hl=en-US. > > 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?hl=en-US. > 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?hl=en-US. For more options, visit https://groups.google.com/groups/opt_out.
