Numerical Algebra, Methods for Large Matrices, matalg08

Staff

Axel Ruhe, lectures and course leader, room 1519

News:

Reports of special assignments

The reports are now scheduled, all in room D4523:

Time	Group	Subject	Speaker
Dec 17 2008, 11:00	4	Multigrid	Catherine Herold, Melanie Rochoux
11:30	10	Jacobi Davidson for eigenvalues	Yuan Changming
13:15
13:45
Jan 14 2009, 11:00	11	Character recognition with SVD	Jakub Olczak, Marwa Mohamed Mohamed Abdul Monem
11:30	7	Pseudospectrum, sensitivity	Juha Korkiakangas
13:15	3	Nonsymmetric iterations	Maria Nordström
13:45	5	Regularization for image processing, the L-curve	Chen Nan, Yuanjun Zhang
14:15	9	Page rank and the Google matrix	Fatih Ertinaz, Mustafa Kavasoglu
14:45	12	Geometry and eigenvalues	Mattias Frånberg, Peter Andersson

Schedule

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.

	Meeting	Text	Contents
F1	Monday Oct 27, 13:15-15 in 4523	D 2.2, 2.2.1	Linear Systems: Perturbations, relative perturbations
		D 2.4.2, 2.4.3	Rounding errors in Gaussian elimination, Condition estimation
F2	Wednesday Nov 5, 13:15-15 in 1537	D 6.6.1 L4.2.1	Krylov subspaces: Arnoldi algorithm, eigenvalues and linear systems
		D 7.2, D 5.2 L4.2.2 E 4.4	Symmetric matrices: Lanczos algorithm, Ritz approximations, perturbation theory, Courant Fischer minimax
F3	Wednesday, Nov 12, 13:15-15 in 1537	D 7.3-4 E 4.4.2-4	Lanczos algorithm: Convergence and orthogonality
		D 6.6.2-3 L 5.1-2	Krylov subspaces, linear systems: Conjugate gradient algorithm
F4	Wednesday Nov 19, 13:15-15 in 4523	D 6.6.4-5 L 5.3	CG: convergence and preconditioning
		D 6.6.6	Linear systems: Further developments, GMRES, QMR
F5	Wednesday Nov 26, 13:15-15 in 4523	E4.4.3, E 4.5	Eigenvalues: Spectral transformation, implicit restart
			Computing the SVD: Bidiagonalization, bidiagonal SVD
F6	Wednesday Dec 3, 13:15-15 in 4523	D 5.3.3	Large tridiagonal matrices: Divide and Conquer, Relative Robust Representation
			Large SVD: Hubs and authorities on the web The largest matrix eigenvalue problem: The Google matrix

Under the heading Text, I give some sections in

• D - the text book: James W. Demmel, Applied Numerical Linear Algebra, SIAM 1997, Order code OT56, homepage
  
  
• E - the Eigentemplate book: Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM 2000, Order code SE11, homepage
• L - the Lecture Notes: Axel Ruhe, Topics in Numerical Linear Algebra, used previously in course DN2252.

The texts are not covering all I intend to discuss. There is more to find in the text books than I will have time to cover. You are advised to have the Demmel book available. I will distribute relevant sections of Eigentemplates at the lectures.

Material distributed in class

Reading instructions and review questions, 2008 edition here:  Rev2Q.pdf

Examination

The examination will have two parts,

1. a take home exam with a set of review questions. Current  exam: Exam2008.html
   
2. Special assignment, done in groups, different tasks chosen by the groups: DN2253 Special assignment.html 

Special assignment 

I will distribute a set of different tasks later in the course. 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.

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.