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 <asmeu...@gmail.com> wrote:
> On Sun, Apr 28, 2013 at 11:51 PM, Thilina Rathnayake
> <thilina.r...@gmail.com> 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 <asmeu...@gmail.com>
> 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
> >> <thilina.r...@gmail.com> 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 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?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 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?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 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?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 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?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 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?hl=en-US.
For more options, visit https://groups.google.com/groups/opt_out.
