You're not currently signed in. Sign in »

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

Thank you for your interest in this class! Unfortunately, due to some last-minute changes to the CS course schedule, this class will not be offered this semester. If you would like to take this class in the future, please email me, and I can let you know once it is being offered again.

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

The numerical solution of a 3D scattering problem

A quadtree as used in a Fast Multipole Method

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

Andreas Kloeckner

Andreas Kloeckner

(Instructor)

Email: andreask@illinois.edu

Office: 4318 Siebel

Course Outline

Note: the section headings in this tree are clickable to reveal more detail.

Class scribbles (click to view)

**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.

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 »