Fast Algorithms and Integral Equation Methods (CS 598APK) Fall 2024
What  Where 

Time/place  Tue/Thu 11:00am12:15pm 1302 Siebel / Catalog 
Class URL  https://bit.ly/fastalgs24 
Class recordings  Watch » 
Discussions  Discuss » 
Calendar  View » 
Assignments
Why you should take this class
Many of the algorithms of introductory scientific computing have superlinear runtime scaling. Gaussian elimination or LU decomposition are good examples, their runtime scales as $O(n^3)$ with the number of unknowns $n$. Even simple matrixvector multiplication exhibits quadratic scaling. Problems in scientific computing, especially those arising from science and engineering questions, often demand largescale computation in order to achieve acceptable fidelity, and such computations will not tolerate superlinear, let alone quadratic or cubic scaling.
This class will teach you a set of techniques and ideas that successfully reduce this asymptotic cost for an important set of operations. This leads to these techniques being called "fast algorithms". We will begin by examining some of these ideas from a linearalgebraic perspective, where for matrices with special structure, large cost gains can be achieved. We will then specialize to PDE boundary value problems, which give rise to many of the largestscale computations. We will see that integral equations are the natural generalization of the linearalgebraic tools encountered earlier, and we will understand the mathematical and algorithmic foundations that make them powerful tools for computation. All throughout, we will pay much attention to the idea of representation–i.e. the choice of what the numerical unknowns of the system to be solved should be.
Instructor
Course Outline
Note: the section headings in this tree are clickable to reveal more detail.
 Introduction
 Dense Matrices and Computation

Tools for LowRank Linear Algebra
 LowRank Approximation: Basics
 LowRank Approximation: Error Control
 Reducing Complexity
 Demo: Interpolative Decomposition
 Demo: Randomized SVD
 Demo: RankRevealing QR

Rank and Smoothness
 Local Expansions
 Multipole Expansions
 Rank Estimates
 Proxy Expansions
 Demo: Checking Rank Estimates
 Demo: Multipole and Local Expansions
 Demo: Skeletonization using Proxies

Near and Far: Separating out HighRank Interactions
 Ewald Summation
 BarnesHut
 Fast Mutipole
 Direct Solvers
 The Butterfly Factorization
 Demo: Butterfly Factorization
 Outlook: Building a Fast PDE Solver

Going Infinite: Integral Operators and Functional Analysis
 Norms and Operators
 Compactness
 Integral Operators
 Riesz and Fredholm
 A Tiny Bit of Spectral Theory

Singular Integrals and Potential Theory
 Singular Integrals
 Green's Formula and Its Consequences
 Jump Relations

Boundary Value Problems
 Laplace
 Helmholtz
 Calderón identities

Back from Infinity: Discretization
 Fundamentals: Meshes, Functions, and Approximation
 Integral Equation Discretizations
 Integral Equation Discretizations: Nyström
 Integral Equation Discretizations: Projection
 Demo: 2D Interpolation Nodes
 Demo: Choice of Nodes for Polynomial Interpolation
 Demo: Vandermonde conditioning
 Demo: Visualizing the 2D PKDO Basis
 Demo: Working with Unstructured Meshes

Computing Integrals: Approaches to Quadrature
 A Bag of Quadrature Tricks
 Quadrature by expansion (`QBX')
 QBX Acceleration
 Reducing Complexity through better Expansions
 Results: Layer Potentials
 Results: Poisson
 Demo: KussmaulMartensen quadrature
 Going General: More PDEs
CAUTION!
These scribbled PDFs are an unedited reflection of what we wrote during class. They need to be viewed in the context of the class discussion that led to them. See the lecture videos for that.
If you would like actual, selfcontained class notes, look in the outline above.
These scribbles are provided here to provide a record of our class discussion, to be used in perhaps the following ways:
 as a way to crosscheck your own notes
 to look up a formula that you know was shown in a certain class
 to remind yourself of what exactly was covered on a given day
By continuing to read them, you acknowledge that these files are provided as supplementary material on an asis basis.
 scribbles20240116andreas.pdf
 scribbles20240123andreas.pdf
 scribbles20240125andreas.pdf
 scribbles20240130andreas.pdf
 scribbles20240201andreas.pdf
 scribbles20240206andreas.pdf
 scribbles20240208andreas.pdf
 scribbles20240213andreas.pdf
 scribbles20240215andreas.pdf
 scribbles20240220andreas.pdf
 scribbles20240222andreas.pdf
Computing
We will be using Python with the libraries numpy, scipy and matplotlib for inclass work and assignments. No other languages are permitted. Python has a very gentle learning curve, so you should feel at home even if you've never done any work in Python.
Running Code on your Own Computer
While running code in this online system should technically suffice to do your work for this class, you may find it useful to also install Python on your own computer.
The recommended way of doing so involves downloading the Anaconda Python distribution. Note that this is a commercial product (even if it is free of charge), and this is not intended as an endorsement of the company or the product. Note that we cannot promise to provide technical support for this installation.
Another way to run Python code is through an online JupyterLab available through the course. Go to https://relate.cs.illinois.edu/lab get started. NOTE that this environment runs entirely in your browser. If you clear your browser data, any work 'saved' there will be irretrievably lost.
Books and Papers
Randomized Linear Algebra
Fast Multipole
Further references:
 A fast algorithm for particle simulations by Greengard and Rokhlin.
Integral Equations/Functional Analysis
A third edition is also available.
Background: Numerical Linear Algebra
Michael T. Heath, Revised Second Edition, Society for Industrial and Applied Mathematics
Further references:

Golub and van Loan is the definitive reference, with an emphasis on reference

Trefethen and Bau is less comprehensive but more approachable
Previous editions of this class
Many of these have videos available.
Related Classes Elsewhere
 Alex Barnett (Dartmouth)
 Mike O'Neil: RNLA, CEM (NYU)
 Gunnar Martinsson: UTexas Dartmouth
 Stéphanie ChaillatLoseille: BEM, Fast Algorithms
Python Help
 Python tutorial
 Facts and myths about Python names and values
 Dive into Python 3
 Learn Python the hard way
 Project Euler (Lots of practice problems)
Numpy Help
 Introduction to Python for Science
 The SciPy lectures
 The Numpy MedKit by Stéfan van der Walt
 The Numpy User Guide by Travis Oliphant
 Numpy/Scipy documentation
 More in this reddit thread
 Spyder (a Python IDE, like Matlab) is installed in the virtual machine. (Applications Menu > Development > Spyder)
 An introduction to Numpy and SciPy
 100 Numpy exercises