Numerical Linear Algebra (BSc)

Course manual 2020/2021

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 A-6.4, an other arrangement will be proposed in consultation with the study advisor.

Assessment

Graded components of NLA are:

• the final exam (65%)
• practical assignments 1 and 2 (10% each)
• homework sets 1, 2, 3, 4 (15% together)

The final exam is individual and written and has a minimum requirement of 5.0 out of 10. 

Each of the two practical assignments and each of the homework sets can be made and handed in together with at most one fellow student. Both students by default get the same grade for the assessment. The composition of couples may be different at each of the six occasions.

In case of a resit for the exam, the final grade is computed as follows:

• the final exam (80%)
• practical assignments 1 and 2 (10% each)

The resit of the final exam also has a minimal requirement of 5.0 out of 10.

Inspection of assessed work

Contact the course coordinator to make an appointment for inspection.

Assignments

Practical assignments

• two programming assignments

The two larger practical assignments can be made in couples. Both students forming a couple get the same grade, which is a number between 1 and 10, rounded to halves. Feedback will be supplied 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 honors extension for this course.

Additional information

Students enrolling in this course should have a good grasp of Linear Algebra, going beyond performing mere matrix computations. In particular, geometrical insight into such manipulations is 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.

On recommendation of the Examinations Board, no minimal requirements on the practical assessments are imposed (in previous years, there was a minimal requirement). Furthermore, homework counts as a fixed percentage (15%) towards the final grade (in previous years it was a bonus on top of a sufficient mark for the exam).

Contact information

Coordinator

• dr. Jan Brandts