169 pages ; Kernel functions are used in a variety of scientific settings to measure relationships or interactions between elements of a vector space. For example, in machine learning, kernel functions are often used to describe similarity or covariance between data points in a feature space. In physics, one method for solving partial differential equations is to reformulate them as boundary integral equations, where the integrand contains a kernel function related to the associated Green's function. A common challenge in computational approaches to problems involving kernel functions is the efficient handling of the associated kernel matrices, whose entries are evaluations of the kernel function on pairs of data points. These matrices are typically dense, and generic linear algebra routines will have time costs that naively scale quadratically with the amount of data for matrix-vector multiplies and cubically for solving linear systems. Since applications typically deal with large amounts of data (e.g., training data points for machine learning applications, quadrature nodes for integrals on complex and/or high dimensional surfaces), there is critical need for efficient techniques for handling kernel matrices. Much research has been done to develop such techniques for a variety of applications in recent decades. A popular approach is to leverage the fact kernel matrices tend to be rank structured which can be exploited to generate compressed representations. Another common tactic in the literature is to take advantage of properties of the kernel function, such as the existence of a reproducing property or a helpful series expansion. A nice aspect of research in this area is the existence of and opportunities for cross-pollination between different scientific disciplines connected by the use of kernel matrices. The primary topic of this dissertation is the development of new techniques for kernel matrix approximation which advance the state of the art in accuracy and efficiency in time and space. Inspired by ...