Fast Algorithms and Integral Equation Methods (CS 598APK) Fall 2019
What | Where |
---|---|
Time/place | Wed/Fri 2:00pm-3:15pm 1109 Siebel / Catalog |
Class URL | https://bit.ly/fastalg-f19 |
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 super-linear 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 matrix-vector multiplication exhibits quadratic scaling. Problems in scientific computing, especially those arising from science and engineering questions, often demand large-scale computation in order to achieve acceptable fidelity, and such computations will not tolerate super-linear, 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 linear-algebraic 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 largest-scale computations. We will see that integral equations are the natural generalization of the linear-algebraic 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 Low-Rank Linear Algebra
- Low-Rank Approximation: Basics
- Low-Rank Approximation: Error Control
- Reducing Complexity
- Demo: Interpolative Decomposition
- Demo: Randomized SVD
- Demo: Rank-Revealing 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 High-Rank Interactions
- Ewald Summation
- Barnes-Hut
- 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: Kussmaul-Martensen 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, self-contained 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 cross-check 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 as-is basis.
- scribbles-2019-08-28.pdf
- scribbles-2019-08-30.pdf
- scribbles-2019-09-04.pdf
- scribbles-2019-09-06.pdf
- scribbles-2019-09-11.pdf
- scribbles-2019-09-13.pdf
- scribbles-2019-09-18.pdf
- scribbles-2019-09-20.pdf
- scribbles-2019-09-25.pdf
- scribbles-2019-09-27.pdf
- scribbles-2019-10-02.pdf
- scribbles-2019-10-09.pdf
- scribbles-2019-10-11.pdf
- scribbles-2019-10-16.pdf
- scribbles-2019-10-18.pdf
- scribbles-2019-10-23.pdf
- scribbles-2019-10-25.pdf
- scribbles-2019-10-30.pdf
- scribbles-2019-11-01.pdf
- scribbles-2019-11-06.pdf
- scribbles-2019-11-08.pdf
- scribbles-2019-11-13.pdf
- scribbles-2019-11-15.pdf
- scribbles-2019-11-20.pdf
- scribbles-2019-11-22.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