Numerical Linear Algebra - 8EC

Aim of the course

To provide theoretical insight and to develop practical skills for solving numerically large scale linear algebra problems. Particular emphasis lies on large-scale linear systems and on eigenvalue problems.

New developments in many applications, such as weather forecasting, airplane design, tomographic problems, analysis of the stability of structures, design of chips and other electrical circuits, etc, rely on numerical simulations. Such simulations require the numerical solution of linear systems or of eigenvalue problems. The matrices involved are sparse and high dimensional (1 billion is not exceptional). The solution of these linear problems are normally by far the most time-consuming part of the whole simulation. Therefore, the development of new solution algorithms is extremely important and forms a very active area of research.

The course will give an overview of the modern solution algorithms for linear systems and eigenvalue problems. Modern approaches rely on schemes that improve approximate solutions iteratively. The course will start with a review of basic concepts from linear algebra, after which solution methods for dense systems (LU, QR and Choleski decomposition) will be discussed.

Next, the basic ideas for iterative solution methods of sparse systems will be explained, which will lead to the main topic of the course: modern Krylov subspace methods. The main ideas of these methods will be explained and how they lead to efficient solvers. Solution algorithms for linear systems that will be discussed include CG, GMRES, CGS, Bi-CGSTAB, Bi-CGSTAB(l) and IDR(s). Furthermore several preconditioning and deflation techniques will be explained. For large scale eigenvalue problems the Lanczos methods, Arnoldi's method and the Jacobi-Davidson method will be treated.

Prerequisites

Good knowledge of linear algebra and some experience in programming in MATLAB.

The text "Preliminaries" collects the Linear Algebra prerequisites that are needed for this course. The material is presented in the form of exercises and can be used to “refresh” Linear Algebra knowledge and skills. Some issues in this collection may not belong to a standard Linear Algebra course. These less-current issues will be introduced and discussed in the course when needed.

On the course page you find a link to a Matlab Tutorial and also to a text with some simple ‘Matlab exercises’ (with some code) that may help you to familiarize you with Matlab and some of its peculiarities.

Rules about Homework / Examination

Quiz, homework assignments and a final project assignment.

Grading is based on the results of one quiz (Q), homework assignments (H) and one final project assignment (P). The grade H of the homework assignments is obtained by averaging the grade of the best 10 sets of homework assignments out of 14 sets (with at least one grade ≥ 6 in each set of four consecutive sets of homework assignments and in the sets of Matlab assignments). If this average happens to be less than 6 (<6), then you have to do an oral exam (on the material of the whole course) and H is the grade for this exam. The final grade C for this course is a weighted average of the grades H and P provided the grade Q for the quiz is ≥ 6:
C=(6*P+4*H)/10.

The quiz is to check whether your knowledge of Linear Algebra is sufficient to do this course. The review quiz 2007 may give you an impression of the level that you can expect.