AMSC 600 / CMSC 760
Advanced Linear Numerical Analysis
Fall 2007

TuTh 9:30am-10:45am (CSI 1121)

New! December 6: Class will begin at 10am, when the University officially opens. Meanwhile, I'm available to answer questions in my office. I will also hold office hours from 2:45 to 3:45 this afternoon.

Prof. Dianne P. O'Leary
Room 3271 A.V. Williams Building, x52678
oleary@cs.umd.edu
http://www.cs.umd.edu/users/oleary/

Prerequisite: AMSC/CMSC 666 or AMSC/CMSC 660 or permission of instructor. Undergraduate-level knowledge of linear numerical analysis: solution of linear equations and eigenvalue problems. Matlab programming.

Themes: The course will focus on solving applications problems efficiently by exploiting matrix structure.

Topics:

  • Sparse matrices and direct methods for solving linear systems (approx. 2 lectures)
    Storage of sparse matrices and the effects of ordering of equations and unknowns.
  • Iterative methods for solving linear systems and eigenproblems (approx. 11 lectures)
    A survey of Krylov-subspace methods for symmetric and non-symmetric linear systems,
    emphasizing open questions and the interconnections among algorithms, sparsity considerations, and choice of preconditioners.
  • Solving structured matrix problems (approx. 6 lectures)
    Methods for matrices with displacement structure, with applications in signal and image processing.
    Problems arising in control and optimization.
  • Parallel matrix computations (approx. 6 lectures)
    The design and analysis of matrix algorithms for computers with multiple processing units.
  • Special topics (time permitting)

    • Grading: based on homework, project, and an optional in-class presentation.

    Primary textbook: Iterative Methods for Sparse Linear Systems, 2nd edition, by Yousef Saad.
    $95 retail, but $66.50 for SIAM members (www.siam.org)
    and SIAM membership is free to students.

    Basic Information:

  • Course Information and Syllabus
  • UMCP Code of Academic Integrity
  • Information about GRACE computer accounts. For your assignments, you may use GRACE or any other machine with Matlab access.
  • Survival Guide for Scientific Computing
  • New! Announcement of AMSC 614, Finite Element Methods Spring 2008

    Lecture Notes: any changes in repostings are marked in green.

  • Part 1: Sparse Matrices and Direct Methods for Solving Linear Systems of Equations and Eigenvalue Problems
  • Reference: Chapter 3 of Saad.
  • Reference: Dianne P. O'Leary, "Solving Sparse Linear Systems: Taking the Direct Approach," Computing in Science and Engineering, vol. 7, no. 5, pp. 62-70, Sept/Oct, 2005 and Vol. 7, No. 6, November/December 2005, pp. 77-80. (Available through UMD Research Port, E-journals)
  • Another good reference: Timothy A. Davis, Direct Methods for Sparse Linear Systems, SIAM Press, 2006.
  • Lecture notes
  • Part 2: Iterative methods for Solving Linear Systems of Equations and Eigenvalue Problems
  • Reference: Chapter 4 of Saad.
  • Stationary Iterative Methods = Slow Iterative Methods Lecture notes
  • Stationary Iterative Methods convergence results
  • Chebyshev Semi-iterative method Lecture notes
  • KMP Methods: Introduction Lecture notes (Reposted 10/01/07)
  • Some notes on conjugate gradients (Reposted 09/25/07)
  • cg1.m
  • Arnoldi Methods Lecture notes (part 1) (Reposted 10/02/07)
  • Arnoldi Methods Lecture notes (part 2) (Reposted 10/02/07)
  • Bi-orthogonalization Methods Lecture notes
  • Preconditioning Lecture notes (Reposted 10/23/07)
  • Multigrid methods Lecture notes (part 1)
  • Multigrid methods Lecture notes (part 2) (reposted 11/01/2007)
  • Part 3: Solution of Discrete Ill-Posed Problems
  • Lecture notes, part 1
  • A sample program and data can be found here.
  • Lecture notes, part 2 (These notes are from Chapter 6 of this book . We have skipped Chapters 3-5, so not everything in the notes will make sense to you.)
  • Lecture notes, part 3 (These notes are from articles J80, J74, J67, and J63 on my list of publications. )
  • New! Article by Rust and O'Leary, to appear in the journal Inverse Problems. We discussed the residual periodogram and used Table 1 in class.
  • Part 3: Matrix Decompositions in Information Retrieval
  • New! Lecture notes

    • Homework:

  • Homework 1 Due 8am Sept. 28 Correction: On problem 1, west0479 is not symmetric, so work with the matrix west0479+west0479'+4*10^5*I. You may use a random right-hand side.
  • Homework 1 Answers
  • Homework 2 Due 8am October 19
  • Corrections to Homework 2: see pdf file above.
  • In 1c, "qr" should be "eig" (which implements the qr algorithm for finding eigenvalues).
  • In 2a, the displayed equations for C Z_k and C^T W_k are not quite right.
  • The matrices Z and W in 2b are not necessarily the same as those in 2a.
  • In 2c, you should implement the algorithm for 2b.
  • Solution to Homework 2:
  • Homework 2 Partial Solution
  • hw2_1c.m for problem 1c, courtesy of Sungwoo Park.
  • lanczos.m used in problem 1c, courtesy of Sungwoo Park.
  • hw2_2c.m for problem 2c, courtesy of Steve Penny.
  • Homework 3 Due 8am November 2.
  • Homework 3 Partial Solution
  • Do not factor any other matrices of size nxn, but you are allowed to factor matrices of size kxk.
  • Homework 4 Due 8am November 16. This is the last homework.
  • Matlab's GMRES does not seem to permit two-sided preconditioning or right-preconditioning.
    Therefore, to accomplish it, you need to send GMRES a pointer to a function for forming matrix-vector products: x = gmres(@amult,bhat).
    To do right preconditioning, your function should take an input vector p and form the output vector A*(M\p). For right preconditioning, set bhat = b.
  • The GMRES problem is harder than I thought. It is more interesting to set the restart parameter to 100 (instead of 20) and the convergence tolerance to 1.e-2 (instead of 1.e-4).
  • Solution:
  • Written part
  • h4p1.m for problem 1
  • h4p1.m for problem 4, courtesy of Sungwoo Park.
  • run_gmres.m for problem 4, courtesy of Sungwoo Park.

    • Term project information: Directions Deadline for bibliography is now November 6, not October 30.