Course Catalog 2010-2011
Postgraduate

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

Course Catalog 2010-2011

MAT-51627 Matrix Algebra 2, 7 cr

Person responsible

Robert Piche

Requirements

Weekly assignments.
Completion parts must belong to the same implementation

Principles and baselines related to teaching and learning

-

Learning outcomes

This course is an introduction to state-of-the-art linear algebra algorithms that are key components of nearly all modern engineering and scientific computations. The course focuses on high-level descriptions of algorithms (matrix factorisations), rigorous analysis of data and roundoff error, analysis of algorithm complexity in modern computer architectures, software libraries (LAPACK), and applications (partial differential equations, data compression, Google's PageRank, etc.). As a by-product of deriving algorithms and proving their properties, you'll also get a thorough workout in matrix algebra theory. Upon successful completion of the course, the student can derive matrix algorithms and can state and prove theorems that relate to numerical properties of these algorithms. He/she can list alternative algorithms for solving linear equations, least squares problems, and eigenvalue problems, and can compare them in terms of efficiency, accuracy, and reliability. He/she can code basic numerical linear algebra algorithms. He/she can use linear algebra software and can design and conduct numerical experiments to demonstrate theoretical properties of algorithms. A prerequisite for the course is a good knowledge of linear algebra (MAT-31090 or equivalent). Teaching is in English. Exam questions are in both Finnish and English, and may be answered in either language. The course is taught at most every second year.

Content

Content Core content Complementary knowledge Specialist knowledge
1. dense linear equations: permutation, LU, PLU, solving linear equation using LU, gaussian elimination with partial pivoting (GEPP), Cholesky decomposition, blocking algorithms for multilevel architectures  complete pivoting, matrix inversion, determinant, transpose equation, ATLAS   
2. perturbation analysis: forward stability, backward stability, condition number, sensitivity of linear equation, backward stability of GEPP, pivot growth factor, backward stability of Cholesky; a-posteriori bounds: relative residual, Hager's condition number estimator  stability of polynomial evaluation and polynomial roots, distance to nearest ill-posed problem, monotone norm, absolute norm, componentwise bounds   
3. least squares: condition, normal equations, Gram-Schmidt QR, Householder QR, SVD existence and properties, pseudoinverse; ill-conditioned problems  modified Gram-Schmidt, backward stability of Householder, regularisation  choice of regularisation parameter 
4. eigenvalues: Schur form existence, eigenvectors, perturbation, Gershgorin disks, power method, PageRank  real Schur form, Bauer-Fike theorem, Rayleigh ratio, PageRank's second eigenvalue   
5. sparse linear equations: finite difference method for Poisson equation on a rectangle (eigenvalues, Kronecker product, FFT method, Hockney's method), Jacobi relaxation and its convergence, Chebyshev acceleration, conjugate gradient method and its convergence; multigrid  Poisson equation in three dimensions, Gauss-Seidel, Krylov space, preconditioning  Chebyshev acceleration's convergence 

Evaluation criteria for the course

Written solutions of weekly assignments.

Assessment scale:

Numerical evaluation scale (1-5) will be used on the course

Partial passing:

Completion parts must belong to the same implementation

Study material

Type Name Author ISBN URL Edition, availability, ... Examination material Language
Book   Applied Numerical Linear Algebra   J. W. Demmel   0-89871-389-7     SIAM 1997      English  

Prerequisite relations (Requires logging in to POP)



Correspondence of content

Course Corresponds course  Description 
MAT-51627 Matrix Algebra 2, 7 cr MAT-51626 Matrix Algebra 2, 6 cr  

Additional information

Suitable for postgraduate studies
Will not be lectured year 2010-2011

Last modified24.02.2010