Numerical Linear Algebra

To provide theoretical insight in and to develop practical skills for numerical solution methods for linear algebra problems of the form

   AX - XB = C + XDX for unknown n x k matrix X

Particular emphasis lies on large-scale linear systems and eigenvalue problems, which are special cases of the above equation.

The 14 lectures consists of several blocks of material, among which are the following topics:

• 01-02 Review of basic concepts from linear algebra
• 03-05 Linear systems: classical versus subspace methods and their combination, the Multi-Grid method
• 06-08 Eigenvalue problems: perturbation theory, pseudospectra, and the theory of subspace methods
• 09-11 Krylov subspace methods and preconditioning
• 12-13 Large-scale eigenvalue problems: algorithms
• 14    Linear algebra methods for initial-value and nonlinear problems.

In the first two weeks, basic tools from linear algebra are reviewed. Most of the material is assumed to be known to the students already, and includes:

• Linear spaces, basis, subspaces, norms and inner products
• Orthogonality, projections, and best approximations
• Matrix factorizations (QR, LU, Cholesky, SVD, Schur)

This part will be concluded with a individual written test, from which students can conclude if they have sufficient background for the course.

In the three weeks to follow, iterative methods for linear systems will be considered. Both classical iterations and subspace methods will be explained in an abstract setting. Their combination leads to the Two-Grid method and the Multi-Grid method for linear systems arising from discretizations of elliptic PDEs. As a special case of subspace methods in which the subspace expands per iteration, the Krylov subspace methods will emerge. The Conjugate
Gradient (CG) method and the Generalized Minimal Residual method (GMRES) are the main examples.

Eigenvalue problems will be studied in the three weeks afterwards. First, the effects of nonlinearity of the eigenvalue problem will be discussed, in the context of perturbation theory and pseudospectra. Then the Power method will be
discussed in relation to the QR iteration. General subspace methods will be the last topic in this block.

In the next six weeks we will see how the theory leads to various modern powerful algorithms for solving linear and eigen-value problems. First, three weeks will be spent on preconditioned Krylov subspace methods for linear system
solution:

• Iterative methods GMRES, CG, QMR, BiCGstab(ell)
• Preconditioning (SSOR, ILU, block preconditioning)

Then the next two weeks will be devoted to practical aspects of subspace based methods for solving large-scale eigenvalue problems such as

• Arnoldi/Lanczos methods and
• Jacobi-Davidson method.

Theory and implementation will go hand in hand.

In week 14 a review will be given on how the ideas of Numerical Linear Algebra can help to solve large scale nonlinear problems and initial-value problems.  Inexact
Newton method will be treated.

In the last six weeks of the course, students work in groups of ideally three persons on project work. This work will be done independently, but with the possibility to consult the lecturers.

The final grade G for this course will be composed from

• four individual theoretical written tests T0, T1, T2, T3 of 30 minutes
• computational assessments A1, A2, A3 made in couples
• the project work P

as G = (T0 + A1 + T1 + A2 + T2 + A3 + T3 + 3P)/10 rounded to integers. Each of the individual tests, assessments and the project work should be 5 or up and G should be 6 or up.

Theoretical Test Tj will generally be about the Assessment Aj, in order to test individually if each student has contributed to the computational work.

Test T4 is a final overview test that should be passed. It does not count towards the final grade.

Lecture Notes, hand-outs, and links to free online sources will be provided by the lecturers. The course will be well-documented at the course web site.

Apart from that, it is advised to get hold of a copy of the third edition of the book "Matrix Computations" by Gene H. Golub and Charles F. van Loan, The John Hopkins University Press, Baltimore and London, 1996

Apart from being prepared to work regularly during the whole semester on theoretical exercises as well as on computational assessments, a good knowledge of the following topics is necessary:

• linear algebra (subspaces and their bases, norms and inner products, orthogonal transformations and
  projections)
• programming in Matlab (matrix building and access, built-in linear algebra functions)

Very helpful is familiarity with

• numerical linear algebra for small scale problems
• Hilbert spaces, inner product spaces
• numerical analysis

Students who doubt whether they are well-prepared for this course are encouraged to contact the lecturers to discuss their participation.

The course web site is at http://staff.science.uva.nl/~brandts/NUMERICAL-ANALYSIS/

A supplementary site is http://www.math.utwente.nl/~botchevma/nla/