- M2 research course at ENS Lyon for 2022-2023
- Organized by LIP members, belonging to the ROMA team

This course focuses on algorithms to improve the performance and resource utilization of sparse linear solvers that solve systems of the form *A**x* = *b*, that appear in many numerical applications. The matrix *A* can be either dense or sparse, that is, mostly made of zero entries. Sparse matrices appear for instance when discretizing Partial Differential Equations (PDEs) on 2D and 3D finite element or finite volume meshes. A classical exemple is the modelization of the heat equation, where the continuous function is discretized into points. Each point corresponds to a row in the matrix *A* and non-zero entries of *A* correspond to interaction between close points, remote interactions being neglected. Graphs and other combinatorial objects are used to model matrices and computations with them. This course will present certain solvers and introduce methods from combinatorial optimization and scheduling domains that enable efficiency in those solvers.

- Bi-monthly homework assignments (1/3 mark):
- A report and a presentation on a research topic of choice (2/3 mark):

- Lecture 1 Notes, 14 Nov.
**Homework 1**is out with two questions (see the lecture notes), and is due 24 nov, before class. - Lecture 2, 17 Nov: Linear algebra refresher, Gaussian Elimination yields
*U*of the LU decomposition; keep track of linear elementary row transfotmations*L*_{n}× ⋯*L*_{2}×*L*_{1}×*A*=*U*; then*A*=*L*_{1}^{−1}×*L*_{2}^{−1}× ⋯ ×*L*_{n}^{−1}×*U*. Each*L*_{i}can be inverted in-place, and the multiplication of the inverses is just the inverses in their place. What happens in the sparse case? - Lecture 3 Notes, 21 nov.
**Homework**2 is out with two questions (see the lecture notes), and is due 1 dec, before class.- A Note on Perfect Elimination Digraphs, D. J. Kleitman, SIAM Journal on Computing, 3 (1974), pp. 280--282 (doi).
- Toward Characterization of Perfect Elimination Digraphs, L. Haskins and D. J. Rose, SIAM Journal on Computing, 2 (1973), pp. 217--224. doi, 1973.
- 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. (doi).

- Lecture 4 Notes.
- Lecture 5 Notes.

- Gaussian elimination and graphs
- Sparse direct solvers

- Elimination game on the graphs, chordal graphs
- Elimination tree
- Fill-reducing ordering methods
- Matching problems on graphs
- Graph and hypergraph models

- The pebble game model, I/O complexity, and lower bounds
- Memory-aware DAG scheduling
- Communication-avoiding algorithms

- Complexity of sparse direct solvers
- Low-rank compression
- Parallelism

- T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006.
- J. W. Demmel, Applied Numerical Linear Algebra, SIAM, 1997.
- G. H. Golub and C. F. Van Loan, Matrix Computations, 4th edition, The Johns Hopkins University Press, 2013.

- L. N. Trefethen and D. Bau III, Numerical Linear Algebra, SIAM, 1997.