Combinatorial scientific computing
Calcul scientifique combinatoire

Semester: Fall 2018
Schedule: Mondays 13:30--15:30
Classroom: B1
Instructors: Fanny Dufossé and Bora Uçar.


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 2018; notes)
  2. Structure prediction and fill-reducing ordering methods (17 Sep 2018; notes)
  3. Elimination tree for Cholesky (24 Sep 2018; notes)
  4. Pivoting and bipartite matching, btf, and cardinality matching, weighted matching (1 Oct 2018; notes, notes)
  5. Parallel sparse matrix vector multiplication (a.k.a. graph/hypergraph partitioning) (Oct 15, notes)
  6. Eigenvalues and combinatorial optimization (Oct 22, notes)
  7. Birkhoff--von Neumann decomposition and linear systems (Nov 5)
  8. Combinatorial solvers (started Nov 5)


Some similar courses

Last updated: Nov 07, 2018