research-article

Scaling and pivoting in an out-of-core sparse direct solver

Author:

Jennifer A. ScottAuthors Info & Claims

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

Article No.: 19, Pages 1 - 23

https://doi.org/10.1145/1731022.1731029

Published: 23 April 2010 Publication History

Abstract

Out-of-core sparse direct solvers reduce the amount of main memory needed to factorize and solve large sparse linear systems of equations by holding the matrix data, the computed factors, and some of the work arrays in files on disk. The efficiency of the factorization and solution phases is dependent upon the number of entries in the factors. For a given pivot sequence, the level of fill in the factors beyond that predicted on the basis of the sparsity pattern alone depends on the number of pivots that are delayed (i.e., the number of pivots that are used later than expected because of numerical stability considerations). Our aim is to limit the number of delayed pivots, while maintaining robustness and accuracy. In this article, we consider a new out-of-core multifrontal solver HSL_MA78 from the HSL mathematical software library that is designed to solve the unsymmetric sparse linear systems that arise from finite element applications. We consider how equilibration can be built into the solver without requiring the system matrix to be held in main memory. We also examine the effects of different pivoting strategies, including threshold partial pivoting, threshold rook pivoting, and static pivoting. Numerical experiments on problems arising from a range of practical applications illustrate the importance of scaling and show that, in some cases, rook pivoting can be more efficient than partial pivoting in terms of both the factorization time and the sparsity of the computed factors.

References

[1]

Arioli, M., Duff, I. S., Gratton, S., and Pralet, S. 2007. A note on GMRES preconditioned by a perturbed LDL^T decomposition with static pivoting. SIAM J. Sci. Comput. 29, 5, 2024--2044.

Digital Library

[2]

Chang, X.-W. 2002. Some features of Gaussian elimination with rook pivoting. BIT 42, 66--83.

[3]

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

Digital Library

[4]

Davis, T. and Duff, I. 1997. An unsymmetric-pattern multifrontal method for sparse LU factorization. SIAM J. Matrix Anal. Appl. 18, 140--158.

Digital Library

[5]

Dongarra, J., Du Croz, J., Duff, I. S., and Hammarling, S. 1990. A set of Level 3 basic linear algebra subprograms. ACM Trans. Math. Softw. 16, 1, 1--17.

Digital Library

[6]

Dongarra, J., Du Croz, J., Duff, I. S., and Hammarling, S. 1998. An extended set of Fortran basic linear algebra subprograms. ACM Trans. Math. Softw. 14, 1, 1--17.

Digital Library

[7]

Duff, I. 1984. Design features of a frontal code for solving sparse unsymmetric linear systems out-of-core. SIAM J. Sci. Comput. 5, 270--280.

[8]

Duff, I. 2004. MA57—a new code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30, 118--144.

Digital Library

[9]

Duff, I. 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.

Digital Library

[10]

Duff, I. and Pralet, S. 2005. Strategies for scaling and pivoting for sparse symmetric indefinite problems. SIAM J. Matrix Anal. Appl. 27, 313--340.

Digital Library

[11]

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

Digital Library

[12]

Duff, I. and Scott, J. 1996. The design of a new frontal code for solving sparse unsymmetric systems. ACM Trans. Math. Softw. 22, 1, 30--45.

Digital Library

[13]

Foster, L. 1997. The growth factor and efficiency of Gaussian elimination with rook pivoting. J. Comput. Appl. Math. 86, 177--194.

Digital Library

[14]

Gill, P., Murray, W., and Saunders, M. 2005. SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 99--131.

Digital Library

[15]

Higham, N. and Higham, D. 1989. Large growth factors in Gaussian elimination with pivoting. SIAM J. Matrix Anal. Appl. 10, 155--164.

Digital Library

[16]

HSL. 2007. A collection of Fortran codes for large-scale scientific computation. http://www.cse.stfc.ac.uk/nag/hsl/.

[17]

Irons, B. 1970. A frontal solution program for finite-element analysis. Int. J. Numer. Meth. Eng. 2, 5--32.

[18]

Li, X. and Demmel, J. 1998. Making sparse Gaussian elimination scalable by static pivoting. In Proceedings of the Conference on Supercomputing.

Digital Library

[19]

Neal, L. and Poole, G. 1992. A geometric analysis of Gaussian elimination, II. Lin. Alg. Appl. 173, 239--264.

[20]

O'Sullivan, M. and Saunders, M. 2002. Sparse rank-revealing LU factorization (via threshold complete pivoting and threshold rook pivoting). Householder Symposium XV on Numerical Linear Algebra. http://www.stanford.edu/group/SOL/talks.html.

[21]

Poole, G. and Neal, L. 2000. The rook's pivoting strategy. J. Comp. Appl. Math. 123, 353--369.

Digital Library

[22]

Reid, J. and Scott, J. 2009a. Algorithm 891: A Fortran virtual memory system. ACM Trans. Math. Softw. 36, 1, Article 5.

Digital Library

[23]

Reid, J. and Scott, J. 2009b. An efficient out-of-core multifrontal solver for large-scale unsymmetric element problems. Int. J. Numer. Meth. Eng. 77, 7, 901--921.

[24]

Reid, J. and Scott, J. 2009c. An out-of-core sparse Cholesky solver. ACM Trans. Math. Softw. 36, 2, Article 9.

Digital Library

[25]

Rothberg, E. and Schreiber, R. 1999. Efficient methods for out-of-core sparse Cholesky factorization. SIAM J. Sci. Comput. 21, 129--144.

