Large and sparse matrix problems arise for instance in numerical approximation of differential equations, network problems and optimisation. In this course we study numerical techniques for solution of systems of linear equations and eigenvalue problems with this type of matrices. For systems of linear equations we present two classes of methods: iterative and direct. Among the iterative methods we study basic stationary methods like Jacobi and SOR methods, orthogonalising methods like conjugate gradients and multigrid methods. The direct methods are based on Gaussian elimination with different renumberings of the unknowns in order to keep computing time and memory requirement small. The eigenvalue routines presented are based on Lanczos and Arnoldi algorithms with or without spectral transformations. When solving the homework assignments and computer labs, the students get experience in implementation and evaluation of different algorithms for sparse problems. We will also study how to use toolkit for scientific computations PETSc for the solution of sparse linear systems of equations using different preconditioners.
- Demmel, Applied Numerical Linear Algebra, SIAM 1997, selled at Cremona. List of Errata for the Textbook
- PETSc libraries which are a suite of data structures and routines for the scalable (parallel) solution of scientific applications; user manual
- Homeworks and computer exercises (will put later)
- Lecture 1 Introduction and outline to the course. Available software on the web. introduction to PETSc. Large, sparse problems in applications. The model test problem: Poisson's equation in one and two dimensions.
- Lecture 2 Iterative methods for systems of linear equations. Basic iterative methods, Jacobi´s and Gauss-Seidel methods. The spectral radius and convergence. Rate of convergence. Good properties of basic iterative methods. Ordering of unknowns, red-black ordering.
- Lecture 3 Irreducibility, strongly connected graph. Convergence criterion for Jacobi's and Gauss-Seidel methods. SOR, successive overrelaxation method. Symmetrizable iterative methods (not in the book). The symmetric SOR method, the SSOR method. Convergence rate of SOR, property(A), consistently ordering Important convergence results. Optimal choice of SOR-parameter.
- Lecture 4 Convergence acceleration, section 6.5.6. Semi-iterative methods, polynomial acceleration Chebyshev polynomials for minimizing the spectral radius. Stopping criteria Krylov methods.
- Lecture 5 Krylov methods (cont.) Arnoldi's and Lanczos methods. Solving Ax=b with Krylov methods. Several "best" approximations. The Conjugate Gradient method. Gradient methods as search methods. Discussion on Gauss-Seidel and SOR from an optimization point of view. Choice of search directions and steplength.
- Lecture 6 The rate of convergence of the CG method. Preconditioning. Incomplete Cholesky factorizations. Modified incomplete Cholesky factorization. I got a question on general MIC, how to make more and more accurate incomplete factorizations. A short introduction to multigrid, section 6.9.
- Lecture 7 Multigrid methods (cont.) Solution (smoothing), restriction and interpolation operators Multigrid v-cycle, full multigrid. Computational complexity for multigrid. Multigrid for the 1D poisson problem Convergence rate of multigrid for the 1D Poisson problem.
- Lecture 8 Direct methods for large, sparse matrices. Data structures for sparse matrices. Compressed row and compressed diagonal storage. Bandmatrices, Theorem 1: No fill-in outside the band in non-pivoting Gaussian elimination. General sparse matrices, envelope, Theorem 2: no fill-in outside the envelope in non-pivoting Gaussian elimination.
- Lecture 9 Methods for large sparse eigenproblems, chapter 7 in the text book. Introduction, the power method, inverse iteration with shift. Relation to the Krylov space, Ritz vectors and Ritz values. Krylov methods for eigenproblems. Arnoldis's method for nonsymmetric and Lanczos method for symmetric eigenproblems. Rayleigh-Ritz method.
- Lecture 10 Theorem 7.1 with proof Lanczos-Raylegh-Ritz method for symmetric problems. Theorem 7.2 with proof.
- Lecture 11 The Lanczos method in exact arithmetic. Misconvergence: (i) small component of q_1 in the direction of an eigenvector. (ii) almost multiple eigenvalues. The Lanczos method in floating point arithmetic: + can compute behind the theoretical break-down. - loss of orthogonality. Reorthogonalization, Selective reorthogonalization, Thm 7.3 (without proof).
- Lecture 12 Domain decomposition methods: nonoverlapping and overlapping methods.
- Lecture 13 Domain decomposition methods for the solution of PDE. Absorbing boundary conditions.
- Lecture 14 Fast Fourier Transform (FFT). The discrete Fourier transform. Computing the FFT.
Fridays 13-15 in computer room MVF24 (exept the first week).
Computer labs and Matlab/PETSc excercises will be included in the assignments below. Templates for computer ex. 2:
Additional templates of PETSc-Makefile and main program in PETSc:
Reference literature:
- Tobin A. Driscoll, Learning MATLAB, ISBN: 978-0-898716-83-2 (The book is published by SIAM)
- Chapter 6, sections 1-6, 9
- mainly repetition and brief revision on basic linear algebra.
- Chapter 7, sections 1 - 4 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 and computer labs 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.
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).
- 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.
- 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.
- Maskinhuset
Grades Chalmers
Points
Grades GU
Points
-
<15
-
3
15-20
G
15-27
4
21-27
VG
>27
5
>27
The first exam will place at 14 March, 8.30-12.30, Maskinhuset at Chalmers:
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).
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
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 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.