<?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-22T16:20:42Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/18243" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/18243</identifier><datestamp>2025-03-26T23:37:22Z</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="advisor">Giesbrecht, Mark</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Storjohann, Arne</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="bc14e801-ea8d-4007-9281-0ac8b7d528ca" confidence="600">Lyu, Saiyue</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2022-05-09T19:01:10Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2022-05-09T19:01:10Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2022-05-09</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2022-04-29</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/18243</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Sparse polynomials are those polynomials with only a few non-zero coefficients relative to their degree.  They can appear in practice in polynomial systems as inputs, where the degree of the input sparse polynomial can be exponentially larger than the bit length of the representation of it. This leads to the difficulties when computing with sparse polynomials, as many efficient algorithms for dense polynomials take polynomial-time in the degree, and hence an exponential number of operations in a natural representation of the sparse polynomial.&#xd;
&#xd;
In this thesis, we explore new and faster methods for sparse polynomials and power series. We reconsider algorithms for the sparse perfect power problem and derive a faster sparsity-sensitive algorithm.  We then show a fast new algorithm for sparse polynomial decomposition, again sensitive to the sparsity of the input and output. Finally, our algorithms to solve the sparse perfect power and decomposition problems lead us to explore a generalization to solving the linear differential equation with sparse polynomial coefficients using a Newton-like method.  We demonstrate an algorithm which will find sparse solutions if they exist, in time polynomial in the input and the output.</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="subject" lang="en">sparse polynomial</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">polynomial decomposition</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">differential equation</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">algorithm</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Faster Algorithms for Sparse Decomposition and Sparse Series Solutions to Differential Equations</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Giesbrecht, Mark</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Storjohann, Arne</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</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>