On The Parallelization Of Integer Polynomial Multiplication

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.

Name thesis:degree_name

M Sc

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

The University of Western Ontario

Year dc:date.issued

2014

Author dc:creator

• Mansouri, Farnam

Advisor dc:contributor.advisor

• Marc Moreno Maza

• Parallel algorithms
• High Performance Computing
• multi-core machines
• Computer Algebra

Language dc:language.iso

en_ca

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14721/34843

OAI identifier oai:identifier

oai:uwo.scholaris.ca:20.500.14721/34843