This course provides an introduction to analysis-based fast algorithms and their applications in computational science. Our primary focus will be on the solution of the partial differential equations of electromagnetics, elasticity, and fluid dynamics using integral equation methods. These include the fast multipole method, the fast Gauss transform, the nonuniform Fast Fourier transform, hierarchical compression schemes, and fast direct solvers. The underlying mathematical theory involves elements of functional analysis, special function theory, asymptotics, potential theory, and matrix computations. Familiarity with partial differential equations, complex analysis, numerical methods, and programming is strongly recommended.
Textbook
There is no course textbook but some useful resources are:- Multilevel Compression of Linear Operators by P.-G. Martinsson and M. Tygert
- A Short Course on Fast Multipole Methods by R Beatson and L. Greengard
- Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions by N. Halko, P.-G. Martinsson, and J. A. Tropp
- Fast Multipole Boundary Element Method, by Y. Liu, Cambridge University Press