# Descent method with gaussian reduction.

Sorry for a very late blog post, I had a really busy week and finally I managed to find sometime to write about the progress I made in the last week. I implemented an improved version of the descent method which uses gaussian reduction. I found this algorithm in [1]. Here is a sketch of the algorithm.

#### descent(a, b)

1. If then swap and , solve the resulting equation, then swap and in the solution obtained.

2. If then set and stop.

3. If then set and stop.

4. If there is no solution (since must be ).

5. If then set and stop.

6. If then let be a solution of , set and stop.

7. Let be a solution to . with , and set , so that .

8. Use** lattice reduction** to find a new nontrivial solution to the congruence with as small as possible.

9. Set and write with square-free.

10. Let be a solution to then

I spent a lot of time finding an algorithm for lattice reduction. There were generalized algorithms but I looked for something which is faster because we are concerned with vectors with two bases. I found gaussian reduction algorithm in [2] which uses a method specific to this case.

#### References

[1] .. Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0.

[2] .. Gaussian lattice Reduction [online]. Available: http://home.ie.cuhk.edu.hk/~wkshum/wordpress/?p=404

- Posted in: GSoC-2013-SymPy
- Tagged: descent method, gaussian reduction

## Recent Comments