Holzer reduction and some modifications
Hi All, This week I managed to implement Holzer’s reduction and change the behaviour of DE module a little bit. First let’s take a look at Holzer’s reduction.
Holzer reduction is concerned with reducing solutions of the quadratic ternary nonrmal equation . The Holzer’s theorem says that if the above equation is solvable there is always a solution such that . The algorithm for this is explained in . Below is a rough sketch. Before applying the algorithm we have to make square free and we assume that positive and is negative(We can always select in such a way that this is the case). Suppose there is a solution that is not Holzer reduced.
- If is even set and let be any solution to the equation .
- If is odd, c is odd let and let be any solution to the equation .
- Let be the nearest integer to .
- Then the following expressions for gives a solution such that .
Continuing this manner one would find a solution such that .
Some changes to DE module
I made some changes to the structure of DE module too. Now every type of equation returns a tuple ordered according to the sorted order of variable names used in the equation. Quadratic ternary forms and linear equations returns only one tuple, the parametric solution, and quadratic binary equation returns a set of tuples. This format may be changed in future. The most important change I did to the DE module is that, now before solving any given equation, DE module checks whether that can be factored and If so, solves those factors separately. For example, given the equation , it will solve and separately and combine those results. Also I managed to implement a general method for testing that would check whether the solutions returned by various methods satisfy the original equation. So I hope to get rid of the other redundant methods like check_ternary_quadratic(), solution_ok_quadratic() in the test file. A thank should go to Aaron for proposing such a methodology.
Pernici has pointed out that some of the solution methodologies in quadratic binary form can be improved so that they take less time. He also has done a great job in implementing the solutions for quadratic congruence . I hope to use those results when his PR gets merged into master. He proposed a method due to cornacchia to improve the speed of the solutions but after a little surveying, I found that implementing solutions for can be used to improve the speed. Current algorithms for solving binary quadratic equation employs a general solving method so it miss out some speed enhancements for the special case . My plan is if can be converted to the form , then solve it using methods for that, otherwise apply the general method. I found a good reference  for this. A huge thank should go to Pernici for pointing out the improvements.
 Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0.
 Binary Quadratic Forms: An Algorithmic Approach, J. Buchmann and U. Vollmer, Springer-Verlag, Berlin, Heidelberg, 2007.