Many matrices that arise in scientific computing and in data science have internal structure that can be exploited to accelerate computations. The focus in this talk will be on matrices that are either of low rank, or can be tessellated into a collection of subblocks that are either of low rank or are of small size. We will describe how matrices of this nature arise in the context of fast algorithms for solving PDEs and integral equations, and also in handling "kernel matrices" from computational statistics. A particular focus will be on randomized algorithms for obtaining data sparse representations of such matrices.
At the end of the talk, we will explore an unorthodox technique for discretizing elliptic PDEs that was designed specifically to play well with fast algorithms for dense structured matrices.