Fast numerical algorithms for the rapid application and compression of certain classes of matrices

This thesis describes algorithms for the compression and rapid application of certain matrices. The construction of low-rank approximations to matrices is very important in many applications of numerical computation. One classical form of these approximations is the singular value decomposition which is known in the statistical literature as the principal component analysis. Another classical form is the approximation obtained via subset selection; we will refer to the matrix representation obtained via subset selection as an interpolative decomposition. Chapter 1 of this thesis introduces an algorithm for the computation of a low-rank approximation of either type to an arbitrary matrix. Chapter 2 of this thesis introduces a new approach to the rapid numerical application to arbitrary vectors of several special function transforms. In addition to enabling the fast application of certain matrices, the algorithm of Chapter 2 can be used as a tool for matrix compression. The n x n matrices are compressed using approximately O (n log(n)) memory. The algorithm works for matrices such that the rank of any contiguous submatrix is bounded by a constant times the number of entries in the submatrix. These rank bounds are proven here for the cases of the Fourier transform and Fourier-Bessel transform. Numerical examples demonstrate a much wider applicability.