CR-09
Sparse Matrix Computations
Algorithmique des matrices creuses


Semester: Fall, 2009
Schedule: Wednesday, 16:00--18:00
Classroom: Salle B2
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 outline


  1. INTRODUCTION

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

  2. SPARSE GAUSSIAN ELIMINATION

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

  3. SOME OTHER ESSENTIAL SPARSE MATRIX ALGORITHMS

    1. Graph and hypergraph partitioning
    2. Iterative methods

  4. CLOSING

    1. Current research activities
    2. Presentations

References


Some similar courses


Last updated: November 20, 2009