Date of Award
2009
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Supervisor
Dr. Éric Schost
Abstract
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.
Recommended Citation
Ding, Ling, "High-performance code generation for polynomials and power series" (2009). Digitized Theses. 4105.
https://ir.lib.uwo.ca/digitizedtheses/4105