Iterative and Multigrid Methods

CS556 — Fall 2026

Course logistics
Class Time	Monday/Wednesday, 11:00 a.m.–12:15 p.m. [Catalog]
Class Location	1214 Siebel Center for Computer Science
Class URL	go.illinois.edu/cs556
Instructor	Luke Olson

About the Course Lectures Homework On Attendance Mental Health and Wellness

About the Course

Do you have a large, sparse matrix or graph problem that you'd like to solve? Then this course is for you!

The sparsity pattern of a linear system Ax=b, nonzeros are mainly along the diagonal.

The course covers roughly three topics: the fundamentals of numerical linear algebra, iterative methods (such as CG and GMRES), and multilevel methods (for example, geometric and algebraic multigrid).

The course involves homeworks and a final project. There is also a strong participation grade based on your attendance (informal) and ability to keep up with handouts and other tasks. The tentative grade breakdown is:

Homework: 40%
Final project: 50%
Attendance and handouts: 10%

This will be finalized by the first week of class.

The final project will be built over the last half (approximately) of the semester.

Goals

The goal of the project is to investigate deeply a specific aspect of multigrid and iterative solvers in a direction that we have not fully covered in class. The project must be on solvers (not discretizations, not the application, etc) — most often there should be a PDE or ODE or numerical method/model driving the core exploration.

Multigrid for XYZ, other preconditioners, domain decomposition topics, etc are all good topics. You may (and should!) connect this with your own research if you can. Solvers + AI is another possible direction, but should be chosen carefully.

Guidelines

The project is a solo effort. There will be regular updates (see below). Be prepared to present updates!

A presentation will serve as the final. The length will be 15 minutes, which includes questions. So target something around 12-13 minutes in presentation length.

Steps

prj00: selecting a topic (Wednesday, October 21, 5pm)
- Short project description
- Peer feedback
prj01: outline and goals (Wednesday, October 28, 5pm)
- 0.5-1 page of details, including steps
- Identify short, medium, and stretch goals
prj02: setup and initial results (Wednesday, November 4, 5pm)
prj03: challenges (Wednesday, November 11, 5pm)
prj04: slides draft (Wednesday, November 18, 5pm)
- 1-3 slides, specific format
prj05: final slides (Tuesday, December 1, noon)

Presentations are in class on December 2, 7, and 9.

Grading

Step	Points
prj00: selecting a topic	3
prj01: outline and goals	3
prj02: setup and initial results	3
prj03: challenges	3
prj04: slides draft	3
prj05: final slides	10
Final presentation	20
Final presentation peer feedback	5
Total	50

Steps prj00–prj04 are graded on completion.

The final slides (10 points) are graded on:

(3) Do you have a clear summary and goals of your project?
(2) Do you provide a sufficient level of detail in showing off your project?
(2) Do you highlight a few (but not all) of the results in your project?
(3) Slide deck design. Is your slide deck polished or AI slop?

Final presentation peer feedback (5 points): for each presentation you attend, answer "What is one takeaway that you had from this presentation?" in a Google Form. Write each takeaway in the positive form. The takeaways are shared with each presenter.

You are expected to attend all three days of presentations (December 2, 7, and 9). Exceptions are made for illness or school-related commitments.

The course homeworks and examples in class will be in Python. In particular, we will use the sparse features in SciPy and the solvers in PyAMG.

Lectures

August
08-24 01

About the course, errors and residuals, my first iterative method, sparse matrices

lecture_20260824.pdfIPYNBintro_first_method.ipynb IPYNBintro_error_vs_residual.ipynb
08-26 02

Jacobi, Gauss-Seidel, convergence criteria

lecture_20260826.pdfIPYNBsparse_matrices.ipynb IPYNBsparse_matvec_basics.ipynb IPYNBsparse_lu.ipynb IPYNBsparse_cost.ipynb
08-31 03

A general projection method

lecture_20260831.pdf projectionsIPYNBrelaxation.ipynb IPYNBrichardson.ipynb
September
09-02 04

One-dimensional projection methods

lecture_20260902.pdf projections2 onedprojection.pyIPYNBonedprojection_demo.ipynb
09-07

Labor Day — no class
09-09 05

Intro to Krylov spaces

lecture_20260909.pdf projections3IPYNBrandmat_12_3_lab.ipynb
09-14 06

GMRES

lecture_20260914.pdf arnoldi.py gmres_mgs.pyIPYNBarnoldi_example.ipynb IPYNBarnoldi_basic.ipynb IPYNBgmres_example.ipynb IPYNBkrylov_basic.ipynb
09-16 07

CG

lecture_20260916.pdf gmres fom.py cg.pyIPYNBfom_example.ipynb IPYNBcg_example.ipynb
09-21 08

CG+GMRES convergence

