Date of Award
2011
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Supervisor
Dr. Marc Moreno Maza
Abstract
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.
Recommended Citation
Ali, Md. Mohsin, "On the Factor Refinement Principle and its Implementation on Multicore Architectures" (2011). Digitized Theses. 3462.
https://ir.lib.uwo.ca/digitizedtheses/3462