Fast algorithms with applications to PDEs

In the first part of this thesis we describe the rebus representation of a linear operator and present algorithms for working with linear systems in this form. The main contributions in the area of algorithms are: a rebus-rebus multiplication, an LU factorization and forward and back substitution algorithms. All of these are described in detail. Implementations of the algorithms are tested and shown to be accurate and stable. The algorithms scale linearly in the size of the rebus and break even with high-performance dense routines for matrix sizes of O(100). These are, to our knowledge, the first algorithms proposed for these operations on a rebus representation.; In the second part of the thesis we apply rebus-based methods to a recurring problem in the numerical solution of partial differential equations. Problems discretized by collocation on the Chebyshev nodes give rise to large non-sparse matrices. Conventionally, a transform to a spectral domain is used to make the differential operator sparse. However, this imposes periodic boundary conditions on the problem, which may not be desirable. The main contribution in the area of numerical solution of PDEs is a procedure for using fast operations to solve problems of this kind with nonperiodic boundary conditions. We implement a fast solver for linearly implicit methods for stiff equations. We describe in detail how different boundary conditions can be imposed and apply the techniques to the Allen-Calm equation and the diffusion equation.