MA 692, Sparse and Structured Matrix Computations, Spring 2011

Lectures: REC 227, TR 1:30-2:45PM
Instructor: Prof. Jianlin Xia                                   Email: (Pls do NOT use my Purdue email address)
Office: MATH 442	Office Hours: TR 3:00-4:00PM, and by appointment

• Lecture notes and references (subject to change)
  • 4/12, 4/14: Structured sparse solution
    • S. Chandrasekaran, P. Dewilde, M. Gu, and N. Somasunderam, On the Numerical Rank of the Off-Diagonal Blocks of Schur Complements of Discretized Elliptic PDEs, SIAM. J. Matrix Anal. & Appl. 31, pp. 2261-2290.
    • J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1382-1411.
    • P. G. Martinsson, A fast direct solver for a class of elliptic partial differential equations, Journal of Scientific Computation, pp. 316-330, 38(3), 2009.
    • P. G. Martinsson, Fast direct solvers for elliptic PDEs (slides)
  • 4/5, 4/7: Multifrontal method
    • I. S. Duff and J. K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software, 9 (1983), pp. 302--325.
    • J. W. H. Liu, The multifrontal method for sparse matrix solution: Theory and practice, SIAM Review, 34 (1992), pp. 82--109.
  • 3/29, 3/31: Hierarchical matrices:
    • Notes by S. Borm., L. Grasedyck, and W. Hackbusch
    • Slides by S. Borm
    • Fast multipole method and H-matrix by X. Xue
  • 2/22, 3/24: Fast companion eigensolvers, hierarchically semiseparable structures
  • 3/9: Treecode (Prof. Li)
  • 3/8, 3/10: Multilevel summation method, semiseparable structures
    • R. D. Skeel, I. Tezcan, and D. J. Hardy, Multiple grid methods for classical molecular dynamics, J. Comp. Chem., 23(2002), pp. 673--684.
    • D. J. Hardy, J. E. Stone, K. Schulten, Multilevel summation of electrostatic potentials using graphics processing units, Parallel Computing, 35(2009), pp. 164--177.
  • 2/24: Fast multipole method (FMM)
    • L. Greengard and V. Rokhlin, A Fast Algorithm for Particle Simulations, J. Comput. Phys., 73 (1987), pp. 325--348.
    • J. Carrier, L. Greengard, and V. Rokhlin, A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. Stat. Comput., 9 (1998), pp. 669--686.
    • R. Beatson, L. Greengard, A short course on fast multipole methods.
    • X. Sun and N. P. Pitsianis, A Matrix Version of the Fast Multipole Method, SIAM Review, 43 (2001), pp. 289--300.
  • 2/22: Multigrid. Preconditioning.
    • Slides: Jim Demmlel's lecture notes on multigrid
    • Matlab codes: Jim Demmel's Multigrid codes for Poisson's equation
    • Video: Gilbert Strang's lecture (MIT OpenCourseWare)
    • Matlab routine for displaying the eigen info of  T1
  • 2/17: Domain decomposition methods and conditioning
    FFT solvers (slides by Jim Demmel). Additional references:
    • J. Mandel, On block diagonal and Schur complement preconditioning.
    • S. C. Brenner, The Condition Number of the Schur Complement in Domain Decomposition.
    • M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J. 25:619--637, 1975.
    • Jim Demmel's lecture notes on graph partitioning
  • 2/15: Krylov subspace methods
  • 2/10: Projection methods
  • 2/8: Basic iterative methods. References:
    • J. Demmel, Applied Numerical Linear Algebra, SIAM.
    • 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
  • 2/1, 2/3: Matrices with displacement structure
  • 1/25, 1/27: Toeplitz matrices and more. References:
    • 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.
  • 1/18, 1/20: Sparse Gaussian elimination. Additional references:
    • J. Demmel, P. Koev, and X. Li, A Brief Survey of Direct Linear Solvers. [link]
    • F. Harary, A graph theoretic approach to matrix inversion by partitioning, Numer. Math., 4 (1962), pp. 128--135.
    • S. V. Parter, The use of linear graphs in gaussian elimination, SIAM Rev., 3 (1961), pp. 119--130.
    • R. P. Tewarson, On the product form of inverses of sparse matrices and graph theory, SIAM Rev., 9 (1967), pp. 91--99.
  • 1/12, 1/18: Sparse matrices. Additional references:
    • A. George, Nested Dissection of a Regular Finite Element Mesh, SIAM J. Numer. Anal. 10 (1973), pp. 345-363. [link]
    • A. George and J. W. H. Liu, Computer solution of large sparse positive definite systems, Prentice-Hall, Englewood Cliffs, NJ, 1981.
  • 1/10: Introduction
• Course information and resources
  • Course description

    Week	Topics
    1–2	Sparse matrices and related graph theory, sparse direct solvers
    3–4	Dense structured matrices (Toeplitz, Vandermonde, etc.)
    4–5	Iterative methods, projection and Krylov subspace methods, preconditioning
    6	Domain decomposition, FFT solver
    7	Multigrid
    8	Fast multipole method, mutilevel summation method
    9	Semiseparable structures, SSS and HSS matrices
    10	H and H2 matrices
    11	Multifrontal method
    12	Sparse structured solution
    13–14	Least squares and eigenvalue problems, summary, presentations

  • Useful seminar series: CAM, CAM lunch, 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