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.
- 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.
The course grade will be determined by
- Homework: 45%
- Participation: 10%
- Final Project: 45%
- 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.
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
- Homework 1 (PDF) Due: Beginning of class, Feb. 5, 2019 Now Assigned!
- Homework 2 (PDF) Due: Beginning of class, Feb. 19, 2019 Now Assigned!
- Homework 3 (PDF) Due: Beginning of class, March 21, 2019 Now Assigned!
- Homework 4 (PDF)
Due: Beginning of class, April 2, 2019 Now Assigned!
Helper file: square.mat
- An overview of the final project is in the syllabus.
- For the grading rubric, and detailed expectations for the final project, see final-guidelines.pdf.
-
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
- 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 - Slides Handout 2 Relaxation.ipynb Richardson.ipynb
- Slides Handout 3 Handout 4 A_Simple_Projection.ipynb OneD_Projections.ipynb onedprojection.py
- Slides Handout onedprojection.py arnoldi.py fom.py A_Basic_Arnoldi_Example.ipynb Minimal_Polynomial.ipynb Testing_Arnoldi.ipynb Testing_FOM.ipynb
- gmres_mgs.py
Testing_GMRES.ipynb
Notes in class: derive GMRES - cg.py
Testing_CG.ipynb
Notes in class: derive CG - Chebychev.ipynb
ILU_preconditioning.ipynb
Notes in class: derive classic convergence bound for CG, Intro to Preconditioning - Slides (Intro to Geometric MG) Relaxation.ipynb Relaxation_and_Modes.ipynb Relaxation_and_omega.ipynb Relaxation_on_smooth_and_non-smooth_error.ipynb
- Slides (Coarse-Grids for Geometric MG) Coarse_Modes.ipynb Error_vs_Solution.ipynb Interpolation_1D.ipynb Nested_Iteration.ipynb
- Multigrid_Two_Grid_Cycle.ipynb
Multigrid_V-cycle.ipynb
Notes in class: more on geometric MG, extending to multiple levels - Multigrid_V-cycle_Part2.ipynb
Notes in class: more on multilevel MG, preconditioning, cost, accuracy - Multigrid_in_2D.ipynb
Notes in class: introduction to some MG theory, look at a cycle in 2D - Slides (Intro to Smoothed Aggregation AMG) Aggregates_and_Splittings.ipynb Components_of_Smoothed_Aggregation.ipynb Smoothed_Aggregation_in_1D.ipynb square.mat
- Review final project guidelines: final-guidelines.pdf
- Slides (Intro to Classical AMG -- Courtesy of Textbook Authors) coarsening.pdf AMG_and_Anisotropy.ipynb square.mat
- AMG_Advanced_Options-Adaptivity_for_Aniso_Diffusion.ipynb AMG_Advanced_Options-Nonsymmetric_flow.ipynb AMG_Advanced_Options-Systems_Elasticity.ipynb
- lecture-AMG-theory.pdf amg_theory.pdf (journal paper) handout20.pdf (not required to do)
- Multigrid reduction in time: MGRIT, lecture21.pdf
- Multigrid reduction in time for optimization : MGRIT, Optimization Slides.pdf
Other Material
PyAMG: https://github.com/pyamg/pyamg -- Make sure to click on WikiPython / SciPy
- Python 3 tutorial
- An introduction to NumPy and SciPy
- The SciPy (scientific Python) Lectures
- 100 NumPy Exercises
- 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
Last updated Spring, 2019