Numerical Linear Algebra

Dr. Gerard L.G. Sleijpen (UU)

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 eigenvalues 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 Cholesky 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.

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.

Fourteen lectures, each consisting of instruction and theoretical and practical assignments.

The practical assignments are essential to the course: they provide insight (the theoretical lectures are low on practical examples; the idea is that it is more instructive to find out things for yourself), give additional (minor but essential) theoretical results, stimulate the development of programming skills, introduce standard packages and point out their strength and weaknesses. Moreover, programming is essential to Numerical Linear Algebra and any other field in Computational Science (CS). In CS, theory is being developed to allow efficient and accurate computations of numerical solutions of practical problems. Clearly, actual computations require programming. But, in addition, theoretical results in CS often lack rigorours mathematical proofs and, therefore, require a back-up by insights and results from well-chosen numerical experiments.
The practical assignments require programming in MATLAB. A Matlab tutorial is available. If you plan to attend this course then, please, bring a laptop to class for the practical assignments under supervision of the teacher. Below, in ‘On MATLAB’, you can find instruction on obtaining MATLAB.

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 a grade ≥ 6 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 grade P for the final project assignment is determined by the report on the project and a review discussion (defence) on the report (that is, an oral exam that focusses on the report's material). The final grade C for this course is a weighted average of the grades H and P provided that 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.

Homework assignments are to be handed in (on paper) before the start of the next lecture. If that is not possible, then make another arrangement with the teacher in advance. If there is no other possibility and you wish to hand in the solutions electronically, then submit one pdf file (no other formats will be excepted and no collection of files [not zipped, not tarred, not separated]. If you have figures (jpg), or m-files that you want to submit, then include them (also) in the one pdf file: .docx files are often hard to get opened and printed in a linux system. Include your name and the exercise number in the name of the file, as NLA-sleijpen-2.pdf).
There is no need to Latex the solutions (nor to use full sentences. Handwritten, ‘exam-style’ is okay, as long as the teacher can follow your arguments. In case of electronic submission, a scan of the handwritten solution is fine). Discussing the assignments with fellow students is allowed (and encouraged). But you have to write down the solutions yourself: copies are not accepted.

With respect to the final project, cooperation is allowed (and even encourage, assuming cooperation leads to more insight). However, cooperation is restricted to couples of two only and each of the authors is responsible for the whole report. As mentioned above, the grade will also depend on the review discussion ("defense") of the report. More specifically, in case of a joint report, the individual grade depends on the individual contribution in the discussion and the discussion may extend to the contribution in the report of your co-author. If you plan to do the final assignment with someone else, let the teacher know the name (& email) of your partner.
The final report should by like a research paper: well written, printed (using LaTeX), well structured, self-contained, with introduction, motivations, background information, well stated claims (theorems), arguments to support the claims (proofs, heuristic arguments, experimental results, whatever is required), well chosen numerical experiments, interpretations and discussions, conclusions, references and cross-references. (Pretend that your audience is not the teacher, but students who took this course sometime ago: they understand the principal arguments in Numerical Linear Algebra, but forgot details and notations and are not specialists.)
Submit electronically a pdf version of the report. Submit the code that you wrote and used as well (supplied with brief comments): pdf of the report and m-files of the code together in a zipped (or tarred and gzipped) folder. If you discuss (part of) the code in the report, then include (that part of) the code in (for instance, as an appendix of) the report with proper cross-references.
Hints for the final report. To facilitate experiments (to be more precise, to allow easy inclusion of preconditioning), it may be helpful to study “Explanation of the code” first. For an instructive representation of numerical results, the “Notes on numerical experiments” may contain useful hints.

Good knowledge of linear algebra and some experience in programming (preferable 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.

Here (below) 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.

Lectures will be at

Location (folow the links also for a marked Google map):     HFG 611AB (Hans Freudenthal Gebouw, room 611),     Budapestlaan 6,     De Uithof, 3584 CD Utrecht     The course will start in week 37, 2017 (13 September, 2017). There will be no lecture in week 43 (Wednesday, 25 October, 2017). The course schedule is under construction. The schedule as well as the “homemade” material will be updated on Wednesdays before the course.

COURSE MATERIAL

COURSE SCHEDULE, TRANSPARENCIES, ASSIGNMENTS

Downloading your own files

Some Useful Links

• NetLib: a wealth of information to numerical software as
  • LAPACK, BLAS: dense linear algebra
  • NETSOLVE: grid computing
  • TEMPLATES: the books plus software
  • MATRIX MARKET: test matrices
• MATRIX MARKET: test matrices
• Henk van der Vorst's homepage with the manuscript of the book
  Lecture Notes on Iterative Methods (Part 1, Part 2, Part 3)
  and the manuscript of a book on eigenvalue problems
  Computational Methods for Large Eigenvalue Problems
  (Contents, Chapters 1,2, Chapters 3,4, Chapters 5,6, Chapters 7,8, Chapters 9,10, Chapters 11-end).
• Gilbert Strang's homepage with video course, demos, etc..

On MATLAB

Matlab is freely available for students (and staff) of Utrecht University: see the news flash of 13 august 2015. This link gives also instruction on how to install MATLAB on the laptop. At the moment, it is not clear whether UU offers MATLAB (during the time of the course) also to non-UU students. If the student's home university does not provide a copy of the MATLAB program, then there are two other options:

• obtain Matlab's student version
• install Octave. Octave is a variant of Matlab that is freely available (and, according to some of last year students, seems to suffice for this course), see also the discussion in Wikipedia

• Online manual matlab
• A Matlab tutorial is available.
  The text “An introduction to Matlab in Computational Science”, introduces (some peculiarities of) Matlab (that are of importance for speeding up large scale computations) and contains some exercises to practise programming in Matlab. There is a partial Matlab code that goes with this text (M-files; zip ).