M/CS 143M, Fall 2013:

INTRODUCTORY MATERIAL:
1. Course green sheet (MS word doc file)
2. Sections covered in Watkins, 3rd edition.
3. Schedule for the semester. The current dates are estimated dates. The schedule will be updated as the semester progresses with a notation such as Updated on xx-yy-zzzz. Please keep track of the most recent version.
4. A short guide to get started in Matlab
5. Alternatives to Matlab
6. A sample quiz covering material that you should know from M129A.

7. MATRIX DECOMPOSITIONS / LINEAR ALGEBRA REVIEW / NORMS:
8. 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
9. List of Important matrix decompositions: LU, QR, eigenvalue and singular value decompositions (SVD)
10. Examples - important matrix decompositions: LU, QR, eigenvalue and SVD. Also tex original.
11. Homework - Basic Decompositions
12. Homework - Linear Algebra Review + Introduction to Norms
13. Four Ways to do Matrix Multiplication
14. Discussion of the Singular Value Decomposition by Cleve Moler, chief scientist at the Mathworks
15. Computing assignment - Curve fitting (QR), Heat flow (LU), Resonance (eigenvalues) and Image Compression (SVD).

16. SQUARE LINEAR SYSTEMS (GUASSIAN ELIMINATION, GROWTH FACTOR, CHOLESKY AND CONDITION NUMBERS):
17. 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. Also tex original.
18. Example - Gaussian elimination with partial pivoting . Also tex original. Updated 9-18-2013.

19. 16B. Example of Gaussian Elimination with no pivoting using the MATLAB debugger (with minor updates 10:11 am, 9-18-013).
16C. Matlab code for Gaussian elimination with no pivoting. L and U are stored separately in the code.
16D. Matlab code for Gaussian elimination with no pivoting. L and U are stored in A (compact storage mode).
16E. Matlab code for Gaussian elimination with partial pivoting. L and U are stored in A (compact storage mode).
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,
23. Homework - the growth factor and calculating the inverse of A .
24. Homework - Cholesky and more condition numbers (and block GE).
25. Example - disasters caused by a small pivot element Also tex original.
26. The accuracy of Gaussian elimination and the growth factor Also tex original.
27. Matlab code for Gaussian elimination with tournament pivoting: getp.m solves Ax = b using tournament pivoting, getp_block.m does an LU factorization of A using tournament pivoting, tslu.m does a "tall skinny" LU factorization using tournament pivoting (called by getp_block.m), and genp.m which does Gaussian elimination with no pivoting. This genp is an update to item 16C. The current version of genp allows A to be rectangular which is needed in tournament pivoting. Tournament pivoting is a communication avoiding pivoting scheme in the sense that the communication (between processors in a parallel processing environment or between fast and slow memory in environments with memory heirachy) is, within a modest factor, the mininum communication possible. Communication avoiding algorithms will be of increasing importance as the use of parallel processing expands. Parallel processing will soon be ubiquitous for scientific (and other) computing systems. The first article discussing tournament pivoting is from 2011: the method is very new!

28. 24B. Example of Gaussian Elimination with tournament pivoting and of block Gaussian elimination (using the MATLAB debugger).
24C. Homework for Gaussian Elimination with tournament pivoting and block Gaussian elimination (using the MATLAB debugger).
24D. Flops, Memory and Parallel Processing and Gaussian Elimination, background on flop counts, memory management, block elimination, parallel processing and Tournament pivoting. Updated on 10-5-2013.
29. (a) genp_block.m : Matlab code for block Gaussian elimination without pivoting. The code calls genp.m, which is in item 24 above. (b) an example illustrating block GE without pivoting and (c) gepp_block.m : Matlab code for block GE with partial pivoting. See item 24D discussion of the block algorithm. Also see homework problem 8 in item 21 and the example in item 24b.. 24a,b,c updated on 10-5-2013.
30. Computing assignment: - Try your own pivoting scheme . (the current version is the modified version for Fall 2013) The files in item 24 are required for the assignment. Also, as an extra credit option, you can 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.
31. Homework - Condition Number
32. Example - the Cholesky decomposition. .Also tex original.
33. Proof that Gaussian Elimination works . Also tex original.
34. Study guides: (a) solving square linear systems and (b) miscellaneous topics.<
35. Study guides: (a) vector and matrix norms (b) matrix condition numbers and (c) computer arithmetic.
36. Example - the matrix condition number.
37. Example - the matrix condition number. (second example)
38. The Hilbert matrix - an (infamous) ill-condtioned matrix.
39. Example - Errors from a Large Growth Factor. Also tex original.

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 in a manner similar to the calculations of Archimedes. This assignment has been updated. The older version is here. If you have not already started with the older version, please use the updated version.
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 . This file has been updated for Fall 2013 (latest updates 11-15-2013, 9 am with minor changes and two significant changes: on page 4 0.02 was corrrect to 0.2 and on page 7 UFweb - a very useful tool - is mentioned). Please read the updated file.
55. Obsolete item
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-18-2013. Please see the additional potential questions.
63. Format of the project report. Updated 11-18-2013.
64. Properties of Krylov Subspace Iterative Methods for Solving Nonsymmetric Systems.. Also tex original
65. Obsolete item
66. Examples applying GMRES, BICG, CGS, BICGSTAB, QMR and LSQR to the sherman5 matrix (using routines provided with Matlab 7).
67. Obsolete item
68. Preconditioning.
69. Obsolete item
70. Obsolete item
71. An example of bicg, preconditioned bicg and cg applied to the sherman5 matrix (using routines built-in Matlab 7 iterative routines ).
• These routines have been updated for Fall 2013 (latest updates to compare_methods.m and compare_methods_stats done on 11-18-2013, 1:30 pm). Please download the files and try them out. The 11-18-13 update allows for using restart in gmres. The routine compare_methods.m allows you to compare two iterative methods on a set of many matrices. Please also download the associated files: compare_methods_stats.m , binom_tails.m , cdfcalc.m , cdfplot2.m , tstat_calc.m , selectUF.m , UFcondest.mat , and UFkinds.mat . You will also need to install UFget so that it accessible from the same folder. After downloading compare_methods, move to the folder that contains compare_methods and type "help compare_methods" to see how to use the program. Also the MS Word file in item 47 discusses compare_methods and includes an example of its use.
• On 11-27-2013 the routines compare_methods.m and compare_methods_stats.m have been updated. Also two new routines iter_stats.m and show_convergence_plots.m are now available. The routine show_convergence_plots allows one to conveniently redisplay all the converge plots for a run of compare_methods. The routine iter_stats compares the iteration counts from a run of compare_methods using a paired sample t-test. The new routines will only work with data from a run of the updated compare_methods. I recommend that you download these updated and new files.
• 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.