We present an effective preconditioner for linear systems that arise from PDE discretizations. The preconditioner is constructed from an incomplete factorization, based on a multifrontal version of classical Gaussian elimination. The fill-in introduced during the factorization is compressed or approximated by rank-structured matrices. Rank-structured matrices are matrices which have sub-blocks that are of low rank. We consider Hierarchically Semi-Separable (HSS) matrices, a specific type of rank-structured or hierarchical matrices. The compression of matrix sub-blocks into a low-rank product representation in the HSS format is performed with a novel randomized sampling techniques.
We apply the incomplete factorization as a preconditioner for GMRES or BiCGStab and compare with a number of other common preconditioners such as ILU and AMG. We look at linear and nonlinear elasticity problems, Maxwell's equation and a number of large-scale applications which are of key importance to the DOE.
Code for this preconditioner is developed as the package STRUMPACK and is released online with a BSD license. The code exploits hybrid parallelism through OpenMP and MPI. We present results obtained on large distributed memory parallel machines from the National Energy Research Scientific Computing Center (NERSC).