MA 692, Sparse and Structured Matrix Computations, Fall 2011

Lectures: BRNG B212, TR 10:30-11:45
Instructor: Prof. Jianlin Xia                                   Email: (Pls do NOT use my Purdue email address)
Office: MATH 442	Office Hours: TR 1:30-2:30PM, and by appointment

• Lecture notes and references(subject to change)
  • Presentations: Starting the week of 11/28
  • 11/22: Condition estimation for eigenvalues and polynomial roots
  • 11/15, 11/17: Condition estimation and statistical condition estimation. References:
    • A basic Matlab code for the condition estimation for Ax=b
    • C. S. Kenney and A. J. Laub, Small-sample statistical condition estimates for general matrix functions, SIAM J. Sci. Comput., 15 (1994), pp. 36--61.
    • C. S. Kenney, A. J. Laub, and M. S. Reese, Statistical condition estimation for linear systems, SIAM J. Sci. Comput., 19 (1998), pp. 566--583.
    • C. S. Kenney, A. J. Laub, and M. S. Reese, Statistical condition estimation for linear least squares, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 906--923.
    • T. Gudmundsson, C. S. Kenney, and A. J. Laub, Small-sample statistical estimates for the sensitivity of eigenvalue problems, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 868--886.
  • 11/8, 11/10: Matrix equations
  • 11/8: Matrix Functions: Theory and Algorithms (Higham). Reference:
    • N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, 2008.
  • 11/3, 11/8: Matrix exponential. References:
    • C. B. Moler and C. F. Van Loan, Nineteen Dubious Ways to Compute the Exponential of a Matrix, SIAM Review, 20 (1978)
    • C. B. Moler and C. F. Van Loan, Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later, SIAM Review, 45 (2003), pp. 3-49
    • N. J. Higham, The scaling and squaring method for the matrix exponential revisited, SIAM Review, 51 (2009), pp. 747-764
  • 11/1: Inexact preconditioning and inner-outer iterations. References:
    • G. Golub and Q. Ye, Inexact preconditioned conjugate gradient method with inner-outer iteration, SIAM J. Sci. Comp. 21 (2000):1305--1320.
  • 11/1: Selected H-matrix techniques. References:
    • S. Borm, L. Grasedyck, and W. Hackbusch, Hierarchical Matrices, 2005.
    • L. Grasedyck, R. Kriemann, S. Le Borne, Domain Decomposition Based H-LU Preconditioning, Numerische Mathematik 112, 565-600 (2009)
  • 10/27, 11/1: Selected advanced sparse matrix techniques. References:
    • X. S. Li, Sparse matrix methods on high performance computers (slides)
    • X. S. Li, Factorization-based sparse solvers and preconditioners (slides)
    • J. H. Gilbert and S.-H. Teng, MESHPART (Matlab package for graph partitioning)
    • L. Grasedyck, R. Kriemann, and S. Le Borne, Parallel black box H-LU preconditioning for elliptic boundary value problems, Comput. Visual Sci., 11 (2008), pp. 273--291.
  • 10/20, 10/25: Structured companion matrix eigenvalue solutions
    • A Matlab code for QR iterations for finding the eigenvalues of a Hessenberg matrix
    • Orthogonal iteration, QR, and Hessenberg QR (D. Bindel)
    • Shift strategies for QR (D. Bindel)
  • 10/18, 10/20: Semiseparable matrix factorization and solution
    • A Matlab code (two examples) showing that the Sherman-Morrison-Woodbury formula is unstable
  • 10/13, 10/18: Algorithms for semiseparable matrices
  • 10/4, 10/6: Semiseparable and hierarchically semiseparable matrices
  • 9/22, 9/27, 9/29: Strong rank-revealing QR/LU factorization
    • M. Gu and S. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, Siam J. Sci. Comput., 17 (1996), pp. 848-869
    • L. Miranian and M. Gu, Strong rank revealing LU factorizations, Linear Algebra Appl., 367 (2003), pp. 1-16
  • 9/13, 9;15, 9/20: Rank-revealing QR factorizations, least squares. References:
    • A RRQR code
    • G. Golub, Numerical methods for solving linear least squares problems, Numer. Math., 7 (1965), pp. 206-216
    • T. F. Chan, Rank revealing QR factorizations, Linear Algebra Appl., 88-89 (1987), pp. 67-82
  • 9/6, 9/8, 9/13: Orthonormal matrices, QR, SVD, and least squares
    • A Matlab code for three ways to compute the Householder matrix (unstable, stable, stable+)
    • A Matlab code for Householder QR
    • Matlab codes for classical Gram-Schmidt and modified Gram-Schmidt (by M. Gu), and the test code
    • A Matlab code showing the use of SVD in image compression
  • 8/30, 9/1: Examples of error, stability, and condition analysis
    • A Matlab code to demonstrate the growth factor
    • Removing Ill-posedness in Numerical Computation - GCD, JCF and Multiple Roots (Slides by Z. Zeng, NEIU)
  • 8/23, 8/25, 8/30: Introduction, rounding error, condition number, backward error, and cancellation
    • A Matlab code to demonstrate catastrophic cancellation
    • A Matlab code (by M. Gu) for both an unstable and a stable way for computing the roots of a quadratic polynomial
• Course information and resources
  • Topics (tentative)

    Week	Topics
    1-2	Introduction, perturbation, stability, and condition analysis
    2–3	Orthogonal matrices, QR, SVD, and least squares
    4-6	Low-rankness, rank-revealing and strong rank-revealing QR/LU
    6-7	Structured matrices and their operations, including randomized methods
    8-9	Structured solvers for linear systems and eigenvalue problems, and their analysis
    10-11	Advanced sparse matrix techniques, including structured ones
    11	Topics for new iterative techniques, matrix exponentials
    12	Matrix equations, their standard and structured solutions
    13	Condition estimation and statistical condition estimation
    14-15	Selected applications, presentations

  • MA 692 for Spring 2011
  • Useful seminar series: CAM, CSE, CS, Math, Science, ECE
  • Jim Demmel's lectures notes for Applied Numerical Linear Algebra
  • Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide