Numerical Linear Algebra (BSc)

Owner	Bachelor Wiskunde
Coordinator	dr. Jan Brandts
Part of	Exchange Programme Faculty of Science, specialisation BSc Mathematics, year 1Bachelor Wiskunde, year 3Dubbele bachelor Wiskunde en Informatica, year 3

Course manual 2019/2020

Course content

This course covers how a number of standard linear algebra problems can be solved or numerically approximated in an efficient and stable way. As such, the course is not only valuable for students who aim to work outside the academic world, but also for those who wish to contribute to the theoretical developments that are still in progress. The charm of the course lies in two aspects. Firstly, the most obvious solution method is not necessarily the most efficient, and secondly, whilst designing an algorithm, one has to take into account its stability: although a computed solution to a problem usually does not solve that problem exactly, it should preferably solve a problem that is, in some norm, in some sense, close to the original problem (this will be made precise in the course). This can lead to surprising insights and results.

It is a common misconception that rounding errors are central in Numerical Linear Algebra. Although it cannot be denied that they play an important role, they are not fundamental. Indeed, it is also true that even if a computer were not to make any rounding error during all its computations, it still would not be able to compute eigenvalues or singular values of a larger matrix exactly (Abel-Ruffini Theorem). Thus, approximations and their error analysis are not just a consequence of the computer's finite precision arithmetic limitations, more often they are a mathematical necessity. 

The course treats a large part of the book ``Numerical Linear Algebra'' by L.N. Trefethen and D. Bau, a book used by graduate students at universities as Cornell, MIT, and Oxford. The first author is an influential contemporary numerical analyst. We refer to his personal website for parts of the book, and some interesting essays on the meaning of Numerical Analysis.

Apart from that, we will add a number of new topics, such as fast multiplication, automorphism groups of nondegenerate bilinear forms and their numerical aspects, and bi-orthogonality for which hand-outs will be made available. Furthermore,  certain topics of the book will be treated in more detail than in the book, hence we strongly advice active participation and presence in class.

Topics to be covered: QR-decomposition using Gram-Schmidt, modified Gram-Schmidt, Givens rotations and Householder reflections, automorphism groups, symplectic and Hamiltonian matrices, linear least-squares problems (full rank and rank-deficient), conditioning and stability, finite precision arithmetic, LU-decomposition with partial pivoting, Cholesky-decomposition, bi-orthogonalization, power method, inverse iteration, QR-iteration with shifts, bisection for eigenvalues, Sturm sequences, divide-and-conquer for eigenvalues, Jacobi method for eigenvalues, Golub-Kahan bidiagonalization.

Study materials

Literature

• Lloyd N. Trefethen and David Bau III: `Numerical Linear Algebra', SIAM Society for Industrial and Applied Mathematics, Philadelphia.

Other

• A number of hand-outs written by the lecturer.

Objectives

• The student can describe the following algorithms for linear algebra problems:  Classical Gram-Schmidt; Modified Gram-Schmidt; Householder-QR; Givens-QR; Least-squares using QR, Least-squares using Gauss' Normal Equations; Least-squares using SVD; LU-decomposition with partial pivoting; Cholesky-decomposition; reduction to Upper Hessenberg form; Power method; Inverse Iteration; QR-iteration with shifts; Bisection for eigenvalues; Jacobi method for eigenvalues; Divide-and-Conquer for eigenvalues; Golub-Kahan bidiagonalization;
• The student can prove and/or explain why the above algorithms produce (or converge to) the desired outcome;
• The student is able to implement the above algorithms on a computer, to experiment with the programs, and to analyze and critically comment their outcomes;
• The student is also able to perform the algorithms by hand in some very simple illustrative examples;
• The student knows how a computer performs elementary calculations (addition, subtraction, multiplication and division) on numbers and also which numbers are exactly representable within the computer;
• The student understands the concepts of `conditioning' and '(backward) stability' of problems and algorithms and is able to determine the conditioning of some simple linear algebra problems and the stability of some algorithms;
• The student grasps some new theoretical topics in linear algebra, such as the direct reduction to similar upper Hessenberg (or tridiagonal) form, and the direct orthogonal transformation to bidiagonal form of a matrix; understands the duality between power iteration and inverse iteration present in the QR-iteration.
• The student can prove perturbation bounds on eigenvalues and singular values.
• The student knows what automorphism groups are, in particular orthogonal, unitary, and symplectic groups, and their corresponding matrix Lie groups and Lie algebras

Teaching methods

• Lecture
• Self-study
• Exercise Class
• Computer lab session/practical training

Lectures provide explanations and illustrations of the material from the book and motivation of the relevance of the topics covered. Often, more details that in the book will be given, and also some topics that are not in the book.

Exercise classes are there to solve both theoretical problems and computer programming assessments. The ability to tackle such problems and assessments gives the student insight in the level of understanding of the material.

Learning activities

Academic skills

Using the Linear Algebra programming environment MatLab.

Attendance

Programme's requirements concerning attendance (OER-B):

• Each student is expected to actively participate in the course for which he/she is registered.
• If a student can not be present due to personal circumstances with a compulsory part of the programme, he / she must report this as quickly as possible in writing to the relevant lecturer and study advisor.
• It is not allowed to miss obligatory parts of the programme's component if there is no case of circumstances beyond one's control.
• In case of participating qualitatively or quantitatively insufficiently, the examiner can expel a student from further participation in the programme's component or a part of that component. Conditions for sufficient participation are stated in advance in the course manual and on Canvas.
• In the first and second year, a student should be present in at least 80% of the seminars and tutor groups. Moreover, participation to midterm tests and obligatory homework is required. If the student does not comply with these obligations, the student is expelled from the resit of this course. In case of personal circumstances, as described in OER-A Article 6.4, an other arrangement will be proposed in consultation with the study advisor.

Assessment

Item and weight	Details
Final grade
1 (100%) Tentamen

The final grade for NLA is determined as follows. Consider:

• the grade T of the exam
• the grades M1, M2, M3 of the Matlab assignments

Minimal requirements to pass are:

• T is at least 5.0;
• Each of M1, M2, M3 is at least 5.0;

If you do not satisfy these requirements, your final grade is the minimum of 5.0 and G, defined as

G = (2/3)*T+(1/9)(M1+M2+M3).

If you do satisfy the requirements, your final grade is G rounded to halves, with the exception that G<5.5 will not be rounded to 5.5: if G<5.5 you fail the course, unless you are eligible for the resit (see below).

Homework bonus (only if G is at least 5.5!)

There will be in total eight graded homework sets. Homework is graded by 0,1,2 or 3. Let H be the sum of these homework sets, then if G is at least 5.5, define

E = G + (10-G)*(H/72)

and your final grade is E rounded to halves, with the exception that 5.5 will (forcibly) not occur.

Thus, if you score the maximum of 24 points for homework, you compensate one third of the difference between G and 10: it raises 5.5 to 7.0 and it raises 7.0 to 8.0. 

Observe that this bonus is particularly attractive if you score not too high for G. And yes, it raises 10 to 10 but who needs a bonus then anyway :-)

Exam Resit

If T < 5.0 you need to do the Exam Resit and score for it a grade R of at least 5.0.
R then replaces T in the definition of G.

In this situation, no homework bonus will be assigned anymore.

Replacing Matlab Assignment

Only if no more than one of the three MatLab assignments is less than 5.0, you can ask for a replacing MatLab assignment, which will then be held in an invigilated setting during three hours.

In other words, you fail the course immediately if two or three of them are less than 5.0

This opportunity will only be given if T is at least 5.0 (or if the resit R is at least 5.0; this means that if you need both the exam resit and a replacing MatLab assignment, the latter will only be given if R is at least 5.0)

Its grade M will then replace the one of M1, M2, M3 that was below 5.0.

Also in this situation, no homework bonus will be assigned anymore.

No Show Formalities

The minimum score for T and M1, M2 and M3 is 1.0, also if you do not show up or do not hand in.

Not handing in homework scores 0 (logically).

Inspection of assessed work

Contact the course coordinator to make an appointment for inspection.

Assignments

Matlab assignments

• three programming assignments

Matlab assignments will be made individually. You get a grade between 1 and 10, rounded to halves. Feedback will be given by the teaching assistant. 

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Timetable

The schedule for this course is published on DataNose.

Honours information

There is no Honours Extension of this course. However, if you did not do so in year 2, it is possible to enroll for the Honours Extension for Numerical Analysis in Spring, which has aspects of both Numerical Analysis and Numerical Linear Algebra.

Additional information

Students enrolling in this course should have a good grasp of Linear Algebra, going beyond performing mere matrix computations. In particular, geometrical insights into such manipulations are indispensable.

Furtherore, students are supposed to have good general computer programming abilities (preferably also in MatLab) and basic knowledge of Numerical Mathematics.

This corresponds to the following courses in the BSc Mathematics:

• Lineaire Algebra 1 (semester 1, year 1, from the book ``Lineaire Algebra'' by Igodt and Veys)
• Lineaire Algebra 2 (semester 2, year 1, from the Lecture Notes of Jan Brandts)
• Inleiding Programmeren voor Wiskundigen (semester 2, year 1)
• Inleiding Numerieke Wiskunde (semester 2, year 1, from the Lecture Notes of Jan Brandts)
• Numerieke Analyse (semester 2, year 2, from the book ``An Introduction to Numerical Analysis'' by Suli and Mayers)

Processed course evaluations

Below you will find the adjustments in the course design in response to the course evaluations.

Contact information

Coordinator

• dr. Jan Brandts