Fast direct algorithms for elliptic equations via hierarchical matrix compression

We present a fast direct algorithm for the solution of linear systems arising from elliptic equations. We extend the work of Xia et al. (2009) on combining the multifrontal method with hierarchical matrices. We offer a more geometric interpretation of that approach, extend it in two dimensions to the unstructured mesh case, and detail an adaptive decomposition procedure for selectively refined meshes. Linear time complexity is shown for a quasi-uniform grid and demonstrated via numerical results for the adaptive algorithm. We also provide an extension to three dimensions with proven linear complexity but a more practical variant with slightly worse scaling is also described.