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 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
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.
PREREQUISITES
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.
CREDITS
8 ECTS
TIME SCHEDULE and LOCATION
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 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
Recommended literature:
"Matrix
Computations", by Gene H. Golub and Charles F. van Loan. The
John Hopkins University Press, Baltimore and London, 1996.
"Iterative Krylov Methods for Large Linear Systems" (Part 1,
Part
2, Part 3),
by Henk A. van der Vorst, Cambridge University Press,
Cambridge, 2003.
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
(in principle, three weeks after assigning) 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". In any
case, solutions will not be accepted when handed in after the end of
January this academical year.
Schedule 2017
Introduction:
preliminaries
(including the theoretical assignments T.0.1,...).
Day 2:
transparencies (pdf,
Handouts),
assignments (Matlab,
Theoretical),
matlab code (zip,
tar.gz;
*) Note: The numbers in magenta on transparencies (as
Ex.2.16) refer to the exercises on the set of Theoretical exercises.
Making these exercises may help to understand the theory.
Homework assignments:
Day 12: transparencies (pdf, Handouts), assignments
(Matlab, Theoretical). EigTool is a nice graphical tool for Matlab to plot
pseudo-spectra of matrices.
Homework assignments:
Day 13: transparencies (pdf, Handouts), assignments
(Matlab, Theoretical), matlab code (zip, tar.gz; *).
Homework assignments: M.12.2 (Hint: use T.6.3.d).
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
NetLib: a wealth of
information to numerical software as
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:
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
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 ).
*
To unwrap FILE.tar.gz: > gunzip
FILE.tar.gz > tar xvf
FILE.tar