Algorithms for Solving Polynomial Equations

17 Jan -- 05 May 2012

Class Timings: Tuesday and Friday 11:30 to 13:00

Tentative Schedule

• Lecture 1: Introduction -- An Overview. Notes
• Lecture 2: Arithmetic -- FFT over complex numbers and modular FFT. Notes
• Lecture 3: Asymptotically Fast Euclid's Algorithm. Notes
• Lecture 4: Euclid's Algorithm over Rings -- The Theory of Subresultants. Notes
• Lecture 5: Resultants. Notes
• Lecture 6: Bounds. Notes
• Lecture 7: Sturm Theory. Notes
• Lecture 8: Complex Root Isolation. Notes
• Lecture 9: The Descartes Method. Notes
• Lecture 10: The Descartes Method -- Bernstein basis interpretation. Notes
• Lecture 11: The Continued Fraction Approach to Root Isolation. Notes
• Lecture 12-13: The Interval Arithmetic Approach to Root Isolation. Notes
• Lecture 14-17: Student Presentations
• Lecture 18: Algebraic Curves -- Introduction. Notes
• Lecture 19: Algebraic Curves -- Singularities and Tangents. Notes
• Lecture 20-21: Algebraic Curves -- Computing Topology of Curves. Notes
• Lecture 22: Generalizing Sturm Theory. Notes

References

Books

• Yap: Fundamental Problems in Algorithmic Algebra.
• Basu, Pollack, Roy: Algorithms in Real Algebraic Geometry.
• Mignotte: Mathematics for Computer Algebra.
• Theory of Equations (various authors).
• Cox, Little, O'Shea: Ideals, Varieties and Algorithms.

Homework

• Homework 1: Assigned on 4th Feb; Due Date 24th Feb (revised to 6th Mar).
• Homework 2: Assigned on 29th Feb; Due Date 16th Mar (revised to 30th Mar).
• Homework 3: Assigned on 13th Apr; Due Date 27th Apr.