2WN10 - Scientific Computing

Teacher: dr.ir. M.J.H. Anthonissen
Scientific Computing Group
Department of Mathematics and Computer Science

Overview

Course name: Scientific Computing
Course code: 2WN10
Semester: A
Target faculties: Mathematics, Physics, Electrical Engineering, Mechanical Engineering

Aim of this course: This course intends to teach mathematical methods for the numerical solution of large scale problems. In particular, methods for the solution of large systems of linear(ized) equations. For such large systems of linear equations, classical methods often introduced in numerical linear algebra (Gauss-Elimination, Jordan decomposition, etc.) do not work. The involved matrices and vectors do not fit into the computer's memory, or the methods are too slow.

This course introduces solution methods for large systems of linear equations. Most of these methods are from the end of the last century, i.e., still recent. The methods require that the system's coefficient matrix satisfies a range of properties (such as positive definite, monotone, diagonally dominant, etc.). Quite a few of these properties have physical counterparts in the boundary value problems which lead to the coefficient matrix. Also the fact that the large systems turn out to be sparse is due to the underlying physics. In order to understand the connection between the physical and mathematical conditions, a minimum amount of attention is spent to Finite Element Methods and Finite Difference/Volume Methods (more details covered in the follow-up course Scientific Computing in Partial Differential Equations (2WN13)).

The computation of a solution of a large sparse system of equations is done with the use of Matlab, and has not been possible since the advent of the faster computers, around 1960.

Amount of credit points:
6

Teaching material:

• Book: Iterative Methods for Sparse Linear Systems, Y. Saad
  The second edition of this book is available as a PDF file, see this course's webpage.

• Book: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, R. Barret et al., SIAM (not required)
  Short introduction in iterative methods, emphasis on implementation. Free download in PostScript.

Notebook:
The use of the notebook is required for the numerical computations (in Matlab).

Teacher:
dr.ir. M.J.H. Anthonissen, HG 8.33, tel 4599, m.j.h.anthonissen@tue.nl

Secretary Scientific Computing Group:
Enna van Dijk, analyse@tue.nl, HG 8.38, tel 2753

Examination:
Assignments + written exam. During the term exercise sets will be handed out during the lectures. It is compulsory to complete all exercises. They account for 50% of the final mark; the other 50% is the written exam. The exercises may be done in pairs: one report per two students.

Short description of goals and contents

The course aims at teaching the (im-)possibilities of calculations with large sparse matrices. A broad range of iterative solution methods (both of the fixed point and of the quadratic minimization type) are introduced. There merits are discuseed, as well as involved computational errors and work load.

• Introduction: Sparse systems of equations; The underlying physical partial differential equations;
• Numerical discretization methods for partial differential equations;
• Vector and Matrix norms to measure errors with;
• Direct solution methods (Gauss-Seidel) - why not;
• Iterative solution methods (fixed point type, fixed step size) - and why;
• Iterative solution methods (quadratic minimization type, flexible step size) - and why;
• Stopping criteria for iterative solution methods (when is the numerical error small enough);
• Properties of matrices, following from the underlying physical partial differential equations;
• Properties of matrices, as required for the iterative solution methods;
• Errors, condition number.

Teaching aims

The student can:

• explain the practical importance of the numerical methods with the use of examples;
• explain the existence of related numerical errors, and keep in mind the consequences;
• make an iterative solver for the determination of the solution of a large sparse system of equations;
• judge this solver's merits concerning efficiency and quality;
• assemble a large sparse system of equations related to a boundary value problem involving diffusion, convection and source terms;
• make use of Matlab in order to solve these assembled systems;
• judge and explain the stability and quality of his solution.

Relation to other courses

Required knowledge:
Introduction Numerical Analysis and (Numerical) Linear Algebra

Instruction information

The course aims at teaching basic insight. The exercises serve the deepening of the knowledge, as well as the exercising of skills in numerical methodologies. The course makes use of a book. Four exercises are distributed, to be worked out in groups of two. (Matlab) Programs have to be written, with the use of the notebook computer. There is enough room for all to ask questions. In part, the exercises have to worked out at home.

Calendar, topics

The section numbers refer to the book by Saad. The following schedule is tentative and may change during the semester.

Quarter A.1, Lecture 1
Outline of the goals and topics of the course: Iterative methods for the solution of boundary value problems; Direct methods versus iterative methods; Discretization of a boundary value problem. Introduction and rehearsal of introduction linear algebra: Determinant and eigenvalues, inner product, vector and matrix norms, matrix classes: symmetric, skew-symmetric, normal, orthogonal
Saad 1.1-1.6

Quarter A.1, Lecture 2
Background in linear algebra, continued: Powers of matrices; Symmetric matrices; Rayleigh quotients; Perturbation analysis of linear systems
Saad 1.8.4, 1.13

Quarter A.1, Lecture 3
Partial differential equations and finite difference discretizations; Partial differential equations of advection-diffusion-reaction type (1D as well as 2D); Central, forward, backward differences
Upwind discretization; Diagonal dominance
Saad 2.1-2.2

Quarter A.1, Lecture 4
Finite element discretizations and the assembly of a stiffness matrix; Properties of the related sparse matrices: Structured (FDM) versus unstructured (FEM). Sparse matrices; Adjacency graph of a matrix; Permutation of the numbering of the unknowns; Data structures
Saad 2.3, 3.1-3.3

Quarter A.1, Lecture 5
Irreducible and reducible matrices. Basic iterative methods: Jacobi, Gauss-Seidel, backward Gauss-Seidel, successive overrelaxation (SOR)
Saad 4.1

Quarter A.1, Lecture 6
Convergence of basic iterative methods. A common framework for projection type iterative solution methods: Iterative methods based on orthogonal and/or skew projections.
Saad 5.1-5.2.1

Quarter A.2, Lecture 1
Iterative methods based on orthogonal and/or skew projections. Typical examples: Steepest descent and Minimal Residual.
Saad 5.3-5.3.2

Quarter A.2, Lecture 2
Krylov-projection methods based on Arnoldi's method (Part 1): Krylov-subspaces. Arnoldi's orthogonalization method. Full orthogonalization method (FOM).
Saad 6.1-6.3.1, 6.4

Quarter A.2, Lecture 3
Krylov-projection methods based on Arnoldi's method (Part 2): Gegeneralized minimal residual (GMRES). Symmetric Lanczos algorithm, Direct Lanczos method.
Saad 6.5-6.5.1, 6.5.4, 6.5.6, 6.5.7, 6.6-6.6.1

Quarter A.2, Lecture 4
Conjugate Gradient method (CG), convergence of CG. Krylov-methods based on Lanczos bi-orthogonalization: Lanczos bi-orthogonalization, BiCG, QMR. Transpose-free methods: CGS, BiCGSTAB. Summary of Krylov subspace methods; how to select an iterative method.
Saad 6.7-6.7.1, 6.11.3, 7.1-7.3.2, 7.4-7.4.2

Quarter A.2, Lecture 5
Preconditioning: Preconditioned iterative methods, incomplete LU-factorizations and the connection with Cuthill-McKee.
Saad 9.1-9.3.2, 10.1-10.3.4

Quarter A.2, Lecture 6

Quarter A.2, Lecture 7

Information

The most recent information is always available at http://www.win.tue.nl/casa/education/courses/2WN10.