Date of Award


Degree Type


Degree Name

Master of Science


Computer Science


Dr. Stephen Watt


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.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.