Symmetric Pivoting in ScaLAPACK

ABSTRACT: Recently codes have been developed for computing the Cholesky factorization with complete pivoting of a symmetric positive semidefinite matrix for the serial LAPACK library. In the parallel ScaLA-PACK library there are only routines for the unpivoted factorization in the positive definite case and no algorithms use complete pivoting. We aim to assess the feasibility of complete pivoting in ScaLAPACK by implementing a parallel pivoted Cholesky routine. We discuss the steps needed to parallelize the existing serial code, and discuss the specific constraints of the data distribution and communication for ScaLAPACK. We present some experiments, comparing our code and the existing ScaLAPACK code, conducted on both a Cray XD1 and a Cray XT3. We show that on fewer processors our new code scales well and the pivoting overhead is small. However, the pivoting overhead increases with the number of processors, but decreases with problem size