article
Author: Anshul Gupta
ACM Transactions on Mathematical Software (TOMS), Volume 28, Issue 3
Pages 301 - 324
Published: 01 September 2002 Publication History
- 58citation
- 998
- Downloads
Metrics
Total Citations58Total Downloads998Last 12 Months20
Last 6 weeks0
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
Get Access
- Get Access
- References
- Media
- Tables
- Share
Abstract
During the past few years, algorithmic improvements alone have reduced the time required for the direct solution of unsymmetric sparse systems of linear equations by almost an order of magnitude. This paper compares the performance of some well-known software packages for solving general sparse systems. In particular, it demonstrates the consistently high level of performance achieved by WSMP---the most recent of such solvers. It compares the various algorithmic components of these solvers and discusses their impact on solver performance. Our experiments show that the algorithmic choices made in WSMP enable it to run more than twice as fast as the best among similar solvers and that WSMP can factor some of the largest sparse matrices available from real applications in only a few seconds on a 4-CPU workstation. Thus, the combination of advances in hardware and algorithms makes it possible to solve those general sparse linear systems quickly and easily that might have been considered too large until recently.
References
[1]
Amestoy, P. R., Davis, T. A., and Duff, I. S. 1996. An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17, 4, 886--905.
[2]
Amestoy, P. R. and Duff, I. S. 1989. Vectorization of a multiprocessor multifrontal code. Int. J. Supercomputer Appl. 3, 41--59.
[3]
Amestoy, P. R. and Duff, I. S. 1993. Memory management issues in sparse multifrontal methods on multiprocessors. I. J. Supercomputer Appl. 7, 64--82.
[4]
Amestoy, P. R., Duff, I. S., and L'Excellent, J. Y. 2000. Multifrontal parallel distributed symmetric and unsymmetric solvers. Computational Methods in Applied Mechanical Engineering 184, 501--520.
[5]
Amestoy, P. R., Duff, I. S., Koster, J., and L'Excellent, J. Y. 2001a. A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 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, 1--34.
[7]
Amestoy, P. R. and Puglisi, C. 2000. An unsymmetrized multifrontal LU factorization. Tech. Rep. RT/APO/00/3, ENSEEIHT-IRIT, Toulouse, France. Also available as Tech. Rep. 46474 from Lawrence Berkeley National Laboratory.
[8]
Ashcraft, C. and Grimes, R. G. 1999. SPOOLES: An object-oriented sparse matrix library. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing.
[9]
Ashcraft, C. and Liu, J. W.-H. 1996. Robust ordering of sparse matrices using multisection. Tech. Rep. CS 96-01, Department of Computer Science, York University, Ontario, Canada.
[10]
Cosnard, M. and Grigori, L. 2000. Using postordering and static symbolic factorization for parallel sparse LU. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS).
[11]
Davis, T. A. 2002. UMFPACK V3.2, an unsymmetric-pattern multifrontal method with a column pre-ordering strategy. Tech. Rep. TR-02-2002, Computer and Information Sciences Department, University of Florida, Gainesville, FL.
[12]
Davis, T. A. and Duff, I. S. 1997a. A combined unifrontal/multifrontal method or unsymmetric sparse matrices. ACM Trans. Math. Softw. 25, 1, 1--19.
[13]
Davis, T. A. and Duff, I. S. January 1997b. An unsymmetric-pattern multifrontal method for sparse LU factorization. SIAM J. Matrix Anal. Appl. 18, 1, 140--158.
[14]
Davis, T. A., Gilbert, J. R., Larimore, S. I., and Ng, E. G.-Y. 2000. A column approximate minimum degree ordering algorithm. Tech. Rep. TR-00-005, Computer and Information Sciences Department, University of Florida, Gainesville, FL.
[15]
Demmel, J. W., Gilbert, J. R., and Li, X. S. 1999. An asynchronous parallel supernodal algorithm for sparse Gaussian elimination. SIAM J. Matrix Anal. Appl. 20, 4, 915--952.
[16]
Duff, I. S., Erisman, A. M., and Reid, J. K. 1990. Direct Methods for Sparse Matrices. Oxford University Press, Oxford, UK.
[17]
Duff, I. S. and Koster, J. 1999. The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM J. Matrix Anal. Appl. 20, 4, 889--901.
[18]
Duff, I. S. and Koster, J. 2001. On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM J. Matrix Anal. Appl. 22, 4, 973--996.
[19]
Duff, I. S. and Reid, J. K. 1984. The multifrontal solution of unsymmetric sets of linear equations. SIAM J. Sci. Stat. Comput. 5, 3, 633--641.
[20]
Duff, I. S. and Reid, J. K. 1993. MA48, a Fortran code for direct solution of sparse unsymmetric linear systems of equations. Tech. Rep. RAL-93-072, Rutherford Appleton Laboratory.
[21]
Eisenstat, S. C. and Liu, J. W.-H. 1993. Exploiting structural symmetry in a sparse partial pivoting code. SIAM J. Sci. Comput. 14, 1, 253--257.
[22]
George, A. and Liu, J. W-H. 1978. Nested dissection of a regular finite element mesh. SIAM J. Num. Anal. 15, 1053--1069.
[23]
George, A. and Liu, J. W.-H. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, NJ.
[24]
George, A. and Ng, E. 1985. An implementation of Gaussian elimination with partial pivoting for sparse systems. SIAM J. Sci. Stat. Comput. 6, 2, 390--409.
[25]
Gilbert, J. R. and Liu, J. W.-H. 1993. Elimination structures for unsymmetric sparse LU factors. SIAM J. Matrix Anal. and Appl. 14, 2, 334--352.
[26]
Grund, F. 1998. Direct linear solver for vector and parallel computers. Tech. Rep. Preprint No./ 415, Weierstrass Institute for Applied Analysis and Stochastics.
[27]
Gupta, A. 2001a. A high-performance GEPP-based sparse solver. In Proceedings of PARCO. http://www.cs.umn.edu/∼agupta/doc/parco-01.ps.
[28]
Gupta, A. August 1, 2001b. Improved symbolic and numerical factorization algorithms for unsymmetric sparse matrices. Tech. Rep. RC 22137 (99131), IBM T. J. Watson Research Center, Yorktown Heights, NY. http://www.cs.umn.edu/∼agupta/doc/sparse-unsymm.ps.
[29]
Gupta, A. 1997. Fast and effective algorithms for graph partitioning and sparse matrix ordering. IBM J. Res. Devel. 41, 1/2, 171--183.
[30]
Gupta, A. 2000. WSMP: Watson sparse matrix package (Part-II: direct solution of general sparse systems). Tech. Rep. RC 21888 (98472), IBM T. J. Watson Research Center, Yorktown Heights, NY. http://www.cs.umn.edu/∼agupta/wsmp.html.
[31]
Gupta, A. and Muliadi, Y. 2001. An experimental comparison of some direct sparse solver packages. In Proceedings of International Parallel and Distributed Processing Symposium.
[32]
Gupta, A. and Ying, L. 1999. On algorithms for finding maximum matchings in bipartite graphs. Tech. Rep. RC 21576 (97320), IBM T. J. Watson Research Center, Yorktown Heights, NY.
[33]
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, Gainsville, FL.
[34]
HSL. 2000. A collection of Fortran codes for scientific computation. Tech. rep., AEA Technology Engineering Software, Oxfordshire, England. http://www.cse.clrc.ac.uk/Activity/HSL.
[35]
Karypis, G. and Kumar, V. 1999. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 1.
[36]
Li, X. S. and Demmel, J. W. 1998. Making sparse Gaussian elimination scalable by static pivoting. In Supercomputing '98 Proceedings.
[37]
Li, X. S. and Demmel, J. W. 1999. A scalable sparse direct solver using static pivoting. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing.
[38]
Lipton, R. J., Rose, D. J., and Tarjan, R. E. 1979. Generalized nested dissection. SIAM J. Num. Anal. 16, 346--358.
[39]
Liu, J. W.-H. 1985. Modification of the minimum degree algorithm by multiple elimination. ACM Trans. Math. Softw. 11, 141--153.
[40]
Liu, J. W.-H. 1990. The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11, 134--172.
[41]
Liu, J. W.-H. 1992. The multifrontal method for sparse matrix solution: Theory and practice. SIAM Review 34, 82--109.
[42]
Schenk, O., Fichtner, W., and Gartner, K. November 2000a. Scalable parallel sparse LU factorization with a dynamical supernode pivoting approach in semiconductor device simulation. Tech. Rep. 2000/10, Integrated Systems Laboratory, Swiss Federal Institute of Technology, Zurich.
[43]
Schenk, O., Gartner, K., Fichtner, W., and Stricker, A. 2000b. PARDISO: A high-performance serial and parallel sparse linear solver in semiconductor device simulation. Future Generation Computer Systems 789, 1--9.
[44]
Shen, K., Yang, T., and Jiao, X. 2001. S+: Efficient 2D sparse LU factorization on parallel machines. SIAM J. Matrix Anal. Appl. 22, 1, 282--305.
[45]
Tarjan, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 146--160.
Cited By
View all
- Dutta SJog C(2023)A monolithic, finite element-based strategy for solving fluid structure interaction problems coupled with electrostaticsComputers & Fluids10.1016/j.compfluid.2023.105966264(105966)Online publication date: Oct-2023
- Dutta SAgrawal MJog C(2022)A monolithic, ALE finite-element-based strategy for partially submerged solids in an incompressible fluid flow using the mortar methodJournal of Fluids and Structures10.1016/j.jfluidstructs.2022.103780115(103780)Online publication date: Nov-2022
- Santhosh AJog C(2022)A monolithic finite element strategy for conjugate heat transferSādhanā10.1007/s12046-022-01991-347:4Online publication date: 1-Nov-2022
- Show More Cited By
Index Terms
Recent advances in direct methods for solving unsymmetric sparse systems of linear equations
Computing methodologies
Symbolic and algebraic manipulation
Symbolic and algebraic algorithms
Linear algebra algorithms
Mathematics of computing
Mathematical analysis
Numerical analysis
Computations on matrices
Recommendations
- Improved Symbolic and Numerical Factorization Algorithms for Unsymmetric Sparse Matrices
We present algorithms for the symbolic and numerical factorization phases in the direct solution of sparse unsymmetric systems of linear equations. We have modified a classical symbolic factorization algorithm for unsymmetric matrices to inexpensively ...
Read More
- A Shared- and distributed-memory parallel general sparse direct solver
An important recent development in the area of solution of general sparse systems of linear equations has been the introduction of new algorithms that allow complete decoupling of symbolic and numerical phases of sparse Gaussian elimination with partial ...
Read More
- The Theory of Elimination Trees for Sparse Unsymmetric Matrices
The elimination tree of a symmetric matrix plays an important role in sparse matrix factorization. By using paths instead of edges to define the tree, we generalize this structure to unsymmetric matrices while retaining many of its properties. If we use ...
Read More
Comments
Information & Contributors
Information
Published In
ACM Transactions on Mathematical Software Volume 28, Issue 3
September 2002
91 pages
ISSN:0098-3500
EISSN:1557-7295
DOI:10.1145/569147
Issue’s Table of Contents
Copyright © 2002 ACM.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 September 2002
Published inTOMSVolume 28, Issue 3
Permissions
Request permissions for this article.
Check for updates
Author Tags
- Multifrontal Method
- Parallel Sparse Solvers
- Sparse LU Decomposition
- Sparse Matrix Factorization
Qualifiers
- Article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
58
Total Citations
998
Total Downloads
- Downloads (Last 12 months)20
- Downloads (Last 6 weeks)0
Other Metrics
View Author Metrics
Citations
Cited By
View all
- Dutta SJog C(2023)A monolithic, finite element-based strategy for solving fluid structure interaction problems coupled with electrostaticsComputers & Fluids10.1016/j.compfluid.2023.105966264(105966)Online publication date: Oct-2023
- Dutta SAgrawal MJog C(2022)A monolithic, ALE finite-element-based strategy for partially submerged solids in an incompressible fluid flow using the mortar methodJournal of Fluids and Structures10.1016/j.jfluidstructs.2022.103780115(103780)Online publication date: Nov-2022
- Santhosh AJog C(2022)A monolithic finite element strategy for conjugate heat transferSādhanā10.1007/s12046-022-01991-347:4Online publication date: 1-Nov-2022
- Farea AÇelebi M(2022)On the evaluation of general sparse hybrid linear solversNumerical Linear Algebra with Applications10.1002/nla.246930:2Online publication date: 28-Sep-2022
- Potghan NJog C(2022)An ALE‐based finite element strategy for modeling compressible two‐phase flowsInternational Journal for Numerical Methods in Fluids10.1002/fld.513494:12(2040-2086)Online publication date: 24-Aug-2022
- Hoelzl MHuijsmans GPamela SBécoulet MNardon EArtola FNkonga BAtanasiu CBandaru VBhole ABonfiglio DCathey ACzarny ODvornova AFehér TFil AFranck EFutatani SGruca MGuillard HHaverkort JHolod IHu DKim SKorving SKos LKrebs IKripner LLatu GLiu FMerkel PMeshcheriakov DMitterauer VMochalskyy SMorales JNies RNikulsin NOrain FPratt JRamasamy RRamet PReux CSärkimäki KSchwarz NSingh Verma PSmith SSommariva CStrumberger Evan Vugt DVerbeek MWesterhof EWieschollek FZielinski J(2021)The JOREK non-linear extended MHD code and applications to large-scale instabilities and their control in magnetically confined fusion plasmasNuclear Fusion10.1088/1741-4326/abf99f61:6(065001)Online publication date: 20-May-2021
- (2021)BibliographyModeling of Resistivity and Acoustic Borehole Logging Measurements Using Finite Element Methods10.1016/B978-0-12-821454-1.00019-4(277-293)Online publication date: 2021
- Pardo DMatuszyk PPuzyrev VTorres-Verdín CNam MCalo V(2021)Parallel implementationModeling of Resistivity and Acoustic Borehole Logging Measurements Using Finite Element Methods10.1016/B978-0-12-821454-1.00017-0(257-264)Online publication date: 2021
- Pardo DMatuszyk PPuzyrev VTorres-Verdín CNam MCalo V(2021)Linear solversModeling of Resistivity and Acoustic Borehole Logging Measurements Using Finite Element Methods10.1016/B978-0-12-821454-1.00016-9(247-256)Online publication date: 2021
- Dutta SJog C(2021)A monolithic arbitrary Lagrangian–Eulerian‐based finite element strategy for fluid–structure interaction problems involving a compressible fluidInternational Journal for Numerical Methods in Engineering10.1002/nme.6783122:21(6037-6102)Online publication date: 30-Aug-2021
- 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.
Sign in
Full Access
Get this Article
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderMedia
Figures
Other
Tables
