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.

Description

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.

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

References

Books:

A combinatorial approach to matrix theory and its applications, by R. A. Brualdi and D. M. Cvetković.
Introduction to algorithms, by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.
Direct methods for sparse linear systems, by T. A. Davis.
Applied Numerical Linear Algebra, by James W. Demmel. SIAM, 1997.
Numerical Linear Algebra, by Lloyd N. Trefethen and David Bau, III. SIAM 1997.
Direct methods for sparse matrices, by I. S. Duff, A. M. Erisman, and J. K. Reid.
Matrix computations, by G. H. Golub and C. Van Loan.
Algorithmic graph theory and perfect graphs, M. C. Golumbic.
Iterative methods for sparse linear systems, by Y. Saad.

Articles on first four courses (Sparse matrices; structure prediction, fill-in, ordering; elimination tree; max cardinality matching):

A blog post about fill-in.
Predicting structure in sparse matrix computations, J. R. Gilbert, SIAM Journal on Matrix Analysis and Applications, 15 (1994), pp. 62--79 (doi). (Paper's title says all.)
Sparse partial pivoting in time proportional to arithmetic operations, J. R. Gilbert and T Peierls, SIAM Journal on Scientific and Statistical Computing, 9 (1988), pp. 862--874 (doi) (Sparse triangular system solution for sparse right hand side vectors).
Algorithmic aspects of vertex elimination on graphs, D. J. Rose, R. E. Tarjan, and G. S. Lueker, SIAM Journal on Computing, 5 (1976), pp. 266--283 (doi). (LexBFS: Lexicographic breadth-first search; triangulated graphs and the elimination process).
Algorithmic aspects of vertex elimination on directed graphs, D. J. Rose and R. E. Tarjan, SIAM Journal on Applied Mathematics, 34 (1978), pp. 176--197.(See the algorithm to compute fill).
A note on perfect elimination digraphs, D. J. Kleitman, SIAM Journal on Computing, 3 (1974), pp. 280--282 (doi).(A fast algorithm not possible? See also Rose and Tarjan'78).
Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, R. E. Tarjan and M. Yannakakis, SIAM Journal on Computing, 13 (1984), pp. 566--579 (doi).(Maximum cardinality search.).
Computing the minimum fill-in is NP-complete, M. Yannakakis, SIAM Journal on Algebraic and Discrete Methods, 2 (1981), pp. 77--79 (doi)

An approximate minimum degree ordering algorithm, by P. R. Amestoy, T. A. Davis, and I. S. Duff, SIAM Journal on Matrix Analysis and Applications, 17 (1996), pp. 886--905 (doi).
Nested dissection of a regular finite element mesh, A. George, SIAM Journal on Numerical Analysis, 10 (1973), 345--363. (doi)
An efficient algorithm to compute row and column counts for sparse Cholesky factorization, J. R. Gilbert, E. G. Ng, and B. W. Peyton, SIAM Journal on Matrix Analysis and Applications, 15 (1994), pp. 1075--1091 (doi) (fast computation of the row and column counts for the Cholesky factorization).
The analysis of a nested dissection algorithm, J. R. Gilbert and R. E. Tarjan, Numerische Mathematik, 50 (1987), pp. 377--404 (doi).
The computational complexity of the minimum degree algorithm, P. Heggernes, S. C. Eisenstat, G. Kumfert, and A. Pothen, Proceedings of NIK 2001---14th Norwegian Computer Science Conference, Tromsø, Norway, pp. 98--109, 2001.
Complexity bounds for regular finite difference and finite element grids, A. J. Hoffman, M. S. Martin, and R. J. Rose, SIAM Journal on Numerical Analysis, 10 (1973), pp. 364--369 (url).

A New Implementation of Sparse Gaussian Elimination, R. Schreiber, ACM Transactions on Mathematical Software, 8 (1982), pp. 256--276 doi Formalization of the elimination tree; Liu'90 is a more expository article.).
The role of elimination trees in sparse factorization, J. W. H. Liu, SIAM Journal on Matrix Analysis and Applications, 11 (1990), pp. 134--172 (doi) (the computation of the elimination tree; the use of elimination tree for structure prediction in Cholesky---for faster algorithms see Gilbert, Ng, and Peyton'94).

On-line bipartite matching made simple, B. Birnbaum and C. Mathieu, SIGACT News, 39 (2008), pp. 80--87 (doi) (Greedy by first permuting the rows obtains (1-1/e)).
Two approximation algorithms for bipartite matching on multicore architectures, F. Dufossé, K. Kaya, and B. Uçar, Journal of Parallel and Distributed Computing, 85 (2015), pp. 62--78 (doi) (Another 1-1/e approximation, and a 2(1-Ω) approximation, where Ω is Lambert's W(1)).
Computing the block triangular form of a sparse matrix, A. Pothen and C.-J. Fan, ACM Transactions on Mathematical Software, 16 (1990), pp. 303--324 (doi) (BTF decomposition and its properties; Greedy is 1/2 approximate).

Articles on presentations

Lx=b, Laplacian Solvers and Their Algorithmic Applications, N. K. Vishnoi (link).

Some similar courses

previously taught with Jean-Yves L'Excellent CR07, and CR09
by Patrick R. Amestoy (who kindly shared his lecture notes with us).
by Alfredo Buttari.
by John R. Gilbert, Sparse matrix algorithms.