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.
