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.
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;
- Elimination tree for Cholesky (1 Oct, 2019;
- BTF and matching (8 Oct, 2019;
- 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
- Hugues Depres and Etienne Vareille talked spectral methods
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
Pegah Pournajafi talks about a Kaczmarz solver
- 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). ()
- 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
- 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). ().
- 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.().
- A note on perfect elimination digraphs, D. J. Kleitman, SIAM Journal on Computing, 3 (1974), pp. 280--282 (doi).().
- 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).().
- Computing the minimum fill-in is NP-complete, M. Yannakakis,
SIAM Journal on Algebraic and Discrete Methods, 2 (1981), pp. 77--79
- 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
- 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 ).
- 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) ().
- On-line bipartite matching made simple, B. Birnbaum and C. Mathieu,
SIGACT News, 39 (2008), pp. 80--87 (doi) ().
- 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) ().
- 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) ().
- Articles on presentations
- Lx=b, Laplacian Solvers and Their Algorithmic Applications, N. K. Vishnoi (link).
Some similar courses