1. DESIGN AND IMPLEMENTATION OF A PARALLEL MARKOWITZ THRESHOLD ALGORITHM.
- Author
-
DAVIS, TIMOTHY A., DUFF, IAIN S., and NAKOV, STOJCE
- Subjects
- *
SPARSE matrices , *ALGORITHMS , *PARALLEL algorithms , *FACTORIZATION , *INDEPENDENT sets - Abstract
We develop a novel algorithm for the parallel factorization of an unsymmetric sparse matrix using a Markowitz threshold algorithm. Our algorithm uses a significant extension of a maximum independent set algorithm of Luby to select a block of independent pivots in parallel. We then use this block to update the matrix again in parallel. This algorithm does not require any symmetry in the matrix and is particularly efficacious when the matrix is structurally very unsymmetric using metrics defined in the paper. We implement this algorithm using OpenMP and show its performance against other state-of-the-art codes on a standard set of sparse matrix test problems. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF