MATH 5485 / CS 5485

Numerical Analysis and Software I

 

Numerical Analysis and Software I

Iterative Methods for Large Sparse Linear Systems - From Basics to Current Research

Iterative methods for linear systems play a fundamental role in virtually all large-scale simulation and optimization problems. Hence, they are of great importance for computational science and engineering applications. In this course, we will introduce and discuss the most popular iterative methods and preconditioners, analyze their theoretical properties (including convergence issues), and evaluate solvers and preconditioners for various applications, including numerical experimentation. Students can use their own research problems for such experiments. Furthermore, we will discuss how variations of these methods can be used for solving large-scale eigenvalue problems, and how these methods relate to nonlinear systems and optimization (more on this will be taught in part II in spring 2010). Finally, we will consider a selection from important current research topics, such as convergence improvement by various projections, efficiently solving long sequences of linear systems, preconditioners for saddle-point problems (incompressible flow, optimization), multilevel methods and preconditioners, solving linear systems with approximate matrices, and recent convergence results and error bounds.

Instructor:

·         Eric de Sturler (click to check what I do the rest of my time)

·         Office: 544 McBryde

·         Phone: (540) 231-5279

·         Email: sturler-at-vt-dot-edu

·         Office hours: TBA and by appointment (send email)

Prerequisites: A senior level numerical analysis course, such as math 4445/4446, or a numerical linear algebra course, including basic (but not advanced) programming skills.

Overview

  • Overview of applications of iterative methods,
  • Mathematical preliminaries: inner products, norms, spectral radius, projections, eigenvalues and singular values, condition number/sensitivity, accuracy and error analysis, matrix polynomials and Krylov spaces (other relevant theoretical topics will be introduced where needed),
  • Projection-based methods, minimum residual solutions, GCR and GMRES,
  • Minimum error solutions, Conjugate Gradients,
  • Numerical comparison of CG with GMRES/GCR, computational costs,
  • Minimum residual methods for Hermitian (symmetric) indefinite systems, MINRES,
  • Convergence analysis, CG, MINRES, GMRES, and restarted GMRES,
  • Improving convergence for restarted/truncated methods for non-Hermitian (nonsymmetric) matrices,
  • Efficient solution of sequences of linear systems,
  • Short term recurrences for non-Hermitian (nonsymmetric) matrices, BiConjugate Gradients (BiCG) and related methods, BiCGSTAB, QMR, TFQMR,
  • Preconditioning
    • Incomplete decompositions
    • Sparse approximate inverses (factorized and explicit)
    • Basic iterative methods, smoothers, and multigrid (brief overview)
    • Multilevel preconditioners
    • Preconditioners for sequences of linear systems   
  • Eigenvalue problems
  • Solving linear systems with approximate matrices
  • Recent results on convergence and error bounds

 

               

Design of an optimal beam

 

Lecture Notes

Textbook:

Iterative Krylov Methods for Large Linear Systems,

Cambridge University Press Series: Cambridge Monographs on Applied and Computational Mathematics (No. 13),

Henk A. van der Vorst, Universiteit Utrecht, The Netherlands.

The lecture notes will cover significant additional material.

Other useful books on iterative methods are:

  • Computer Solution of Large Linear Systems, Gerard Meurant, North Holland,
  • Iterative Methods for Sparse Linear Systems, Yousef Saad, SIAM (note that Yousef generously makes an older version of the book available online),
  • Iterative Methods for Solving Linear Systems, Anne Greenbaum, SIAM,
  • Numerical Linear Algebra for High Performance Computers (more general with focus on high-performance computing), Jack Dongarra, Iain Duff, Danny Sorensen, and Henk van der Vorst, SIAM,
  • Iterative Solution Methods, Owe Axelsson, Cambridge,
  • Multi-Grid Methods and Applications, Wolfgang Hackbusch, Springer,
  • Multigrid, U. Trottenberg, C. Oosterlee, A. Schüller, Academic Press,

Some books focusing on preconditioning are:

  • Multilevel Block Factorization Preconditioners, Matrix-based Analysis and Algorithms for Solving Finite Element Equations, Panayot S. Vassilevski, Springer,
  • Matrix Preconditioning Techniques and Applications, Ke Chen, Cambridge
  • Domain Decomposition, Barry Smith, Petter Bjørstad, and William Gropp, Cambridge
  • Domain Decomposition Methods – Algorithms and Theory, Andrea Toselli and Olof Widlund, Springer

Homework:

    Your homework is now officially late!

Quizzes will only be given on request J

Course Policies

Class Projects (link will be added shortly)