Examiner and Lecturer: Ivar Gustafsson

- See you at the course start on Wednesday January 19, time 13.15 in room MVF32 at Mathematical Sciences - Physics building.

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 (inlämningsuppgifter) and experimental assignments (laborationer), the students get experiences in implementation and evaluation of different algorithms for sparse problems.

For some learning outcomes of this course, see outcomes.

- James W. Demmel: Applied Numerical Linear Algebra, SIAM 1997, selled at Cremona.

List of Errata for the Textbook - Lecture notes on direct methods for large and sparse linear systems.

The homework assignments give bonus credit points for the examination, totally at most five times one points.

Passed computer exercises will be graded with grades 3, 4 or 5, based on quantity and/or quality.

Wednesdays 13-15 in MVF32.

Chapter 6, sections 1 - 6, 9.

Chapter 7: sections 1 - 4

The following questions in the textbook are recommended:

Chapter 6: 1, 2, 3, 4, 11, 12, 13, 14, 15

Chapter 7: 1, 2, 3

Some additional questions will be given along the lectures.

Large, sparse problems in applications

Outline of the course, problems and methods.

Available software on the web.

The model test problem: Poisson's equation in one and two dimensions.

Discussion on HA1 and CE1.

Basic iterative methods, Jacobi´s and Gauss-Seidel methods.

The spectral radius and convergence,

Lemma 6.4, Lemma 6.5, and Thm 6.1.

Rate of convergence

Good properties of basic iterative methods

Ordering of unknowns, red-black ordering

Irreducibility, strongly connected graph

Convergence criterion for Jacobi's and Gauss-Seidel methods, Thm 6.3.

Symmetrizable iterative methods

Convergence rate of SOR, property(A), consistently ordering

Important convergence results: Thm 6.6 and Thm 6.7

Convergence acceleration, section 6.5.6.

Semi-iterative methods, polynomial acceleration

Chebyshev polynomials for minimizing the spectral radius.

Krylov methods

Arnoldi's and Lanczos methods.

Solving Ax=b with Krylov methods.

Several "best" approximations.

The Conjugate Gradient method.

Choice of search directions and steplength.

The rate of convergence of the CG method.

Preconditioning.

Incomplete and modified incomplete Cholesky factorizations.

Discussion on HA2 and CE2.

Solution (smoothing), restriction and interpolation operators

Multigrid v-cycle, full multigrid.

Computational complexity for multigrid.

Multigrid for the 1D poisson problem

SECOND PART OF THE COURSE: Direct methods for large, sparse matrices, lecture notes.

Data structures for sparse matrices.

Compressed row and compressed diagonal storage.

Bandmatrices, No fill-in within the band in non-pivoting Gaussian elimination.

General sparse matrices, envelope, no fill-in within the envelope in non-pivoting Gaussian elimination.

Dynamic and static sparse structures, cholinc resp. (m)ic(d).

Orderings for sparsity, for minimizing fill-in

Graph theory for ordering

Reverse Cuthill-McKee ordering

Elimination graphs

Markowitz algorithm

Nested dissection orderings

Dicussion on CE3

MATLAB tools for sparse orderings and graphs.

Discussion on and MATLAB-tools for HA4 and CE4

Numerical methods for large sparse least-squares problems, a survey (not to be examined).

THIRD PART OF THE COURSE: Methods for large sparse eigenproblems, chapter 7 in the text book.

Introduction, the power method, invers iteration with shift.

Relation to the Krylov space, Ritz vectors and Ritz values.

Krylov methods for symmetric eigenproblems.

Lanczos-Raylegh-Ritz method for symmetric problems.

Theorem 7.1 with proof

Theorem 7.2 with proof

- The statement in Ex 6.9

- Exercise 5 in lecture notes on solving systems with iterative methods

- An extra exercise on generalized eigenproblems and different orderings

Solution of Question 7.2

Solution of Question 7.3

Discussion on Question 7.3 related to CE5.

The Lanczos method in exact arithmetic.

The Lanczos method in floating point arithmetic

Reorthogonalization, Selective reorthogonalizationi, Thm 7.3 (without proof).

Discussion om HA5 and CE5.

Poisson's equation, five-point-matrix, Kronecker product.

Basic iterative methods:

Fixpointiteration, splitting, Jacobi's method, Gauss-Seidel's method, SOR method.

Iteration matrix, norm and spectral radius.

Irrecucibility, diagonal dominans.

Convergence rate, condition number.

Consistently ordering, property(A)i, red-black ordering.

Converegence acceleration.

Krylov techniques:

Krylov space.

Lanczos and Arnoldi methods, Conjugate Gradient techniques.

Preconditioning, incomplete factorization.

Multigrid method:

V-cycle, full multigrid.

Multigrid for Poisson's problem in 1D, idea of convergence rate.

Bandmatrices.

Envelope minimization

fill-in minimization.

Sparse storage techniques.

Ordering methods for sparsity: RCM, minimum degree

Nested dissection for 2D Poisson's problem

Graph theory, elimination graphs.

Symbolic and numerical factorization.

Dynamic and static sparse structures.

Lanczos-Rayleigh-Ritz method.

Lanczos method in exact arithmetic, reorthogonalization, misconvergence.

Lanczos method in floating point arithmetic, reothogonalization.

selective reorthogonalization.

- Homework Assignment and Computer Exercise 1. Deadline January 31.

A p-code MATLAB program for red-black to be used for checking your reordering: red_black.p - Homework Assignment and Computer Exercise 2. Deadline February 14.

A number of programs to your disposal:delsq3d.m, ic0_2d.m, mic0_2d , ic2_2d.m, mic2_2d.m,

ic0_3d.m, mic0_3d.m , ic3_3d.m, mic3_3d.m. - Homework Assignment and Computer Exercise 3. Deadline February 23.

Programs to your disposal: makemgdemo.m, testfmgv.m , fmgv.m , mgv.m , mgvrhs.m .

- Homework Assignment and Computer Exercise 4. Deadline March 7.

- Homework Assignment and Computer Exercise 5. Deadline March 18.

Means of assistance at the examination: none.

The total number of points in the written examination is 25 plus possibly 5 bonus points. The number of attained points on the written examination and the computer exercises are added and the final grade for the course is based on this sum.

Preliminary grades CTH: 28p for grade 3, 35p for grade 4 and 42p for grade 5.

Preliminary grades GU: 28p for grade G and 38p for grade VG.

Wednesday March 16, 13-14.30 in my office.

Thursday March 17, 9-13 Room MVF32.

Please find the examination.