Design and Implementation of a Parallel Markowitz Threshold Algorithm
Timothy A. Davis, Iain Duff, Stojce Nakov · SIAM Journal on Matrix Analysis and Applications · 2020
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.