The Factorization of Sparse Symmetric Indefinite Matrices
The Harwell multifrontal code MA27 is designed to solve symmetric indefinite systems of linear equations such as those that arise from least-squares and constrained optimization algorithms. The method employed in the subroutine involves a preliminary analysis phase to chose a tentative pivot sequence from the sparsity pattern alone. The strategy assumes that the matrix is definite so that all the diagonal entries are nonzero and suitable as \(1\times 1\) pivots. For the indefinite case, this tentative pivot sequence is modified in the factorization phase to maintain stability by delaying the use of a pivot if it is too small or by replacing two pivots by a \(2\times 2\) block pivot. The penalty paid for reanalysis during factorization can be quite large, amounting to a factor of three or more in actual floating arithmetic over the predicted floating arithmetic in examples presented in this paper. Furthermore, the penalty for this strategy over one more suitale for indefinite matrices is more than a factor of a hundred in some examples in the paper. The authors present several pivoting strategies based on \(1\times 1\) pivots and two special types of \(2\times 2\) pivots: \textit{oxo} pivots and \textit{tile} pivots. \textit{Tile} pivot blocks are of the form \[ \left[{h\atop a}{a\atop 0}\right] \] and \textit{oxo} pivot blocks are of the form \[ \left[{0\atop a}{a\atop 0}\right]. \] The strategies are compared among themselves and with the original method for a selection of matrices. The best of the new strategies show dramatic improvements over the original method.
- Partial factorization of a dense symmetric indefinite matrix
- scientific article; zbMATH DE number 1924346
- scientific article; zbMATH DE number 1343494
- A sparsity for decomposing a symmetric matrix
- Incomplete factorization methods for systems with sparse matrices
- On fast factorization pivoting methods for sparse symmetric indefinite systems
- An alternative full-pivoting algorithm for the factorization of indefinite symmetric matrices
- Factorizations of a matrix into symmetric matrices with prescribed nullities
- Improved Symbolic and Numerical Factorization Algorithms for Unsymmetric Sparse Matrices
- scientific article; zbMATH DE number 1786068
- The design and use of a sparse direct solver for skew symmetric matrices
- A novel primal-mixed finite element approach for heat transfer in solids
- The spectral properties of the Hermitian and skew-Hermitian splitting preconditioner for generalized saddle point problems
- The role of the augmented system in interior point methods
- Solving symmetric indefinite systems in an interior-point method for linear programming
- Experimental study of ILU preconditioners for indefinite matrices
- Componentwise analysis of direct factorization of real symmetric and Hermitian matrices
- Sparse algorithms for indefinite system of linear equations
- New parallel sparse direct solvers for multicore architectures
- Inertia-controlling factorizations for optimization algorithms
- Using the KKT matrix in an augmented Lagrangian SQP method for sparse constrained optimization
- On PSS-based constraint preconditioners for singular nonsymmetric saddle point problems
- On generalized parameterized inexact Uzawa method for a block two-by-two linear system
- A sparsity for decomposing a symmetric matrix
- Symmetric elimination without pivoting
- Detecting ``dense columns in interior point methods for linear programs
- Splitting-based block preconditioning methods for block two-by-two matrices of real square blocks
- A sparse symmetric indefinite direct solver for GPU architectures
- Partial factorization of a dense symmetric indefinite matrix
- scientific article; zbMATH DE number 4217769 (Why is no real title available?)
- Structured preconditioners for nonsingular matrices of block two-by-two structures
- Towards Stable Mixed Pivoting Strategies for the Sequential and Parallel Solution of Sparse Symmetric Indefinite Systems
- A partial pivoting strategy for sparse symmetric matrix decomposition
- On threshold pivoting in the multifrontal method for sparse indefinite systems
- scientific article; zbMATH DE number 1786068 (Why is no real title available?)
- New pivot selection for sparse symmetric indefinite factorization
- Perturbation analysis of saddle-point problems
- Bunch–Kaufman Factorization for Real Symmetric Indefinite Banded Matrices
- On Using Cholesky-Based Factorizations and Regularization for Solving Rank-Deficient Sparse Linear Least-Squares Problems
- On HSS-based constraint preconditioners for generalized saddle-point problems
- MA57---a code for the solution of sparse symmetric definite and indefinite systems
- A survey of direct methods for sparse linear systems
- Sparse direct factorizations through unassembled hyper-matrices
- Sparse linear least-squares problems
- \(K\)-theory and pseudospectra for topological insulators
- Computing projections for the Karmarkar algorithm
- Variable parameter Uzawa method for solving a class of block three-by-three saddle point problems
- Fast corrected Uzawa methods for solving symmetric saddle point problems
- On fast factorization pivoting methods for sparse symmetric indefinite systems
This page was built for publication: The Factorization of Sparse Symmetric Indefinite Matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4713428)
