SYM-ILDL: Incomplete LDL^ T factorization of symmetric indefinite and skew-symmetric matrices

DOI10.1145/3054948zbMATH Open1380.65061arXiv1505.07589OpenAlexW2964248269WikidataQ113310135 ScholiaQ113310135MaRDI QIDQ3133592FDOQ3133592

Authors:

Publication date: 5 February 2018

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Abstract: SYM-ILDL is a numerical software package that computes incomplete $LD{L}^T$ (or `ILDL') factorizations of symmetric indefinite and real skew-symmetric matrices. The core of the algorithm is a Crout variant of incomplete LU (ILU), originally introduced and implemented for symmetric matrices by [Li and Saad, Crout versions of ILU factorization with pivoting for sparse symmetric matrices, Transactions on Numerical Analysis 20, pp. 75--85, 2005]. Our code is economical in terms of storage and it deals with real skew-symmetric matrices as well, in addition to symmetric ones. The package is written in C++ and it is templated, open source, and includes a MATLAB interface. The code includes built-in RCM and AMD reordering, two equilibration strategies, threshold Bunch-Kaufman pivoting and rook pivoting, as well as a wrapper to MC64, a popular matching based equilibration and reordering algorithm. We also include two built-in iterative solvers: SQMR preconditioned with ILDL, or MINRES preconditioned with a symmetric positive definite preconditioner based on the ILDL factorization.

Full work available at URL: https://arxiv.org/abs/1505.07589

Recommendations

• Algorithm 849
• The design and use of a sparse direct solver for skew symmetric matrices
• Low-density incomplete \(LDL^T\) factorizations
• An algorithm for symmetric indefinite linear systems
• scientific article

zbMATH Keywords

skew-symmetric matricessymmetric indefinite

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Factorization of matrices (15A23)

Cited In (9)

• On Using Cholesky-Based Factorizations and Regularization for Solving Rank-Deficient Sparse Linear Least-Squares Problems
• A Robust Iterative Scheme for Symmetric Indefinite Systems
• TRPL+K: Thick-Restart Preconditioned Lanczos+K Method for Large Symmetric Eigenvalue Problems
• A two-level iterative scheme for general sparse linear systems based on approximate skew-symmetrizers
• The design and use of a sparse direct solver for skew symmetric matrices
• Limited-memory LDL\(^{\top}\) factorization of symmetric quasi-definite matrices with application to constrained optimization
• Preconditioners for Krylov subspace methods: An overview
• SYM-ILDL
• Linear systems arising in interior methods for convex optimization: a symmetric formulation with bounded condition number

Uses Software

• Matlab
• SparseMatrix

This page was built for publication: SYM-ILDL: Incomplete LDL\(^{\mathrm T}\) factorization of symmetric indefinite and skew-symmetric matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133592)