IMF: An Incomplete Multifrontal $LU$-Factorization for Element-Structured Sparse Linear Systems

We propose an incomplete multifrontal $LU$-factorization (IMF) preconditioner that extends supernodal multifrontal methods to incomplete factorizations. It can be used as a preconditioner in a Krylov-subspace method to solve large-scale sparse linear systems with an element structure, e.g., those arising from a finite element discretization of a partial differential equation. The fact that the element matrices are dense is exploited to increase the computational performance and the robustness of the factorization through efficient partial pivoting. IMF is compared with the multilevel ARMS2, the level of fill-in ILU, and the threshold-based ILUTP preconditioners. Our experiments indicate that IMF is competitive with ARMS2 on saddle-point problems arising in the solution of the steady-state Navier--Stokes equation. Experiments with element-structured matrices arising from structural engineering applications, found in the University of Florida Sparse Matrix Collection, illustrate the robustness of IMF. Final...