### Course Catalog 2010-2011 Basic

Basic Pori International Postgraduate Open University Search

|Degrees|     |Study blocks|     |Courses|

# MAT-51627 Matrix Algebra 2, 7 cr

Robert Piche

#### Requirements

Weekly assignments.
Completion parts must belong to the same implementation

-

#### 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