MATH 5485 / CS 5485 Numerical Analysis and Software I

 

Numerical Analysis and Software I

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

Iterative methods for linear systems and eigenvalue problems 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 the spring course on nonlinear inverse problems). 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.

Although some material on iterative methods is taught in our general 4445/6 and 5465/6 numerical analysis courses, this course treats the topic much more extensively and in greater theoretical depth.

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: Tuesday 11am - 1pm, Wednesday 2pm - 3pm, and by appointment (send email). These times may have to be changed due to scheduling conflicts.

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: a brief overview of basic numerical linear algebra (LU, Choleski, QR factorization), 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 - requires the solution of a long sequence of slowly changing linear systems

 

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)