|
|
|||||||||||||||||
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:
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 |
|
|
|
Additional information
Suitable for postgraduate studies
Will not be lectured year 2010-2011