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

Time/place  Wed/Fri 2:00pm3:15pm 1109 Siebel / Catalog 
Class URL  https://bit.ly/fastalgf19 
Class recordings  Watch » (also on Echo 360) 
Piazza  Discuss » 
Calendar  View » 
Homework
 Homework set 1
 Homework set 2
 Homework set 3
 Homework set 4
 Project Proposal
 Project Material Submission
Final Project Presentations
Date  Slot  Presenter 

Dec 4  1  Guanhua 
Dec 4  2  Yashraj 
Dec 6  1  Hongliang 
Dec 6  2  Vedant 
Dec 6  3  Yiming 
Dec 11  1  Jonathan 
Dec 11  2  Yuchen 
 Presentations will take place after Fall Break during the three remaining class periods.
 Presentations will be 22 minutes in length, with three minutes for questions at the end.
 Class attendance during final project presentation is required.
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.
 scribbles20190828.pdf
 scribbles20190830.pdf
 scribbles20190904.pdf
 scribbles20190906.pdf
 scribbles20190911.pdf
 scribbles20190913.pdf
 scribbles20190918.pdf
 scribbles20190920.pdf
 scribbles20190925.pdf
 scribbles20190927.pdf
 scribbles20191002.pdf
 scribbles20191009.pdf
 scribbles20191011.pdf
 scribbles20191016.pdf
 scribbles20191018.pdf
 scribbles20191023.pdf
 scribbles20191025.pdf
 scribbles20191030.pdf
 scribbles20191101.pdf
 scribbles20191106.pdf
 scribbles20191108.pdf
 scribbles20191113.pdf
 scribbles20191115.pdf
 scribbles20191120.pdf
 scribbles20191122.pdf
Computing
We will be using Python with the libraries numpy, scipy and matplotlib for 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.
Virtual Machine Image
While you are free to install Python and Numpy on your own computer to do homework, the only supported way to do so is using the supplied virtual machine image.
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
Related Classes Elsewhere
 Alex Barnett (Dartmouth)
 Shravan Veerapaneni (Michigan)
 Leslie Greengard (NYU)
 Gunnar Martinsson: UC Boulder Dartmouth
 Jianlin Xia (Purdue)
 Francesco Andriulli (ENS TELECOM Bretagne)
 Mark Tygert
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