Nada bild

2D1253, Numerisk algebra, metoder för stora matriser, 4 poäng

Aktuell kursomgång: period 2 05/06

Kursledare: Axel Ruhe
Datorpostadress: ruhe@nada.kth.se

Studiehandbokstexten på svenska och engelska.

Staff

Axel Ruhe, lectures and course leader, room D4527

Report individual assignments scheduled:

Assignments listed on bottom of course homepage.

Sign up for time with me! Tell me if you will need a computer projector!

Times available:

First day, Friday January 13 2006 in room D1537 (same floor as my office, western block)
14:15
 Dag Lindbo
 Multigrid for linear systems
14:30
 Oana Marin
 Regularization in image processing
14:45

Time
 Names
 Subject

Second day, Monday January 16 2006 in room D1625 (one floor higher, western block)
Time
 Names
 Subject
13:15

13:30
 Hilda Sundström
 Compare lanso and eigs
13:45
 Kenneth Duru, Emmanuel Doro
 Pseudospectra
14:15
 Zhu Xueyu, Mikael Stöckli
 Laplace matrix for graph partitioning
14:30
 Huang Xuejun
 Regularization for image processing
14:45


Third day, Wednesday February 1 in room D4523,
Time Names Subject
13:15
 Gaël Dubus, Mathieu Scotto Fields of values and closest normal matrix
13:40
 Katharina Wagner, Anne Lebhardt Information retrieval with SVD

Schedule of lectures

We will discuss some of the material in the lectures but the main work in the course will be to study the literature and perform assignments. Here is a list of the different subjects and days for meetings. Different from previously announced in KTH schedule!


 Meeting
 Text
 Contents
1
 Tuesday Oct 25, 13:15-15 in D4523
 D 2.2, 2.2.1
 Linear Systems: Perturbations, relative perturbations
2
D 2.4.2, 2.4.3
 Rounding errors in Gaussian elimination, Condition estimation
3
 Wednesday Nov 2, 10:15-12 in D4523
 D 6.6.1
L4.2.1
 Krylov subspaces: Arnoldi algorithm, eigenvalues and linear systems
4
D 7.2, D 5.2 L4.2.2
E 4.4
 Symmetric matrices: Lanczos algorithm, Ritz approximations, perturbation theory, Courant Fischer minimax
5
 Wednesday, Nov 9, 13:15-15 in D4523
 D 7.3-4
E 4.4.2-4
 Lanczos algorithm: Convergence and orthogonality
6
D 6.6.2-3
L 5.1-2
 Krylov subspaces, linear systems: Conjugate gradient algorithm
7
 Monday Nov 14, 10:15-12 in D4523
 D 6.6.4-5
L 5.3
 CG: convergence and preconditioning
8
D 6.6.6
 Linear systems: Further developments, GMRES, QMR
9
 Wednesday Nov 23, 13:15-15 in D4523
 E4.4.3,
E 4.5
 Eigenvalues: Spectral transformation, implicit restart
10

Computing the SVD: Bidiagonalization, bidiagonal SVD
11
 Wednesday Nov 30, 13:15-15 in D4523
 D 5.3.3
 Large tridiagonal matrices: Divide and Conquer, Relative Robust Representation
12
 Wednesday, Dec 7, 13:15-15 in D4523
Large SVD: Hubs and authorities on the web
The largest matrix eigenvalue problem: The Google matrix
13



Under the heading Text, I give some sections in
The texts are not covering all I intend to discuss, there is more to find in the text book than I will have time to cover.

Material distributed in class

Reading instructions and review questions: Rev2Q.pdf

Examination

The examination will have two parts,
  1. a take home exam with a set of review questions: Exam_2005.html
  2. programming assignment, done in groups, different tasks chosen by the groups. 

Special assignment 

Take one of the tasks given below! They are not given in any systematic order, so look at them all before you decide. You may also work on a project of your own designation, in that case talk to me, and we can find out what is an appropriate formulation.
Send me an email!If any group will take up a task that is already chosen, write to me and we may discuss it.

You may work in groups of two or individually.  I will help you with copies of some of the papers necessary.  You may work at any time.
Write up a short report readable for the other participants in the course. Describe what is done in simple enough terms, and tell about the experiments you have done, if any.
Your work is to be presented orally in front of the group at an appropriate time towards the end of the course. Tentative dates: December 19, 13:15-15,  January 16, 13:15-15.

Pointers to material needed for the projects given below. Use also the homepage referred to in the Demmel book, I did find it at
http://www.cs.berkeley.edu/~demmel/ma221/Matlab/

Nr
 Task and comments
 People
1
 Recursive BLAS for fastest parallel linear systems
2
 Preconditioned iterations for large linear systems
3
 Multigrid for linear systems Demmel Q 6.16
 Dag Lindbo
4
 Regularization for image processing, the L-curve Look at works of Per Christian Hansen, Copenhagen, especially his Matlab toolbox regtools and its use for smooth regression by Michael Wendland.
 Oana Marin, Huang Xuejun
5
 Information retrieval with SVD Study Latent semantic indexing LSI, and the Krylov space variant developed with Katarina Blom. Matlab routines are available.
 Katharina Wagner, Anne Lebhardt
6
 Sensitivity of eigenvalues, pseudospectrum The pseudospectrum is used by L N Trefethen, and people in France under the name spectral portraits. Do Demmel Q 4.14 eigscat.m
 Kenneth Duru, Emmanuel Doro
7
 Compare lanso and eigs Lanczos with selective orthogonalization, lanso, and implicit restart Arnoldi, eigs. Etemplates 4.4.4.
 Hilda Sundström
8
 Lanczos with Cullum's device Etemplates 4.4.4
9
 Jacobi Davidson for eigenvalues Etemplates 4.7.
10
 Jacobi is better than QR, high relative precision Demmel 5.3.5 and 5.4.3. Read original article J. Demmel and K. Veselic, Jacobi’s method is more accurate than QR, SIAM J.
Matrix Anal. Appl., 13 (1992), pp. 1204–1245
11
 Fields of values and closest normal matrix Read my article 
Axel Ruhe. Closest normal matrix finally found!
BIT, 27:585-598, 1987.
Test Matlab implementation by Higham in The Matrix Computation Toolbox

Gaël Dubus, Mathieu Scotto
12
 Simultaneous diagonalization of several matrices
 Askar Beishenaliev
13
 Laplace matrix for graph partitioning Alex Pothen uses the second eigenvector of the Laplace matrix of a graph for partitioning. A. Pothen, H. D. Simon, and K.-P. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl., 11:430--452, 1990 Study works by Karypis
 Zhu Xueyu, Michael Stöckli
14
 Geometry and eigenvalues Demmel Q 4.16.
 M'hamed Begdadi


^ Upp till Nadas kurser.

Sidansvarig: <ruhe@nada.kth.se>
Senast ändrad 2 january 2006
Tekniskt stöd: <webmaster@nada.kth.se>