M/CS 143M, Fall 2012:

INTRODUCTORY MATERIAL:
1. Course green sheet (MS word doc file)
2. Sections covered in Watkins, 3rd edition. Updated 8-27-2012.
3. A short guide to get started in Matlab
4. Alternatives to Matlab
5. A sample quiz covering material that you should know from M129A.

6. MATRIX DECOMPOSITIONS / LINEAR ALGEBRA REVIEW / NORMS:
7. Top ten algorithms from the 20th century (from SIAM). We discuss four of these: matrix decompositions, Krylov subspace methods, QR algorithm for eigenvalues, and programming in a high level language
8. List of Important matrix decompositions: LU, QR, eigenvalue and singular value decompositions (SVD)
9. Examples - important matrix decompositions: LU, QR, eigenvalue and SVD. Updated 9-10-2012. Also tex original.
10. Homework - Basic Decompositions
11. Homework - Linear Algebra Review + Introduction to Norms Updated 9-10-2012. (page numbers fixed compared to handout given in class on 8-27-2012)
12. Four Ways to do Matrix Multiplication Updated 10-4-2012. A sentence about Strassen's algorithm added at the bottom of the page.
13. Schedule for the semester , Updated 9-10-2012. (with the due date for the Gaussian Elimination Homework fixed)
14. Quiz 1 solutions, Posted 9-10-2012. (with one typo fixed)
15. Discussion of the Singular Value Decomposition by Cleve Moler, chief scientist at the Mathworks
16. Computing assignment - Curve fitting (QR), Heat flow (LU), Resonance (eigenvalues) and Image Compression (SVD).

17. SQUARE LINEAR SYSTEMS (GUASSIAN ELIMINATION, GROWTH FACTOR, CHOLESKY AND CONDITION NUMBERS):
18. Algorithms for Gaussian elimination (pseudocode): GENP, GE with no pivoting, GEPP, GE with partial pivoting, GECP, GE with complete pivoting, and GERP, GE with rook pivoting. Update 10-11-2012. Also tex original. Older version is here.
19. Example - Gaussian elimination with partial pivoting . Also tex original.
20. Examples - GEPP, GECP and GERP. Also tex original.
21. Example - GENP can lead to a disaster, inaccurate result. Also tex original.
22. Homework - Gaussian elimination, Updated 9-26-2012. The problem numbers corrected.
23. Homework - the growth factor and calculating the inverse of A .
24. Homework - Cholesky and more condition numbers (and block GE). Updated 10-4-2012. Problem 8 added and title on this web page changed to match the title on the handout.
25. Example - disasters caused by a small pivot element Updated 9-19-2012. (a typo was fixed after the handout in class - the bottom corner element of the matrix is c not b). Also tex original.
26. The accuracy of Gaussian elimination and the growth factor Updated 10-11-2012.(references added and wording changes). Also tex original.
27. Computing assignment: - Try your own pivoting scheme. One option is to use the Matlab Mex utility. Here are some files that illustrate how to use Matlab's Mex utility: gecp.m (describe use of the three files), gecp.c (a Mex gateway function), and gecpf.c (a C function implementing Gaussian elimination with complete pivoting). P.S. ignore any reference to f2c.h in the above material. Updated 10-13-2012. Capitalization consistent in pseudocode.
28. Schedule for the semester. Updated 10-2-2012.
29. Homework - Condition Number
30. Example - the Cholesky decomposition. Updated 10-2-2012. The algorithm description was added to the example and a typo (in red in the correction) was fixed. .Also tex original.
31. Proof that Gaussian Elimination works . Updated 10-10-2012. Theorem statememts moved to the beginning. Also tex original.
32. Study guides: (a) solving square linear systems and (b) miscellaneous topics. Updated 10-10-2012. Item 9 and 20 changed.
33. Study guides: (a) vector and matrix norms (b) matrix condition numbers and (c) computer arithmetic.
34. Example - the matrix condition number.
35. Example - the matrix condition number. (second example)
36. The Hilbert matrix - an (infamous) ill-condtioned matrix.
37. Example - Errors from a Large Growth Factor. Also tex original.
38. Schedule for the semester. Updated 10-8-2012. Note that item 35 may also be a topic of the quiz on Monday, 10-15-2012.
39. Quiz 2 Solutions. Quiz date 9-26-2012.

