CS497, Section MH, Spring 1999 TOPICS AND BACKGROUND READING Graph Model and Sparse Data Structures Chapter 3 and Sections 5.1 & 5.2 of A. George and J. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, NJ, 1981. (Sections 5.2 and 5.3 in postscript version) Chapter 2 of I. Duff, A. Erisman and J. Reid, Direct Methods for Sparse Matrices, Oxford University Press, New York, 1986. Ordering to Sparse Matrices to Special Forms Chapters 6 & 8 of I. Duff, A. Erisman and J. Reid, Direct Methods for Sparse Matrices, Oxford University Press, New York, 1986. Chapter 4 of A. George and J. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, NJ, 1981. Minimum Degree Ordering Section 5.3 of A. George and J. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, NJ, 1981. (Section 5.4 in postscript version) Chapter 7 of I. Duff, A. Erisman and J. Reid, Direct Methods for Sparse Matrices, Oxford University Press, New York, 1986. A. George and J. Liu, The evolution of the minimum degree ordering algorithm, SIAM Review 31:1-19, 1989. Graph Partitioning and Nested Dissection Orderings Chapters 7-8 of A. George and J. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, NJ, 1981. Chapter 11 of I. Duff, A. Erisman and J. Reid, Direct Methods for Sparse Matrices, Oxford University Press, New York, 1986. A. Pothen and H. D. Simon and K.-P. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11: 430-452, 1990. G. Miller S.-H. Teng, W. Thurston, and S. Vavasis, Automatic mesh partitioning, in Graph Theory and Sparse Matrix Computation, Springer- Verlag, New York, pp. 57-84, 1993. C. Ashcraft and J. Liu, Robust ordering of sparse matrices using multisection, SIAM J. Matrix Anal. Appl., 19:816-832, 1998. G. Karypis and V. Kumar, Parallel multilevel k-way partitioning scheme for irregular graphs, SIAM Review, 41:278-300, 1999. H. Simon and S.-H. Teng, How good is recursive bisection?, SIAM J. Sci. Comput., to appear. D. Spielman and S.-H. Teng, Spectral partitioning works: planar graphs and finite element meshes, to appear. CHACO JOSTLE METIS SCOTCH Elimination Trees and Symbolic Factorization J. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl. 11:134-172, 1990. Section 5.4 of A. George and J. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, NJ, 1981. (Section 5.5 in postscript version) J. Blair and B. Peyton, An introduction to chordal graphs and clique trees, in Graph Theory and Sparse Matrix Computation, Springer-Verlag, New York, pp. 1-29, 1993. Numeric Factorization Sections 2.1 & 5.5 of A. George and J. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, NJ, 1981. (Sections 2.2 and 5.6 in postscript version) C. Ashcraft, S. Eisenstat, J. Liu and A. Sherman, A comparison of three column-based distributed sparse factorization schemes, Tech. Rept. YALEU/DCS/RR-810, Dept. of Computer Science, Yale University, New Haven, CT, 1990. C. Ashcraft, The fan-both family of column-based distributed Cholesky factorization algorithms, in Graph Theory and Sparse Matrix Computation, Springer-Verlag, New York, pp. 159-190, 1993. E. Rothberg and A. Gupta, An evaluation of left-looking, right-looking, and multifrontal approaches to sparse Cholesky factorization on hierarchical-memory machines, Intl. J. High Speed Comput., 5:537-593, 1993. Multifrontal Method J. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review 34:82-109, 1992. I. S. Duff, Parallel implementation of multifrontal schemes, Parallel Computing 3:193-204, 1986. Triangular Solution Section 2.2 of A. George and J. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs, NJ, 1981. (Section 2.3 in postscript version) M. Heath and P. Raghavan, Performance of parallel sparse triangular solution, in Algorithms for Parallel Processing, Springer-Verlag, New York, 1999, pp. 289-305. F. Alvarado, A. Pothen, and R. Schreiber, Highly parallel sparse triangular solution, in Graph Theory and Sparse Matrix Computation, Springer-Verlag, New York, pp. 141-157, 1993. M. Joshi, A. Gupta, G. Karypis, and V. Kumar, A high performance two dimensional scalable parallel algorithm for solving sparse triangular systems, to appear. Nonsymmetric Systems Section 7.8 & Chapters 9-10 of I. Duff, A. Erisman and J. Reid, Direct Methods for Sparse Matrices, Oxford University Press, New York, 1986. J. Demmel, S. Eisenstat, J. Gilbert, X. Li, and J. Liu, A supernodal approach to sparse partial pivoting, SIAM J. Matrix Anal. Appl., to appear. Sparse Least Squares Problems M. T. Heath, Numerical methods for large sparse linear least squares problems, SIAM J. Sci. Stat. Comput., 5: 497-513, 1984. Chapter 6 of A. Bjorck, Numerical Methods for Least Squares Problems, SIAM, 1996. Conditioning and Iterative Refinement Chapters 4-5 of I. Duff, A. Erisman and J. Reid, Direct Methods for Sparse Matrices, Oxford University Press, New York, 1986. Parallel Implementation J. Liu, Computational models and task scheduling for parallel sparse Cholesky factorization, Parallel Computing 3:327-342, 1986. J. Liu, Reordering sparse matrices for parallel elimination, Parallel Computing 11:73-91, 1989. M. T. Heath, E. Ng and B. W. Peyton, Parallel algorithms for sparse linear systems, SIAM Review 33:420-460, 1991. M. T. Heath, Parallel direct methods for sparse linear systems, in Parallel Numerical Algorithms, ed. by D. E. Keyes, A. Sameh, and V. Venkatakrishnan, Kluwer Academic Publishers, Boston, 1997, pp. 55-90. Chapter 11 of V. Kumar, A. Grama, A. Gupta and G. Karypis, Introduction to Parallel Computing: Design and Analysis of Algorithms, Benjamin/Cummings, Redwood City, CA, 1994. A. Gupta, G. Karypis, and V. Kumar, Highly scalable parallel algorithms for sparse matrix factorization, IEEE Trans. Parallel Distrib. Systems 8:502-520, 1997. A. Gupta, F. Gustavson, M. Joshi, G. Karypis, and V. Kumar, Design and implementation of a scalable parallel direct solver for sparse symmetric positive definite systems: preliminary results, to appear. J. Demmel, J. Gilbert, and X. Li, An asynchronous parallel supernodal algorithm for sparse Gaussian elimination, SIAM J. Matrix Anal. Appl., to appear. Scalability T. Rauber, G. Runger, and C. Scholtes, Scalability of sparse Cholesky factorization, International J. High Speed Computing 10:19-52, 1999. R. Schreiber, Scalability of sparse direct solvers, in Graph Theory and Sparse Matrix Computation, Springer-Verlag, New York, pp. 191-209, 1993. S. A. Vavasis, Gaussian elimination with pivoting is P-complete, SIAM J. Disc. Math., 2:413-423, 1989. Software Additional References George & Liu book