Back to search

University of Waterloo

Faster Algorithms for Sparse Decomposition and Sparse Series Solutions to Differential Equations

Abstract

dc:description.abstract

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. 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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lyu, Saiyue
Advisors dc:contributor.advisor
  • Giesbrecht, Mark
  • Storjohann, Arne

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/18243

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lyu, Saiyue. Faster Algorithms for Sparse Decomposition and Sparse Series Solutions to Differential Equations. University of Waterloo, 2022. http://hdl.handle.net/10012/18243