Timothy A. Davis
Skip Abstract Section
Abstract
A new method for sparse LU factorization is presented that combines a column pre-ordering strategy with a right-looking unsymmetric-pattern multifrontal numerical factorization. The column ordering is selected to give a good a priori upper bound on fill-in and then refined during numerical factorization (while preserving the bound). Pivot rows are selected to maintain numerical stability and to preserve sparsity. The method analyzes the matrix and automatically selects one of three pre-ordering and pivoting strategies. The number of nonzeros in the LU factors computed by the method is typically less than or equal to those found by a wide range of unsymmetric sparse LU factorization methods, including left-looking methods and prior multifrontal methods.
- Amestoy, P. R., Davis, T. A., and Duff, I. S. 1996a. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Applic. 17, 4, 886--905. Google Scholar
- Amestoy, P. R., Davis, T. A., and Duff, I. S. 2004. Algorithm: AMD, an approximate minimum degree ordering algorithm. ACM Trans. Math. Softw., to appear. Google Scholar
- Amestoy, P. R., Davis, T. A., Duff, I. S., and Hadfield, S. M. 1996b. Parallelism in multifrontal methods for matices with unsymmetric structures. In Abstracts of the Second SIAM Conference on Sparse Matrices. Snowbird, Utah.Google Scholar
- Amestoy, P. R. and Duff, I. S. 1989. Vectorization of a multiprocessor multifrontal code. Intl. J. Supercomputer Appl. 3, 3, 41--59.Google Scholar
- Amestoy, P. R., Duff, I. S., L'Excellent, J.-Y., and Koster, J. 2001a. A fully asynchronous multifrontal solver using distributed dynmamic scheduling. SIAM J. Matrix Anal. Applic. 23, 1, 15--41. Google Scholar
- Amestoy, P. R., Duff, I. S., L'Excellent, J.-Y., and Li, X. S. 2001b. Analysis and comparison of two general sparse solvers for distributed memory computers. ACM Trans. Math. Softw. 27, 4, 388--421. Google Scholar
- Amestoy, P. R., Duff, I. S., and Puglisi, C. 1996a. Multifrontal QR factorization in a multiprocessor environment. Numer. Linear Algebra Appl. 3, 4, 275--300.Google Scholar
- Amestoy, P. R. and Puglisi, C. 2002. An unsymmetrized multifrontal LU factorization. SIAM J. Matrix Anal. Applic. 24, 553--569. Google Scholar
- Arioli, M., Demmel, J. W., and Duff, I. S. 1989. Solving sparse linear systems with sparse backward error. SIAM J. Matrix Anal. Applic. 10, 2, 165--190.Google Scholar
- Ashcraft, C. C. and Grimes, R. 1989. The influence of relaxed supernode partitions on the multifrontal method. ACM Trans. Math. Softw. 15, 4, 291--309. Google Scholar
- Ashcraft, C. C. and Liu, J. W. H. 1998. Robust ordering of sparse matrices using multisection. SIAM J. Matrix Anal. Applic. 19, 3, 816--832. Google Scholar
- Berger, A. J., Mulvey, J. M., Rothberg, E., and Vanderbei, R. J. 1995. Solving multistage stochastic programs using tree dissection. Tech. Rep. SOR-95-07, Dept. of Civil Eng. and Operations Research, Princeton Univ., Princeton, NJ. June.Google Scholar
- Brainman, I. and Toledo, S. 2002. Nested-dissection orderings for sparse LU with partial pivoting. SIAM J. Matrix Anal. Applic. 23, 998--1012. Google Scholar
- Bunch, J. R. and Parlett, B. N. 1971. Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8, 639--655.Google Scholar
- Coleman, T. F., Edenbrandt, A., and Gilbert, J. R. 1986. Predicting fill for sparse orthogonal factorization. J. ACM 33, 517--532. Google Scholar
- Davis, T. A. University of Florida sparse matrix collection. www.cise.ufl.edu/research/sparse.Google Scholar
- Davis, T. A. 2004. Algorithm 832: UMFPACK V4.3, an unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30, 2. Google Scholar
- Davis, T. A. and Duff, I. S. 1997. An unsymmetric-pattern multifrontal method for sparse LU factorization. SIAM J. Matrix Anal. Applic. 18, 1, 140--158. Google Scholar
- Davis, T. A. and Duff, I. S. 1999. A combined unifrontal/multifrontal method for unsymmetric sparse matrices. ACM Trans. Math. Softw. 25, 1, 1--19. Google Scholar
- Davis, T. A., Gilbert, J. R., Larimore, S. I., and Ng, E. G. 2004a. Algorithm: COLAMD, a column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw., to appear. Google Scholar
- Davis, T. A., Gilbert, J. R., Larimore, S. I., and Ng, E. G. 2004b. A column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw., to appear. Google Scholar
- Demmel, J. W., Eisenstat, S. C., Gilbert, J. R., Li, X. S., and Liu, J. W. H. 1999. A supernodal approach to sparse partial pivoting. SIAM J. Matrix Anal. Applic. 20, 3, 720--755. Google Scholar
- Dongarra, J. J., Du Croz, J. J., Duff, I. S., and Hammarling, S. 1990. A set of Level 3 Basic Linear Algebra Subprograms. ACM Trans. Math. Softw. 16, 1--17. Google Scholar
- Duff, I. S. 1977. On permutations to block triangular form. J. Inst. of Math. Appl. 19, 339--342.Google Scholar
- Duff, I. S. 1981. On algorithms for obtaining a maximum transversal. ACM Trans. Math. Softw. 7, 315--330. Google Scholar
- Duff, I. S. 1984. The solution of nearly symmetric sparse linear systems. In Computing methods in applied sciences and engineering, VI, R. Glowinski and J.-L. Lions, Eds. North Holland, Amsterdam New York and London, 57--74.Google Scholar
- Duff, I. S. 2002. A new code for the solution of sparse symmetric definite and indefinite systems. Tech. Rep. TR-2002-024, Rutherford Appleton Laboratory.Google Scholar
- Duff, I. S., Erisman, A. M., and Reid, J. K. 1986. Direct Methods for Sparse Matrices. London: Oxford Univ. Press. Google Scholar
- Duff, I. S. and Koster, J. 2001. On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM J. Matrix Anal. Applic. 22, 4, 973--996. Google Scholar
- Duff, I. S. and Reid, J. K. 1982. MA27 - a set of Fortran subroutines for solving sparse symmetric sets of linear equations. Tech. Rep. AERE-R-10533, AERE Harwell Laboratory, United Kingdom Atomic Energy Authority.Google Scholar
- Duff, I. S. and Reid, J. K. 1983a. The multifrontal solution of indefinite sparse symmetric linear systems. ACM Trans. Math. Softw. 9, 302--325. Google Scholar
- Duff, I. S. and Reid, J. K. 1983b. A note on the work involved in no-fill sparse matrix factorization. IMA J. Num. Anal. 3, 37--40.Google Scholar
- Duff, I. S. and Reid, J. K. 1984. The multifrontal solution of unsymmetric sets of linear equations. SIAM J. Sci. Statist. Comput. 5, 3, 633--641.Google Scholar
- Duff, I. S. and Reid, J. K. 1996. The design of MA48, a code for the direct solution of sparse unsymmetric linear systems of equations. ACM Trans. Math. Softw. 22, 2, 187--226. Google Scholar
- Duff, I. S. and Scott, J. A. 1996. The design of a new frontal code for solving sparse unsymmetric systems. ACM Trans. Math. Softw. 22, 1, 30--45. Google Scholar
- Eisenstat, S. C. and Liu, J. W. H. 1992. Exploiting structural symmetry in unsymmetric sparse symbolic factorization. SIAM J. Matrix Anal. Applic. 13, 1, 202--211. Google Scholar
- George, A. and Liu, J. W. H. 1981. Computer Solution of Large Sparse Positive Definite Systems. Englewood Cliffs, New Jersey: Prentice-Hall. Google Scholar
- George, A. and Liu, J. W. H. 1989. The evolution of the minimum degree ordering algorithm. SIAM Rev. 31, 1, 1--19. Google Scholar
- George, A. and Ng, E. G. 1985. An implementation of Gaussian elimination with partial pivoting for sparse systems. SIAM J. Sci. Statist. Comput. 6, 2, 390--409.Google Scholar
- George, A. and Ng, E. G. 1987. Symbolic factorization for sparse Gaussian elimination with partial pivoting. SIAM J. Sci. Statist. Comput. 8, 6 (Nov.), 877--898. Google Scholar
- Gilbert, J. R., Li, X. S., Ng, E. G., and Peyton, B. W. 2001. Computing row and column counts for sparse QR and LU factorization. BIT 41, 4, 693--710.Google Scholar
- Gilbert, J. R., Moler, C., and Schreiber, R. 1992. Sparse matrices in MATLAB: design and implementation. SIAM J. Matrix Anal. Applic. 13, 1, 333--356. Google Scholar
- Gilbert, J. R. and Peierls, T. 1988. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Statist. Comput. 9, 862--874.Google Scholar
- Goto, K. and van de Geijn, R. 2002. On reducing TLB misses in matrix multiplication, FLAME working note 9. Tech. Rep. TR-2002-55, The University of Texas at Austin, Department of Computer Sciences.Google Scholar
- Gupta, A. 2002. Improved symbolic and numerical factorization algorithms for unsymmetric sparse matrices. SIAM J. Matrix Anal. Applic. 24, 529--552. Google Scholar
- Gupta, A., Gustavson, F., Joshi, M., Karypis, G., and Kumar, V. 1999. PSPASES: an efficient and scalable parallel sparse direct solver. In Kluwer Intl. Series in Engineering and Science, T. Yang, Ed. Vol. 515. Kluwer.Google Scholar
- Hadfield, S. M. 1994. On the LU factorization of sequences of identically structured sparse matrices within a distributed memory environment. Ph.D. thesis, University of Florida, Gainesville, FL. Google Scholar
- Hadfield, S. M. and Davis, T. A. 1995. The use of graph theory in a parallel multifrontal method for sequences of unsymmetric pattern sparse matrices. Cong. Numer. 108, 43--52.Google Scholar
- Heath, M. T. and Raghavan, P. 1995. A Cartesian parallel nested dissection algorithm. SIAM J. Matrix Anal. Applic. 16, 1, 235--253. Google Scholar
- Hendrickson, B. and Rothberg, E. 1999. Improving the runtime and quality of nested dissection ordering. SIAM J. Sci. Comput. 20, 468--489. Google Scholar
- Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359--392. Google Scholar
- Larimore, S. I. 1998. An approximate minimum degree column ordering algorithm. Tech. Rep. TR-98-016, Univ. of Florida, Gainesville, FL. www.cise.ufl.edu.Google Scholar
- Liu, J. W. H. 1990. The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Applic. 11, 1, 134--172. Google Scholar
- Liu, J. W. H. 1992. The multifrontal method for sparse matrix solution: Theory and practice. SIAM Rev. 34, 1, 82--109. Google Scholar
- Matstoms, P. 1994. Sparse QR factorization in MATLAB. ACM Trans. Math. Softw. 20, 1, 136--159. Google Scholar
- Ng, E. G. and Raghavan, P. 1999. Performance of greedy ordering heuristics for sparse Cholesky factorization. SIAM J. Matrix Anal. Applic. 20, 4, 902--914. Google Scholar
- Rothberg, E. and Eisenstat, S. C. 1998. Node selection strategies for bottom-up sparse matrix orderings. SIAM J. Matrix Anal. Applic. 19, 3, 682--695. Google Scholar
- Whaley, R. C., Petitet, A., and Dongarra, J. J. 2001. Automated emperical optimization of software and the ATLAS project. Parallel Computing 27, 1-2, 3--35.Google Scholar
- Yannakakis, M. 1981. Computing the minimum fill-in is NP-Complete. SIAM J. Alg. Disc. Meth. 2, 77--79.Google Scholar
Index Terms
- A column pre-ordering strategy for the unsymmetric-pattern multifrontal method
Recommendations
A column approximate minimum degree ordering algorithm
Sparse Gaussian elimination with partial pivoting computes the factorization PAQ = LU of a sparse matrix A, where the row ordering P is selected during factorization using standard partial pivoting with row interchanges. The goal is to select a column ...
Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm
Two codes are discussed, COLAMD and SYMAMD, that compute approximate minimum degree orderings for sparse matrices in two contexts: (1) sparse partial pivoting, which requires a sparsity preserving column pre-ordering prior to numerical factorization, ...
Algorithm 832: UMFPACK V4.3---an unsymmetric-pattern multifrontal method
An ANSI C code for sparse LU factorization is presented that combines a column pre-ordering strategy with a right-looking unsymmetric-pattern multifrontal numerical factorization. The pre-ordering and symbolic analysis phase computes an upper bound on ...
Comments