Fast Algorithms and Integral Equation Methods (CS 598APK) Fall 2017

Class Projects

Materials, reports, and presentations from the projects that students completed as part of this course are now available.

Homework

• Homework set 1
• Homework set 2
• Homework set 3
• Project Proposal
• Homework set 4
• Project Presentation Signup (use @illinois.edu to sign in)
• Homework set 5
• Project Material Submission

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

I will insert links to class material, books, and papers into this tree as time goes on.

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.

Download Virtual Machine »

Books and Papers

• For randomized linear algebra: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions by Halko/Martinsson/Tropp

• For FMMs:

  • A fast algorithm for particle simulations by Greengard and Rokhlin.

  • A Fast Adaptive Multipole Algorithm for Particle Simulations

• For numerical linear algebra:

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

  • Trefethen and Bau is less comprehensive but more approachable

  • Mike Heath's sci comp book also contains almost everything you actually need to know about numerical LA

• For the functional analysis basics we need as well as the integral equation material, the best match for the course is Kress's book on linear integral equations. The references in the notes are for the second edition, linked above. A third edition is also available.

  These can be downloaded as an ebook through the UIUC library's subscription to SpringerLink.

Previous editions of this class

• Fall '13 (Similar, but with a heavier emphasis on Integral Equations)
• Fall '15

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

Grading Policies

View grading policies »