On the Factor Refinement Principle and its Implementation on Multicore Architectures

The factor refinement principle turns a partial factorization of integers (or polynomi­ als) into a more complete factorization represented by basis elements and exponents, with basis elements that are pairwise coprime. There are lots of applications of this refinement technique such as simplifying systems of polynomial inequations and, more generally, speeding up certain algebraic algorithms by eliminating redundant expressions that may occur during intermediate computations. Successive GCD computations and divisions are used to accomplish this task until all the basis elements are pairwise coprime. Moreover, square-free factorization (which is the first step of many factorization algorithms) is used to remove the repeated patterns from each input element. Differentiation, division and GCD calculation op­ erations are required to complete this pre-processing step. Both factor refinement and square-free factorization often rely on plain (quadratic) algorithms for multipli­ cation but can be substantially improved with asymptotically fast multiplication on sufficiently large input. In this work, we review the working principles and complexity estimates of the factor refinement, in case of plain arithmetic, as well as asymptotically fast arithmetic. Following this review process, we design, analyze and implement parallel adaptations of these factor refinement algorithms. We consider several algorithm optimization techniques such as data locality analysis, balancing subproblems, etc. to fully exploit modern multicore architectures. The Cilk++ implementation of our parallel algorithm based on the augment refinement principle of Bach, Driscoll and Shallit achieves linear speedup for input data of sufficiently large size.

Name thesis:degree_name

M Sc

Discipline thesis:degree_discipline

Computer Science

Year dc:date.issued

2011

Author dc:creator

• Ali, Md. Mohsin

Advisor dc:contributor.advisor

• Maza, Marc Moreno

• Factor refinement
• Coprime factorization
• Square-free factorization
• GCD-free basis
• Parallelism
• Muticore architectures.

Handle dc:identifier.uri

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

OAI identifier oai:identifier

oai:uwo.scholaris.ca:20.500.14721/18467