Date of Award
2007
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Supervisor
Dr. Stephen Watt
Abstract
Symbolic polynomials, whose exponents themselves are integer-valued multivariate polynomials, arise often in algorithm analysis. Unfortunately, modern computer algebra systems do not provide ample support for their algebraic structures. Basic operations involving symbolic polynomials are indeed trivial (addition, multiplication, derivatives); however, other crucial operations remain much more difficult, such as factorization and GCD. Watt has given two separate methods to solve these challenging problems. The first uses a change of variables, e.g. xn to X, xnm to Y. Doing so increases the number of variables potentially exponentially. Evaluation/Interpolation is used in the second algorithm. Projection methods introduce fewer variables but have larger degrees. We propose several adaptations to this idea to attempt to reduce the degree and number of required images. These include: sparse interpolation, evaluation point optimization and evaluating at primitive roots of unity. We give an in depth comparison of these algorithms, both empirically and theoretically.
Recommended Citation
Malenfant, Matt, "A Comparison of Two Families of Algorithms for Symbolic Polynomials" (2007). Digitized Theses. 4495.
https://ir.lib.uwo.ca/digitizedtheses/4495