General information

Numerical Linear Algebra ENM-TMA265 and GU-MMA600 7.5 credit points
Last News
For homeworks and computer exercises, see section Programme
Obs! Participation at least 50% of lectures at this course is necessary!
All students should register for this course. For registration see antagning.se
• Answers to the questions at examination are here:
• Answers for examination at 25.10.2016
• Already is known that re-examination will be at 05.01.2017, 14:00-18:00, Maskinhuset.
• Here are some available topics for Master works:
• High Performance Scientific software for the solution of Helmholtz equation
• Parameter identification in mathematical model of HIV infection with drug therapy
• Optimization approach in the design of approximate cloaking structures
• I thank all of You who will answer to the following course evaluation survey (I assume that it is only for students at Chalmers, but GU students can fill out course evaluation from GU-page):
• Course evaluation survey
• This survey helps me get feedback from You and improve course for the next time. I will be very grateful if You can fill it.

Contents:

Problems of numerical linear algebra arise in many different fields of science like computational fluid dynamics, solid mechanics, electrical networks, signal analysis, and optimisation. In this course we study basic linear algebra concepts like matrix algebra, theory for linear systems of equations, spectral theory, and vector- and matrix norms as well as numerical aspects like efficiency, reliability, error analysis and condition numbers. We will study following topics:

• For solving linear systems of equations we will present Gaussian elimination with different pivoting strategies and blocking algorithms for higher performance using BLAS (basic linear algebra subroutines).
• For least-squares problems we study QR-factorisation and Singular Value Decomposition (SVD).
• The methods for solution of eigenvalue problems which are based on transformation techniques for symmetric and non-symmetric matrices.
• The basic iterative methods (Jacobi, Gauss-Seidel and Successive overrelaxation (SOR)) for solution of linear systems.
• Introduction to the Krylov subspace methods.
For all topics above we will discuss numerical algorithms with respect to applicability, reliability, accuracy, and efficiency. By implementing computer exercises in MATLAB and C++/PETSc the students will get experience in implementation and evaluation of numerical algorithms for problems of linear algebra.

By the completion of this course the students will be able to:

• use numerical linear algebra as building bricks in computation.
• make a linear algebra model of problems from the physical reality.
• derive and use the numerical techniques needed for a professional solution of a given linear algebra problem.
• use computer algorithms, programs and software packages to compute solutions to current problems.
• critically analyze and give advice regarding different choices of models, algorithms, and software with respect to efficiency and reliability.
• critically analyze the accuracy of the obtained numerical result and to present it in a visualized way.
The course consists of 36 lecture hours, 20 exercise hours and gives 7.5 points. The course code for engineering schools and students registered at Chalmers is TMA265. The course code for students registered in GU is MMA600.
Latest news
All current and recent information will be placed here. Regarding examination : CTH students should not register for this exam. Only GU students can register for the examination. CTH and GU students will get their personal exam numbers from Observers of this exam. Examination usually is at Maskinhuset at Chalmers:
• Where exactly (in which one room) will be exam You will know at the day of examination: the announcement will be placed at the blackboard close to the entree of Maskinhuset. Notes: GU students can do re-examination but they can not high their scores (for example, from G to VG) but Chalmers students can do re-examination and high scores. Please, follow this site to get exact information when and where will be re-examonation closer to the day of re-examination.
The schedule for the course can be found via the link to webTimeEdit top of the page.
Schedule

Day Time Place Remarks Office Hours
MON 13:15-15:00 MVF33 Lecture
WED 13:15-15:00 MVF24 Computer exercises
THU 10:00-11:45 MVL14 Lecture
FRI 13:15-15:00 MVF24 Computer exercises
Link to the system ping pong:
• Ping Pong
• Teachers
Course coordinator: Larisa Beilina, larisa@chalmers.se, room 2089, homepage

