<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T12:06:23Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1035" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1035</identifier><datestamp>2017-03-21T19:13:00Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="6c3b2c20-0eb3-4b66-9135-8887104381ac" confidence="600">Botting, Brad</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:22:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:22:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1035</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">This thesis presents techniques for accurately computing a number of fundamental operations on approximate polynomials.   The general goal is to determine nearby polynomials  which have a non-trivial result for the operation.       We proceed by first translating each of the polynomial operations to a particular structured matrix system, constructed to represent dependencies in the polynomial coefficients.    Perturbing this matrix system to a nearby system of reduced rank yields the nearby polynomials that have a non-trivial result.       The translation from polynomial operation to matrix system permits the use of emerging  methods for solving sophisticated least squares problems.   These methods introduce the  required dependencies in the system in a structured way, ensuring a certain minimization is  met.   This minimization ensures the determined polynomials are close to the original input.       We present translations for the following operations on approximate polynomials:  &amp;lt;ul&amp;gt;  &amp;lt;li&amp;gt;Division&amp;lt;/li&amp;gt;  &amp;lt;li&amp;gt;Greatest Common Divisor (GCD)&amp;lt;/li&amp;gt;  &amp;lt;li&amp;gt;Bivariate Factorization&amp;lt;/li&amp;gt;  &amp;lt;li&amp;gt;Decomposition&amp;lt;/li&amp;gt;  &amp;lt;/ul&amp;gt;  The Least Squares problems considered include classical Least Squares (LS), Total Least  Squares (TLS) and Structured Total Least Squares (STLS).   In particular, we make use  of some recent developments in formulation of STLS, to perturb the matrix system, while  maintaining the structure of the original matrix.   This allows reconstruction of the resulting polynomials without applying any heuristics or iterative refinements, and guarantees a  result for the operation with zero residual.       Underlying the methods for the LS, TLS and STLS problems are varying uses of the Singular Value Decomposition (SVD).   This decomposition is also a vital tool for deter-  mining appropriate matrix rank, and we spend some time establishing the accuracy of the  SVD.   We present an algorithm for &amp;lt;i&amp;gt;relatively accurate&amp;lt;/i&amp;gt; SVD recently introduced in [8], then  used to solve LS and TLS problems.   The result is confidence in the use of LS and TLS for  the polynomial operations, to provide a fair contrast with STLS.   The SVD is also used to  provide the starting point for our STLS algorithm, with the prescribed guaranteed accuracy.       Finally, we present a generalized implementation of the Riemannian SVD (RiSVD), which  can be applied on any structured matrix to determine the result for STLS.   This has the  advantage of being applicable to all of our polynomial operations, with the penalty of  decreased efficiency.   We also include a novel, yet naive, improvement that relies on ran-  domization to increase the efficiency, by converting a rectangular system to one that is  square.       The results for each of the polynomial operations are presented in detail, and the benefits  of each of the Least Squares solutions are considered.   We also present distance bounds  that confirm our solutions are within an acceptable tolerance.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">592465 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2004, 
  Botting, Brad. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Structured Total Least Squares for Approximate Polynomial Operations</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>