40. COMPUTER ARITHMETIC:
41. Limitations in storing floating point numbers. Know the range and significant digits entries in the "Key values" table, the items in bold in the table at the bottom of the page (and the remainder of the information).
42. Details - storing floating point numbers in the IEEE standard.
43. Example - overflow error: . Also word original.
44. Example - subtractive cancellation: Patriot missile disaster . Also word original.
45. Homework - Computer Arithmetic . Also tex original.
46. Accuracy limits inherent in a problem and errors introduced by an algorithm .
47. Computing assignment - calculate Pi as Archimedes may have . Due Wednesday, October 24.
48. A poem about subtractive cancellation .

49. LEAST SQUARES / RECTANGULAR SYSTEMS:
50. Example - solving a least squares problem using the normal equations.. Also tex original.
51. Example - solving a least squares problem using Gram-Schmidt and a QR factorization.. Also tex original.
52. Example - solving a least squares problem with Householder transformations.. Also tex original.

53. ITERATIVE METHODS:
54. Project on Krylov Subspace Iterative Methods Description .
55. Files for Krylov Subspace Project..
56. Ideas underlying the conjugate gradient method.. Also tex original.
57. Properties of the conjugate gradient method.. Also tex original.
58. Conjugate gradient algorithm and an example.. Also tex original.
59. Homework for iterative methods..
60. Matlab code (cg_step.m) that does one step of the conjugate gradient method..
61. Summary of Iterative Methods for Non-symmetric Linear Equations That Are Related to the Conjugate Gradient (CG) Method.. Also tex original.
62. Potential questions for the project. Updated 11-25-2012.
63. Format of the project report.
64. Properties of Krylov Subspace Iterative Methods for Solving Nonsymmetric Systems.. Also tex original (thanks to Meredith for texing this).
65. Examples applying GMRES, BICG, CGS, BICGSTAB and QMR to the sherman5 matrix (using routines from Templates for the Solution of Linear Systems, modified slightly) .
66. Examples applying GMRES, BICG, CGS, BICGSTAB, QMR and LSQR to the sherman5 matrix (using routines provided with Matlab 7). Updated 11-16-2012, the runs in the handout from class had a different right hand side b. The b in the update is the same as the b in handout 60.
67. A minor modification of the older bicgstab program at this site. The modification is required for the code to work in recent versions of Matlab. If you downloaded bicgstab earlier please replace your copy with the updated version.
68. Preconditioning.
69. An example of bicg, preconditioned bicg and cg applied to the sherman5 matrix (using routines from Templates for the Solution of Linear Systems, modified slightly).
70. A model discussion comparing proprerties of an iterative method for matrices in a class of matrices. Statistical tools are discussed that can compare the results for sets of matrices. The discussion uses the Matlab script file test_soln_type.m, which runs bicg over a selected set of matrices and collects statistics, the Matlab function selectUF.m, which helps select matrices from the University of Florida (UF) Sparse Matrix Collection, tstat_calc.m, which calculates a t-test statistics, chisquarecont.m which applies a Chi-square test, a license associated with chisquarecont.m, and UFcondest.mat, a file of precomputed values of Matlab's condition estimator. One option for the project is too study a class of matrices or a larger set of matrices. If you are interested in this option, I suggest that you download the items above and use them as a model for some of your analysis. Files updated 11-19-2012, 9:30 am. Please download the current version of the files.
71. An example of bicg, preconditioned bicg and cg applied to the sherman5 matrix (using routines built-in Matlab 7 iterative routines and not routines from Templates for the Solution of Linear Systems).
• The routine compare_methods.m allows you to compare two iterative methods on a set of many matrices. To change the methods or change the set of matrices you only need to change a few lines (lines 45,77 and / or 86) of the file. I encourage some of you to use this approach.
• Routine mat_init.m is helpful if you download matrices in Matlab format (rather than Matrix Market) format from the UF website. mat_init.m initializes variables in a convenient manner.
73. Study guide for iterative methods.

74. MORE LEAST SQUARES / RECTANGULAR SYSTEMS:
75. The Algebra of a Reflection (first idea behind least squares algorithm using Householder transformations). Also tex original (except for a picture).
76. A Reflection to Zero Out All but the First Component of a Vector (second idea behind least squares algorithm using Householder transformations). Also tex original (except for a picture).
77. The Accuracy of Algorithms for Solving Least Squares Problems. Also tex original.
78. Example illustrating the Accuracy of Algorithms for Solving Least Squares Problems. Also tex original.
79. Study guide for rectangular systems.

80. EIGENVALUES:
81. Study guide for eigenvalues.

See Fall 2009 for a complete collection of handouts and documents for the course from Fall 2009.

>