Delayed polynomial arithmetic and applications

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2008
Authors/Contributors
Author: Vrbik, Paul
Abstract
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.
Document
Copyright statement
Copyright is held by the author.
Permissions
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Attachment Size
etd4282.pdf 2.02 MB