MA 692, Sparse and Structured Matrix Computations, Fall 2016

Lectures:TTh 1:30-2:45am, MATH 215Instructor: Prof. Jianlin Xia Email:Office: MATH 442 Office Hours: TTh 2:50-3:50pm, and by appointment Course webpage:http://www.math.purdue.edu/~xiaj/teaching/692.16f/

- Lecture notes and references
(subject to change)
- Fast structured eigenvalue solutions
- A Matlab test for Rayleigh quotient iterations
- A Matlab test for Hermitian QR iterations (no deflation)

- Fast structured sparse direct solutions
- Rank-revealing factorizations
- Gu and Eisenstat, Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization, SIAM J. Sci. Comput., 17(4), 848–869.

- HSS matrices
- Fast multipole method
(updated: 10/20)
- Slides on FMM by X. Xue
- A Matlab code to show degenerate expansions and numerical ranks
- Beatson and Greengard, A short course on fast multipole methods
- Top 10 algorithms of the 20th century, SIAM News 33(4)

- Sparse iterative solvers (updated: 10/6)
- A Matlab code to demonstrate the condition numbers of Schur complements
- A Matlab code to demonstrate the dependence of the convergence on the number of distinct eigenvalues
- A Matlab code to demonstrate the performance for weighted Jacobi
- A Matlab code to demonstrate the accuracy of simple iterative solvers
- A Matlab code to demonstrate the convergence of iterative refinement

- Sparse direct solvers (updated: 9/27)
- A Matlab code to demonstrate the accuracy of basic sparse direct solvers
- A Matlab code to demonstrate spectral partitioning
- Yousef Saad's Matlab Suite that includes some commonly used algorithms
- T. Davis, Summary of available software for sparse direct methods
- A Matlab package for graph partitioning and matrix ordering: MESHPART
- A. Pothen, H. D. Simon, K.-P. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIMAX

- Introduction and preliminaries
(updated: 9/20)
- 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
- A Matlab code for estimating f'(x)
- 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 (two examples) showing that the SMW formula is unstable

- Fast structured eigenvalue solutions
- Course information and resources
- Course outline
(subject to change)
- Introduction and preliminaries
- Sparse matrices and sparse direct solvers
- Sparse iterative solvers
- Fast multipole method
- Rank structures, accuracy, and stability
- Randomization
- Structured sparse direct solvers
- Preconditioning
- Eigensolvers
- Other topics

- 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

- Course outline
(subject to change)
**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