Delayed polynomial arithmetic and applications

The goal of this thesis is to develop an environment for doing delayed polynomial arithmetic. We present the various known ‘heap’ methods for multiplication and division and adapt them to create a high performance implementation in C. We also present a storage-minimizing variant of this package that allows us to address some fundamental problems with Bareiss’ fraction-free method for calculating determinants and the subresultant algorithm. We show that the memory usage for both of these algorithms can be linearly related to the size of the output instead of the intermediate values.