Math 221, Matrix Computations, Fall 2007.

• Term Projects
  • Orbit of Ceres: Gauss invented the least squares method in the process of recovering the orbit of dwarf planet Ceres. The aim of this project is to recover exactly what Gauss did 200 years ago. People involved in this project:
    • Jeffrey Donatelli, Math.
    • Jeffrey Hunt, CEE.
    • Veronique Le Corve, CEE.
    Here is their report .
  • Symmetric Definite Pencil: This project looks into different methods for solving the Symmetric Definite generalized eigenvalue problem where one of the matrices is indefinite. People involved in this project:
    • Sindre Hilden, Math.
    • Todd Kosloff, CS.
    • Erik Lian, Math.
    • Erik Nesvold, Math.
    Here is their report .
  • Estimating Forward Errors in linear system solutions: In this project we compare forward error estimates suggested in the text with an alternative one. People involved in this project:
    • Sage Briscoe, Math.
    • Vasily Volkov, CS.
    Here is their report .
• Class Information
  • I will be in office 1:00PM-3:00PM on Tuesday and Wednesday, Dec. 11-12.
  • Project Presentation: Friday, Dec. 7, 1:00-2:00PM, 959 Evans. Course Review: Friday, Dec. 7, 4:00-5:00PM, 959 Evans (Note room change). Final Exam: Wednesday, Dec. 12, 10:00AM-1:00PM, 961 Evans.
  • Here is a link to Jonathan Shewchuk's introductory paper on conjugate gradient: "How could fifteen lines of pseudocode take fifty pages to explain?"
  • Here is a link to a brief discussion of Chebyshev polynomials and approximation theory .
  • In Section 4.5, we will skip all applications, singular matrix pencils, and nonlinear eigenvalue problems. In Chapter 5, we will skip 5.2.1, 5.3.3, 5.3.4, and 5.5
  • It is next week: Oct. 17 is the day for the introductory scientific computing seminar on parallel computing, by Prof. Jim Demmel. The seminar starts at 11:00AM in 380 Soda Hall. I hope to see everyone there.
  • General information.
  • Syllabus.
  • Current set of term projects .
• Homework Sets
  • Homework Set #1, Due Sept. 4 with Selected solutions . Here is a link to George Forsythe's paper on solving quadratic equations .
  • Homework Set #2, Due Sept. 11, with selected solutions .
  • Homework Set #3, Due Sept. 20, with selected solutions .
  • Homework Set #4, Due Sept. 27, with selected solutions
  • Homework Set #5, Due Oct. 4. Note that Problem 3.10 has been taken out of the homework set, thanks to Veronique who discovered that the problem is wrong. Selected solutions
  • Homework Set #6, Due Oct. 11. Selected solutions
  • Homework Set #7, Due Oct. 25. Selected solutions .
  • Homework Set #8, Due Nov. 1. Selected solutions.
  • Homework Set #9, Due Nov. 8. Selected solutions.
  • Homework Set #10, Due Nov. 15. Selected solutions.
  • Homework Set #11, Due Nov. 29. Selected solutions.
  • Homework Set #12. Do not hand it in.
  Midterm Solutions.
• Midterm Solutions.
• Matlab codes
  • pcg.m is a matlab program implementing the preconditioned conjugate gradient (pcg) method to solve linear system of equations.
  • housetest.m is a matlab program that tests the numerical stability of two slightly different ways of computing the Householder transformation.
  • Classicl Gram-Schmidt and modified Gram-Schmidt for computing QR factorization.
  • A simple matlab code for computing quadratic roots in two different ways, with its modified version to reduce overflow/underflow problems.
  • Hager's Condition Estimator . This version estimates the 1-norm of a given matrix B. However, Hager's condition estimator can sometimes fail badly. Read this code and run it to see the results.
  • Generalized Kahan Matrix. This matrix causes very large element growth with GEPP.
  • Here is another one of those Kahan Matrices. This one misses tiny singular values in QR with column pivoting.
  • Here is the QR method. It can be used to drive one eigenvalue to zero.
  • Here is the Symmetric QR method. It can be used to drive one eigenvalue to zero.
  • Here is the Rayleigh Quotient Iteration method. It is usually cubically convergent (to some unknown eigenvalue). But it does not always converge.
  • Here is the dqds method for the bidiagonal SVD problem, without shifts. It should always converge to the smallest singular value.
• Pictures
  • The modified Grcar matrix is a banded matrix with upper bandwidth 10 and lower bandwidth 3, where the non-zero entries on and above the main diagonal are all 1 and non-zero entries below the main diagonal are all -1. pseudospectra of a modified Grcar matrix with complex perturbations.
  • pseudospectra of a modified Grcar matrix with real perturbations.
  • Convergence Behavior of Power Method on random matrices.
  • Convergence Behavior of Inverse Power Method on random matrices. Here we used the shift -1 for an eigenvalue -0.994.
• External Link
  • Prof. Demmel has taught Math221 in the past, using his own text. See Demmel's Math 221 Website. Among other things, there is an errata of the text book, as well as a number of relevant matlab codes.