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