1. Abstract. This article presents a fast dense solver for hierarchically off-diagonal low-rank (HODLR) matrices. This solver uses algebraic techniques such as the adaptive cross approximation (ACA) algorithm to construct the low-rank approximation of the off-diagonal matrix blocks. This allows us to apply the solver to any dense matrix that has an off-diagonal low-rank structure without any prior knowledge of the problem. Using this solver, we propose an algorithm to lower the computational cost of the multifrontal sparse solve process for finite-element matrices arising out of 2D elliptic PDEs. This algorithm relies on the fact that dense "frontal" matrices that arise from the sparse elimination process can be efficiently represented as a hierarchically off-diagonal low-rank (HODLR) matrix. We also present an extended review of the literature on fast direct solvers for dense and sparse matrices. 2. Introduction. In many engineering applications, solving large finite element systems is of great significance. Consider the system (2.1) arising from the finite element discretization of an elliptic PDE, where A ∈ R (N ×N ) is a sparse symmetric positive definite matrix. Our goal is to accelerate the direct solve process of such matrices using fast structured dense solvers. The major advantages of direct solvers are that they require no pre-conditioners and are robust in handling ill-conditioned matrices. Further, the accuracy of direct solvers is less sensitive to the eigenvalue distribution in the complex plane. Finally, direct methods preserve any structure present in the problem and can exploit that structure [26] . To be consistent with our previous work, we adopt the notations used in [1] . We should also mention that we use 'n' to refers to the size of dense matrices and 'N ' to refer to the size of sparse matrices (e.g., number of degrees of freedom in a finite-element mesh). In the next section, we review the previous literature on both sparse multifrontal solvers and dense structured solvers. We then introduce our black box HODLR solver in section 4. Section 5 discusses the application of the dense HODLR solver to the sparse multifrontal solve process and demonstrates the fast direct solver for a turbine blade geometry. We also show an application in combination with the FETI-DP method [6] . The FETI method is a family of domain decomposition algorithms to accelerate finite-element analysis on parallel computers. We present the results and numerical benchmarks in section 6. 3. Previous Work. 3.1. Dense Matrices. We review previously developed structured dense solvers and discuss them in relation to our solver. Quite a few fast direct solvers have been developed for different dense matrix structures, which have the off-diagonal low-rank property. The HODLR matrix structure is the most general off-diagonal low-rank structure for which fast direct solvers have been developed. Solvers for this matrix class have a computational cost of O(n log 2 n). In an HODLR matrix, the off-diagonal low-rank bases do not have a nested structure across different levels. The p-HSS matrix class has a partially nested off-diagonal low-rank structure [1] . Solvers for p-HSS matrices have a computational cost of O(n log n) [1]. Finally, solvers for the HSS matrix, which has a full nested off-diagonal low-rank structure, have O(n) complexity [27, 3] .
For example, Hierarchically Off-Diagonal Low-Rank (HODLR) REF which approximates all off-diagonal blocks in low-rank is considered as a specific subclass of H-matrices.
A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
ArXiv
ArXiv
Mathematics Computer Science