MA 692, Sparse and Structured Matrix Computations, Fall 2012

Lectures: TTh 1:30-2:45pm, REC 103
Instructor: Prof. Jianlin Xia                                   Email: (Pls do NOT use my @purdue.edu email address)
Office: MATH 442	Office Hours: TTh 3-4pm, and by appointment
Course webpage: http://www.math.purdue.edu/~xiaj/teaching/692.12f/

• Lecture notes and references (subject to change)
  • 11/20: Matrix equations
    • N. J. Higham, Matrix Functions: Theory and Algorithms
    • N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, 2008
  • 11/13, 11/15: 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)
  • 11/8: Matrices with displacement structure (updated: 11/8)
  • 11/1, 11/6: Toeplitz matrices and more
    • E. H. Bareiss, Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices, Numer. Math. 13 (1969), pp. 404--424.
    • G. Cybenko, The numerical stability of the Levinson-Durbin algorithm for Toeplitz systems of equations, SIAM I. Sci. Statist. Comput. 1 (1980), pp. 303--319.
    • N. Levinson, The Wiener RMS error criterion in filter design and prediction, J. Math. Phys., 25 (1947), pp. 261--278.
    • J. Nagy, Fast Inverse QR Factorization for Toeplitz Matrices, SIAM J. Sci. Comput., 14 (1993), pp. 1174--1193.
  • 10/30: Hierarchical matrices
    • Notes by S. Borm., L. Grasedyck, and W. Hackbusch
    • Slides by S. Borm
    • Fast multipole method and H-matrix by X. Xue
  • 10/23: Fast multipole method (updated: 10/23)
    • R. Beatson and L. Greengard, A short course on fast multipole methods
    • http://fastmultipole.org
  • 10/16, 10/18: Structured multifrontal method
  • 10/16: Structured inversion
    • A Matlab code (two examples) showing that the Sherman-Morrison-Woodbury formula can be unstable
  • 10/11: Multifrontal method
    • J. W. H. Liu, The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
  • 10/2, 10/4: Randomized sampling for matrix compression and HSS construction
    • P. G. Martinsson, Randomized Algorithms for Very Large-Scale Linear Algebra (slides)
  • 10/2: Strong rank-revealing factorizations
  • 9/27, 10/2: Rank-revealing factorizations
    • An 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/25: Orthogonal matrices (part)
    • 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
  • 9/13, 9/15, 9/18, 9/19: Semiseparable and hierarchically semiseparable matrices (last updated: 9/24)
    • Matlab code for testing low-rankness
    • J. Xia, et al., Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 953-976.
    • S. Chandrasekaran, et al., Some Fast Algorithms for Sequentially Semiseparable Representations, SIAM. J. Matrix Anal. Appl., 27 (2006), 341–364.
  • 9/11: Additional iterative methods and Krylov subspace methods
  • 9/4, 9/6: Basic iterative methods
    • Y. Saad, Iterative methods for sparse linear systems (from Saad's webpage) (2nd ed.). This is the same text as the book with the same title offered by SIAM
  • 8/28, 8/30: Sparse Gaussian elimination
    • X. S. Li, Direct solvers for sparse matrices (survey)
  • 8/23, 8/28: Sparse matrices (last updated: 8/27)
  • 8/21: Introduction
• Course information and resources
  • Course outline (subject to change)

    Week	Topics
    1–2	Sparse matrices and related graph theory, sparse direct solvers
    3	Iterative methods, projection and Krylov subspace methods, preconditioning
    3–5	Semiseparable structures, SSS and HSS matrices
    5–7	Low-rank structures and rank-revealing factorizations
    7	Randomized methods
    8	Multifrontal method
    9	Sparse structured factorization
    10	Fast multipole method, mutilevel summation method
    11	H and H2 matrices
    12–13	Dense structured matrices (Toeplitz, Vandermonde, etc.)
    13–14	Least squares and eigenvalue problems, summary, presentations

  • Prof. Gleich's CS 515 course: Numerical Linear Algebra
  • Useful seminar series: CAM, CAM lunch, CSE, CS, Math, Science, ECE
  • Demmel's lectures notes for Applied Numerical Linear Algebra
  • Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide
• Reference books
  • Demmel, Applied Numerical Linear Algebra, 1997
  • Golub and Van Loan, Matrix Computations, 4th ed., 2012
  • Laub, Computational Matrix Analysis, 2012
  • Saad, Iterative Methods for Sparse Linear Systems, 2003
  • Trefethen and Bau, Numerical Linear Algebra