AmirHossein Aminfar

AmirHossein Aminfar, Eric Darve

In this article, we introduce a fast and memory efficient solver for sparse matrices arising from the finite element discretization of elliptic partial differential equations (PDEs). We use a fast direct (but approximate) multifrontal solver as a preconditioner, and use an iterative solver to achieve a desired accuracy. This approach combines the advantages of direct and iterative schemes to arrive at a fast, robust and accurate solver. We will show that this solver is faster ($\sim$ 2x) and more memory efficient ($\sim$ 2--3x) than a conventional direct multifrontal solver. Furthermore, we will demonstrate that the solver is both a faster and more effective preconditioner than other preconditioners such as the incomplete LU preconditioner. Specific speed-ups depend on the matrix size and improve as the size of the matrix increases. The solver 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 (HODLR) matrices. Using this idea, we replace all large dense matrix operations in the multifrontal elimination process with $O(N)$ HODLR operations to arrive at a faster and more memory efficient solver.

Amirhossein Aminfar, Sivaram Ambikasaran, Eric Darve

This article presents a fast solver for the dense "frontal" matrices that arise from the multifrontal sparse elimination process of 3D elliptic PDEs. The solver relies on the fact that these matrices can be efficiently represented as a hierarchically off-diagonal low-rank (HODLR) matrix. To construct the low-rank approximation of the off-diagonal blocks, we propose a new pseudo-skeleton scheme, the boundary distance low-rank approximation, that picks rows and columns based on the location of their corresponding vertices in the sparse matrix graph. We compare this new low-rank approximation method to the adaptive cross approximation (ACA) algorithm and show that it achieves betters speedup specially for unstructured meshes. Using the HODLR direct solver as a preconditioner (with a low tolerance) to the GMRES iterative scheme, we can reach machine accuracy much faster than a conventional LU solver. Numerical benchmarks are provided for frontal matrices arising from 3D finite element problems corresponding to a wide range of applications.