Degree
Master of Science
Program
Computer Science
Supervisor
Dr. Marc Moreno Maza
Abstract
With the advent of hardware accelerator technologies, multi-core processors and GPUs, much effort for taking advantage of those architectures by designing parallel algorithms has been made. To achieve this goal, one needs to consider both algebraic complexity and parallelism, plus making efficient use of memory traffic, cache, and reducing overheads in the implementations.
Polynomial multiplication is at the core of many algorithms in symbolic computation such as real root isolation which will be our main application for now.
In this thesis, we first investigate the multiplication of dense univariate polynomials with integer coefficients targeting multi-core processors. Some of the proposed methods are based on well-known serial classical algorithms, whereas a novel algorithm is designed to make efficient use of the targeted hardware. Experimentation confirms our theoretical analysis.
Second, we report on the first implementation of subproduct tree techniques on many-core architectures. These techniques are basically another application of polynomial multiplication, but over a prime field. This technique is used in multi-point evaluation and interpolation of polynomials with coefficients over a prime field.
Recommended Citation
Mansouri, Farnam, "On The Parallelization Of Integer Polynomial Multiplication" (2014). Electronic Thesis and Dissertation Repository. 2039.
https://ir.lib.uwo.ca/etd/2039