Hi Ondrej, I am pleased to say that I managed to implement the solutions for quadratic ternary forms. Only thing we have to verify is that whether they are complete. I found one incident in the current implementation where it returned a partial solution. I added it as a different test. I plan to implement the algorithm Implemented in MAGMA in the upcoming days, and also it seems like MAGMA's algorithm is faster. So we can make it the main algorithm used by `diop_solve()`.
There is one major factor affecting the speed of the algorithm, the overhead of the function `quadratic_congruence()` which solves a quadratic congruence. This function was also used in solving binary quadratic forms also. I found a link to a reference material on the problem. Also the parametric solution returned by the solver would be more elegant if we could reduce the basic solution we found using the `descent()` by the Hozler's reduction algorithm. These are the area's I am going to focus in the future. (PS - You have already commented in the pull request. Thank you for that. I'll get to it as soon as I finish writing this week's blog post) Regards, Thilina. On Fri, Jul 19, 2013 at 9:31 PM, Ondřej Čertík <[email protected]>wrote: > On Fri, Jul 19, 2013 at 1:48 AM, Thilina Rathnayake > <[email protected]> wrote: > > Ondrej, > > > > I thought of implementing the sieving method described in the book to > verify > > the answers > > returned by the descent method. It's simple to implement. What actually > we > > need to check > > in descent method is whether it finds a solution if one exist, base > solution > > returned by different > > algorithms will be different and it's sufficient to check whatever the > > solutions returned indeed > > satisfy the equation. > > > > But I would say verifying descent with the algorithm in MAGMA would be > more > > convincing. > > Only thing is that I don't know much about lattice reduction. But I can > > always get help from > > the SymPy community if something goes wrong. So I will give a try to > > implement it. > > That sounds like a good plan. > > > > > Yes, next thing is to get the parametrized formula for all the > solutions. I > > am working on it > > Excellent, cannot wait to play with it. > > Ondrej > > > now. > > > > > > Regards, > > Thilina > > > > > > > > > > On Fri, Jul 19, 2013 at 2:30 AM, Ondřej Čertík <[email protected]> > > wrote: > >> > >> Thilina, > >> > >> On Thu, Jul 18, 2013 at 1:43 PM, Thilina Rathnayake > >> <[email protected]> wrote: > >> > Seems like they haven't implement it anywhere else. I found an > algorithm > >> > that > >> > was implemented in MAGMA, but it involves lattice reduction and since > I > >> > am > >> > almost finished with the descent method, I didn't try to implement > that. > >> > I > >> > would > >> > try that If I can find some free time or perhaps after completing all > >> > the > >> > deliverables of my > >> > project proposal. > >> > >> But you should be able to check the final results, after you implement > >> the calculation of all solutions. Right? > >> > >> > > >> > And once again, Thank you very much mario. If not for your help, I > would > >> > have wasted a > >> > lot of time with this. But sadly, there is still a few problems. The > >> > programme ran infinitely > >> > when an input like (-3 , -4) was given. It should return (None, None, > >> > None) > >> > in this case. > >> > I fixed it by adding a if condition to return a None-tuple when both > the > >> > inputs are negative. > >> > So now it's okay. I have attached the modified version herewith. > >> > > >> > Also when I gave the input (3, 3), it runs infinitely. I couldn't fix > >> > it. > >> > But I found a > >> > workaround to get rid of all of these bugs. I used a slightly modified > >> > version of your first > >> > programme and before I call descent() method in it, I made the two > >> > inputs A > >> > and B square > >> > free and did some after-processing to recover the solutions for the > >> > original > >> > inputs. > >> > Now it's all fine. > >> > >> Excellent! Great job. > >> > >> > > >> > If not for the case with the input (3, 3) ( same thing happens with > (7, > >> > 7), > >> > ..) your second > >> > programme produces simpler answers than the first one. However there > is > >> > a > >> > way to reduce > >> > the magnitude of the answers returned by the descent method so we can > >> > use it > >> > with the > >> > current implementation if needed. I plan to give the user the choice > to > >> > specify whether > >> > the base solutions should be reduced before using them in the > >> > parametrization to find all the > >> > solutions for the equation. > >> > >> So I think the next step is to implement the retrieval of all the > >> solutions, > >> as described by the book, isn't it? > >> > >> Ondrej > >> > >> > > >> > Thank you and best regards, > >> > Thilina > >> > > >> > > >> > > >> > On Thu, Jul 18, 2013 at 7:10 PM, Ondřej Čertík < > [email protected]> > >> > wrote: > >> >> > >> >> Thanks Mario! > >> >> > >> >> I really appreciate your help. That's quite amazing that they had few > >> >> bugs in the algorithm. Do you think they didn't actually implement it > >> >> in any software? > >> >> > >> >> Ondrej > >> >> > >> >> On Thu, Jul 18, 2013 at 5:36 AM, mario <[email protected]> > wrote: > >> >> > The attached version works in the mentioned cases; the bug is fixed > >> >> > reducing > >> >> > to the case ``A > 0, B > 0`` > >> >> > > >> >> > > >> >> > On Thursday, July 18, 2013 11:28:22 AM UTC+2, Thilina Rathnayake > >> >> > wrote: > >> >> >> > >> >> >> I should try making input coefficients to be square free. I think > >> >> >> the > >> >> >> algorithm in general, > >> >> >> does not work when the coefficients are not square free. > >> >> >> > >> >> >> > >> >> >> > >> >> >> On Thu, Jul 18, 2013 at 2:53 PM, Thilina Rathnayake > >> >> >> <[email protected]> > >> >> >> wrote: > >> >> >>> > >> >> >>> We can add descent(23, 616) to the bug list too. It also return > >> >> >>> (None, > >> >> >>> None, None) > >> >> >>> but (6, 1, 38) is a solution. By finding more and more test cases > >> >> >>> which > >> >> >>> fail, I think we can > >> >> >>> identify a pattern and then the cause for the bug. > >> >> >>> > >> >> >>> Regards, > >> >> >>> Thilina > >> >> >> > >> >> >> > >> >> > -- > >> >> > 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. > >> >> > >> >> > >> > > >> > -- > >> > 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. > >> > >> > > > > -- > > 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. > > > -- 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.
