Date of Award
Master of Science
Dr. Éric Schost
Newton iteration is a versatile tool. In this thesis, we investigate its applications to the computation of power series solutions of first-order non-linear differential equations.
To speed-up such computations, we first focus on improving polynomial multi plication and its variants: plain multiplication, transposed multiplication and short multiplication, for Karatsuba’s algorithm and its generalizations. Instead of rewriting code for different multiplication algorithms, a general approach is designed to output computer-generated code based on multiplication graph representations.
Next, we investigate the existing Newton iteration algorithms for differential equa tion solving problems. To improve their efficiency, we recall how one can reduce the amount of useless computations by using transposed multiplication and short mul tiplication. We provide an optimized code generator that applies these techniques automatically to a given differential equation.
Ding, Ling, "High-performance code generation for polynomials and power series" (2009). Digitized Theses. 4105.