CR-08
Combinatorial scientific computing
Calcul scientifique combinatoire

Semester: Fall 2014,
Schedule: Wednesday/Mercredi 10h15--12h15,
Classroom: Salle B1 (4th floor),
Instructor: 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.
• Matrix Iterative Analysis, by Richard S. Varga, Second (revised and expanded edition of Prentice-Hall, Englewood Cliffs, New Jersey, 1962), Springer, 2000. (page 18 contains historical references to irreducibility)
• Applied Numerical Linear Algebra, by James W. Demmel. SIAM, 1997.
• Numerical Linear Algebra, by Lloyd N. Trefethen and David Bau, III. SIAM 1997.
• How ordinary elimination became Gaussian elimination, by Joseph F. Grcar, Historia Mathematica, 38 (011), pp. 163--218 (doi also at arxiv)
• The decompositional approach to matrix computation, by G. W. Stewart, Computing in Science and Engineering, vol. 2, no. 1, pp. 50--59, 2000 (doi).
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).
• Complexity bounds for regular finite difference and finite element grids, by A. J. Hoffman, M. S. Martin, and R. J. Rose, SIAM Journal on Numerical Analysis, 10 (1973), pp. 364--369 (url).
• 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
• Optimal parallel solution of sparse triangular systems, by F. L. Alvarado and R. Schreiber, SIAM Journal on Scientific Computing, 14 (1993), pp. 446--460. (doi).
• 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).
• On algorithms for permuting large entries to the diagonal of a sparse matrix, by I. S. Duff and J. Koster, SIAM Journal on Matrix Analysis and Applications 22 (2001), pp. 973--996. (doi) (weighted matching and scaling).
• Nested dissection of a regular finite element mesh, A. George, SIAM Journal on Numerical Analysis, 10 (1973), 345--363. (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).
• The computational complexity of the minimum degree algorithm, by P. Heggernes, S. C. Eisenstat, G. Kumfert, and A. Pothen, Proceedings of NIK 2001---14th Norwegian Computer Science Conference, Tromsø, Norway, pp. 98--109, 2001.
• On the storage requirement in the out-of-core multifrontal method for sparse factorization, by J. W. H. Liu, ACM Transactions on Mathematical Software, 12 (1986), pp. 249--264. (doi) (tree traversal in postoder to obtain minimum peak peak memory in the multifrontal solver.).
• An application of generalized tree pebbling to sparse matrix factorization, by J. W. H. Liu, SIAM Journal on Algebraic and Discrete Methods, 8 (1987), p.p. 375--395. (doi) ( tree traversal in any topological order to minimize the peak memory in the multifrontal solver).
• 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 new pivoting strategy for Gaussian elimination, by M. Olschowka and A. Neumaier, Linear Algebra and Its Applications, 240 (1996), pp. 131--151 (doi) (weighted matching and scaling).
• 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
• Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, by R. Barrett and M. Berry and T. F. Chan and J. Demmel and J. Donato and J. Dongarra and V. Eijkhout and R. Pozo and C. Romine and H. Van der Vorst (online), (Overview of iterative methods, their classification, and costs).
• Equilibration of symmetric matrices in the max-norm, by J. R. Bunch, Journal of the ACM, 18 (1971), pp. 566--572 (doi).
• 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).
• 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 scaling algorithm to equilibrate both rows and columns norms in matrices, by D. Ruiz, Tech. Rep. RAL-TR-2001-034 and RT/APO/01/4, Rutherford Appleton Laboratory, Oxon, UK and ENSEEIHT-IRIT, Toulouse, France.
• A Symmetry preserving algorithm for matrix scaling, by P. A. Knight, D. Ruiz, and B. Uçar, SIAM Journal on Matrix Analysis and Applications, 35 (2014), pp. 931--955 (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: December 17, 2014