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 unm.edu
Office Hours: SMLC 332
    Wednesday: 9:30am-11am
    Thursday: 1:00pm-2:30pm

Syllabus:  PDF1

Prerequisites: Math 504

Texts:
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:

• Spring Break: March 10-17
• Final Project:    See Final Project in syllabus for details on what's due on each day.
• Topic Selection: April 4,      Bring your topic to class!
• Final Outline: April 15
• Present Outline to Class: April 16
• Final Progress on Numerics: April 26
• Final Rough Draft: May 2
• Final Version Due: May 9
• No office hours Wednesday and Thursday, March 27 and 28
  These office hourse are now moved to Friday, March 29 from 3pm till 5pm.

Top

Grading:

The course grade will be determined by

• Homework: 45%
• Participation: 10%
• Final Project: 45%

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

• A-, 90% or above
• B-, 80% or above
• C-, 70% or above
• D, 60% or above
• F, below 60%

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.

• Course follows UNM handbook D-170 https://handbook.unm.edu/policies/section-d/d170.html
• Note, the handbook says "A student with excessive absences may be dropped from a course by the instructor with a grade of W/P or W/F."
• If you need to miss more than two classes during the semester, please contact the instructor. Conference attendance, illness, etc... are all excusable.
• For information on how absences affect your participation grade, see below.

Top

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

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

Top

Other Material

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

Python / SciPy

• Python 3 tutorial
• An introduction to NumPy and SciPy
• The SciPy (scientific Python) Lectures
• 100 NumPy Exercises

And more Python / SciPy..

• Software-carpentry also has a good introduction to Python
• One Jupyter Notebook Tutorial
• Another Jupyter Notebook Tutorial
• Project Euler (lots of practice problems)
• NumPy MedKit (Stefan van der Walt)
• Spyder IDE

Top