Ling Ding

Date of Award


Degree Type


Degree Name

Master of Science


Computer 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.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.