CR02: Combinatorial scientific computing

Semester: Fall 2019
Schedule: Tuesdays 13:30--15:30
Classroom: Salle B1
Instructors: Fanny Dufossé and Bora Uçar.
Note pad (for instructors): here.


Sparse matrix computations, mostly the solution of sparse linear systems of equations, are at the core of many scientific computing applications. Often, discrete mathematical algorithms and techniques, mostly from graph theory, are used to achieve efficiency in these kind of computations. In this course, we will explore the interplay between these two seemingly distant domains. The course is organized as follows: we take a sparse matrix computation, pose a practical question related to its performance (minimum memory requirements, running time, maximum parallel efficiency), and investigate the problem from combinatorial perspective. Whereas the sparse matrix computations side covers the basic notions, the combinatorial side of the course investigates, whenever doable, NP-completeness proofs, approximation algorithms, and exact algorithms.

Prerequisites: There is no specific background requirement for the course. The necessary material will be introduced throughout the semester. A little maturity in mathematical reasoning, working knowledge of basic linear algebra, and exposure to algorithm design can help understand the course contents (and many other things).

Evaluation: We will have a written exam or presentations of papers/projects.

Texts: We will not be following a particular text book. We will use course notes and research and survey articles throughout the semester.

Tentative outline

The starting date of each section is given in parenthesis.

  1. Sparse matrices and graphs (10 Sep 2019; notes)
  2. Structure prediction and fill-reducing ordering methods (17 Sep 2019; notes)
  3. Elimination tree for Cholesky (1 Oct, 2019; notes)
  4. BTF and matching (8 Oct, 2019; notes)
  5. Weighted matching (22 Oct, 2019; notes)
  6. Eigenvalues and combinatorial optimization (5 Nov, 2019; notes)
  7. Birkhoff--von Neumann decomposition and linear systems (Nov 12, 2019; notes)
  8. Denis Rochette and Julien Devevey talked about Laplacians and spectral partitioning (here).
  9. Hugues Depres and Etienne Vareille talked spectral methods (here).
  10. Remy Cerda talks about sparsity estimation.
  11. Krishna Acharya and Nacim Oijid talk about scaling.
  12. Florent Guepin and Felix Klingelhoefer talk about preconditioning with support trees and sparsification (slides).
  13. Lucas Perotin and Emmanuel Rodriguez talk about the minimum degree (slides).


Some similar courses