![Electronic Thesis and Dissertation Repository](../../assets/md5images/943042f88f25dd8adfffc3aeec6e330c.png)
Degree
Master of Science
Program
Computer Science
Supervisor
Moreno Maza, Marc
Abstract
Polynomials may be represented sparsely in an effort to conserve memory usage and provide a succinct and natural representation. Moreover, polynomials which are themselves sparse – have very few non-zero terms – will have wasted memory and computation time if represented, and operated on, densely. This waste is exacerbated as the number of variables increases. We provide practical implementations of sparse multivariate data structures focused on data locality and cache complexity. We look to develop high-performance algorithms and implementations of fundamental polynomial operations, using these sparse data structures, such as arithmetic (addition, subtraction, multiplication, and division) and interpolation. We revisit a sparse arithmetic scheme introduced by Johnson in 1974, adapting and optimizing these algorithms for modern computer architectures, with our implementations over the integers and rational numbers vastly outperforming the current wide-spread implementations. We develop a new algorithm for sparse pseudo-division based on the sparse polynomial division algorithm, with very encouraging results. Polynomial interpolation is explored through univariate, dense multivariate, and sparse multivariate methods. Arithmetic and interpolation together form a solid high-performance foundation from which many higher-level and more interesting algorithms can be built.
Recommended Citation
Brandt, Alex, "High Performance Sparse Multivariate Polynomials: Fundamental Data Structures and Algorithms" (2018). Electronic Thesis and Dissertation Repository. 5593.
https://ir.lib.uwo.ca/etd/5593
Included in
Algebra Commons, Numerical Analysis and Scientific Computing Commons, Theory and Algorithms Commons