Randomized complete pivoting for solving symmetric indefinite linear systems
From MaRDI portal
Abstract: The Bunch-Kaufman algorithm and Aasen's algorithm are two of the most widely used methods for solving symmetric indefinite linear systems, yet they both are known to suffer from occasional numerical instability due to potentially exponential element growth or unbounded entries in the matrix factorization. In this work, we develop a randomized complete pivoting (RCP) algorithm for solving symmetric indefinite linear systems. RCP is comparable to the Bunch-Kaufman algorithm and Aasen's algorithm in computational efficiency, yet enjoys theoretical element growth and bounded entries in the factorization comparable to that of complete-pivoting, up to a theoretical failure probability that exponentially decays with an oversampling parameter. Our finite precision analysis shows that RCP is as numerically stable as Gaussian elimination with complete pivoting, and RCP has been observed to be numerically stable in our extensive numerical experiments.
Recommendations
- An algorithm for symmetric indefinite linear systems
- Accurate Symmetric Indefinite Linear Equation Solvers
- Compressed threshold pivoting for sparse symmetric indefinite systems
- An algorithm for solving the symmetric indefinite linear system Ax=b
- Towards Stable Mixed Pivoting Strategies for the Sequential and Parallel Solution of Sparse Symmetric Indefinite Systems
Cites work
- scientific article; zbMATH DE number 2109363 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- A Partial Condition Number for Linear Least Squares Problems
- A fast randomized algorithm for the approximation of matrices
- A partial pivoting strategy for sparse symmetric matrix decomposition
- A randomized algorithm for the decomposition of matrices
- Accelerating Linear System Solutions Using Randomization Techniques
- Accuracy and Stability of Numerical Algorithms
- Accurate Symmetric Indefinite Linear Equation Solvers
- Acoustic and electromagnetic equations. Integral representations for harmonic problems
- An algorithmic theory of learning: Robust concepts and random projection
- Analysis of the Diagonal Pivoting Method
- Compressed threshold pivoting for sparse symmetric indefinite systems
- Direct Methods for Solving Symmetric Indefinite Systems of Linear Equations
- Error Analysis of Direct Methods of Matrix Inversion
- Extensions of Lipschitz mappings into a Hilbert space
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- Householder QR factorization with randomization for column pivoting (HQRRP)
- LAPACK Users' Guide
- Monte Carlo Methods for Applied Scientists
- Numerical Optimization
- Numerical methods for solving linear least squares problems
- Numerical solution of saddle point problems
- On the reduction of a symmetric matrix to tridiagonal form
- Randomized Algorithms for Matrices and Data
- Randomized QR with column pivoting
- Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems
- Stability of the Diagonal Pivoting Method with Partial Pivoting
- Statistical Condition Estimation for Linear Least Squares
- Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems
- Subspace Iteration Randomization and Singular Value Problems
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- The University of Florida sparse matrix collection
- The growth-factor bound for the Bunch-Kaufman factorization is tight
Cited in
(3)
This page was built for publication: Randomized complete pivoting for solving symmetric indefinite linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4556022)
