Large sparse linear systems

In this class, we focus on the solution of linear systems arising from the discretization of partial differential equations. Those systems of equations are typically very large, i.e. millions of unknowns, and sparse, i.e. most of the entries in the matrix are NULL. With this knowledge it is possible to design efficient data-structures and algrotihms to perform operations on matrices and vectors, like a matrix-vector product.

For very large systems, decomposition/parallelization strategies must be developed. We want to discuss solution strategies involving the structure of the problem, e.g. that the equations arise from discretization on a computational grid. Partitioning and distributing the grid will allow us to reduce the size of the (local) linear systems and thus to handle it on a single core. Aspects of parallelization of the algorithms will be discussed and some methods developed especially for system from partitioned domain discretization.

Room and Time

Topics

• Simple iterative methods (Jacobi, Gauss-Seidel, SOR)
• Krylov-Subspace methods (CG, GMRES)
• Multigrid methods
• Domain decomposition

Bibliography

• Iterative Methods for Sparse Linear Systems, Second Edition, 2003 (Yousef Saad)
• Parallele numerische Verfahren, 2002 (Alefeld, Lenhardt, Obermaier)