lecture_20260921.pdf cg_gmresIPYNBminimum_polynomial.ipynb
09-23 09

Preconditioned Krylov methods

lecture_20260923.pdf cg.pyIPYNBcg_preconditioning.ipynb IPYNBcg_example.ipynb IPYNBgeikj.ipynb IPYNBilu_preconditioning.ipynb
09-28 10

Preconditioned Krylov methods

lecture_20260928.pdf lecture_pcg_supplement.pdf
09-30 11

Domain decomposition
October
10-05 12

Relaxation methods

lecture-mg-basics-part1.pdf lecture-mg-basics-part1-notes.pdf mg_relaxationIPYNBmg-01-model-problem.ipynb IPYNBmg-02-relaxation-Jacobi.ipynb IPYNBmg-03-smooth-error.ipynb
10-07 13

Smooth error, coarse-grid correction

lecture-mg-basics-part2.pdf lecture-mg-basics-part2-notes.pdfIPYNBmg-02-relaxation-Jacobi.ipynb IPYNBmg-03-smooth-error.ipynb IPYNBmg-04-coarse-modes.ipynb IPYNBmg-05-interpolation.ipynb IPYNBmg-06-multigrid-two-level.ipynb IPYNBmg-07-multigrid-two-level-matrix-form.ipynb IPYNBmg-08-multigrid-v-cycle.ipynb
10-12 14

IPYNBmg-08-extensions.ipynb
10-14 15

Multigrid accuracy and cost

lecture-mg-basics-part3.pdf lecture-mg-basics-part3-notes.pdfIPYNBmg-07-multigrid-two-level-matrix-form.ipynb IPYNBmg-08-multigrid-v-cycle.ipynb
10-19 16

Multigrid in 2D, anisotropy, variable coarsening

lecture-mg-basics-part3.pdf lecture-mg-basics-part3-notes.pdfIPYNBmg-08-multigrid-v-cycle.ipynb IPYNBmg-09-multigrid-2d.ipynb
10-21 17

Anisotropy, line relaxation, coarse meshes

Project topic selectionIPYNBmg-10-multigrid-anisotropy.ipynb IPYNBmg-11-multigrid-2d-line-relaxation.ipynb IPYNBmg-12-AMG-coarse-mesh.ipynb
10-26 18

AMG, by CF splitting

IPYNBmg-12-AMG-coarse-mesh.ipynb IPYNBmg-13-rotated-anisotropy.ipynb IPYNBmg-14-anisotropy-cf-amg.ipynb IPYNBmg-15-CF-AMG-interpolation.ipynb
10-28 19

AMG, by CF splitting (cont.)

Project outline and goalsIPYNBmg-12-AMG-coarse-mesh.ipynb IPYNBmg-13-rotated-anisotropy.ipynb IPYNBmg-14-anisotropy-cf-amg.ipynb IPYNBmg-15-CF-AMG-interpolation.ipynb
November
11-02 20

AMG, by smoothed aggregation

IPYNBmg-16-aggregation.ipynb IPYNBmg-17-smoothed-aggregation-1d.ipynb IPYNBmg-18-components-of-smoothed-aggregation.ipynb
11-04 21

Advanced AMG

Project setup and initial resultsIPYNBmg-17-smoothed-aggregation-1d.ipynb IPYNBmg-18-components-of-smoothed-aggregation.ipynb
11-09 22

Advanced AMG, AMG theory

IPYNBmg-19-advanced-options-anisotropy.ipynb IPYNBmg-20-advanced-options-nonsymmetric-flow.ipynb IPYNBmg-21-advanced-options-systems-elasticity.ipynb
11-11 23

AMG, theory

Project challenges
11-16 24

TBD
11-18 25

Parallel AMG

Project slides draft
11-30 26

ILU preconditioning

Project final slides
December
12-02 27

Project presentations
12-07 28

Project presentations
12-09 29

Project presentations

Books

We will be using Saad's book Iterative Methods for Sparse Linear Systems

In addition, there are several other helpful texts (optional):

On Attendance

If you have cold-like symptoms or otherwise do not feel well, please stay home.

Missing class because you are ill will not affect your grade, and I will work with you to cover the material, over Zoom if that helps.

Mental Health and Wellness

Significant stress, mood changes, excessive worry, substance/alcohol misuse or interferences in eating or sleep can have an impact on academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings which are covered through the Student Health Fee. If you or someone you know experiences any of the above mental health concerns, we strongly encourage you to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do for yourself and for those who care about you.

Counseling Center (217) 333-3704
McKinley Health Center (217) 333-2700
988 Suicide & Crisis Lifeline — call or text 988, or chat at 988lifeline.org
Rosecrance Crisis Line (217) 359-4141 (available 24/7, 365 days a year)
If you are in immediate danger, call 911.

Adapted from the statement approved by the University of Illinois Counseling Center.