CPSC 302: Numerical Computation for Algebraic Problems

2017/2018 Winter Term 1 (September-December 2017)

Mon/Wed/Fri 13:00-14:00, DMP 301

Tentative Lecture and Pre-Reading Schedule

The schedule is tentative, and materials will be updated as we go. Pre-class materials will be posted several days before class. Clicker questions and in-class exercises will be posted after class.
Readings are from Ascher & Greif (AG) or Heath, 2nd edition (H).
Required Reading: It is important to complete the pre-class reading for Friday classes, marked below with ❗. For Monday and Wednesday classes, you are free to study the required reading before or after the lecture.
Due Date: This column shows the due dates of the weekly out-of-class quizzes (in Connect), bi-weekly homework assignments, and surveys (in Connect, if not mentioned otherwise).
For the students on the waiting list, I will copy a PDF of the quizzes/surveys into Piazza until Sept 19.

Date	Topic	Required Reading	Due Date (1pm)	Slides	Optional Reading	Relevant Files/Links	Clickers and Exercises
Wed Sep 6	Introduction to CPSC 302.	Syllabus Sign up for Piazza and answer poll Register iClicker/REEF (bonus questions start Sep 20)		L01_2017-09-06	Collapse of the Tacoma Narrows bridge The Mathematics Behind Google's PageRank (until slide 16)
Fri Sep 8	Introduction to Matlab. Bring your laptop: Each group of 4 should have at least one laptop with access to Matlab.	Get access to Matlab Origins of Matlab Getting Started with Matlab Introduction to Matlab	Pre-Class Readings Quiz	L02_2017-09-08	Introductions to Matlab More history of Matlab: The Gatlinburg and Householder Symposia	buildA.m buildf.m	ex1
Mon Sep 11	1. Numerical Algorithms and Errors. Intro. Errors.	AG 1.2	Interest Inventory Survey	L03_pre-class L03_2017-09-11	H 1.2.1-1.2.2, 1.2.4 Roundoff vs. Discretization Error	combined_ error.ipynb	CQ_03
Wed Sep 13	Problem conditioning and algorithm stability I: Theory.	AG 1.3		L04_pre-class L04_2017-09-13	H 1.2.3, 1.2.6-1.2.7 Accuracy and Stability of Numerical Algorithms (Significant digits, Sec. 1.2; Stability, e.g. Sec. 1.5, 1.18; Conditioning, Sec 1.6) Towards a formal definition of numerical stability Significant digits (page 3)	stability_condi- tioning.ipynb	CQ_04
Fri Sep 15	Problem conditioning and algorithm stability II: Practice.	AG 1.3 stability_conditioning.pdf	Pre-Class Readings Quiz	L05_2017-09-15			ex2
Mon Sep 18	Floating point systems. The IEEE standard.	AG 2.1-2.2, 2.4	Prior Knowledge Quiz	L06_pre-class L06_2017-09-18	H 1.3.1.-1.3.8 Floating Point Systems Rounding Rules Accuracy and Stability of Numerical Algorithms (Sec 2) Numerical Computing with IEEE Floating Point Arithmetic Patriot Missile Failure Video Patriot Missile Failure Collection of Software Bugs	roundoff _error.ipynb	CQ_06
Mon Sep 18	Matlab Tutorial. 6-8pm in DMP 301. Bring your laptop.
Wed Sep 20	Roundoff error accumulation and cancellation error.	AG 2.1, 2.3		L07_pre-class L07_2017-09-20	H 1.3.9 Quadratic Formula Infinite Series	roundoff _error _accu.ipynb
Fri Sep 22	2. Nonlinear Equations in One Variable. Intro. Bisection method.	AG 3.1-3.2	Pre-Class Readings Quiz	L08_2017-09-22	H 5.1-5.5.1 Interval Bisection	bisection.ipynb bisectmod.m fex.m fex2.m fex3.m	ex3
Mon Sep 25	Fixed point iteration.	AG 3.3	Prior Knowledge Quiz	L09_pre-class L09_2017-09-25	H 5.5.2 Fixed Point Iteration	fixed_point.ipynb fixed_point.m gex.m gex2.m gex3.m	CQ_09
Wed Sep 27	Newton's method and variants.	AG 3.4	Assignment 1	L10_pre-class L10_2017-09-27	H 5.5.3-5.5.4 Newton's Method A Short History of Newton's Method Secant Method	newton.ipynb secant.ipynb newton.m secant.m fex.m fdex.m fex4.m fdex4.m fex5.m fdex5.m
Fri Sep 29	Minimizing a function in one variable.	AG 3.5 H 6.4-6.4.1 (the Golden Section Search Video in the Optional Reading is quite nice for understanding, although the roles of x₁ and x₂ are interchanged)	Pre-Class Readings Quiz		Golden Section Search Video Golden Section Search Newton's Method Successive Parabolic Interpolation		ex4
Mon Oct 2	3. Review Linear Algebra. Basics. Norms.	AG 4.1-4.2	Prior Knowledge Quiz	L12_pre-class L12_2017-10-02	H 2.3.1-2.3.2 Linear Algebra and its Applications Introduction to Linear Algebra Vector p-Norms	linear_algebra_ I.ipynb spectrum.ipynb	CQ_12
Wed Oct 4	Matrices. Singular values. Examples.	AG 4.3-4.5		L13_pre-class L13_2017-10-04	Matrix Computations, 4th Edition, by G.H. Golub and C.F. Van Loan Low Rank Approximation using SVD Applications of SVD		CQ_13
Fri Oct 6	4. Linear Systems: Direct Methods. Gaussian elimination and backward substitution.	AG 5.1	Pre-Class Readings Quiz	L14_2017-10-06	H 2.1-2.2, 2.4.1-2.4.3 Gaussian Elimination Mathematicians of Gaussian Elimination History of Gaussian Elimination		ex5
Mon Oct 9	Thanksgiving Day.
Wed Oct 11	LU decomposition.	AG 5.2	Assignment 2	L15_pre-class L15_2017-10-11	H 2.4.4		CQ_15
Fri Oct 13	Pivoting strategies. Efficient implementation.	AG 5.3-5.4	Pre-Class Readings Quiz		H 2.4.5-2.4.6 Three mysteries of Gaussian elimination Numerical Linear Algebra Applied Numerical Linear Algebra Matrix computations with Fortran and paging Numerical Linear Algebra for High-Performance Computers A Set of Level 3 Basic Linear Algebra Subprograms An Extended Set of FORTRAN Basic Linear Algebra Subprograms Basic Linear Algebra Subprograms for Fortran Usage		ex6
Mon Oct 16	Estimating errors and the condition number.	AG 5.8	Prior Knowledge Quiz	L17_pre-class L17_2017-10-16	H 2.3.3-2.3.5 Error Analysis of Direct Methods of Matrix Inversion Conditioning of Solutions Matrix Condition Number Error Bound A Survey of Condition Number Estimation for Triangular Matrices		CQ_17
Wed Oct 18	The Cholesky decomposition.	AG 5.5		L18_pre-class L18_2017-10-18	H 2.5.1 Cholesky Factorization Cholesky's 1910 manuscript		CQ_18
Fri Oct 20	Sparse matrices. Permutations and ordering strategies.	AG 5.6-5.7 Reverse Cuthill-McKee Algorithm (You will need this for the in-class group exercise, where you will solve a similar example.)	Pre-Class Readings Quiz		H 2.5.1 Direct methods for sparse matrices Direct methods for sparse matrices (I) Direct methods for sparse matrices (II)		ex7
Mon Oct 23	5. Linear Least Squares Problems. Motivation. Data fitting.	Data Fitting in AG 6.1	Prior Knowledge Quiz Mid-Course Feedback	L20_pre-class L20_2017-10-23	H 3.1 The Discovery of the Method of Least Squares Least Squares Data Fitting Video: Least-squares Morphing of Dynamic Meshes Least-squares Morphing of Dynamic Meshes Image Deformation Using Moving Least Squares		CQ_20
Wed Oct 25	Midterm Exam.	Location: PHRM 1201 Be on time: Exam starts at 13:00. Bring your student ID. One side of a letter-sized (216mm × 279mm) sheet with handwritten notes.
Fri Oct 27	Least squares and the normal equations.	AG 6.1	Pre-Class Readings Quiz		H 3.2		ex8
Mon Oct 30	Conditioning. Orthogonal transformations and QR decomposition.	AG 6.2	Prior Knowledge Quiz	L22_pre-class L22_2017-10-30	H 3.4.3, 3.4.5		CQ_22
Wed Nov 1	Householder transformations and Gram-Schmidt orthogonalization.	AG 6.3	Assignment 3	L23_pre-class L23_2017-11-1	H 3.5 Numerical methods for solving linear least squares problems Numerical Methods for Least Squares Problems Solving Least Squares Problems Gram-Schmidt Orthogonalization Householder Transformations Householder QR Factorization Givens QR Factorization Classical Gram-Schmidt QR Factorization Modified Gram-Schmidt QR Factorization QR Factorization with Column Pivoting		CQ_23
Fri Nov 3	SVD and Truncated SVD (TSVD).	Quiz Pre-Reading: AG 8.2 Group Exercise Pre-Reading: ex9-pre.pdf	Pre-Class Readings Quiz		H 3.6 On the Early History of the Singular Value Decomposition Outer Product Expansions and Their Uses in Digital Image Processing Singular value decomposition and improved frequency estimation using linear prediction Principal component analysis in linear systems: Controllability, observability, and model reduction Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion Singular Value Decomposition Lower-Rank Approximation		ex9
Mon Nov 6	6. Linear Systems: Iterative Methods. Motivation. Poisson equation.	AG 7.1	Prior Knowledge Quiz	L25_pre-class L25_2017-11-06	Iterative Methods for Sparse Linear Systems Iterative Methods for Solving Linear Systems Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics
Wed Nov 8	Stationary iteration and relaxation methods.	AG 7.2		L26_pre-class L26_2017-11-08	H 11.5.1-11.5.4 Extrapolation and Krylov Subspace Methods: a Historical Approach Über eine neue Auflösungsart der bei der Methode der kleinsten Quadrate vorkommenden linearen Gleichungen Iterative methods for solving partial difference equations of elliptical type	stationary.ipynb	CQ_26
Fri Nov 10	Convergence of stationary methods.	Quiz Pre-Reading: AG 7.3 Group Exercise Pre-Reading: ex10-pre.pdf	Pre-Class Readings Quiz		H 11.5.6	stationary _conv.ipynb	ex10
Mon Nov 13	Statutory holiday in lieu of Remembrance Day.
Wed Nov 15	Gradient descent methods. Conjugate gradient (CG) method and Preconditioning (Part I).	AG 7.4	Assignment 4	L28_pre-class L28_2017-11-15	H 11.5.5 Methods of Conjugate Gradients for Solving Linear Systems An Introduction to the Conjugate Gradient Method Without the Agonizing Pain Some History of the Conjugate Gradient and Lanczos Algorithms: 1948–1976 Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method Preconditioning A survey of preconditioned iterative methods for linear systems of algebraic equations Numerical solution of saddle point problems	cg.ipynb	CQ_28
Fri Nov 17	Multigrid methods.	Quiz Pre-Reading: AG 7.6 Group Exercise Pre-Reading: ex11-pre.pdf	Pre-Class Readings Quiz		Video: Multigrid for Poisson equation A Multigrid Tutorial Introduction to multigrid methods Multigrid Methods Multigrid methods: Fundamental algorithms, model problem analysis and applications		ex11
Mon Nov 20	Krylov subspace methods. Review: CG and PCG as Krylov subspace methods (Part II).		Prior Knowledge Quiz	L30_pre-class L30_2017-11-20	AG 7.5 Iterative Methods for Sparse Linear Systems The Idea behind Krylov Methods Recent computational developments in Krylov subspace methods for linear systems		CQ_30
Wed Nov 22	TA Evaluations 7. Small to Moderate-Sized Eigenvalue Problems. Review eigenvalues. Power method.	Power method in AG 8.1		L31_pre-class L31_2017-11-22	H 4.5.1 Numerical Methods for Large Eigenvalue Problems Computational Methods for Large Eigenvalue Problems Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide Numerical Methods for General and Structured Eigenvalue Problems Eigenvalue computation in the 20th century Numerical Solution of Linear Eigenvalue Problems Herman Müntz: A Mathematician's Odyssey Power Iteration and Inverse Iteration	power.ipynb	CQ_31
Fri Nov 24	Power method and PageRank.	PageRank in AG 8.1	Pre-Class Readings Quiz (optional)	L32_pre-class L32_2017-11-24	The anatomy of a large-scale hypertextual Web search engine Google's PageRank and Beyond Graphs of the Internet Animation: Graph of the Internet Check PageRank of a Website The $25,000,000,000 Eigenvector: The Linear Algebra behind Google The Mathematics Behind Google's PageRank		CQ_32
Mon Nov 27	The inverse and Rayleigh quotient iterations.	Rest of AG 8.1	Prior Knowledge Quiz (optional)	L33_pre-class L33_2017-11-27	H 4.5.2-4.5.5 A history of inverse iteration	rqi.ipynb	CQ_33
Wed Nov 29	QR iteration.	AG 8.3	Assignment 5	L34_pre-class L34_2017-11-29	H 4.5.6 The QR algorithm Understanding the QR Algorithm QR Iteration with Shifts		CQ_34
Fri Dec 1	Review. Questions.			recap
Wed Mon 4			Teaching Evaluation Survey
Wed Dec 6			Bonus Assignment (submit to CPSC 302 Assignment Box in ICCS X235)
Wed Dec 13	Final Exam.	Location: SWNG 222 Be on time: Exam starts at 19:00. Bring your student ID. One letter-sized (216mm × 279mm) sheet with handwritten notes.