Some of the material will be updated during the semester.

Updates will be noted by Updated on xx-yy-zzzz or similar.

- Course green sheet (MS word doc file)
- Sections covered in Watkins, 3rd edition.
- 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. NOTE: Updated on 09-19-2014. NOTE: Updated on 10-20-2014.
- A short guide to get started in Matlab
- Alternatives to Matlab
- A sample quiz covering material that you should know from M129A.
- 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
- List of Important matrix decompositions: LU, QR, eigenvalue and singular value decompositions (SVD)
- Examples - important matrix decompositions: LU, QR, eigenvalue and SVD. Also tex original.
- Homework - Basic Decompositions
- Homework - Linear Algebra Review + Introduction to Norms
- Four Ways to do Matrix Multiplication
- Discussion of the Singular Value Decomposition by Cleve Moler, chief scientist at the Mathworks
- Computing assignment - Curve fitting (QR), Heat flow (LU), Resonance (eigenvalues) and Image Compression (SVD).
- 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.
- Example - Gaussian elimination with partial pivoting . Also tex original.
- Examples - GEPP, GECP and GERP. Also tex original.
- Example - GENP can lead to a disaster, inaccurate result. Also tex original.
- Homework - Gaussian elimination,
- Homework - the growth factor and calculating the inverse of A .
- Homework - Cholesky and more condition numbers (and block GE).
- Example - disasters caused by a small pivot element Also tex original.
- The accuracy of Gaussian elimination and the growth factor Also tex original.
- TOURNAMENT PIVOTING. Tournament pivoting is a communication
avoiding pivoting scheme. Communication is increasingly the bottleneck in program speed as computer architectures advance.
With tournament pivoting 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. The first article discussing tournament pivoting is from 2011: the method is very new!

24A. 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.

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.

- Block Gaussian elimination:

(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. - 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 -- describes use of the three files,

gecp.c -- a Mex gateway function, and

gecpf.c -- a C function implementing Gaussian elimination with complete pivoting. - Homework - Condition Number
- Example - the Cholesky decomposition. .Also tex original.
- Proof that Gaussian Elimination works . Also tex original.
- Study guides: (a) solving square linear systems and (b) miscellaneous topics.<
- Study guides: (a) vector and matrix norms (b) matrix condition numbers and (c) computer arithmetic.
- Example - the matrix condition number.
- Example - the matrix condition number (second example). Also word original.
- The Hilbert matrix - an (infamous) ill-condtioned matrix.
- Example - Errors from a Large Growth Factor. Also tex original.
- 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).
- Details - storing floating point numbers in the IEEE standard.
- Example - overflow error: . Also word original.
- Example - subtractive cancellation: Patriot missile disaster . Also word original.
- Homework - Computer Arithmetic . Also tex original.
- Accuracy limits inherent in a problem and errors introduced by an algorithm .
- Computing assignment - calculate Pi in a manner similar to the calculations of Archimedes.
- A poem about subtractive cancellation .
- Example - solving a least squares problem using the
normal equations.. Also tex original.

44B. Homework for Least Squares Updated on 11-8-2014.

- Example - solving a least squares problem using Gram-Schmidt and a QR factorization.. Also tex original.
- Example - solving a least squares problem with Householder transformations.. Also tex original.
- Project on Krylov Subspace Iterative Methods Description . This file has been updated for Fall 2014
- A zip file with all the Matlab files needed for the project (including UFget).
. To get started

(a) download the zip file to a folder of your choice. If you expect to be changing computers I recommend a USB drive for the project files.

(b) Unzip the file. For example, in Matlab you can move to the folder with the zip file and type "unzip project_F14_all_files.zip".

You are ready to start. For example, from Matlab prompt one can type

Problem = UFget(246);

mat_init

and do the examples in items 59 or 64. Or enter

method1 = 'bicg'

method2 = 'gmres'

compare_methods

This will produce result similar to those on page 4 of item 47, but for a different set of matrices.

- Ideas underlying the conjugate gradient method.. Also tex original.
- Properties of the conjugate gradient method.. Also tex original.
- Conjugate gradient algorithm and an example.. Also tex original.
- Homework for iterative methods..
- Matlab code (cg_step.m) that does one step of the conjugate gradient method..
- Summary of Iterative Methods for Non-symmetric Linear Equations That Are Related to the Conjugate Gradient (CG) Method.. Also tex original.
- Potential questions for the project.
- Format of the project report.
- Properties of Krylov Subspace Iterative Methods for Solving Nonsymmetric Systems.. Also tex original
- Obsolete item
- Examples applying GMRES, BICG, CGS, BICGSTAB, QMR and LSQR to the sherman5 matrix (using routines provided with Matlab 7).
- Obsolete item
- Preconditioning.
- Examples using preconditioning with compare_methods..
- Obsolete item
- An example of bicg, preconditioned bicg and cg applied to the sherman5 matrix (using routines built-in Matlab 7 iterative routines ).
- Matlab routines: These routines have been updated for Fall 2014. All the files are in the
zip file in item 48, but the descriptions below may be helpful.
- (a) The routine compare_methods.m allows you to compare two iterative methods on a set of many matrices. After downloading compare_methods.m , from Matlab, type "help compare_methods" for more information. (Type "help filename" for help on any of these files). Also pages 4 and 5 of item 47 illustrate compare_methods.
- (b) The routine selectUF.m allows one to select a set of matrices with selected properties. Pages 5 and 6 of item 47 describe selectUF.
- (c) The routine show_convergence_plots.m allows one to conveniently redisplay all the converge plots for a run of compare_methods.
- (d) The routine iter_stats.m compares the iteration counts from a run of compare_methods using a paired sample t-test.
- (e) Routine UFget allows convenient downloading of UFsparse matrices directly into Matlab.
- (f) Routine mat_init.m is helpful for initialization after a matrix is download to Matlab format from the UF website, for example with UFget.
- (g) Other files called by compare_methods are binom_tails.m , cdfcalc.m , cdfplot2.m , tstat_calc.m , compare_methods_stats.m , UFcondest.mat , and UFkinds.mat

- Study guide for iterative methods.
- The Algebra of a Reflection (first idea behind least squares algorithm using Householder transformations). Also tex original (except for a picture).
- 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).
- The Accuracy of Algorithms for Solving Least Squares Problems. Also tex original.
- Example illustrating the Accuracy of Algorithms for Solving Least Squares Problems. Also tex original.
- Study guide for rectangular systems.
- Study guide for eigenvalues.
- Some eigenvalue results
- Eigenvalue algorithms
- Example of QR iteration for eigenvalues .

INTRODUCTORY MATERIAL:

MATRIX DECOMPOSITIONS / LINEAR ALGEBRA REVIEW / NORMS:

SQUARE LINEAR SYSTEMS (GUASSIAN ELIMINATION, GROWTH FACTOR, CHOLESKY AND CONDITION NUMBERS):

COMPUTER ARITHMETIC:

LEAST SQUARES / RECTANGULAR SYSTEMS:

ITERATIVE METHODS:

Project Description: items 47, 55, 56

Background: 49,50,51,54,57,61

Matlab code: items 48, 53, 65

Examples: items 47, 59, 64

Homework and study guide: items 52 and 66

MORE LEAST SQUARES / RECTANGULAR SYSTEMS:

EIGENVALUES: