[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Numerically Aware Orderings for Sparse Symmetric Indefinite Linear Systems

Published: 16 August 2017 Publication History

Abstract

Sparse symmetric indefinite problems arise in a large number of important application areas; they are often solved through the use of an LDLT factorization via a sparse direct solver. While for many problems prescaling the system matrix A is sufficient to maintain stability of the factorization, for a small but important fraction of problems numerical pivoting is required. Pivoting often incurs a significant overhead, and consequently, a number of techniques have been proposed to try and limit the need for pivoting. In particular, numerically aware ordering algorithms may be used, that is, orderings that depend not only on the sparsity pattern of A but also on the values of its (scaled) entries.
Current approaches identify large entries of A and symmetrically permute them onto the subdiagonal, where they can be used as part of a 2 × 2 pivot. This is numerically effective, but the fill in the factor L and hence the runtime of the factorization and subsequent triangular solves may be significantly increased over a standard ordering if no pivoting is required.
We present a new algorithm that combines a matching-based approach with a numerically aware nested dissection ordering. Numerical comparisons with current approaches for some tough symmetric indefinite problems are given.

References

[1]
P. R. Amestoy, T. A. Davis, and I. S. Duff. 2004. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Trans. Math. Software 30, 3 (2004), 381--388
[2]
C. Ashcraft, I. S. Duff, J. D. Hogg, J. A. Scott, and H. S. Thorne. 2016. Nested Dissection Revisited. Technical Report RAL-TR-2016-4. STFC Rutherford Appleton Laboratory. http://purl.org/net/epubs/work/24733312.
[3]
C. Ashcraft, R. G. Grimes, and J. G. Lewis. 1999. Accurate symmetric indefinite linear equation solvers. SIAM J. Matrix Analysis Appl. 20, 2 (1999), 513--561. 0895-4798
[4]
J. R. Bunch and L. Kaufman. 1977. Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comp. 31 (1977), 163--179.
[5]
I. S Duff. 2004. MA57—A code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Software 30, 2 (2004), 118--144.
[6]
I. S. Duff and J. R. Gilbert. 2002. Maximum-weighted matching and block pivoting for symmetric indefinite systems. In Abstract Book of Householder Symposium XV. 73--75.
[7]
I. S. Duff, N. I. M. Gould, J. K. Reid, J. A. Scott, and K. Turner. 1991. Factorization of sparse symmetric indefinite matrices. IMA J. Numer. Anal. 11 (1991), 181--2044.
[8]
I. S. Duff and J. Koster. 1999. The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM J. Matrix Analysis Appl. 20, 4 (1999), 889--901.
[9]
I. S. Duff and S. Pralet. 2005. Strategies for scaling and pivoting for sparse symmetric indefinite problems. SIAM J. Matrix Analysis Appl. 27 (2005), 313--240.
[10]
A. George. 1973. Nested dissection of a regular finite-element mesh. SIAM J. Numer. Analysis 10 (1973), 345--363.
[11]
A. George and J. W. H. Liu. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, NJ.
[12]
A. Gupta. 2015. Private communication. (2015).
[13]
A. Gupta and H. Avron. 2013. WSMP: Watson Sparse Matrix Package. Part I - Direct Solution of Symmetric Systems. Version 13.06. Technical Report RC 21886. IBM T. J. Watson Research Center, Yorktown Heights, NY. http://www.research.ibm.com/projects/wsmp.
[14]
M. Hagemann and O. Schenk. 2006. Weighted matchings for preconditioning symmetric indefinite linear systems. SIAM J. Sci. Comput. 28, 2 (2006), 403--420.
[15]
B. Hendrickson and R. Leland. 1994. A multilevel algorithm for partitioning graphs. SIAM J. Sci. Comput. 16 (1994), 452--469.
[16]
B. Hendrickson and R. Leland. 1995. The Chaco Users Guide, Version 2.0. Technical Report SAND942692. Sandia National Laboratories, Albuquerque, NM.
[17]
J. D. Hogg. 2010. High Performance Cholesky and Symmetric Indefinte Factorizations with Applications. Ph.D. Dissertation. University of Edinburgh.
[18]
J. D. Hogg. 2016. A New Sparse LDLT Solver Using a Posteriori Threshold Pivoting. Technical Report RAL-TR-2016-017. STFC Rutherford Appleton Laboratory.
[19]
J. D. Hogg and J. A. Scott. 2011. HSL_MA97: A Bit-Compatible Multifrontal Code for Sparse Symmetric Systems. Technical Report RAL-TR-2011-024. STFC Rutherford Appleton Laboratory.
[20]
J. D. Hogg and J. A. Scott. 2013. Pivoting strategies for tough sparse indefinite systems. ACM Trans. Math. Software 40 (2013). Article 4, 19 pages.
[21]
J. D. Hogg and J. A. Scott. 2014. Compressed threshold pivoting for sparse symmetric indefinite systems. SIAM J. Matrix Analysis Appl. 35, 2 (2014), 783--817.
[22]
G. Karypis and V. Kumar. 1995. METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System. Technical Report TR 95-035. University of Minnesota.
[23]
G. Karypis and V. Kumar. 1998. METIS: A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices - Version 4.0. Retrieved from http://www-users.cs.umn.edu/∼karypis/metis/.
[24]
F. Pellegrini. 2012. SCOTCH 6.0. Retrieved from http://www.labri.fr/perso/pelegrin/scotch/.
[25]
O. Schenk and K. Gärtner. 2006. On fast factorization pivoting methods for symmetric indefinite systems. Electron. Trans. Numer. Analysis 23 (2006), 158--179.
[26]
O. Schenk, A. Wächter, and M. Hagemann. 2007. Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization. J. Comput. Optimization Appl. 36, 2--3 (2007), 321--341.
[27]
M. Yannakakis. 1981. Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2, 1 (1981), 77--79.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software
ACM Transactions on Mathematical Software  Volume 44, Issue 2
June 2018
242 pages
ISSN:0098-3500
EISSN:1557-7295
DOI:10.1145/3132683
Issue’s Table of Contents
This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 August 2017
Accepted: 01 May 2017
Revised: 01 April 2017
Received: 01 March 2016
Published in TOMS Volume 44, Issue 2

Check for updates

Author Tags

  1. Nested dissection
  2. numerically aware ordering
  3. sparse direct methods
  4. sparse matrix ordering
  5. sparse symmetric matrices

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

  • EPSRC

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 217
    Total Downloads
  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)1
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media