- 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):
- HW1 and HW2 by B. Uçar
- HW3 by G. Pichon, due on January 9th

- A report and a presentation on a research topic of choice (2/3 mark):
- In group of one or two students
- Research article
- 6 pages report (deadline 19/01) and 30 min (+ 15 min questions) presentation
- Presentation 23/01 and 27/01 (on Friday for once) with other students attending

- For both the report and the presentation, we are asking for:
- A presentation of the background regarding the work
- The general idea of the work
- A detailed analysis of some parts of the work
- Discussions regarding the state of the art
- You will have to show why the work presented in the paper is of interest and also to give some feedback on it (what could have be done, potential extension, parts which are not clear enough, missing information...)

- Articles for final evaluation:
- Two applications of Birkhoff decomposition: e.g., the following--or feel free to suggest others. Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches and Fairness of Exposure in Rankings
- Cover the eigen-solvers (basic algorithmics, no need for numerical properties, convergence rate etc), then the elimination approach here described with hypergraphs. Hypergraph edge elimination - a symbolic phase for hermitian eigensolvers based on rank-1 modifications
If you know the keywords: Solving polynomial systems, Groebner basis. Chordal networks of polynomial ideals based on Exploiting chordal structure in polynomial ideals: a Groebner bases approach

**Presentation on Friday, 27th January, 16h45. Taken by Jolyne Gatt and Hristina Nikolic.**Extending a sparse direct solver for the use of GPUs. Addressing Irregular Patterns of Matrix Computations on GPUs and Their Impact on Applications Powered by Sparse Direct Solvers- Low-rank compression within a domain-decomposition solver. parGeMSLR: A Parallel Multilevel Schur Complement Low-Rank Preconditioning and Solution Package for General Sparse Matrices
**Presentation on Friday, 27th January, 15h45. Taken by Maxime Cautrès and Thomas Pickles.**Managing carefully memory consumption with the multifrontral approach. Robust memory-aware mappings for parallel multifrontal factorizations**Presentation on Monday, 23th January, 15h45. Taken by Momeni Mohammadabadi Ali.**The use cases in this article are the family of tensor contraction expressions and convolutional neural networks. IOOpt: Automatic Derivation of I/O Complexity Bounds for Affine Programs- This article goes from theoretical results to actual executions on one thousand processors of LU and Cholesky factorizations. On the Parallel I/O Optimality of Linear Algebra Kernels: Near-Optimal Matrix Factorizations
**Presentation on Monday, 23th January, 16h45. Taken by Yasaman Asgari and Fatemeh Gashemi Mohsen.**From theory to practice, optimize the volume of communications for Cholesky factorization. I/O-Optimal Algorithms for Symmetric Linear Algebra Kernels

- 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 and 6: Sparse direct solvers: efficiency, complexity and parallelism Notes.
- Lecture 7: Low-Rank Compression in Sparse Direct Solvers Slides
- Performance and Scalability of the Block Low-Rank Multifrontal Factorization on Multicore Architectures, P. Amestoy, A. Buttari, J-Y. L’Excellent, T. Mary, ACM Transactions on Mathematical Software, 2019
- Sparse supernodal solver using block low-rank compression: Design, performance and analysis, G. Pichon, E. Darve, M. Faverge, P. Ramet, J. Roman, International Journal of Computational Science and Engineering, 2018

- Lecture 8: Ordering techniques to enhance sparse direct solvers Slides
- Lecture 9: Trade-off between execution time and memory consumption when using low-rank compression in sparse direct solvers Slides
- Lecture 10: Introduction to Scheduling Under Memory Constraints and Pebble Game Models Slides Notes
- Lecture 11: Pebble game models for I/Os Slides Notes
- Lecture 12: Communication-Avoiding Algorithms Slides
**Homework 3**Subject - Lecture 13: Memory-Aware DAG Scheduling Slides

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