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
Course home page

Reading list

1. INTRODUCTION
• World's largest sparse matrix computation, by C. Moler (the article dates 2002; the matrices in question got larger and larger). See also the corresponding chapter in Moler's e-book.
2. GRAPH THEORY AND ALGORITHMS
• The analysis of a nested dissection algorithm, by J. R. Gilbert and R. E. Tarjan, Numerische Mathematik, 50 (1987), pp. 377--404 (doi).
• Depth-first search and linear graph algorithms, by R. Tarjan, SIAM Journal on Computing, 2 (1972), pp. 146--160 (doi) (see le palmier et ses frondes).
• Computing the minimum fill-in is NP-complete, by M. Yannakakis, SIAM Journal on Algebraic and Discrete Methods, 2 (1981), pp. 77--79 (doi)
3. SPARSE MATRIX COMPUTATIONS AND GRAPHS
• An approximate minimum degree ordering algorithm, by P. R. Amestoy, T. A. Davis, and I. S. Duff, SIAM Journal on Matrix Analysis and Applications, 17 (1996), pp. 886--905 (doi).
• Predicting structure in sparse matrix computations, by J. R. Gilbert, SIAM Journal on Matrix Analysis and Applications, 15 (1994), pp. 62--79 (doi).
• An efficient algorithm to compute row and column counts for sparse Cholesky factorization, by J. R. Gilbert, E. G. Ng, and B. W. Peyton, SIAM Journal on Matrix Analysis and Applications, 15 (1994), pp. 1075--1091 (doi) (fast computation of the row and column counts for the Cholesky factorization).
• Sparse partial pivoting in time proportional to arithmetic operations, by J. R. Gilbert and T Peierls, SIAM Journal on Scientific and Statistical Computing, 9 (1988), pp. 862--874 (doi) (Sparse triangular system solution for sparse right hand side vectors).
• Equivalent sparse matrix reordering by elimination tree rotations, by J. W. H. Liu, SIAM Journal on Scientific and Statistical Computing, 9 (1988), pp. 424--444 (doi).
• The role of elimination trees in sparse factorization, by J. W. H. Liu, SIAM Journal on Matrix Analysis and Applications, 11 (1990), pp. 134--172 (doi) (the computation of the elimination tree; the use of elimination tree for structure prediction in Cholesky---for faster algorithms see ginp:94).
• A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, by D. J. Rose, in Graph Theory and Computing, ed. R. C. Read, Academic Press, 1972, pp. 183--217 (tringulated graphs and the elimination process; minimum degree ordering).
• Algorithmic aspects of vertex elimination on graphs, by D. J. Rose, R. E. Tarjan, and G. S. Lueker, SIAM Journal on Computing, 5 (1976), pp. 266--283 (doi) (LexBFS: Lexicographic breadth-first search; triangulated graphs and the elimination process).
• Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, by R. E. Tarjan and M. Yannakakis, SIAM Journal on Computing, 3 (1984), pp. 566--579 (doi) (MCS: Maximum cardinality search).
4. PARALLELIZATION
• A Mapping Algorithm for Parallel Sparse Cholesky Factorization, by A. Pothen and C. Sun, SIAM Journal on Scientific Computing, 14 (1993), pp. 1253--1257 (doi) (The proportional mapping algorithm).
• Analysis and Comparison of Two General Sparse Solvers for Distributed Memory Computers, by P. R. Amestoy, I. S. Duff, J.-Y. L'Excellent, X. S. Li, ACM Transactions on Mathematical Software, 27 (2001), pp. 388--421 (doi) (Different approaches to parallelism).
• Parallel algorithms for sparse linear systems, by M. T. Heath, E. Ng, and B. W. Peyton, SIAM Review, 33 (1991), pp. 420--460 (doi).
5. NUMERICAL ASPECTS
• The multifrontal solution of indefinite sparse symmetric linear systems, by I. S. Duff and J. K. Reid, ACM Transactions on Mathematical Software, 9 (1983), pp. 302--325 (doi) (The formalization of the multifrontal method).
• On the reduction of a symmetric matrix to tridiagonal form, by J. O. Aasen, BIT Numerical Mathematics, 11 (1971), pp. 233--242 (doi).
• Decomposition of a symmetric matrix, by J. R. Bunch and L. Kaufman and B. N. Parlett, Numerische Mathematik, 27 (1976), pp. 95--109 (doi).
• Strategies for scaling and pivoting for sparse symmetric indefinite problems, by I. S. Duff and S. Pralet, SIAM Journal on Matrix Analysis and Applications, 27 (2005), pp. 313--340 (doi).
• Matrix computations, by G. H. Golub and C. Van Loan (Chapter 3 for existence and uniqueness of LU decomposition, and pivoting).
• A geometric analysis of Gaussian elimination - II, by L. Neal and G. Poole, Linear Algebra and its Applications, 173 (1992), pp. 239--264 (doi) (rook pivoting).
• Error analysis of direct methods of matrix inversion, by J. H. Wilkinson, Journal of the ACM, 8 (1961), pp. 281--330 (doi).
6. SURVEY ARTICLES
• Parallel algorithms for sparse linear systems, by M. T. Heath, E. Ng, and B. W. Peyton, SIAM Review, 33 (1991), pp. 420--460 (doi).
• Combinatorial scientific computing: The enabling power of discrete algorithms in computational science, by B. Hendrickson and A. Pothen, Lecture Notes in Computer Science 4395:260--280, 2007 (paper).
• Combinatorial problems in solving linear systems, by I. S. Duff and B. Uçar (LIP research report RR-2009-15).

Last updated: September 29, 2010