CR-08
Combinatorial scientific computing
Calcul scientifique combinatoire
Semester: Fall 2014,
Schedule: Wednesdays, 10h15--12h15.
Classroom: Salle B1 (4th floor),
Instructor: 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. 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.
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
The starting date of each section is given in square brackets.
- INTRODUCTION
- Sparse matrices [10/09] (notes)
- Graph theory and algorithms for sparse matrices [10/09] (notes)
- Linear algebra basics [24/09]. (relevant resources are Chapters
7, 10, 11, 20--23, 25 of Trefethen and Bau III's book; Chapter 1 of Demmel's book; Chapters 3 and 5 of Golub and Van Loan's book; and the article by Stewart---see the list of articles.)
- SPARSE GAUSSIAN ELIMINATION
- Structure prediction and fill-reducing ordering methods [1/10] (notes).
- Elimination tree [22/10] (notes, updated Nov the 5th. Oguz Kaya discussed the fast row and column count algorithms, based on the paper by Gilbert, Ng, and Peyton [see in the list of articles]).
- Pivoting and bipartite matching, btf, and cardinality matching, weighted matching (notes, weighted matching notes) [19/11, then 3/12].
- Computing inverse entries, a.k.a., tree partitioning problems (notes [3/12])
- SOME OTHER ESSENTIAL SPARSE MATRIX ALGORITHMS
- Iterative methods and parallelization/partitioning (notes [10/12])
- Matrix scaling algorithms (covered parallel scaling, Bunch's scaling algorithm (doi) and its parallelization by making use of a variant of the Gallai-Hasse-Roy-Vitaver theorem, and the use of the 1-norm scaling algoritm in designing a matching heuristic (notes) [17/10])
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.
- 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.
- A list [updated Dec 17, 2014] of articles (the list will grow as we proceed).
Some similar courses
Last updated: December 17, 2014