A column pre-ordering strategy for the unsymmetric-pattern multifrontal method

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.

REFERENCES

• 1: Patrick R. Amestoy , Timothy A. Davis , Iain S. Duff, An Approximate Minimum Degree Ordering Algorithm, SIAM Journal on Matrix Analysis and Applications, v.17 n.4, p.886-905, Oct. 1996 [doi>10.1137/S0895479894278952]
• 2: Patrick R. Amestoy , Enseeiht-Irit , Timothy A. Davis , Iain S. Duff, Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.381-388, September 2004 [doi>10.1145/1024074.1024081]
• 3: 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.
• 4: Amestoy, P. R. and Duff, I. S. 1989. Vectorization of a multiprocessor multifrontal code. Intl. J. Supercomputer Appl. 3, 3, 41--59.
• 5: Patrick R. Amestoy , Iain S. Duff , Jean-Yves L'Excellent , Jacko Koster, A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling, SIAM Journal on Matrix Analysis and Applications, v.23 n.1, p.15-41, 2001 [doi>10.1137/S0895479899358194]
• 6: Patrick R. Amestoy , Iain S. Duff , Jean-Yves L'excellent , Xiaoye S. Li, Analysis and comparison of two general sparse solvers for distributed memory computers, ACM Transactions on Mathematical Software (TOMS), v.27 n.4, p.388-421, December 2001 [doi>10.1145/504210.504212]
• 7: 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.
• 8: Patrick R. Amestoy , Chiara Puglisi, An Unsymmetrized Multifrontal LU Factorization, SIAM Journal on Matrix Analysis and Applications, v.24 n.2, p.553-569, 2002 [doi>10.1137/S0895479800375370]
• 9: 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.
• 10: Cleve Ashcraft , Roger Grimes, The influence of relaxed supernode partitions on the multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.15 n.4, p.291-309, Dec. 1989 [doi>10.1145/76909.76910]
• 11: Cleve Ashcraft , Joseph W. H. Liu, Robust Ordering of Sparse Matrices using Multisection, SIAM Journal on Matrix Analysis and Applications, v.19 n.3, p.816-832, July 1998 [doi>10.1137/S0895479896299081]
• 12: 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.
• 13: Igor Brainman , Sivan Toledo, Nested-Dissection Orderings for Sparse LU with Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.23 n.4, p.998-1012, 2001 [doi>10.1137/S0895479801385037]
• 14: 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.
• 15: Thomas F. Coleman , Anders Edenbrandt , John R. Gilbert, Predicting fill for sparse orthogonal factorization, Journal of the ACM (JACM), v.33 n.3, p.517-532, July 1986 [doi>10.1145/5925.5932]
• 16: Davis, T. A. University of Florida sparse matrix collection. www.cise.ufl.edu/research/sparse.
• 17: Timothy A. Davis, Algorithm 832: UMFPACK V4.3---an unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.196-199, June 2004 [doi>10.1145/992200.992206]
• 18: Timothy A. Davis , Iain S. Duff, An Unsymmetric-Pattern Multifrontal Method for Sparse LU Factorization, SIAM Journal on Matrix Analysis and Applications, v.18 n.1, p.140-158, Jan. 1997 [doi>10.1137/S0895479894246905]
• 19: Timothy A. Davis , Iain S. Duff, A combined unifrontal/multifrontal method for unsymmetric sparse matrices, ACM Transactions on Mathematical Software (TOMS), v.25 n.1, p.1-20, March 1999 [doi>10.1145/305658.287640]
• 20: Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.377-380, September 2004 [doi>10.1145/1024074.1024080]
• 21: Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.353-376, September 2004 [doi>10.1145/1024074.1024079]
• 22: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
• 23: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 24: Duff, I. S. 1977. On permutations to block triangular form. J. Inst. of Math. Appl. 19, 339--342.
• 25: I. S. Duff, On Algorithms for Obtaining a Maximum Transversal, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.315-330, Sept. 1981 [doi>10.1145/355958.355963]
• 26: 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.
• 27: 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.
• 28: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 29: I. S. Duff , J. Koster, On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix, SIAM Journal on Matrix Analysis and Applications, v.22 n.4, p.973-996, 2000 [doi>10.1137/S0895479899358443]
• 30: 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.
• 31: I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
• 32: 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.
• 33: 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.
• 34: I. S. Duff , J. K. Reid, The design of MA48: a code for the direct solution of sparse unsymmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.187-226, June 1996 [doi>10.1145/229473.229476]
• 35: I. S. Duff , J. A. Scott, The design of a new frontal code for solving sparse, unsymmetric systems, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.30-45, March 1996 [doi>10.1145/225545.225550]
• 36: Stanley C. Eisenstat , Joseph W. H. Liu, Exploiting structural symmetry in unsymmetric sparse symbolic factorization, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.202-211, Jan. 1992 [doi>10.1137/0613017]
• 37: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 38: A. George , W. H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Review, v.31 n.1, p.1-19, Mar. 1989 [doi>10.1137/1031001]
• 39: 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.
• 40: Alan George , Esmond Ng, Symbolic factorization for sparse Gaussian elimination with partial pivoting, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.877-898, November 1, 1987 [doi>10.1137/0908072]
• 41: 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.
• 42: John R. Gilbert , Cleve Moler , Robert Schreiber, Sparse matrices in matlab: design and implementation, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.333-356, Jan. 1992 [doi>10.1137/0613024]
• 43: Gilbert, J. R. and Peierls, T. 1988. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Statist. Comput. 9, 862--874.
• 44: 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.
• 45: Anshul Gupta, Improved Symbolic and Numerical Factorization Algorithms for Unsymmetric Sparse Matrices, SIAM Journal on Matrix Analysis and Applications, v.24 n.2, p.529-552, 2002 [doi>10.1137/S089547980139604X]
• 46: 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.
• 47: Steven Michael Hadfield , Timothy A. Davis, On the lu factorization of sequences of identically structured sparse matrices within a distributed memory environment, 1994
• 48: 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.
• 49: Michael T. Heath , Padma Raghavan, A Cartesian Parallel Nested Dissection Algorithm, SIAM Journal on Matrix Analysis and Applications, v.16 n.1, p.235-253, Jan. 1995 [doi>10.1137/S0895479892238270]
• 50: Bruce Hendrickson , Edward Rothberg, Improving the Run Time and Quality of Nested Dissection Ordering, SIAM Journal on Scientific Computing, v.20 n.2, p.468-489, March 1998 [doi>10.1137/S1064827596300656]
• 51: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 52: 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.
• 53: Joseph W. H. Liu, The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications, v.11 n.1, p.134-172, January 1990 [doi>10.1137/0611010]
• 54: Joseph W. H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review, v.34 n.1, p.82-109, March 1992 [doi>10.1137/1034004]
• 55: Pontus Matstoms, Sparse QR factorization in MATLAB, ACM Transactions on Mathematical Software (TOMS), v.20 n.1, p.136-159, March 1994 [doi>10.1145/174603.174408]
• 56: Esmond G. Ng , Padma Raghavan, Performance of Greedy Ordering Heuristics for Sparse Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.902-914, Oct. 1999 [doi>10.1137/S0895479897319313]
• 57: Edward Rothberg , Stanley C. Eisenstat, Node Selection Strategies for Bottom-Up Sparse Matrix Ordering, SIAM Journal on Matrix Analysis and Applications, v.19 n.3, p.682-695, July 1998 [doi>10.1137/S0895479896302692]
• 58: 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.
• 59: Yannakakis, M. 1981. Computing the minimum fill-in is NP-Complete. SIAM J. Alg. Disc. Meth. 2, 77--79.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis; Efficiency

General Terms:
Algorithms, Experimentation, Performance

Keywords:
linear equations, multifrontal method, ordering methods, sparse nonsymmetric matrices