Teaching page G. Sleijpen

Numerical Linear Algebra

Course code: WISL 601 (Utrecht: WISM 458); this course is part of the Mastermath program

INSTRUCTORS

Dr. Gerard L.G. Sleijpen (UU)

CONTENT

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.

AIM

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.

EDUCATIONAL FORM

Fourteen lectures, each consisting of instruction and theoretical and practical assignments. The practical assignments require programming in MATLAB. A Matlab tutorial will be provided.

GRADING

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.

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).
There is no need to Latex the solutions (or to use full sentences. As long as the teacher can follow your arguments). 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. More specifically, in case of a joint report, the grade will also depend on the review discussion ("defense") of the report. If you plan to do the final assignment with someone else, let us know the name (& email) of your partner.
The final report should by like a research paper: well written, printed (LaTeX), well structured, self-contained, with introduction, motivations, background information, well stated claims (theorems), arguments to support the claims (proofs), well chosen numerical experiments, interpretations and discussions, conclusions, 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, the appendix of) the report.
Hints for the final report. To facilitate experiments (to be more precise, to make including preconditioning in a number of codes easier), 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.

PREREQUISITES

Good knowledge of linear algebra and some experience in programming (preferable Matlab).

TIME SCHEDULE and LOCATION

Lectures will be at

Location:
    BBL 103: (Buys Ballot Lab, room 103),
    Princetonplein 5 (Google maps),
    De Uithof, 3584 CC Utrecht
    There are instructions (in Dutch) to get there
    by public transport, by car.
Time: Wednesdays from 14:00-17:00
Dates: week 36, 2011 - week 50, 2011
    (September 7, 2011 - December 14, 2011)

The course will start in week 36, 2011 (September 7, 2011).
There will be no lecture in week 45 (Wednesday, November 9).

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


Warning. The material that is available from the links below for “the days to come”, is from last years course. The actual material that will be used may be (slightly) different. Updates will be made available before the lecture.
Transparencies, handouts, assignments
The number X.D.n of an assignment is constructed as follows: X is either T (for theoretical assignment) or M (for Matlab assignment), D refers to the number of the "Day", n is number of the assignment (of Day D).
If an assignment number is clickable, then the date for handing in the solution is closed and clicking leads to the solution of the assignment. If you are still interested in getting a grade, then you can do the "alternative assignments".

Schedule 2011
  • Day 1 (Dr. M. van Gijzen): transparencies (pdf, Handouts), assignments (Matlab, Theoretical).
    Homework assignments:
  • Day 2 (Dr. M. van Gijzen): transparencies (pdf), assignments (Matlab, Theoretical), matlab code (zip, tar.gz; *)
    Homework assignments:
  • Day 3: Review quiz, transparencies (pdf, Handouts), assignments (Matlab, Theoretical)
    Note: The numbers in magenta on the transparencies (as Ex.3.12) refer to the exercises on the Theoretical assignment papers. Making the exercises may help to understand the theory.
    Homework assignments:
  • Day 4 (Dr. M. van Gijzen): transparencies (pdf), assignments (Matlab, Theoretical), matlab code (zip, tar.gz; *)
    Homework assignments:
  • Day 5: transparencies (pdf, Handouts), assignments (Matlab, Theoretical), matlab code (zip, tar.gz; *, explanation of the code).
    Homework assignments:
  • Day 6: transparencies (pdf, Handouts), assignments (Matlab, Theoretical), matlab code (zip, tar.gz; *, explanation of the code).
    Homework assignments:
  • Day 7: transparencies (pdf), assignments (Matlab, Theoretical)
    Homework assignments: M.7
  • Day 8: transparencies (pdf, Handouts), assignments (Matlab, Theoretical), matlab code (zip, tar.gz; *).
    Homework assignments:
  • Day 9 (Dr. M. van Gijzen): transparencies (pdf), assignments (Matlab, Theoretical), matlab code (zip, tar.gz; *)
    Homework assignments:
  • Day 10 (Dr. M. van Gijzen): transparencies (pdf), assignments (Matlab, Theoretical), matlab code (zip, tar.gz; *).
    Homework assignments: M.10
  • Day 11 (Dr. M. van Gijzen): transparencies (pdf), assignments (Matlab, matlab code (zip, tar.gz; *)
    Homework assignments:
  • Day 12: transparencies (pdf, Handouts), assignments (Matlab, Theoretical).
    Homework assignments:
  • Day 13: transparencies (pdf, Handouts), assignments (Matlab), Theoretical), matlab code (zip, tar.gz; *).
    Homework assignments: M.12.2 (Hint: use T.12.c; both assignments to be found under Day 12).
  • Day 14 (Dr. M. van Gijzen): transparencies (pdf), assignments (Matlab), matlab code (zip, tar.gz; *).
    Homework assignments: M.14.1, M.14.2, M.14.3.
  • matlab code (zip, tar.gz; *). Explanation of the code.

Downloading your own files

If you are not a student from Utrecht University but you have a login (for doing the matlab exercises in class), then you can download the code that you produced in class by
    sftp to students.science.uu.nl
(with, for instance, winscp in windows or a commandline
sftp students.science.uu.nl in linux).


Some Useful Links



*   To unwrap FILE.tar.gz:
    > gunzip FILE.tar.gz
    > tar xvf FILE.tar





  © Gerard L. G. Sleijpen   <sleijpen@math.uu.nl>
  Last modified: Wednesday, 12-Oct-2011 17:05:03 CEST