Show simple item record

dc.contributor.authorLyu, Saiyue 19:01:10 (GMT) 19:01:10 (GMT)
dc.description.abstractSparse 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. 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.en
dc.publisherUniversity of Waterlooen
dc.subjectsparse polynomialen
dc.subjectpolynomial decompositionen
dc.subjectdifferential equationen
dc.titleFaster Algorithms for Sparse Decomposition and Sparse Series Solutions to Differential Equationsen
dc.typeMaster Thesisen
dc.pendingfalse R. Cheriton School of Computer Scienceen Scienceen of Waterlooen
uws-etd.degreeMaster of Mathematicsen
uws.contributor.advisorGiesbrecht, Mark
uws.contributor.advisorStorjohann, Arne
uws.contributor.affiliation1Faculty of Mathematicsen

Files in this item


This item appears in the following Collection(s)

Show simple item record


University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages