Fast Algorithms and Integral Equation Methods (CS 598APK) Fall 2022
What | Where |
---|---|
Time/place | Wed/Fri 2:00pm-3:15pm 305 Materials Science & Eng Bld / Catalog |
Class URL | https://bit.ly/fastalg-f22 |
Class recordings | Watch » |
Discussions | Discuss » |
Calendar | View » |
Homework
(none yet!)
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
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.
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
Carrier, Greengard, Rokhlin: A Fast Adaptive Multipole Algorithm for Particle Simulations
Further references:
- A fast algorithm for particle simulations by Greengard and Rokhlin.
Integral Equations/Functional Analysis
Rainer Kress, Linear integral equations. (second edition) The references in the notes are for the second edition.
A third edition is also available.
David Colton and Rainer Kress, Inverse Acoustic and Electromagnetic Scattering Theory. (3rd edition)
Background: Numerical Linear Algebra
Scientific Computing: An Introductory Survey / E-Book (accessible free of charge from campus network/VPN)
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)
- 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