Course literature
1. Demmel, Applied Numerical Linear Algebra, SIAM 1997, selled at Cremona. List of Errata for the Textbook
2. L. Beilina, E. Karchevskii, M. Karchevskii, Numerical Linear Algebra: Theory and Applications.
3. PETSc libraries which are a suite of data structures and routines for the scalable (parallel) solution of scientific applications; user manual
Programme
• Homeworks and computer exercises
• Homeworks
• Deadlines for homeworks and comp.ex.:
• Homework 1 and comp. ex. 1: 16 September
• Homework 2: 23 September
• Homework 3 and comp.ex. 2: 7 October
• Homework 4 and comp.ex. 3: 14 October Comp.ex. 4-8: 21 October
• Computer Exercises
• Lecture 1
• Introduction to the course. Read chapter 1 in the textbook yourselves. Introduction to linear algebra and numerical linear algebra. If this looks unfamiliar you should better consult you former literature in linear algebra and refresh your knowledges. We will concentrate on the three building bricks in Numerical Linear Algebra (NLA) : (1) Linear Systems, (2) Overdetermined systems by least squares, and (3) Eigenproblems. The building bricks serve as subproblems also in nonlinear computations by the idea of linearization. We considered example of application of linear systems: solution of nonlinear equation by reduction to the solution of linear system, image compression using SVD, image deblurring. We introduced some basic concepts and notations: transpose, lower and upper triangular matrices, singular matrices, symmetric and positive definite matrix, conjugate transpose matrix, row echelon form, rank, cofactor, invertible matrix.
• Lecture 1
• Lecture 2
• We will continue with the introduction: eigenvalues and eigenvectors, characteristic equation, spectral radius, diagonalization, orthoganality. We will discuss why we need norms: (1) to measure errors, (2) to measure stability, (3) for convergence criteria of iterative methods. We will discuss computer exercise 1 and perturbation theory in polynomial evaluation.
• Lecture 3
• System of linear equations. Gaussian elimination, LU-factorization. Gaussian elimination (and LU factorization) by outer products (elementary transformations). Pivoting, partial and total.
• Lecture 4
• We will discuss the need of pivoting and uniqueness of factorization of A. Different versions of algorithms of Gaussian elimination. Example: how to solve Poisson's equation on a unit square using LU factorization. Complexity of the LU factorization. Error bounds for the solution Ax=b. Roundoff error analysis in LU factorization. Estimating condition numbers. Hagers's algorithm.
• Lecture 5
• Componentwise error estimates. Improving the Accuracy of a Solution for Ax=b: Newton's method and equilibration technique. Convergence of the Newton's method. Real Symmetric Positive Definite Matrices. Cholesky algorithm. Band Matrices, example: application of Cholesky decomposition in the solution of ODE.
• Lecture 6
• Continuation of considering example: application of Cholesky decomposition in the solution of ODE. Linear least squares problems. Introduction and applications. The normal equations. Example: Polynomial fitting to curve. Solution of nonlinear least squares problems: examples.
• Lecture 7
• QR and Singular value decomposition (SVD). SVD and the fundamental subspaces. SVD for linear least squares problems. Numerical rank, truncated SVD, condition number, best approximation of a matrix, truncated pseudoinverse, truncated least squares.
• Lecture 8
• Householder transformations and Givens rotations. QR-factorization by Householder transformation and Givens rotation. Examples of performing Householder transformation for QR decomposition and tridiagonalization of matrix. Moore-Penrose pseudoinverse. Rank-Deficient Least Squares Problems.
• Lecture 9
• At the beginning I gave examples of QR-factorization by Given's rotation. Introduction to spectral theory, eigenvalues, right and left eigenvectors. Similar matrices. Defective eigenvalues. Canonical forms: Jordan form and Schur form, real Schur form. Gerschgorin's theorem. Perturbation theory, Bauer-Fike theorem.
• Lecture 10
• Discussed algorithms for the non-symmetric eigenproblems: power method, inverse iteration, inverse iteration with shift, orthogonal iteration, QR iteration and QR-iteration with shift. Hessenberg matrices, preservation of Hessenberg form. Hessenberg reduction. Tridiagonal and bidiagonal reduction.
• Lecture 11
• The basic iterative methods (Jacobi, Gauss-Seidel and Successive overrelaxation (SOR)) for solution of linear systems. Jacobi, Gauss-Seidel and SOR for the solution of the Poisson's equation in two dimension. Study of Convergence of Jacobi, Gauss-Seidel and SOR. Introduction to the Krylov subspace methods. Arnoldi, Lanczos algorithms. Conjugate gradient algorithm. Preconditioning for Linear Systems. Preconditioned conjugate gradient algorithm. Common preconditioners.
• Lecture 12
• Regular Matrix Pencils and Weierstrass Canonical Form. Singular Matrix Pencils and the Kronecker Canonical Form. Application of Jordan and Weierstrass Forms to Differential Equations. Symmetric eigenproblems Perturbation theory: Weyl's theorem. Corollary regarding similar result for singular values. Application of Weyl's theorem: Error bounds for eigenvalues computed by a stable method. Courant-Fischer (CF) theorem. Inertia, Sylvester's inertia theorem. Definite Pencils. We discussed the solution of comp.ex.3.
• Lecture 13
• Theorem that the Rayleigh quotient is a good approximation to an eigenvalue. Algorithms for the Symmetric eigenproblem: Tridiagonal QR iteration, Rayleigh quitient iteration, Divide-and-conquer algorithm. QR iteration with Wilkinson's shift. Divide-and-conquer, bisection and inverse iteration.
• Lecture 14
• Algorithms for symmetric matrices (continuation): bisection and inverse iteration algorithms, different versions of Jacobi's method. Algorithms for the SVD: QR iteration and Its Variations for the Bidiagonal SVD, LR iteration, divide-and-conquer, bisection and inverse iteration, Jacobi's method for the SVD, one-sided Jacobi. Example of construction of a lower triangular matrix using Given's rotation.
Computer labs
Wednesdays 13-15 (except the first week) in computer room MVF24 (Mathematical Sciences in Physics building).
Fridays 13-15 in computer room MVF24 (exept the first week).
Computer labs and Matlab/PETSc excercises will be included in the assignments below. Matlab programs which will be used in computer exercises:
• Poisson2D_LU.m
• DiscretePoisson2D.m
• BackSub.m
• ForwSub.m
• LU_factor.m
• Templates for programs written in PETSc:
• Template for computing of discretized Laplacian
• Template for the main program in PETSC for LU decomposition
• Example of Makefile to be able compile PETSc program at Chalmers
• Template for petsc function which removes zeros from the original matrix. We can work then with resulting matrix without zeros in the same way as with original matrix.

