J. B. Schroder Home

Math / CS 576, Numerical Linear Algebra
Spring, 2019

Overview  ::  Dates  ::  Grading  ::  Homework  ::  Lecture Materials  ::  Other Materials

Time and Place: Tuesday / Thursday, SMLC 352, 9:30am-10:45am
Instructor: Jacob B. Schroder, jbschroder -att- unm.edu
Office Hours: SMLC 332
    Wednesday: 9:30am-11am
    Thursday: 1:00pm-2:30pm

Syllabus:  PDF1

Prerequisites: Math 504

1) Iterative Methods for Sparse Linear Systems, 2nd Edition by Y. Saad (free) PDF
2) A Multigrid Tutorial, 2nd Edition by W. L. Briggs, V. E. Henson, S. F. McCormick (free) PDF

Course Description: This is an introductory course to iterative methods for solving systems of (non)linear equations, focusing on Krylov and multigrid methods. The target systems of equations are large (in the millions or billions of degrees-of-freedom), sparse, and usually derived from discretized partial differential equations (PDEs). Traditional direct solution methods are impractical, so instead iterative solution methods must be used. Some possible application areas for Krylov and multigrid methods include (but are not limited to) elliptic PDEs, elasticity, fluid dynamics, and machine learning.

This is an advanced course for graduate students seeking to know how to efficiently solve large sparse linear systems, potentially for their own research.

Schedule of topics, course goals, and desired learning outcomes: Please see the syllabus.

Important Dates:



The course grade will be determined by

The final grade for the class will be based on the summed weighted percentages above. Letter grades will be assigned as follows:

The instructor reserves the right to curve grades to offset unforeseen circumstances. Such a curve will never decrease a student's letter grade below that from the above scheme.

Participation: 10% of the grade is from course participation, which is calculated based a student's attendance and in-class participation (which includes in-class handouts). If you (1) attend each class, (2) pay attention, and (3) participate with any in-class hand-outs, then you will receive all 10%. Unexplained absences (beyond your two "freebies") will lower this grade.

Absences Policy: : It is expected that each student regularly attend class, and participate by asking questions and commenting on the material.


Homework: Homework will be posted every 1 to 2 weeks on the course webpage, during the first part of course. Once the final project due dates start, other homework assignments will cease. Each homework will consist of computer and theoretical problems. You need to hand in a written report on the due date in class.

You are strongly encouraged to work in pairs (a group of two students) for the homework and hand in a single report, but it is expected that both of you can explain the theory and computer codes. Groups of more than two students are not allowed.

Late homeworks are not accepted; however, if an extenuating circumstance (hardship) arises, please let the instructor know before the homework due date (if at all possible). In such cases, the instructor will be flexible.

Homework grading disputes must be submitted in writing within one week after the work is returned.

Software: Use of numerical Python with the open-source PyAMG package will be required to complete the course homework assignments. Please see https://github.com/pyamg/pyamg/wiki/Installing for tips on installing PyAMG.

Homework Assignments
  1. Homework 1 (PDF)    Due: Beginning of class, Feb. 5, 2019    Now Assigned!
  2. Homework 2 (PDF)    Due: Beginning of class, Feb. 19, 2019    Now Assigned!
  3. Homework 3 (PDF)    Due: Beginning of class, March 21, 2019    Now Assigned!
  4. Homework 4 (PDF)    Due: Beginning of class, April 2, 2019    Now Assigned!
    Helper file: square.mat
Final Project:
  1. An overview of the final project is in the syllabus.
  2. For the grading rubric, and detailed expectations for the final project, see final-guidelines.pdf.
  3. The final project write-up is to be written in Latex with the standard SIAM journal article style files:
    1) final-template.tex
    2) siamplain.bst
    3) siamart171218.cls
    1. Top

Lecture Materials:
  1.   Slides     Handout 1     Error_vs_Residual.ipynb     My_First_Iterative_Method.ipynb     Small_Sparse_Matrix_Example.ipynb     Sparse_Matrices.ipynb  
      Sparse_Matrix-Vector_Multiplication.ipynb     Sparse_Cost.ipynb     Sparse_LU.ipynb  
  2.   Slides     Handout 2     Relaxation.ipynb     Richardson.ipynb  
  3.   Slides     Handout 3     Handout 4     A_Simple_Projection.ipynb     OneD_Projections.ipynb     onedprojection.py  
  4.   Slides     Handout     onedprojection.py     arnoldi.py     fom.py     A_Basic_Arnoldi_Example.ipynb     Minimal_Polynomial.ipynb     Testing_Arnoldi.ipynb     Testing_FOM.ipynb  
  5.   gmres_mgs.py     Testing_GMRES.ipynb  
    Notes in class: derive GMRES
  6.   cg.py     Testing_CG.ipynb  
    Notes in class: derive CG
  7.   Chebychev.ipynb     ILU_preconditioning.ipynb  
    Notes in class: derive classic convergence bound for CG, Intro to Preconditioning
  8.   Slides (Intro to Geometric MG)     Relaxation.ipynb     Relaxation_and_Modes.ipynb     Relaxation_and_omega.ipynb     Relaxation_on_smooth_and_non-smooth_error.ipynb  
  9.   Slides (Coarse-Grids for Geometric MG)     Coarse_Modes.ipynb     Error_vs_Solution.ipynb     Interpolation_1D.ipynb     Nested_Iteration.ipynb  
  10.   Multigrid_Two_Grid_Cycle.ipynb     Multigrid_V-cycle.ipynb  
    Notes in class: more on geometric MG, extending to multiple levels
  11.   Multigrid_V-cycle_Part2.ipynb  
    Notes in class: more on multilevel MG, preconditioning, cost, accuracy
  12.   Multigrid_in_2D.ipynb  
    Notes in class: introduction to some MG theory, look at a cycle in 2D
  13.   Slides (Intro to Smoothed Aggregation AMG)     Aggregates_and_Splittings.ipynb     Components_of_Smoothed_Aggregation.ipynb     Smoothed_Aggregation_in_1D.ipynb     square.mat
  14. Review final project guidelines: final-guidelines.pdf
  15.   Slides (Intro to Classical AMG -- Courtesy of Textbook Authors)     coarsening.pdf     AMG_and_Anisotropy.ipynb     square.mat
  16.   AMG_Advanced_Options-Adaptivity_for_Aniso_Diffusion.ipynb     AMG_Advanced_Options-Nonsymmetric_flow.ipynb     AMG_Advanced_Options-Systems_Elasticity.ipynb  
  17.   lecture-AMG-theory.pdf     amg_theory.pdf (journal paper)     handout20.pdf (not required to do)  
  18. Multigrid reduction in time: MGRIT, lecture21.pdf
  19. Multigrid reduction in time for optimization : MGRIT, Optimization Slides.pdf


Other Material

PyAMG: https://github.com/pyamg/pyamg -- Make sure to click on Wiki

Python / SciPy And more Python / SciPy..


Last updated Spring, 2019