Spring 2020  MATH 561
Numerical Linear Algebra (= Numerical Analysis I)

Class: MTWF 2:00--2:50pm, Engrg E105

Instructor
: Prof. Jiangguo (James) Liu (liu@math.colostate.edu, www.math.colostate.edu/~liu/)
Textbook
: James W. Demmel,  Applied Numerical Linear Algebra, SIAM, 1997, ISBN 0-89871-389-7 

Final/Qual Exam: Tuesday, May 12, 2020, 11:50am--01:50pm (Mountain Daylight Savings Time)
(ZOOM,  Instructor in Weber 237;  Closed-book, Closed-notes;  Independent work)

Review: Guidelines for preparing for the final/qual exam 

Lectures
Videos available on CANVAS for Mon. 03/23/2020 -- Fri. 05/08/2020

Week 1: 
See Textbook Sec.1.7; Sec.2.3 

-- Norms of vectors & matrices;
-- Gaussian Elimination (GE)

Week 2: 
See textbook Sec.2.2; Sec.2.3; Sec.2.4 
-- Operations count for GE;
-- GE with partial pivoting (GEPP);
-- Condition numbers; Thm.2.1 & proof; 

Week 3:
 
See Textbook Sec.2.7   

-- Cholesky factorization for SPD matrices;

-- GE for tri-diagonal system;

-- Gram matrices, Hilbert matrices, Projection to polynomial spaces 

Week 4: 
See Textbook Q2.19; Sec.6.5 
-- Strictly row/column diagonally dominant matrices;
-- Application: Linear systems from FDM for 2-point BVP;
-- Iterative solvers;
-- Jacobi and Gauss-Seidel


Week 5:
s.r.d.d. systems, Steepest descent 

-- Jacobi & Gauss-Seidel applied to s.r.d.d. systems; 

-- Equivalence of SPD sys. and quadratic minimization 
-- Steepest descent (SD) method

Week 6 & 7:
Conjugate gradient (CG) method 

-- Derivation and simplification of CG formulas;
-- Conjugacy (A-orthogonal); Properties;
-- Theory behind CG: hyperplanes, Krylov subspaces;

Week 8:
Iterative methods & More
-- Chebyshev polynomials;
-- FDM for 2d Poisson BVP;
-- Take-Home Midterm Exam due Fri. 03/13, 5pm

Spring Break:
(03/14 -- 03/24)

Week 9: 
QR-factorization

-- Brief review of Gram-Schimdt orthogonalization;
-- QR-factorization based on Householder reflections;
  
QR-factorization of Hessenberg matrices;
-- Direct solvers based on QR-factorization
See Textbook Sec.3.2.2; Sec.3.4
Lecture Notes on QR (updated May 4, 12:06pm)

Week 10:
Singular Value Decomposition (SVD)
-- SVD theorem and its proof, More properties;

-- Implementation in Matlab and Python;
-- Application to image compression;
-- Pseudo-inverse and more
See Textbook Sec.3.2.3 

Lecture Notes on SVD (updated Apr.04,09:44pm)

Week 11:
Least Squares Problems;
Review of eigenvalues and canonical forms

See Textbook Sec.3.2; Sec.3.5;
Sec.3.6; Sec.4.2 
Lecture Notes on Least Squares Problems (updated Apr.07,06:40pm)
Lecture Notes on Eigenvalues: Part I (updated Apr.10,01:37pm)

Week 12 & 13:
Numerical Methods for Eigenvalues
See Textbook Sec.4.4.1-7; Sec.5.3.1-3
Lecture Notes on Eigenvalues: Part II (updated Apr.15, 07:30am)
Lecture Notes on Eigenvalues: Part III (updated May 4, 12:01pm)

Week 14: (Mon.Wed.Fri. Apr.27,29; May 1) 
Krylov Subspaces
Lecture Notes on Krylov subspaces (updated May 4, 11:58am)

Week 15:
Selective Topics & Review

-- Principal component analysis (PCA); 

-- Sinkhorn algorithms;

-- Review for final & Qualifying Exam

Lecture Notes on New Topics (updated May 4, 11:46am)

Assignments
  Assignment #1:  Due Wed. 02/05

  Assignment #2:  Due Fri. 02/21
  Assignment #3:  Due Mon. 03/09

 Take-Home Test:  Due Fri. 03/13, 5pm
  Assignment #4:  Due Wed. 04/08 
  Assignment #5:  Due Fri. 05/01
Final & Qual.E.:  Tue. 05/12 (11:50am--01:50pm, ZOOM)

Last modified by J.Liu on Fri. 2020/05/08