• Additional templates of PETSc-Makefile and main program in PETSc:
• Example of the main program in PETSC.
• Example of the Makefile to compile the above main program like that: make hello

• Reference literature:
• Tobin A. Driscoll, Learning MATLAB, ISBN: 978-0-898716-83-2 (The book is published by SIAM)
Course outline and requirements
The following sections in the textbook will be considered in the book.
Chapter 1
mainly repetition and brief revision on basic linear algebra.
Chapter 2
1-6, 7 except 2.7.4 and 2.7.5
Chapter 3
1-5
Chapter 4
1-4
Chapter 5
1-4
Chapter 6
1-6, except 6.3.3, 6.5.6, 6.6.4,6.6.6
The following questions in the textbook are recommended:
• Chapter 1: 1, 2, 3, 4, 5, 7, 13.
• Chapter 2: 3, 6, 7, 10, 11, 12, 17, 19.
• Chapter 3: 1, 2, 3(parts 1,2,3), 4, 5, 6, 8, 9, 11, 14, 15, 18.
• Chapter 4: 1, 3, 4, 5, 6, 7, 10, 11, 12, 13.
• Chapter 5: 1, 3 (for symmetric matrix), 6, 7, 14, 15, 16, 17, 18, 22, 27, 28.
To each chapter belong an optional homework assignment and a computer exercise. The homework assignments are similar to the questions in the textbook and such you could expect at the examination. In the computer exercises you will be trained in using different algorithms in numerical linear algebra using MATLAB or PETSc libraries. Either you will use already existing MATLAB and PETSC programs or write your own small MATLAB or PETSc codes. The homework assignments give bonus credit points for the examination. Since the occasions reserved for the computer exercises are without supervision you may put questions on these exercises to me at the lectures. Passed computer exercises will be graded with grades 3, 4, or 5, see examination below.
Assignments

You may work in a group of 2 persons but hand in only one report for the group.

Wednesdays 13-15 (except the first week) in computer room MVF24 (Mathematical Sciences at Physics building) Fridays 13-15 in computer room MVF24 (exept the first week when it is in room MVF25). Hand in a short report of your work before the final exam.

Examination
• To pass this course you should pass the written exam and 2 computer assignments, see description of comp. assignments above.
• The two compulsory home assignments should be handed in before the final exam.

Written examination
• Final exam is compulsory, written.
• The theory questions will be choosen from the following list
• List of questions
• You should be able to state and explain all definitions and theorems given in the course and also apply them in problem solving.
• Grades are set according to the table below.
- <15 -
3 15-20 G 15-27
4 21-27 VG >27
5 >27
Bring ID and receipt for your student union fee (this is requirement only for Chalmers students. GU students can come on the exam without receipt).

Solutions to the exam will be published at the following link (will be added). You will be notified the result of your exam by email from LADOK (This is done automatically as soon as the exams have been marked an the results are registered.)
The exams will then be kept at the students office in the Mathematical Sciences building.
Check that the number of points and your grade given on the exam and registered in LADOK coincide.
Complaints of the marking should be written and handed in at the office. There is a form you can use, ask the person in the office.).

The following link will tell you all about the examination room rules at Chalmers: Examination room instructions

Examination procedures
In Chalmers Student Portal you can read about when exams are given and what rules apply on exams at Chalmers.
At the link Schedule you can find when exams are given for courses at University of Gothenburg.
At the exam, you should be able to show valid identification.
Before the exam, it is important that you report that you want to take the examination. If you study at Chalmers, you will do this by the Chalmers Student Portal, and if you study at University of Gothenburg, so sign up via GU's Student Portal.

You can see your results in Ladok by logging on to the Student portal.

At the annual examination:
When it is practical a separate review is arranged. The date of the review will be announced here on the course website. Anyone who can not participate in the review may thereafter retrieve and review their exam on Mathematical sciences study expedition, Monday through Friday, from 9:00 to 13:00. Check that you have the right grades and score. Any complaints about the marking must be submitted in writing at the office, where there is a form to fill out.

At re-examination:
Exams are reviewed and picked up at the Mathematical sciences study expedition, Monday through Friday, from 9:00 to 13:00. Any complaints about the marking must be submitted in writing at the office, where there is a form to fill out.
Old exams
Old exams with answers are given here:
• Old exams