NUMA11/FMNN01 - Schedule

The course runs for seven weeks in study period 1 in the fall of 2011. We meet for Lectures three times per week. The first meeting is Monday August 29th. The last meeting is Friday October 14th.

Monday 15:15-17:00	Lecture	Lecture Hall MH:B
Wednesday 15:15-17:00	Lecture	Lecture Hall MH:A
Thursday 10:15-12:00	Counseling	Office MH:428/547
Friday 15:15-17:00	Lecture	Lecture Hall MH:B

Course Outline

Course Diary

• Lecture 1, August 29: Review of pages 1-22 up to Example 3.6 in the textbook. Theorem 3.1, first part. An equivalence theorem for norms, contained in the proof of theorem 14.1 on page 107, was mentioned. A relation between the 2-norm of matrices and eigenvalues was also mentioned and is given here.
• Lecture 2, August 31: More detailed coverage of pages 25-30, 32-35 including Theorem 4.1 and Theorem 5.8. The proof of these theorems, which are in the book, were left for self-study. Note: when deriving matrix properties from the SVD, it is usually sufficient with a reduced SVD. But if the nullspace is of interest, one needs a full SVD. See the MATLAB documentation for the difference between svd(A,0) and svd(A,'econ').
• Lecture 3, September 2: Projectors, pages 41-46. In Theorem 6.1, the short first part was left for self-study while the longer second part was worked out on the blackboard.
• Lecture 4, September 5: Classical Gram-Schmidt and modified column-oriented Gram-Schmidt. Pages 48-52, 54, 56-57. General discussion about floating point arithmetic and BLAS . An example program priority1.txt / priority.m was shown. If this is not at all familiar, please also read about floating point arithmetic and Chapter 1.7 in Moler.
• Lecture 5, September 7: Modified Gram-Schmidt. Column-oriented and row-oriented implementations. Pages 58-61. In addition a few words about column pivoting and the A*E=Q*R factorization, obtained via [Q,R,E]=qr(A), where E is a permutation matrix (orthogonal but not necessarily symmetric). In the textbook, column pivoting is mentioned in passing on pages 139, 140, and 143.
• Lecture 6, September 9: Householder Triangularization. Pages 69-75. Note that once R is computed via Algorithm 10.1, the matrix Q can be computed via Algorithm 10.3 applied to the identity matrix. If one saves the v_k vectors and takes advantage of sparsity, the extra computational cost of computing Q is similar to the original cost of computing R. Also note that for the case of a matrix A with complex elements, Figure 10.1 and Figure 10.2 are more involved than the authors suggest. Algorithm 10.1, however, still holds with a suitable interpretation of the sign function. The paper The computation of elementary unitary matrices gives a more detailed treatment of pages 71-72 in the course book. When m < n, the loop in Algorithm 10.1 should be: for k=1 to min(m,n).
• Lecture 7, September 12: Least squares problems. Pages 77-84. Some extra information about the Moore-Penrose Pseudoinverse and Generalized inverses. Main points were uniqueness of the solution, and the three numerical routes to computing the solution. What happens with these standard methods if the system matrix is rank-deficient? Well, check for yourself with this program: rankdef.txt / rankdef.m
• Lecture 8, September 14: Conditioning and condition numbers. Pages 89-95. Particular emphasis on pages 93-95. Extra details were given in some proofs, where we specialized to 2-norm. A summary paper was handed out. Those interested in componentwise, as opposed to normwise, condition numbers and further developments could check the notes for Chapter 12 on pages 333-334.
• Lecture 9, September 16: Stability and Backward error alysis. Pages 98-99, 102-105, 111-112, 116-117. The most important result was Theorem 15.1, and I tried to give a more detailed proof than the textbook. Theorems 19.1, 19.2, 19.3, and 19.4 were mentioned in passing.
• Lecture 10, September 19: Conditioning of least squares problems. Pages 129-135. We did not transform the problem into diagonal form. Theorem 18.1 is central. The lecture focused on those perturbations in input which (approximately) realize these numbers. In the notes on page 335 the authors admit that "The literature on this subject is not especially easy to read". Perhaps this can explain that the mathematics of this chapter does not seem to be entirely rigorous. Does anyone know of a better text? Theorems 19.1, 19.2, 19.3, and 19.4 should be interesting reading, since they tie together several important concepts in the course. We also discussed the program leastime.txt / leastime.m
• Lecture 11, September 21: Back substitution, Augmented systems, and Gaussian elimination. Pages 121-122, 139, 147-153. Algorithm 17.1 and Algorithm 20.1 are particularly important. Note that the MATLAB backslash command recognizes triangular systems and permutations of triangular systems and automatically chooses back/forward substitution or permuted back/forward substitution whenever it applies. Note also that the qr(A) command gives a full matrix whose relation to R is R=triu(qr(A)). The lower triangular part of R contains the vectors needed to build the elementary Householder reflectors. See documentation for DGEQRF.f
• Lecture 12, September 23: September 24: LU-factorization with partial pivoting and Cholesky factorization. Pages 155-161, bottom of page 166, 172-177. Algorithm 21.1 and Algorithm 23.1. An example program illustrating complexity in MATLAB was shown: baqr.txt / baqr.m. Note that MATLAB's backslash operator checks for eight different special properties of system matrices before it decides to do Gaussian Elimination. Hermiticity and Positive Definiteness is checked as follows: First Hermiticity is checked. If OK, then the diagonal elements are checked for positiveness. If OK, then Cholesky factorization is attempted. If it works then the system matrix was Positive Definite. The work is done. If it fails, then the system matrix was not positive definite. Gaussian Elimination is used.
• Lecture 13, September 26: Review of spectral theory. Pages 181-188. Focus was on concepts that will be used for the construction of algorithms in subsequent chapters. Proofs were left for self-study. In addition to this material I said a few words about right and left eigenvectors , the Cayley-Hamilton theorem , minimal polynomials, and compared Jordan matrix decomposition to Schur decomposition.
• Lecture 14, September 28: Overview of eigenvalue algorithms and reduction to Hessenberg form via Householder reflections. Pages 190-194, 196-200. Algorithm 26.1 is important. In connection with reduction to Hessenberg form, I mentioned the alternative Gram-Schmidt-like procedure known as "the Arnoldi process", on pages 251-252. An illustration to Problem 3 on Assignment 4 can be found here: demo2.txt / demo2.m.
• Lecture 15, September 30: Power Iteration, Shifted Inverse Iteration, and Rayleigh Quotient Iteration. Pages 202-209. A few extra details on the derivation of Theorem 27.1 and Theorem 27.3.
• Lecture 16, October 3: The QR-algorithm. Pages 211-217, 219-220. I used a slightly different notation than the authors: I let Q belong to simultaneous iteration and Q-tilde belong to the QR-algorithm.
• Lecture 17, October 5: The QR-algorithm with shifts and other eigenvalue algorithms. Pages 220-223 in detail. Brief overview of pages 225-232. Check also the LAPACK pages Eigenvalue problems and Symmetric Eigenproblems and What's New in Version 3.3? and What's New in Version 3.3.1? and the Wikipedia page QR Algorithmus. A few remarks on Assignment 5: The Björk-Pereyra algorithm based on Newton-interpolation for solving Vandermonde systems in O(n^2) work is described in chapter 4.6.1 of "Golub Van Loan". Problem 7 is perhaps most easily solved via eq.(9) in On deriving the inverse of a sum of matrices, see the Course library.
• Lecture 18, October 7: Brief overview of algorithms for the SVD, pages 234-239, and iterative methods in general, pages 243-248. The Arnoldi iteration 250-255. Note that page 251 may be misleading. Both Arnoldi and Householder can be used for Hessenberg reduction, even if you choose to stop part-way and use an arbitrary q1. But Arnoldi is generally cheaper and easier to implement. If q1=e1, then Arnoldi with Gram-Schmidt and Householder reduction to Hessenberg form produce results that theoretically are identical up to signs. See further this paper .
• Lecture 19, October 10: Ritz values and GMRES. Pages 257-264, 266-268. Emphasis on Theorem 34.1 and its consequences for the Ritz values. Brief orientation about the results of Exercise 35.4.
• Lecture 20, October 12: Convergence of GMRES, pages 269-274 and particular emphasis on Theorem 35.2 and its consequences. The Lanczos iteration, pages 276-278, 282-283. A few words were said about GMRES in MATLAB and about other iterative solvers for non-symmetric systems. See, further, Templates for the Solution of Linear Systems: Building Blocks for Iterative methods. I also constrcucted a well-conditioned matrix which was extremely unfavourable in terms of GMRES convergence. Please take a look at this example program: badex2.txt badex2.m . Note that despite the convergence problems, GMRES produces a solution that is slightly better than backslash!
• Lecture 21, October 14: Conjugate Gradients. A summary of pages 293-301 with focus on Algorithm 38.1 and Theorems 38.4 and 38.5. A few words about proofs and relations to other iterative methods. Then pages 313-319. I did not list all preconditioners included in the survey, but we discussed how to use equation (40.4) in practice. That is, how to implement a Hermitian Positive Definite preconditioner M into the Algorithm 38.1 without using C.

-Johan Helsing