Fast Algorithms, Matrix Compression and Design by Simulation

During the last two decades, a variety of fast algorithms have been developed for large-scale problems in scientific computing, governed by the equations of electromagnetics, elasticity, and fluid mechanics. They are most easily understood, perhaps, in the case of particle simulations, where they reduce the cost of computing all pairwise interactions in a system of N particles from O(N^2) to O(N) or O(N log N) operations. Most recently, a number of researchers have been developing an infrastructure for such problems using a linear algebraic formulation that makes closer connections to some central ideas in machine learning. We will describe the computational foundations of these methods, as well as some of their applications to the problems of design in geometrically complicated environments.