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.

The starting date of each section is given in parenthesis.

- Sparse matrices and graphs (10 Sep 2018; notes)
- Structure prediction and fill-reducing ordering methods (17 Sep 2018; notes)
- Elimination tree for Cholesky (24 Sep 2018; notes)
- Pivoting and bipartite matching, btf, and cardinality matching, weighted matching (1 Oct 2018; notes, notes)
- Parallel sparse matrix vector multiplication (a.k.a. graph/hypergraph partitioning) (Oct 15, notes)
- Eigenvalues and combinatorial optimization (Oct 22, notes)
- Birkhoff--von Neumann decomposition and linear systems (Nov 5)
- Combinatorial solvers (started Nov 5)

- 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.
- Direct methods for sparse matrices, by I. S. Duff, A. M. Erisman, and J. K. Reid.
- Computer solution of large sparse positive definite systems, by A. George and J. W. H. Liu.
- Matrix computations, by G. H. Golub and C. Van Loan.
- Algorithmic graph theory and perfect graphs, M. C. Golumbic.
- Combinatorial optimization: Networks and matroids, by E. Lawler.
- Iterative methods for sparse linear systems, by Y. Saad.
- Data structures and network algorithms, by R. E. Tarjan.
- Numerical Linear Algebra, by Lloyd N. Trefethen and David Bau, III. SIAM 1997.
- Laplacian solvers:
*Lx=b*, Laplacian solvers and their algorithmic applications, by Nisheeth K. Vishnoi. Available online.- A Simple, combinatorial algorithm for solving SDD systems in nearly-linear time, by Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. In STOC'13, also available at arxiv.
- Articles:
- Predicting structure in sparse matrix computations, by 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, by 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, by 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, by 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, by 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, by 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, by J. R. Gilbert and R. E. Tarjan, Numerische Mathematik, 50 (1987), pp. 377--404 (doi).
- The computational complexity of the minimum degree algorithm, by 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, by 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, by 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).

- 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.

Last updated: *Nov 07, 2018*