article

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

Author:

Timothy A. DavisAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 30, Issue 2

Pages 165 - 195

https://doi.org/10.1145/992200.992205

Published: 01 June 2004 Publication History

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]

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.

[2]

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.

[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]

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.

[6]

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.

[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]

Amestoy, P. R. and Puglisi, C. 2002. An unsymmetrized multifrontal LU factorization. SIAM J. Matrix Anal. Applic. 24, 553--569.

[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]

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.

[11]

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.

[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]

Brainman, I. and Toledo, S. 2002. Nested-dissection orderings for sparse LU with partial pivoting. SIAM J. Matrix Anal. Applic. 23, 998--1012.

[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]

Coleman, T. F., Edenbrandt, A., and Gilbert, J. R. 1986. Predicting fill for sparse orthogonal factorization. J. ACM 33, 517--532.

[16]

Davis, T. A. University of Florida sparse matrix collection. www.cise.ufl.edu/research/sparse.

[17]

Davis, T. A. 2004. Algorithm 832: UMFPACK V4.3, an unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30, 2.

[18]

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.

[19]

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.

[20]

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.

[21]

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.

[22]

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.

[23]

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.

[24]

Duff, I. S. 1977. On permutations to block triangular form. J. Inst. of Math. Appl. 19, 339--342.

[25]

Duff, I. S. 1981. On algorithms for obtaining a maximum transversal. ACM Trans. Math. Softw. 7, 315--330.

[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]

Duff, I. S., Erisman, A. M., and Reid, J. K. 1986. Direct Methods for Sparse Matrices. London: Oxford Univ. Press.

[29]

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.

[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]

Duff, I. S. and Reid, J. K. 1983a. The multifrontal solution of indefinite sparse symmetric linear systems. ACM Trans. Math. Softw. 9, 302--325.

[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]

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.

[35]

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.

[36]

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.

[37]

George, A. and Liu, J. W. H. 1981. Computer Solution of Large Sparse Positive Definite Systems. Englewood Cliffs, New Jersey: Prentice-Hall.

[38]

George, A. and Liu, J. W. H. 1989. The evolution of the minimum degree ordering algorithm. SIAM Rev. 31, 1, 1--19.

[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]

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.

[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]

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.

[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]

Gupta, A. 2002. Improved symbolic and numerical factorization algorithms for unsymmetric sparse matrices. SIAM J. Matrix Anal. Applic. 24, 529--552.

[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]

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.

[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]

Heath, M. T. and Raghavan, P. 1995. A Cartesian parallel nested dissection algorithm. SIAM J. Matrix Anal. Applic. 16, 1, 235--253.

[50]

Hendrickson, B. and Rothberg, E. 1999. Improving the runtime and quality of nested dissection ordering. SIAM J. Sci. Comput. 20, 468--489.

[51]

Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359--392.

[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]

Liu, J. W. H. 1990. The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Applic. 11, 1, 134--172.

[54]

Liu, J. W. H. 1992. The multifrontal method for sparse matrix solution: Theory and practice. SIAM Rev. 34, 1, 82--109.

[55]

Matstoms, P. 1994. Sparse QR factorization in MATLAB. ACM Trans. Math. Softw. 20, 1, 136--159.

[56]

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.

[57]

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.

[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.

Cited By

Annamalai BVenugopal P(2024)Finite element analysis of the nonlocal diffusion effect in a two-species chemotaxis systemDiscrete and Continuous Dynamical Systems - S10.3934/dcdss.2024164(0-0)Online publication date: 2024
https://doi.org/10.3934/dcdss.2024164
Manimaran JBaskar AParthiban VShangerganesh L(2024)Analytical and numerical studies of a cancer invasion model with nonlocal diffusionJournal of Nonlinear, Complex and Data Science10.1515/jncds-2023-0021Online publication date: 8-Aug-2024
https://doi.org/10.1515/jncds-2023-0021
Middleton SDimbath EMaddipati VPeach MJu AGeorge SVadati A(2024)A Multi-Scale Computer Model of Mechanical Ventilation for COVID-19 PatientsJournal of Multiscale Modelling10.1142/S175697372350010514:04Online publication date: 8-Feb-2024
https://doi.org/10.1142/S1756973723500105
Show More Cited By

Index Terms

A column pre-ordering strategy for the unsymmetric-pattern multifrontal method
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
  2. Mathematical software

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

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 30, Issue 2

June 2004

142 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/992200

Issue’s Table of Contents

Copyright © 2004 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2004

Published in TOMS Volume 30, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

275
Total Citations
View Citations
1,925
Total Downloads

Downloads (Last 12 months)59
Downloads (Last 6 weeks)7

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Annamalai BVenugopal P(2024)Finite element analysis of the nonlocal diffusion effect in a two-species chemotaxis systemDiscrete and Continuous Dynamical Systems - S10.3934/dcdss.2024164(0-0)Online publication date: 2024
https://doi.org/10.3934/dcdss.2024164
Manimaran JBaskar AParthiban VShangerganesh L(2024)Analytical and numerical studies of a cancer invasion model with nonlocal diffusionJournal of Nonlinear, Complex and Data Science10.1515/jncds-2023-0021Online publication date: 8-Aug-2024
https://doi.org/10.1515/jncds-2023-0021
Middleton SDimbath EMaddipati VPeach MJu AGeorge SVadati A(2024)A Multi-Scale Computer Model of Mechanical Ventilation for COVID-19 PatientsJournal of Multiscale Modelling10.1142/S175697372350010514:04Online publication date: 8-Feb-2024
https://doi.org/10.1142/S1756973723500105
Angelin Shena SManimaran JSethukumarasamy KShangerganesh L(2024)Convergence of BDF2-Galerkin finite element scheme for cancer invasion modelThe European Physical Journal Special Topics10.1140/epjs/s11734-024-01272-6Online publication date: 12-Aug-2024
https://doi.org/10.1140/epjs/s11734-024-01272-6
Manimaran JShangerganesh LZaky MAkgül AHendy A(2024)Numerical discretization for Fisher-Kolmogorov problem with nonlocal diffusion based on mixed Galerkin BDF2 schemeApplied Numerical Mathematics10.1016/j.apnum.2024.02.018201(145-158)Online publication date: Jul-2024
https://doi.org/10.1016/j.apnum.2024.02.018
Feng YMena JYang HWang HJeremić B(2024)Domain specific language for finite element modeling and simulationAdvances in Engineering Software10.1016/j.advengsoft.2024.103666193(103666)Online publication date: Jul-2024
https://doi.org/10.1016/j.advengsoft.2024.103666
Botchev M(2024)On convergence of waveform relaxation for nonlinear systems of ordinary differential equationsCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-024-00578-061:2Online publication date: 5-Jun-2024
https://dl.acm.org/doi/10.1007/s10092-024-00578-0
Gonçalves JSilva E(2023)Salt reconstruction in full-waveform inversion using topology optimization techniquesGeophysical Journal International10.1093/gji/ggad150234:2(1484-1504)Online publication date: 3-Apr-2023
https://doi.org/10.1093/gji/ggad150
Rodrigo CGaspar FAdler JHu XOhm PZikatanov L(2023)Parameter-robust preconditioners for Biot’s modelSeMA Journal10.1007/s40324-023-00336-281:1(51-80)Online publication date: 5-Aug-2023
https://doi.org/10.1007/s40324-023-00336-2
Botchev M(2022)Solving anisotropic heat equations by exponential shift-and-invert and polynomial Krylov subspace methodsKeldysh Institute Preprints10.20948/prepr-2022-4(1-17)Online publication date: 2022
https://doi.org/10.20948/prepr-2022-4
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents