Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations

作者：Ho Kenneth L^*; Ying Lexing

来源：Communications on Pure and Applied Mathematics, 2016, 69(8): 1415-1451.

DOI：10.1002/cpa.21582

This paper introduces the hierarchical interpolative factorization for elliptic partial differential equations (HIF-DE) in two (2D) and three dimensions (3D). This factorization takes the form of an approximate generalized LU/LDL decomposition that facilitates the efficient inversion of the discretized operator. HIF-DE is based on the nested dissection multifrontal method but uses skeletonization on the separator fronts to sparsify the dense frontal matrices and thus reduce the cost. We conjecture that this strategy yields linear complexity in 2D and quasi-linear complexity in 3D. Estimated linear complexity in 3D can be achieved by skeletonizing the compressed fronts themselves, which amounts geometrically to a recursive dimensional reduction scheme. Numerical experiments support our claims and further demonstrate the performance of our algorithm as a fast direct solver and preconditioner. MATLAB (R) codes are freely available.

• 出版日期2016-8