"High-performance code generation for polynomials and power series" by Ling Ding

Author

Ling Ding

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.

Share

COinS
 
 

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.