Digital Library

[26]

Rotkin, V. and Toledo, S. 2004. The design and implementation of a new out-of-core sparse Cholesky factorization method. ACM Trans. Math. Softw. 30, 1, 19--46.

Digital Library

[27]

Ruiz, D. 2001. A scaling algorithm to equilibrate both rows and columns norms in matrices. Tech. rep. RAL-TR-2001-034. Rutherford Appleton Laboratory, Chilton, U.K.

[28]

Scott, J. 2006. A frontal solver for the 21st century. Comm. Numer. Meth. Eng. 22, 1015--1029.

[29]

Skeel, R. 1979. Scaling for numerical stability in Gaussian elimination. J. ACM 26, 494--526.

Digital Library

Cited By

Grubišić LLacmanović DPalaversa MPrebeg PTambača J(2022)An Open-Source Processing Pipeline for Quad-Dominant Mesh Generation for Class-Compliant Ship Structural AnalysisJournal of Marine Science and Engineering10.3390/jmse1002020910:2(209)Online publication date: 4-Feb-2022
https://doi.org/10.3390/jmse10020209
Davis TRajamanickam SSid-Lakhdar W(2016)A survey of direct methods for sparse linear systemsActa Numerica10.1017/S096249291600007625(383-566)Online publication date: 23-May-2016
https://doi.org/10.1017/S0962492916000076
Torres EChu YPark J(2015)Accuracy Enhanced Distributed Sparse Matrix Solver with Block-Based Pivoting for Large Linear Systems2015 IEEE 12th Intl Conf on Ubiquitous Intelligence and Computing and 2015 IEEE 12th Intl Conf on Autonomic and Trusted Computing and 2015 IEEE 15th Intl Conf on Scalable Computing and Communications and Its Associated Workshops (UIC-ATC-ScalCom)10.1109/UIC-ATC-ScalCom-CBDCom-IoP.2015.151(758-763)Online publication date: Aug-2015
https://doi.org/10.1109/UIC-ATC-ScalCom-CBDCom-IoP.2015.151
Show More Cited By

Index Terms

Scaling and pivoting in an out-of-core sparse direct solver
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Numerical differentiation
  2. Mathematical software
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Random Matrices Generating Large Growth in LU Factorization with Pivoting

We identify a class of random, dense, $n\times n$ matrices for which LU factorization with any form of pivoting produces a growth factor typically of size at least $n/(4 \log n)$ for large $n$. The condition number of the matrices can be arbitrarily chosen, ...
An out-of-core sparse Cholesky solver

Direct methods for solving large sparse linear systems of equations are popular because of their generality and robustness. Their main weakness is that the memory they require usually increases rapidly with problem size. We discuss the design and ...
A Supernodal Approach to Sparse Partial Pivoting

We investigate several ways to improve the performance of sparse LU factorization with partial pivoting, as used to solve unsymmetric linear systems. We introduce the notion of unsymmetric supernodes to perform most of the numerical computation in dense ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 37, Issue 2

April 2010

281 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1731022

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 2010

Accepted: 01 November 2009

Revised: 01 February 2009

Received: 01 July 2008

Published in TOMS Volume 37, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Engineering and Physical Sciences Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
301
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Grubišić LLacmanović DPalaversa MPrebeg PTambača J(2022)An Open-Source Processing Pipeline for Quad-Dominant Mesh Generation for Class-Compliant Ship Structural AnalysisJournal of Marine Science and Engineering10.3390/jmse1002020910:2(209)Online publication date: 4-Feb-2022
https://doi.org/10.3390/jmse10020209
Davis TRajamanickam SSid-Lakhdar W(2016)A survey of direct methods for sparse linear systemsActa Numerica10.1017/S096249291600007625(383-566)Online publication date: 23-May-2016
https://doi.org/10.1017/S0962492916000076
Torres EChu YPark J(2015)Accuracy Enhanced Distributed Sparse Matrix Solver with Block-Based Pivoting for Large Linear Systems2015 IEEE 12th Intl Conf on Ubiquitous Intelligence and Computing and 2015 IEEE 12th Intl Conf on Autonomic and Trusted Computing and 2015 IEEE 15th Intl Conf on Scalable Computing and Communications and Its Associated Workshops (UIC-ATC-ScalCom)10.1109/UIC-ATC-ScalCom-CBDCom-IoP.2015.151(758-763)Online publication date: Aug-2015
https://doi.org/10.1109/UIC-ATC-ScalCom-CBDCom-IoP.2015.151
Saule EAktulga HYang CNg EÇatalyürek Ü(2015)An Out-of-Core Task-based Middleware for Data-Intensive Scientific ComputingHandbook on Data Centers10.1007/978-1-4939-2092-1_22(647-667)Online publication date: 17-Mar-2015
https://doi.org/10.1007/978-1-4939-2092-1_22
Reid JScott J(2012)Partial factorization of a dense symmetric indefinite matrixACM Transactions on Mathematical Software10.1145/2049673.204967438:2(1-19)Online publication date: 5-Jan-2012
https://dl.acm.org/doi/10.1145/2049673.2049674
Zhou ZSaule EAktulga HYang CNg EMaris PVary JCatalyurek U(2012)An Out-of-Core Dataflow Middleware to Reduce the Cost of Large Scale Iterative SolversProceedings of the 2012 41st International Conference on Parallel Processing Workshops10.1109/ICPPW.2012.13(71-80)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1109/ICPPW.2012.13

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