More Web Proxy on the site http://driver.im/

research-article

HSL_MI28: An Efficient and Robust Limited-Memory Incomplete Cholesky Factorization Code

Authors:

Jennifer Scott,

Miroslav TůmaAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 40, Issue 4

Article No.: 24, Pages 1 - 19

https://doi.org/10.1145/2617555

Published: 08 July 2014 Publication History

Abstract

This article focuses on the design and development of a new robust and efficient general-purpose incomplete Cholesky factorization package HSL_MI28, which is available within the HSL mathematical software library. It implements a limited memory approach that exploits ideas from the positive semidefinite Tismenetsky-Kaporin modification scheme and, through the incorporation of intermediate memory, is a generalization of the widely used ICFS algorithm of Lin and Moré. Both the density of the incomplete factor and the amount of memory used in its computation are under the user's control. The performance of HSL_MI28 is demonstrated using extensive numerical experiments involving a large set of test problems arising from a wide range of real-world applications. The numerical experiments are used to isolate the effects of scaling, ordering, and dropping strategies so as to assess their usefulness in the development of robust algebraic incomplete factorization preconditioners and to select default settings for HSL_MI28. They also illustrate the significant advantage of employing a modest amount of intermediate memory. Furthermore, the results demonstrate that, with limited memory, high-quality yet sparse general-purpose preconditioners are obtained. Comparisons are made with ICFS, with a level-based incomplete factorization code and, finally, with a state-of-the-art direct solver.

References

[1]

Patrick R. Amestoy, Timothy A. Davis, and Iain S. Duff. 2004. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 3, 381--388.

Digital Library

[2]

Owe Axelsson, Igor Kaporin, Igor Konshin, Andrey Kucherov, Maya Neytcheva, Ben Polman, and Alex Yeremin. 2000. Comparison of algebraic solution methods on a set of benchmark problems in linear elasticity. Final Report of the STW project NNS.4683. Department of Mathematics, University of Nijmegen.

[3]

Owe Axelsson and Niels Munksgaard. 1983. Analysis of incomplete factorizations with fixed storage allocation. In Preconditioning Methods: Analysis and Applications. Topics in Computational Mathematics, Vol. 1, Gordon & Breach, New York, 219--241.

[4]

Lourenco Beirão da Veiga, Vitaliy Gyrya, Konstantin Lipnikov, and Gianmarco Manzini. 2009. Mimetic finite difference method for the Stokes problem on polygonal meshes. J. Comput. Phys. 228, 19, 7215--7232.

Digital Library

[5]

Michele Benzi. 2002. Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 2, 418--477.

Digital Library

[6]

Michele Benzi, John C. Haws, and Miroslav Tůma. 2000. Preconditioning highly indefinite and nonsymmetric matrices. SIAM J. Sci. Comput. 22, 4, 1333--1353.

Digital Library

[7]

Michele Benzi and M. Tůma. 2003. A robust incomplete factorization preconditioner for positive definite matrices. Numer. Linear Algebra Appl. 10, 5--6, 385--400.

[8]

Elisabeth H. Cuthill and James McKee. 1969. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 24th National Conference of the ACM. ACM Press, 157--172.

Digital Library

[9]

Timothy A. Davis and Yifan Hu. 2011. The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw. 38, Article 1.

Digital Library

[10]

Elizabeth D. Dolan and Jorge J. Moré. 2002. Benchmarking optimization software with performance profiles. Math. Prog. 91, 2, 201--213.

[11]

Iain. S. Duff and Jacko Koster. 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

[12]

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

Digital Library

[13]

Roland W. Freund and Nöel M. Nachtigal. 1990. An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, part II. Tech. Rep., TR 90--46. RIACS, NASA Ames Research Center.

[14]

Thomas George, Anshul Gupta, and Vivek Sarin. 2009, revised 2011. An empirical analysis of the performance of preconditioners for SPD systems. Res. Rep. RC 24737, IBM.

[15]

Thomas George, Anshul Gupta, and Vivek Sarin. 2012. An empirical analysis of the performance of preconditioners for SPD systems. ACM Trans. Math. Softw. 38, Article 24.

Digital Library

[16]

Nicholas I. M. Gould, Yifan F. Hu, and Jennifer A. Scott. 2007. A numerical evaluation of sparse direct symmetric solvers for the solution of large sparse, symmetric linear systems of equations. ACM Trans. Math. Softw. 33, Article 10.

Digital Library

[17]

Nicholas I. M. Gould and Jennifer A. Scott. 2004. A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations. ACM Trans. Math. Softw. 30, 3, 300--325.

Digital Library

[18]

Anshul Gupta and Thomas George. 2010. Adaptive techniques for improving the performance of incomplete factorization preconditioning. SIAM J. Sci. Comput. 32, 1, 84--110.

Digital Library

[19]

Jonathan D. Hogg and Jennifer A. Scott. 2008. The effects of scalings on the performance of a sparse symmetric indefinite solver. Tech. Rep., RAL-TR-2008-007, Rutherford Appleton Laboratory.

[20]

Jonathan D. Hogg and Jennifer A. Scott. 2011. HSL_MA97: A bit-compatible multifrontal code for sparse symmetric systems. Tech. Rep., RAL-TR-2011-024, Rutherford Appleton Laboratory.

[21]

Jonathan D. Hogg and Jennifer A. Scott. 2014. Pivoting strategies for tough sparse indefinite systems. ACM Trans. Math. Softw. 40, 1, Article 4.

Digital Library

[22]

HSL. 2013. A collection of Fortran codes for large-scale scientific computation. http://www.hsl.rl.ac.uk.

[23]

David Hysom and Alex Pothen. 2001. A scalable parallel algorithm for incomplete factor preconditioning. SIAM J. Sci. Comput. 22, 6, 2194--2215.

Digital Library

[24]

Alan Jennings and George M. Malik. 1977. Partial elimination. J. Inst. Math. Appl. 20, 3, 307--316.

[25]

Alan Jennings and George M. Malik. 1978. The solution of sparse linear equations by the conjugate gradient method. Int. J. Numer. Methods Engrg. 12, 1, 141--158.

[26]

Mark T. Jones and Paul E. Plassmann. 1995a. Algorithm 740: Fortran subroutines to compute improved incomplete Cholesky factorizations. ACM Trans. Math. Softw. 21, 1, 18--19.

Digital Library

[27]

Mark T. Jones and Paul E. Plassmann. 1995b. An improved incomplete Cholesky factorization. ACM Trans. Math. Softw. 21, 1, 5--17.

Digital Library

[28]

Igor E. Kaporin. 1998. High quality preconditioning of a general symmetric positive definite matrix based on its U^TU+U^TR+R^TU decomposition. Numer. Linear Algebra Appl. 5, 6, 483--509.

[29]

George Karypis and Vipin Kumar. October 1997. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices (Version 3.0). Tech. Rep., University of Minnesota, Department of Computer Science and Army HPC Research Center.

[30]

Chih-Jen Lin and Jorge J. Moré. 1999. Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21, 1, 24--45.

Digital Library

[31]

Konstantin Lipnikov, Mikhail Shashkov, Daniil Svyatskiy, and Yuri Vassilevski. 2007. Monotone finite volume schemes for diffusion equations on unstructured triangular and shape-regular polygonal meshes. J. Comput. Phys. 227, 1, 492--512.

Digital Library

[32]

Konstantin Lipnikov, Daniil Svyatskiy, and Yuri Vassilevski. 2009. Interpolation-free monotone finite volume method for diffusion equations on polygonal meshes. J. Comput. Phys. 228, 3, 703--716.

Digital Library

[33]

Thomas A. Manteuffel. 1980. An incomplete factorization technique for positive definite linear systems. Math. Comp. 34, 150, 473--497.

[34]

John K. Reid and Jennifer A. Scott. 1999. Ordering symmetric sparse matrices for small profile and wavefront. Int. J. Numer. Methods Eng. 45, 1737--1755.

[35]

Daniel Ruiz. 2001. A scaling algorithm to equilibrate both rows and columns norms in matrices. Tech. Rep., RAL-TR-2001-034, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England.

[36]

Daniel Ruiz and Bora Uçar. 2011. A symmetry preserving algorithm for matrix scaling. Tech. Rep., INRIA RR-7552, INRIA, Grenoble, France.

[37]

Yousef Saad. 1994. ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl. 1, 4, 387--402.

[38]

Yousef Saad. 1996. Iterative Methods for Sparse Linear Systems. PWS Publishing Co., Boston.

Digital Library

[39]

Jennifer A. Scott and Miroslav Tůma. 2011. The importance of structure in incomplete factorization preconditioners. BIT 51, 2, 385--404.

[40]

Jennifer A. Scott and Miroslav Tůma. 2014. On positive semidefinite modification schemes for incomplete Cholesky factorization. SIAM J. Sci. Comput. 36, 2, A634--A667.

[41]

Scott W. Sloan. 1986. An algorithm for profile and wavefront reduction of sparse matrices. Int. J. Numer. Methods Eng. 23, 239--251.

[42]

Scott W. Sloan. 1989. A Fortran program for profile and wavefront reduction. Int. J. Numer. Methods Eng. 28, 2651--2679.

[43]

Made Suarjana and Kincho H. Law. 1995. A robust incomplete factorization based on value and space constraints. Int. J. Numer. Methods Eng. 38, 1703--1719.

[44]

Miron Tismenetsky. 1991. A new preconditioning technique for solving large sparse linear systems. Linear Algebra Appl. 154--156, 331--353.

[45]

Ichitaro Yamazaki, Zhaojun Bai, Wenbin Chen, and Richard Scalettar. 2009. A high-quality preconditioning technique for multi-length-scale symmetric positive definite linear systems. Numer. Math. Theory, Methods and Appl. 2, 4, 469--484.

Cited By

Scott JTůma M(2024)Avoiding Breakdown in Incomplete Factorizations in Low Precision ArithmeticACM Transactions on Mathematical Software10.1145/365115550:2(1-25)Online publication date: 12-Mar-2024
https://dl.acm.org/doi/10.1145/3651155
Aricò CHelmig RPuleo DSchneider M(2024)A new numerical mesoscopic scale one-domain approach solver for free fluid/porous medium interactionComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2023.116655419(116655)Online publication date: Feb-2024
https://doi.org/10.1016/j.cma.2023.116655
Fabian MShpiro BBaer R(2022)Linear Weak Scalability of Density Functional Theory Calculations without Imposing Electron LocalizationJournal of Chemical Theory and Computation10.1021/acs.jctc.1c0082918:4(2162-2170)Online publication date: 26-Mar-2022
https://doi.org/10.1021/acs.jctc.1c00829
Show More Cited By

Index Terms

HSL_MI28: An Efficient and Robust Limited-Memory Incomplete Cholesky Factorization Code
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

Recommendations

Symmetric Permutations for I-matrices to Delay and Avoid Small Pivots During Factorization

In this article, we present several new permutations for I-matrices making these more suitable for incomplete LU-factorization preconditioners used in solving linear systems by iterative methods. A general matrix can be transformed by row permutation as ...
MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least-Squares Problems

This paper describes a multilevel incomplete QR factorization for solving large sparse least-squares problems. The algorithm builds the factorization by exploiting structural orthogonality in general sparse matrices. At any given step, the algorithm ...
Low-rank updates of balanced incomplete factorization preconditioners

Let Ax = b be a large and sparse system of linear equations where A is a nonsingular matrix. An approximate solution is frequently obtained by applying preconditioned iterations. Consider the matrix B = A + PQT where P,Qźźn k$P, Q \in \mathbb {R}^{n \...

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 40, Issue 4

June 2014

154 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2639949

Editor:
Michael A. Heroux
Sandia National Laboratories

Issue’s Table of Contents

Copyright © 2014 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 the author(s) 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: 08 July 2014

Accepted: 01 October 2013

Revised: 01 October 2013

Received: 01 April 2013

Published in TOMS Volume 40, Issue 4

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
Grant Agency of the Czech Republic Project No. 13-06684S
Akademie ved Ceské Republiky

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
302
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Scott JTůma M(2024)Avoiding Breakdown in Incomplete Factorizations in Low Precision ArithmeticACM Transactions on Mathematical Software10.1145/365115550:2(1-25)Online publication date: 12-Mar-2024
https://dl.acm.org/doi/10.1145/3651155
Aricò CHelmig RPuleo DSchneider M(2024)A new numerical mesoscopic scale one-domain approach solver for free fluid/porous medium interactionComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2023.116655419(116655)Online publication date: Feb-2024
https://doi.org/10.1016/j.cma.2023.116655
Fabian MShpiro BBaer R(2022)Linear Weak Scalability of Density Functional Theory Calculations without Imposing Electron LocalizationJournal of Chemical Theory and Computation10.1021/acs.jctc.1c0082918:4(2162-2170)Online publication date: 26-Mar-2022
https://doi.org/10.1021/acs.jctc.1c00829
Chen JSchäfer FHuang JDesbrun M(2021)Multiscale Cholesky preconditioning for ill-conditioned problemsACM Transactions on Graphics10.1145/3450626.345985140:4(1-13)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459851
Daas HRees TScott J(2021)Two-Level Nyström--Schur Preconditioner for Sparse Symmetric Positive Definite MatricesSIAM Journal on Scientific Computing10.1137/21M139548X43:6(A3837-A3861)Online publication date: 11-Nov-2021
https://doi.org/10.1137/21M139548X
Chen CLiang TBiros G(2021)RCHOL: Randomized Cholesky Factorization for Solving SDD Linear SystemsSIAM Journal on Scientific Computing10.1137/20M138062443:6(C411-C438)Online publication date: 21-Dec-2021
https://doi.org/10.1137/20M1380624
Scott JTůma M(2020)Strengths and Limitations of Stretching for Least-squares Problems with Some Dense RowsACM Transactions on Mathematical Software10.1145/341255947:1(1-25)Online publication date: 8-Dec-2020
https://dl.acm.org/doi/10.1145/3412559
Pearson JPestana J(2020)Preconditioners for Krylov subspace methods: An overviewGAMM-Mitteilungen10.1002/gamm.20200001543:4Online publication date: 21-Oct-2020
https://doi.org/10.1002/gamm.202000015
Scott JTůma M(2019)Sparse Stretching for Solving Sparse-Dense Linear Least-Squares ProblemsSIAM Journal on Scientific Computing10.1137/18M118135341:3(A1604-A1625)Online publication date: 16-May-2019
https://doi.org/10.1137/18M1181353
Huang CFu M(2018)A composite collocation method with low-period elongation for structural dynamics problemsComputers and Structures10.5555/3162418.3162519195:C(74-84)Online publication date: 15-Jan-2018
https://dl.acm.org/doi/10.5555/3162418.3162519
Show More Cited By

View Options

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