CR-07
Sparse Matrix Computations
Algorithmique des matrices creuses

Semester: Fall, 2010
Schedule: Friday, 10h15--12h15
Classroom: Salle B1
Instructors: Jean-Yves L'Excellent and Bora Uçar

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.

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: The students are expected to study research articles related to the contents of the course, write a report, and do an oral presentation.

Texts: We will not be following a particular text book. We will use course notes and research and survey articles throughout the semester.

Tentative contents

---

1. INTRODUCTION

---

1. Sparse matrices (course notes)
2. Graph theory and algorithms (course notes)
3. Linear algebra basics (course notes)

---

2. SPARSE GAUSSIAN ELIMINATION

---

4. Structure prediction and fill-reducing ordering methods (course notes)
5. Elimination tree (course notes)
6. Pivoting and bipartite matching
7. Factorization: Methods (course notes)
8. Factorization: Parallelization aspects (see the one above for course notes)

---

3. SOME OTHER ESSENTIAL SPARSE MATRIX ALGORITHMS

---

9. Graph and hypergraph partitioning
10. Iterative methods

---

4. CLOSING

---

11. Current research activities
12. Presentations

---

5. APPENDIX

---

1. Reading list (the list will grow as we proceed).

References

• 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. See the web page of the book
• 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.
• 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.

Some similar courses

• by Patrick R. Amestoy (who kindly shared his lecture notes with us).
• by John R. Gilbert, Sparse matrix algorithms.
• by Cevdet Aykanat (who kindly shared some of his notes on algorithms with us)

Last updated: October 21, 2010