General information



This course focuses on algorithms to improve the performance and resource utilization of sparse linear solvers that solve systems of the form Ax = b, that appear in many numerical applications. The matrix A can be either dense or sparse, that is, mostly made of zero entries. Sparse matrices appear for instance when discretizing Partial Differential Equations (PDEs) on 2D and 3D finite element or finite volume meshes. A classical exemple is the modelization of the heat equation, where the continuous function is discretized into points. Each point corresponds to a row in the matrix A and non-zero entries of A correspond to interaction between close points, remote interactions being neglected. Graphs and other combinatorial objects are used to model matrices and computations with them. This course will present certain solvers and introduce methods from combinatorial optimization and scheduling domains that enable efficiency in those solvers.

Mesh after discretization
Sparse matrix
Original picture
Compression with storage reduced by 25
Compression with storage reduced by 5


Lecture notes



Part I: Graph algorithms

Part II: Scheduling under memory constraints

Part III: Low-rank compression for sparse direct solvers