M/CS 143M, Fall 2014:

Some of the material will be updated during the semester.
Updates will be noted by Updated on xx-yy-zzzz or similar.

    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. NOTE: Updated on 09-19-2014. NOTE: Updated on 10-20-2014.
  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.

  19. 16B. Example of Gaussian Elimination with no pivoting using the MATLAB debugger.
    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. 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.
  28. 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.
  29. 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.
  30. Homework - Condition Number
  31. Example - the Cholesky decomposition. .Also tex original.
  32. Proof that Gaussian Elimination works . Also tex original.
  33. Study guides: (a) solving square linear systems and (b) miscellaneous topics.<
  34. Study guides: (a) vector and matrix norms (b) matrix condition numbers and (c) computer arithmetic.
  35. Example - the matrix condition number.
  36. Example - the matrix condition number (second example). Also word original.
  37. The Hilbert matrix - an (infamous) ill-condtioned matrix.
  38. Example - Errors from a Large Growth Factor. Also tex original.

  39. COMPUTER ARITHMETIC:
  40. 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).
  41. Details - storing floating point numbers in the IEEE standard.
  42. Example - overflow error: Ariane explosion. Also word original.
  43. Example - subtractive cancellation: Patriot missile disaster . Also word original.
  44. Homework - Computer Arithmetic . Also tex original.
  45. Accuracy limits inherent in a problem and errors introduced by an algorithm .
  46. Computing assignment - calculate Pi in a manner similar to the calculations of Archimedes.
  47. A poem about subtractive cancellation .

  48. LEAST SQUARES / RECTANGULAR SYSTEMS:
  49. Example - solving a least squares problem using the normal equations.. Also tex original.
    44B. Homework for Least Squares Updated on 11-8-2014.
  50. Example - solving a least squares problem using Gram-Schmidt and a QR factorization.. Also tex original.
  51. Example - solving a least squares problem with Householder transformations.. Also tex original.

  52. 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
  53. Project on Krylov Subspace Iterative Methods Description . This file has been updated for Fall 2014
  54. 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.
  55. Ideas underlying the conjugate gradient method.. Also tex original.
  56. Properties of the conjugate gradient method.. Also tex original.
  57. Conjugate gradient algorithm and an example.. Also tex original.
  58. Homework for iterative methods..
  59. Matlab code (cg_step.m) that does one step of the conjugate gradient method..
  60. Summary of Iterative Methods for Non-symmetric Linear Equations That Are Related to the Conjugate Gradient (CG) Method.. Also tex original.
  61. Potential questions for the project.
  62. Format of the project report.
  63. Properties of Krylov Subspace Iterative Methods for Solving Nonsymmetric Systems.. Also tex original
  64. Obsolete item
  65. Examples applying GMRES, BICG, CGS, BICGSTAB, QMR and LSQR to the sherman5 matrix (using routines provided with Matlab 7).
  66. Obsolete item
  67. Preconditioning.
  68. Examples using preconditioning with compare_methods..
  69. Obsolete item
  70. An example of bicg, preconditioned bicg and cg applied to the sherman5 matrix (using routines built-in Matlab 7 iterative routines ).
  71. 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
  72. Study guide for iterative methods.

  73. MORE LEAST SQUARES / RECTANGULAR SYSTEMS:
  74. The Algebra of a Reflection (first idea behind least squares algorithm using Householder transformations). Also tex original (except for a picture).
  75. 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).
  76. The Accuracy of Algorithms for Solving Least Squares Problems. Also tex original.
  77. Example illustrating the Accuracy of Algorithms for Solving Least Squares Problems. Also tex original.
  78. Study guide for rectangular systems.

  79. EIGENVALUES:
  80. Study guide for eigenvalues.
  81. Some eigenvalue results
  82. Eigenvalue algorithms
  83. Example of QR iteration for eigenvalues .
envalues. de for eigenvalues.