A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite-element matrices

In this article, we introduce a fast, memory efficient and robust sparse preconditioner that is based on a direct factorization scheme for sparse matrices arising from the finite-element discretization of elliptic partial differential equations. We use a fast (but approximate) multifrontal approach as a preconditioner and use an iterative scheme to achieve a desired accuracy. This approach combines the advantages of direct and iterative schemes to arrive at a fast, robust, and accurate preconditioner. We will show that this approach is faster (similar to 2x) and more memory efficient (similar to 2-3x) than a conventional direct multifrontal approach. Furthermore, we will demonstrate that this preconditioner is both faster and more effective than other preconditioners such as the incomplete LU preconditioner. Specific speedups depend on the matrix size and improve as the size of the matrix increases. The preconditioner can be applied to both structured and unstructured meshes in a similar manner. We build on our previous work and utilize the fact that dense frontal and update matrices, in the multifrontal algorithm, can be represented as hierarchically off-diagonal low-rank matrices. Using this idea, we replace all large dense matrix operations in the multifrontal elimination process with O(N) hierarchically off-diagonal low-rank operations to arrive at a faster and more memory efficient factorization scheme. We then use this direct factorization method at low accuracies as a preconditioner and apply it to various real-life engineering test cases. Copyright (C) 2016 John Wiley & Sons, Ltd.