Compressed threshold pivoting for sparse symmetric indefinite systems
From MaRDI portal
Abstract: A key technique for controlling numerical stability in sparse direct solvers is threshold partial pivoting. When selecting a pivot, the entire candidate pivot column below the diagonal must be up-to-date and must be scanned. If the factorization is parallelized across a large number of cores, communication latencies can be the dominant computational cost. In this paper, we propose two alternative pivoting strategies for sparse symmetric indefinite matrices that significantly reduce communication by compressing the necessary data into a small matrix that can be used to select pivots. Once pivots have been chosen, they can be applied in a communication-efficient fashion. For an n x p submatrix on P processors, we show our methods perform a factorization using O(log P) messages instead of the O(p log P) for threshold partial pivoting. The additional costs in terms of operations and communication bandwidth are relatively small. A stability proof is given and numerical results using a range of symmetric indefinite matrices arising from practical problems are used to demonstrate the practical robustness. Timing results on large random examples illustrate the potential speedup on current multicore machines.
Recommendations
- A new sparse LDL^T solver using a posteriori threshold pivoting
- Towards Stable Mixed Pivoting Strategies for the Sequential and Parallel Solution of Sparse Symmetric Indefinite Systems
- On threshold pivoting in the multifrontal method for sparse indefinite systems
- A partial pivoting strategy for sparse symmetric matrix decomposition
- On fast factorization pivoting methods for sparse symmetric indefinite systems
Cited in
(10)- New parallel sparse direct solvers for multicore architectures
- Scaling and pivoting in an out-of-core sparse direct solver
- Partial factorization of a dense symmetric indefinite matrix
- Pivoting strategies for tough sparse indefinite systems
- Towards Stable Mixed Pivoting Strategies for the Sequential and Parallel Solution of Sparse Symmetric Indefinite Systems
- Issues in the design of scalable out-of-core dense symmetric indefinite factorization algorithms
- A partial pivoting strategy for sparse symmetric matrix decomposition
- Randomized complete pivoting for solving symmetric indefinite linear systems
- A new sparse LDL^T solver using a posteriori threshold pivoting
- Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods
This page was built for publication: Compressed threshold pivoting for sparse symmetric indefinite systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2923371)
